Procedural terrain generation
Using procedural algorithms to generate terrain maps.
There was a time (before No Man's Sky came out) when I thought that procedurally generated worlds would be the future of video games. How cool would it be to walk through a forest, or fly over the mountains of a world that was generated specially for you? After bouncing around the web I've found that I'm not the only one. http://pcg.wikidot.com/category-pcg-algorithms and https://www.reddit.com/r/proceduralgeneration/ are filled with amateurs and professionals alike, using a wide variety of algorithms to create virtual worlds, maps, and games. But over the past few months I've shifted from thinking that it would be fun to play in a procedurally generated world, to knowing it's way more fun to figure out how to generate the world in the first place.
I started working on these algorithms with a focus on terrain generation. I've also focused on making these examples extensible, and configurable, so that they could potentially be used in a game. For example, if you're going to be traveling over a small part of a large world, then it's not really feasible to generate the entire world right off the bat. The algorithms and code need to be able to generate a local patch of terrain, with only limited knowledge of the terrain of the rest of the world.
Here are some technical constraints that I applied so that the simulations can run in the browser.
- Maps are 256x256 points.
- I used the HTML5 canvas and javascript to generate the maps, but I used
<img>tags to add them to the document. This allows me to make the maps responsive and easier to place. It also allows me to more easily save the images. - Each map or set of maps is generated using Web Workers, so that this page doesn't lock up.
- Some algorithms are more expensive than others, and can take up to 60 seconds to run on a high-end MacBook. Keep that in mind while rendering maps.
- Maps are showing elevation relative to maximum and minimum elevations, where white is the highest value and black is the lowest value.
The code for this post is available at https://github.com/vogtb/terrain-map.
Standard Diamond-Square Algorithm
I looked around at a couple of different procedural generation algorithms, and found that the gold standard of terrain generation is actually made of diamond! The Diamond-Square algorithm involves taking four points in a square configuration, pseudo-randomly setting their elevation, and then taking the points in-between those, and adjusting them to be the average of their neighbors, plus or minus a random amount, and repeating. I'd recommend taking a quick look at the wikipedia article for more details. In addition to being really easy to implement, the Diamond-Square algorithm (hereafter referred to as DS) allows you to generate terrain at a high-level, and increase the resolution of the terrain simply by adding more points in your grid, and continuing the algorithm.
Below are several examples of the DS algorithm applied with varying amounts of deviation.
As you can see, you get some interesting, and slightly realistic looking topographies. But if you study them for awhile, you can definitely see the pattern. For example, mountain chains are more likely to run parallel to other mountain chains. But if we use this as a starting point, we can apply some algorithms to make the elevation look a little less predictable and jagged.
Smoothing Pass
The simplest way to smooth out the DS map is to iterate through the grid, averaging each point with the neighbors that are in a certain radius. Below are several examples of smoothing, with 0, 10, and 20 as the radii.
This looks better, but the highs and lows are muted. There are a lot of rolling hills instead of mountains. It's the equivalent to having mountains suddenly rise, and then having non-stop rain for millions of years. All the mountains would show roughly the same weathering. To get a more dynamic elevation map, we need something a little more complex.
Multiple Maps
So far, we've generated a unaltered DS map, and a smoothed DS map. But if we view each map not as a map, but as a layer of data, we can start to combine them in different ways. Then we can have algorithms that accept maps as input, and output more maps, which can be input into other algorithms. For example, we can use a DS map, and a smoothed DS map, and combine them with a third DS map to create a final resulting map that is smooth in some parts, and rugged in other parts. Below is an example of this:
Above we've combined a DS, DS smoothed (10), and DS smoothed (20) maps. This is done by generating "standard", then "standard-two", a completely different map. Then using each of these to generate a smoothed version of themselves, standard-10 and standard-two-20. Then we can combine standard with standard-10, using standard-two-20 as the map controlling which parts of the previous two maps are used for the result. For example the higher the value of a given point on standard-two-20, the stronger the value taken from standard and assigned to the resulting map. The lower the value of a given point on standard-two-20, the stronger the value taken from standard-10 and assigned to the resulting map.
Simple Erosion
Smoothing the DS map is a crude approximation of erosion. A small step towards simulating more realistic erosion involves using what I call the Greedy Raindrop Algorithm. This is a crude variation on the Raindrop Algorithm. In my version, each point on the map steals a small amount of the height of its tallest neighboring point.
You can see that we end up with blotchy, plateau-like formations, rather than simple smoothed hills, like with the smoothing algorithm. We're closer to having realistic looking terrain, but not all the way there.
Simple Hydraulic Erosion Algorithm
To actually create geographic terrain that looks like it's been eroded, we need to model erosion in a more sophisticated and real way. In real erosion, a raindrop lands, erodes that point, and carries sediment, depositing it at lower points. This simple hydraulic erosion algorithm randomly picks a point for a water droplet to land. The algorithm then steals some elevation from that point, moves the droplet to lowest neighbor, and deposits elevation, or sediment, if you will, if our water droplet's carrying-capacity is reached. The algorithm repeats this process with thousands of water droplets. The carrying capacity can vary depending on how extreme we want our erosion to be.
So now we have more clearly defined plateaus and cliffs. We even start to see something approximating canyons!
Complex Hydraulic Erosion
We're getting closer to creating real erosion, but we're not all the way there. During real erosion droplets don't just choose the path of least resistance (i.e. the lowest neighbor.) They have momentum, and they go where other droplets have boldly gone before. So in this version of the algorithm, we're going to approximate momentum when choosing the next point. If a droplet has been traveling in one of the cardinal directions, we increase the probability of it continuing in that direction on the next iteration. For this we use velocity, and the slope between points, with a minimum and maximum slope enforced.
Now we have streams, river valleys, and gullies! We're getting close to having an elevation map that varies!
Combining Multiple Maps
Now that we can apply erosion algorithms in a more realistic manner, we need to consider that erosion isn't uniform. We need to apply it in a semi-random way. For example, areas with high rainfall smoothly transition into areas with low rainfall. For this, we can apply our earlier technique of combining multiple maps. For instance, we can create one standard DS map, one smoothed DS map, and one DS map with complex erosion, and combine them to produce a final map that has terrain that is a little more dynamic.
Below are a couple examples of combining maps in different orders. If you checkout the code on github, you can pretty easily play around with these functions to create your own maps.
Combining Smoothing, Greedy Raindrop, and Complex Erosion
Combining Smooth, and Complex Erosion Maps
Smoothing a Complex Erosion Map
Smoothing a Simple Erosion Map
Next steps
We've gone from simple erosion to more complex, realistic erosion, and combined every type in between. We've also created a sort-of algebra for maps! There are more combinations, and, to be honest, ways to optimize the existing algorithms. But you can see how the idea of using combinations of maps can be a powerful tool for terrain generation. The Diamond-Square algorithm isn't just applicable to elevation though. You can use it to approximate clouds, and weather patterns. You could use it to simulate the type of sediment, or rock that makes up an area, and take that into account when eroding the landscape. Gypsum erodes much faster than apatite, which erodes faster than quartz. You could use DS to approximate biomass, which could minimize or maximize erosion. Biomass, sediment type, weather, and climate, could all be represented as maps, waiting for you to find the algorithm that combines them in a realistic or interesting way.
If you'd like to experiment with your own combinations and algorithms, the code for this blogpost is available at https://github.com/vogtb/terrain-map.