Map Generator 3.0 - Please Critique!

Wow. Look at the blueprints. It’s like it is 10th dimension and I live in 2D.

As in they are that hard to understand? :stuck_out_tongue:

I do realize that by this point, I can’t explain the systems in a deep enough manner for anyone to be able to understand and replicate these processes.

I guess most of this thread is for higher level discussion on better methods of doing things. Stuff like “You could use this or that configuration of loops to do X, Y, or Z better”. Also, hopefully the basics are shown well enough that people can get a general idea of what they might be able to do using blueprints, and maybe even a few ideas or tricks such as 2D array emulation using 1D arrays that they can use in their own projects.

That and a lot of times as I write things out I come up with new ideas and solutions as I write it out.

Some Before and After:

I chose these generations because they have the nice North/Central America analog, and I didn’t even save the boundary seed between those gens. It seems to be pretty common. :slight_smile:

The second image got kind of lucky with that amount of erosion still having 3 decent mountain passes to the west coast. Normally I would need a higher erosion level for the same effect which would lead to the range looking a little more sparse. I think I have found a good baseline(earth-like) though with a little higher erosion than the above image. I may re-evaluate it later when I am working on unit movement through and/or around mountains. Whether a “Mountain Pass” turns out to be a lane with no mountains, or a lane with fewer mountains, will determine the proper baseline erosion setting.

I think the next move is to work on a plate-varied erosion rate since a setting that works well for the Rockies isn’t necessarily the same setting that works well for the much thinner Andes. It may tie in with my improvements to the plate boundary upgrade, which I am still theorizing on.

The idea I am running through my head right now(literally came up with this as I wrote this post) is to give each plate a weighted preference for specific boundary types. So Antarctica’s plate preference would be divergent boundary, with a very high weight so that it would always have water surrounding it’s Continent. Ocean plates would be convergent, very high weight, but slightly under Antarctica plate weighting in order to form land/mountain ranges along all plate boundaries except Antarctic plates.

The tricky part would be handling North/South America, Africa, Eurasia, and Indo-Australian plates. They need to be Convergent on one side, but Divergent on another. They would all have weights lower than the ocean and Antarctic plates, yet varying in relation to each other. Each would probably have weights both for convergent and for divergent, so depending on how a neighbor plate is weighted, they could have different boundary reactions with various neighbors.

Then on top of that, I could put the convergent type directly into the plates. That way I could just call the plate a South America plate, and wherever mountain ranges formed in that plate, they would be thin and perhaps more or less resistant to erosion depending on how sharp you want the range. At that point I have control over how old each plate’s mountain ranges are just by specifying how much erosion takes place on a per plate basis.

I will see what I can work out this week. :slight_smile:

I implemented the new tectonic boundary creation system which gives me a lot more control over the interaction between plates. It is also smaller than the previous system, and generates in a cleaner fashion, so that is bonus. :slight_smile:

Each plate has a Convergent and a Divergent weighting. When setting each boundary tile, both neighbor plate’s weightings are measured, compared, and then the boundary is set based on those values. It also takes into account the losing plate’s value when setting the type of Convergent boundary which determines what type of mountain range forms on that boundary. That system is actually the most complicated portion of the new system though, and I can foresee circumstances where it would have to get even more complicated. Doing per-continent erosion isn’t really practical since you can easily get continents with more than one type of mountain range on them. So I can instead split up each Convergent type, which would represent different states of erosion per mountain range.

For now though, I will leave it as it is. I am pretty sure I can (generally) recreate the shape of Earth and it’s continents just by properly weighting the plates and precisely distributing the plate seeds, which is pretty much the level of control that I wanted. There will be lots of fine tuning and balancing to do in the future.

I also moved some things around and made it so that I can switch between overlays(tectonic, to topological, etc) while I am working in the map.

Next up I was thinking about working rivers into the erosion system(for those fertile river valleys), but first I will implement an idea I had that should help me upgrade the river system and implement river erosion at the same time. I have been wanting to get back to the rivers for some time now as there is a lot of inefficiency and lack of control in that system.

I am going to create a height map of the world and use that to flow rivers downhill towards the oceans. I kind of already have this, but it a somewhat unofficial manner. Now that I have proper mountain ranges I can slope the terrain down around these ranges. It won’t be a visual sloping, just a general mountains = tall, next to mountains = less tall, etc until you get to the ocean. So a plains next to a mountain may have a rather high elevation while still being a plains.

