As I was playing around with my terrain engine, I began to notice that for ground-level explorations, a resolution of 90 meters wasn't going to cut it anymore. I needed a way to increase the resolution of these heightmaps.
At first, I simply resized a heightmap to 4801 x 4801 (4x in both directions) using bicubic interpolation and added some Perlin noise to it. It didn't look bad, but it didn't look natural either. So I looked for a way to simulate some sort of natural process to apply this detail. That's when I decided to use some sort of water erosion algorithm.
Searching the intarwebs, I found a paper called Realtime Procedural Terrain Generation (PDF warning). It contained an algorithm for hydraulic erosion. I implemented it but I found that the simulation was a little too perfect. It wore down the mountains and spewed the resulting sediment out into the valleys, choking many small lakes in the process. It was definitely cool to see, but it didn't serve my purpose. I just wanted to add some erosion-like features to the terrain.
I took some of the ideas from that paper and made an algorithm that would produce erosion-like features. When run on this heightmap:
it results in this heightmap:
The erosion algorithm in detail
Before running the erosion algorithm, the heightmap needs to be enlarged using bicubic interpolation. I also find adding a small bit of Perlin noise helps.
The erosion algorithm performs a number of iterations specified by the user. Each iteration performs the following three steps:
- Select a random point on the heightmap
- Make a river starting at that point
- Carve out the ground under the river
(The above image comes from a heightmap with 128,000 iterations applied to it.)
The descriptions of these steps uses the following 5 x 5 heightmap in their examples:
Step 1: Select a random point on the heightmap
This step is self-explanatory. It simply selects a random point on the heightmap (in yellow):
Step 2: Make a river starting at that point
This is the most time-consuming step of the algorithm. It makes the river by selecting a series of points such that each point in the series has an elevation that is lower than its previous point.
The first thing it does is retrieve all the point's neighbors (in blue):
Rivers cannot flow uphill, so the algorithm ignores the neighbors (in red) that have a higher elevation than the current point:
Of the remaining neighbors, the algorithm randomly selects one to be the next point in the river. The lower the neighbor, the more likely it will be selected as the next point.
To calculate the probability for each neighbor, the algorithm first sums together all of the elevation differences between the current point and the neighbor points. In this example, the sum of the differences is:
(15 - 14) + (15 - 14) + (15 - 12) + (15 - 10) = 10.
The probability of selecting a neighbor for the next point in the river is equal to the elevation difference between the current point and the neighbor, divided by the sum of all elevation differences. For example:
- Right neighbor: (15 - 14) / 10 = 0.1 = 10%
- Bottom-left neighbor: (15 - 14) / 10 = 0.1 = 10%
- Bottom neighbor: (15 - 12) / 10 = 0.3 = 30%
- Bottom-right neighbor: (15 - 10) / 10 = 0.5 = 50%
Once it select the neighbor, the algorithm continues step 2 until there are no more lower neighbors (the river enters a "pit") or the river leaves the edge of the heightmap.
Step 3: Carve out the ground under the river
This step subtracts a constant elevation amount from each point in the river, except the last point.
Excluding the last point is important. This last point will have a lower elevation than all its surrounding neighbors, creating a 1 x 1 "pit" at the end of the river. Successive iterations of the erosion algorithm can cause these pits to become quite deep, which generally makes the resulting heightmap look like hell.
Problems with the erosion algorithm
One thing I've noticed about this algorithm was that some rivers were carved much too deeply into the terrain. If I reduced the number of iterations or reduce the carve amount, the main rivers didn't get as deep, but I could barely see the smaller rivers.
Take a look at the following difference map, which is created by taking the difference between the original heightmap and the eroded one:
The areas in red are at least 40 meters lower than the corresponding elevations from the original heightmap, which I found was too deep for a heightmap with a resolution of 22.5 meters. Also, the river edges were too sharp, showing up as aliasing artifacts on the heightmap. If I clamp the difference values to 40 meters (this parameter is user-defined) and blur them to remove the aliasing, the difference map looks like this:
To produce the final heightmap, simply subtract this difference map from the original heightmap.
