Subscribe to The Gamer's Algorithms to Goove By        RSS Feed
-----

Terrain Erosion

Icon Leave Comment
We've come a long way in procedural terrain generation from the "Brute Force Terrain" algorithm to "Fault Line Terrain Generation". But the problem with Fault Line terrain generation is that it produces a "mountain range" of terrain that is all but completely un-usable.

Now we're going to talk about an algorithm to simulate natural terrain erosion that will smooth out this chaotic landscape into something you can actually use and allow you to have an end result anywhere between gently rolling hills to the rugged mountain range you started with.

This algorithm is known as a FIR filter. FIR stands for First Impulse Response. This may sound really technical and terrible, but it's a more straight forward and simple algorithm than Fault Line terrain generation. So if you've made it this far, the rest is pretty easy.

At a high level, what this does is take height values and kind of mathematically "smear" them in one direction. It does this "smearing" by looping through all the values in the terrain height array one at a time. You have to apply this alogrithm four times, once for each of the cardinal direction (north, south, east, and west). Basically, you "smear" the height values from west to east, then east to west, then north to south, and finally from south to north. The order that you do these four "smearing" operations is unimportant.

This makes sense if you think of this as simulating water rushing over the terrain and washing some of the terrain "down hill" as it goes. This is not a "perfect" simulation and going from east to west is not the same thing as rain eroding things from top down to the bottom. So, you only "erode" - as you're going from east to west for example - from higher to lower values and thus can't erode downward unless the lower value is to the right. If the lower value is on the left, you ignore it. But you can pick it up on a pass in the opposite direction from west to east. If you erode in all four cardinal directions, the results will be the terrain "washing" down hill in all four directions.

The actual erosion algorithm, or FIR algorithm, erodes one column or row at a time depending on whether you're going left to right, top to bottom, or in the opposite direction.

You will apply an "erosion" value between 1 and 0. But values between 0.3 to 0.6 are said to give the best results between rugged mountains and gently rolling hills.

You start by getting the altitude value in the height map array at the first position and storing it as the "Previous Value". A PreviousValue variable can keep track of the array element that was looked at last. Then you move to the next element in the row or column being processed.

Whether it is a row, or a column that you are processing in the terrain height map array, the erosion formula is the same.

ErosionValue * PreviousValue + (1 - ErosionValue) * HeightAtThisPosition

What you are doing here is basically interpolating between the height in the previous array element with the current array element. Whatever percentage the ErosionValue is, you will use that percentage of the PreviousValue and add that to the inverse percentage of the current value. So, let's say the erosion value is 0.3. That represents 30%. So the formula becomes "take 30% of the previous value and combine that with 70% of the current value". A value of 1.0 would be 100% and you would get a flat plain because it would "smear" the first value 100% into all the other values into the row or column. A value of 0.0 would be 0% and the result would be 0% of the previous value and 100% of the current value. The final result would be absolutely no change to the row or column, and ultimately no change to the shape of the terrain. So, you can hopefully see that this ErosionValue is a percentage of how flat you want the terrain to be.

Believe it or not, that's all there is to this algorithm. You simply process every row in the array from left to right using this formula, then do it again from right to left, then do it again from top to bottom using columns instead of rows, and then do it again from bottom to top using columns instead of rows. And your terrain will be "eroded" by whatever percentage you used for the ErosionValue.

This turns a mess of a terrain, such as the one generated by the Fault Line algorithm, into a terrain with "just the right amount" of roughness to the terrain and it yields a result that looks very natural.

Now if you want to take this algorithm further, you find a way to use one function or method to process a column or row regardless of whether its a column or row. So, whether you are processing from left to right or bottom to top, you call the same function or method. This takes a little more work, but can be done.

The difference is just whether you advance +1 or -1 depending on whether you are going in one direction or its opposite. And then whether you are processing a column or a row. In an x,y array where x is horizontal and y is vertical, you would process a row as x going from 0 to the width of the array by steps of +1, or process the row as x going from the width of the array to zero by steps of -1. And the columns are likewise traversed. So basically, you have to control the direction (whether horizontal or vertical) and also whether the steps move in the positive or negative direction.

Regardless, the algorithm is still the same: get the previous value and then interpolate the current value with the previous value based on the erosion variable. Then you process the next value in the array and the old current value becomes the previous value.

That pretty much sums up what you need to make your own procedurally generated terrains of any size. Enjoy!

0 Comments On This Entry

 

Trackbacks for this entry [ Trackback URL ]

There are no Trackbacks for this entry

August 2014

S M T W T F S
     12
3456789
10111213141516
17181920212223
242526 27 282930
31      

Tags

    Recent Entries

    Search My Blog

    0 user(s) viewing

    0 Guests
    0 member(s)
    0 anonymous member(s)