This will generally only matter for rivers and maybe some other behind the scenes map related systems, unless I can find a decent way to visualize it for the player. Most likely it will just be a way to smooth out the slope of the mountain ranges to get the rivers to flow in the direction I want, which the player won’t necessarily need to know about. Right now rivers are just as likely to flow into a mountain pocket if it happens to be filled with plains as they are to flow to the ocean. Basically this height map will look like my previous topographical maps but with more than 3 layers and it will be smoother in general.

So when that is done, I will see if washing out river valleys makes sense. And then I might be ready for the climate upgrade, if nothing else needs my attention. :slight_smile:

First pass at the height map. The ugly colors will probably be the first thing I work on tomorrow… :stuck_out_tongue:

So white is mountain, and it goes down hill from there. Apart from the mountains, the colors do not represent hills or anything else other than the general decline to the ocean.

I think it will work pretty well for the rivers, but there are a few problems I will have to work out. For rivers that get stuck inland, I will have to ensure my existing system of lake/swamp creation is up to the task, and also figure out a way to tunnel a river through a mountainous area similar to the Colorado River.

My idea for river tunneling is to neighbor check further and further out until an ocean tile is found, and then guide the river to that ocean and through/around whatever is in the way. My rivers already use some semi-pathfinding logic to move about, so this should be similar but over a longer distance and with an objective.

Another problem that you see in this generation is the giant semi-donut of mountains which is the main reason I need Colorado-esque rivers, but that isn’t actually an issue because this generation is running with a decently high plate collision setting. For a more Earth-like appearance, with plate collisions only happening on one side of the plate, I can reduce the setting until I get the desired quantity of collisions. I am still seeing a bit more randomness than I would like, but that will all work out with some fine tuning down the line.

Going over my river generator again, it has become clear that the newest iteration of the river generator must implement some form of proper pathfinding which will take more thought and work than I was planning at this time. The river generator currently uses what one might call pathfinding, but it is basically binary, weight driven randomness. If rivers fall into a body of water it is random chance. If a river blindly flows itself into a corner or loops itself, then that generation must be discarded. Eventually, the rivers flow where and how they are supposed to and those are kept. As you can imagine this is pretty wasteful and lacks control.

Going forward, I will implement some form of A*(or similar) that uses the topographical map for costing, and is objective driven to the nearest, cheapest(close and downhill) river outlet(lake, ocean, another river, etc).

I had already planned to work on pathfinding as the beginning of the next leg of this project, which is to perfect an AI that can move and engage objectives on the map.

So, before I do any of that, I am going to work on the weather/climate system which should segue nicely into the river revamp. Hopefully have significant progress on that by the end of the year. :slight_smile:

This might be the coolest infographic I have ever seen:

All kinds of wind and water settings. Drag the screen around to check the world out.

Check out the wind and precipitation around the Andes mountains:

Pretty stark visualization of how the mountain ranges affect the wind and in turn affect precipitation.

Hey Zeus, your stuff is looking awesome! I wanted to respond sooner but you’ve got so much to read up on. :slight_smile: I was wondering, is your map generator meant to just generate a (great) layout and be done with it, or is it an updating world as well? I see you’re planning on having advanced weather and climate systems, is that to steer the creation of the map or to update the map after creation?

Is the map itself actually a system that game events can have influence on? Sorry if you already discussed this in your previous topics.

Thanks for the support!

Most of the generator will be used only to generate the world. Following that, there is plenty of room for localized updating of the map, but most of those updates will be handled on a case by case basis. For instance, flooding the coasts if/when the poles melt will be a process not used in the generation and will happen during gameplay by a separate function.

Climate and rivers are still an open question though. The same process used to generate weather will likely be reusable during climate change events. That is the easy part. Harder yet is potentially altering the flow of dozens of rivers as a result, especially if they are only partially changed. Would be easy to simply regenerate them all, but that wouldn’t make sense in most of the cases. Should be doable with the new river system, especially if it implements some level of pathfinding to have more control over the river routes.

Still working out the theory behind the new climate generator though. I have been melting my brain researching climate phenomenon. Hoping I can get it working before I return to work, but the kids are home too so all bets are off. :stuck_out_tongue:

Wouldn’t water always head towards the local minimum? I don’t think A* would accurately model how rivers actually work. Then you could take a second pass through to form ‘lakes’ where the land was about the same level for several contiguous hexes.

Yes rivers would allways search from the heighest point to the lowest. Either It would form a lake/inland ocean, or start pooling up untill it comes over the height of a hill/mountain and erode that away untill that is the same level/lower then the current terrain. The problem here being that elevation is per tile level, and it might very well be a lower point for the actuall riverbed then the tile average. Ofcourse a tile with a lower average height would probably be more likely to be the path the river takes. So I guess it’s less of a path finding as of a random pick prioritizing lower points in the heightmap? ^^

You have to realize that these rivers did not form just before the game starts, but millions of years prior. I have to simulate what they look like ages after they first start to trickle down those slopes, such as carving a path through mountainous terrain on their way to the ocean, which all rivers will flow into. There will be no dead end rivers. They connect to each other and to lakes, but always have an exit to sea. Also, I am generally only simulating the largest river formations, so any special cases that are only seen by smaller tributaries do not apply.

The primary driving factor for river flow is that they take the path of least resistance(down hill or erode through softer rock). That is what A* will make them do with the heightmap costs. The outliers will be those cases where a river starts in a pit and has to path its way out of there(canyon erosion). These are the cases where you will see a river tunnel through a mountain range because that is the cheapest route to the ocean. Rivers already form lakes as they make their way to the ocean, so this will still happen when appropriate, but nothing will stop the river from making it to the ocean one way or another.

The path finding portion is using A* to calculate the cost from A to B(or of many B’s, from which one will be chosen). Choosing the destination will be the most important part. Perhaps the hardest part will be ensuring rivers are not too linear in their approach to the ocean. Generally the first river will head to the ocean, and all other rivers would feed into that one(think Mississippi).

I’d think the hard part would be modifying the A* cost of traversing to the next node so that the water doesn’t end up travelling uphill or as little as possible, and so it meanders. Distance probably doesn’t matter that much.

One thing I’ve done you might consider. Randomizing the directions that A* takes, that is, instead of always going clockwise, it looks in random directions. I’ve added a random generator for a given run based on the hex x, y other factors. That is, a specific random number assigned to each hex. I then use that random number generator when shuffling the exit hexes for use by the A* algorithm. The end result (for me) was that I had repeatable results for my A* algorithm.

That goes along with ensuring the river is not a linear beeline to the ocean, and I am not sure I am going to rely solely on cost to do that. Though honestly, the first river can roughly beeline to the ocean because every other nearby river will beeline to it and it will look more or less natural(Like the Mississippi). It will also have to go up hill at some point because it will eventually need to “tunnel” through a range because of a lack of better options. Properly tuning the costs won’t be “easy”, but because it is a known quantity that makes it quite a bit simpler than creating the mechanic that finds the best Point B. That system has to give me the best Point B destination while trying to take into account a continent whose shape and composition I can’t know ahead of time, but of course even that ties back into tile costs. I will have a better idea of where I am taking that when see how the river flows with just the height map costing.

So you use the random number to generate a Random Seed which is then used to generate the random decision on the next tile? How high is this random number you store for each tile?

What kind of project are you working on by the way? I can’t remember if I have seen it or not.

Perhaps instead of trying to choose a destination for rivers, you could try a model for tile-to-tile water interactions using a stored water level, incoming rate and outgoing rate. When water flows into a tile that is a local minimum height wise, it would increase the local water level over the course of several water simulation steps until the tile’s (height + water level) exceeds a neighbor tile’s (height + water level) allowing the water to leave the tile towards the neighbor.

You would then specify an infinite water source at mountain tops and specify a sea level S so that tiles below S function as a sink. For example, for tiles with height below S, their water level only rises until S and all excess water is vaporized. Then you would simulate until an equilibrium is reached. Have you considered something like this? I’m not sure if this well actually produce good looking rivers, and the simulation step size will affect the results and convergence time.

How would you take into account all the river tiles previously generated? Where would you begin filling up a tile in the chain of rivers without knowing where you are going? The river is going to flow around the obstacle. At some point, it won’t have a way out because it will be trapped behind the mountains. Rather than filling up an area that might be the size of Siberia with water, I would rather simulate that at some point, somewhere, the river eroded/winded a channel through the range and into the ocean beyond.

There are other reasons for needing a destination.

Lets see if we can cost this out. Refer to the most recent image for reference:


We can use the Eastern continent with the enclosed plains as the test case.

For the sake of simplicity of this thought experiment I will not take into account changes between heights, or even tile type, just the heightmap costs which I just made up on the spot:

Green = 1
Yellow = 5
Orange = 10
Red = 20
White = High/Infinite

Lets say a river generates somewhere near the Southernmost green tile in that enclosed plains area. All nearby escape points for the river have been calculated(total cost divided by Manhattan distance) and it is determined that the river can not escape to the ocean without going through a mountain range. I will define “Pass” as those paths to the ocean through which there are no mountains(White) in the way. And lets just look at the 3 most obvious paths to the ocean from that southernmost area:

The cost through the Southern pass is about 185. Manhattan distance of about 11. 16.8 average cost per distance.

The cost through the Eastern pass is about 144. Manhattan distance of about 19. 7.5 average cost per distance.

The cost through the South Western pass is about 206. Manhattan distance of about 11. 18.7 average cost per distance.

So there are many ways I could use this information to guide generation. Maybe if it is the first river of a continent then I don’t mind traversing the continent to the Eastern pass(largest Manhattan distance). That might be preferred in general. Maybe for some reason I want the cheapest of the short routes which would be the Southern Pass. Maybe the other 2 more preferable destinations already have a river exiting within 5-10 tiles so I want to take the South Western pass that is less water-flow-efficient, but better for overall map balance.

If a second river generates in the north end of this continent, it immediately has an exit point found in the first river that is cheaper than any alternative. But perhaps even then I want it to find it’s own way out, based on X, Y, and Z conditions.

So lets step back a bit and apply this to the Colorado river. The river already starts inside a mountain range. It could plow through the mountains and head east to the Gulf of Mexico or the Mississippi river, but instead heads west and south through even more mountainous terrain and dumps in the Gulf of California. In our map generation scenario, maybe it does this because there were big white mountain tiles in the way, or the Gulf of Mexico already has 2 major rivers dumping into it, and the Western US could use the water anyway.


Look at how the rivers just zip right for the Mississippi across the great plains. That would be me getting all the nearest river exit points and setting the best/closest as destinations for the latest river to generate in those mountains.

Another major reason for wanting the ability to set the river destination is control otherwise not found in a randomly snaking river system. You don’t know where the river is going to end up until it gets there. I basically already have that system. It gets the job done, but isn’t really ideal.

For my own path finding, using A* was a mistake that cost me a lot of time (even though it will probably be useful for something else), and I believe it probably would be in your case as well. A* is only good in situations were you have decided the destination beforehand, which you have already mentioned might be tricky.

Instead I would recommend doing something like Dijkstra’s algorithm instead, where you search in all directions equally until you reach an ocean tile. Since you don’t need all paths to be optimal, you wouldn’t even have to re-check nodes, which would make the algorithm quite a bit faster. A* only wins out over Dijkstra for quite long paths, and considering the average length of rivers on the sorts of maps you are showing in the screenshots, I think Dijkstra is a better bet, especially considering that you need a separate mathod of deciding the end point for A*.

Tweak the tile costs for different elevations while you test it out and add a bit of randomness and I think you’re good to go. You could for example continue Dijkstra a few tiles further after finding the ocean once, and if you find any other paths you could choose randomly between these.

I think I would probably use Dijkstra’s to find the destinations for the river, and then A* to plot their course to those destinations. Maybe I throw the term A* around a little too loosely when talking about pathfinding… :stuck_out_tongue:

Yeah, I used to use the term A* too much as well (might be doing the same with Dijkstra now :stuck_out_tongue: ). First using Dijkstra and then using A* is actually unnecessary. You get everything you need just from Dijkstra. When you have “found” a destination you already have everything you need, and have plotted an optimal path to every tile within range, including tile costs. Do not bother with A* at all unless you’re calculating very long paths, and don’t even bother with Dijkstra unless you use movement costs. If you don’t you can just use a breadth first search (Dijkstra is best for your rivers, though. I have a few recommendations to make an even more efficient search when you get that far). I probably lost a month of work because I insisted on using Dijkstra, so please take my word for it so you don’t make the same mistake I did :slight_smile:

Oh yeah, I guess I wouldn’t need to run the search twice if I already have them. It is early. :stuck_out_tongue:

You mean A*?

I don’t think you lost a month, you just came to understand the systems better. Most of my time making this generator is me making things that I am later going to toss in the garbage.