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

Fault Line Terrain Generation

Icon Leave Comment
There are several ways to generate a terrain including the Diamond-Square algorithm. However, the "Fault Line" algorithm is very simple and very useful, especially when you apply a filter to simulate natural terrain corrosion to smooth out the results.

I'm going to primarily discuss this as a continuation of this series from the "Brute Force Terrain Generation" algorithm. However, you could use this algorithm for other things, including shaping the "terrain" in a MineCraft like voxel world.

In the "Brute Force Terrain Generation" alogrithm we looked at how to generate a 3D terrain and shape that terrain using a 2D array containing the heights, or altitudes, of every corner of every square, or quad, in the grid. Then in "Maps: Storing Array Data in a File" we talked about how to load data into the terrain array to shape it using a height map file. We also looked at how to save the data from the array to a height map file. What we have not covered is how to generate the data from scratch in the first place.

Granted, you can get programs like L3DT to generate a height map for you. But what if you want to make your own height map editor or incorporate height map editing into a level editor. What if you want to randomly generate the terrain every time the game is played. Then you're going to have to know how to generate your own height data and that's where this algorithm comes in.

The algorithm itself is very simple at the overview level. You have your terrain array with height values at every corner of a grid square. You could even think of that data as a blank height map image (perhaps with all of the altitude colors set to black to represent zero altitude). All you do is draw a completely random line across the terrain and raise all of the terrain by a set amount on one side of the line. If you do this once or twice, you will see exactly what you expect which is the lines criss crossing the terrain and plateaus of altitude. However, by the time you've done it about 4,000 times or so, you no longer see the lines but simply have a chaotic mountain range of height values.

Really, that's the whole algorithm. It's unbelievably simple at the high level. It's the details that will get you. First, the results are better if you raise the height on one side of the line less and less with each iteration. Second, How do you create a random "line" mathematically. Or how do you create a line across an array? And what exactly is meant by a "completely random line"? Can you just draw a line from the left side to the right or alternate between left to right and top to bottom? Third - and surprisingly this is the most difficult part, how do you raise the terrain on one side of the line? How do you know which terrain values are on one side and which are on the other? It's really the math behind this that makes the algorithm a bit complex and difficult to understand. But we'll cover these questions.

First, how do you "draw" a mathematical line across an array so that it is truely random and doesn't favor one side of the array or another? The answer is that you simply pick two completely random points in the array and draw a mathematical line between the first point (point A) and the second point (point B). You form that "line" between these two random points as a vector. A vector, of course, is an amount tied to a direction, but here we are using it as a mathematical "trick" to not only represent the line that divides the array, but also as a "trick" to determine whether a given point is on one side of the line or the other.

I should maybe mention at the outset here that the vectors in this algorithm are 2D vectors even though we are working in "3D space". Actually, we're working with the 2D height map and that's why there's no need to do this in 3D. So, all these vectors are 2D vectors, not 3D vectors.

To create the vector-line that will represent our fault line, you represent points A and B as vectors (positions stored in a vector object). When you subtract the vector of Point A from Point B, you will get a vector that represents the line as the result. When you do vector subtraction like that, you will get a vector that points from one position towards the other. In other words, the result is a vector that points the direction from one point to the other and has a length of the distance from one point to the other. Combine that vector with Point A, and it basically becomes a vector that points straight down our fault line and is positioned on top of our fault line when combined with Point A.

So, then we have a line/vector that represents the division line, or fault line, across our array. Next, we need to determine whether a given point in the array is on one side of the line/vector or the other.

You can easily produce another vector that points from Point A to the given point in the array. First, you turn the given point in the array into a vector so that you can do vector math on it. Then you do "vector subtraction" to subtract Point A from the given point in the array. The result is a vector that points in the direction from Point A to the given point.

So, now we have two vectors that both can be imagined to have their tail at Point A, one that points down the fault line, and another that points at the point in the array we are testing. So, we just need to determine the angle between the two vectors to know which side of the line the given point is on.

A good way to do this is to use the Perp-Dot Product of the two vectors. First, be very aware that this is not the cross product, or the dot product of two vectors. The Perp-Dot Product is also called the Perpendicular Dot Product. I have not taken the time to go through all the trigonometry necessary to fully understand this mathematical identity, but sometimes its best just to accept a truth. This is a known identity that has been well established as "true"; I leave it up to you whether you want to take the time to figure out why it works. You can spend the time proving it if you like, but it will still be just as true. Sometimes, when you're in a dark room it's better to flip the light switch then to spend a year studying Alternating Current and the calculus of circuit analysis. Whether you understand it or not, flipping the switch will turn the lights on.

But anyway, I believe this is actually the dot product of a vector perpendicular to a given vector and another vector. Regardless, the results will definitively show which side of the line the point is on. If the result is zero, then the point is on the line. If it is greater than zero, it is on one side of the line, and if it is less than zero, then it is on the other side of the line. For our purposes here we don't really care which side it is on as long as we always raise the terrain on one side of the line.

The formula for the Perp-Dot product is TPD.x * FLV.y - TPD.y * FLV.x and you simply raise the height of the terrain if the result is greater than zero, where TPD is the Tested Point's Direction vector and FLV is the Fault Line's Vector. The x and y are, of course, the x and y components of those vectors.

Now all you need to do is run two "for" loops to test every x and y position in the height map array and only raise the altitude for positions in the array where the Perp-Dot tests greater than zero. The result will be raising all values on one side of the line only.

If you do another "for" loop to raise the terrain on one side of the fault line enough times (4,000 is a good place to start in determining how many times is "enough"), the result will be a very rugged "mountainous" terrain.

It should also be mentioned that it is accepted that the results are best if you raise the height by a decreasing amount every time you do a fault line. So, at first the results are dramatic, but more subtle as it progresses. This is done by interpolating between two values as it goes from the first iteration to the last iteration. You may want to start with a maximum height raise per iteration of about 1.25 that progresses to a minimum height raise per iteration of about 0.25. You can experiment with these values or even let the user choose them, but that should be a good starting range.

If you take the number of the current iteration you are on and divide it by the number of iterations you will be doing in total, the result will be the percentage of the current iteration from being complete where 100% will be 1.0 and 0.5 will be 50%. You can apply this percentage (through multiplication) to the difference between the max value and the min value to interpolate between the two values and slowly go from the max change to the min change from start to finish.

It should also be pointed out that the resulting terrain may have height values way outside of the 255 values you can store in a heightmap image and you may need to "normalize" the values into a range that is "usable". Start by looping through every element in the terrain height array and recording the minimum and maximum altitude. Then loop through them again and set them to be an interpolated value between 0 and 255. This again starts with turning the current value into a percentage and multiplying that percentage by 255, to force it into a value between 0 and 255. If you take the current element's height and subtract the minimum height and divide that result by the maximum height minus the minimum height result, you will get a percentage that you can then multiply by 255 to get an interpolated value between 0 and 255.

I suggest "normalizing" the height values between 0 and 255 after you have eroded the terrain.

It may be easier to see this in code. I have this fully coded on my website at VirtuallyProgramming.com.

And that is fault line terrain generation. One of fault line terrain generation's great strengths is that it works on any rectangular terrain. A lot of terrain algorithms, such as Square-Diamond, require the terrain to be square and the sides to be a power of two plus 1 (the plus 1 part is so that it can be evenly split down the middle). Fault Line terrain generation does not have this requirement.

However, one of the "downsides" of this algorithm is the resulting terrain is so rugged and mountainous that it's all but useless. That's where our next algorithm comes in. The next algorithm we cover is for terrain erosion - to smooth out the terrain, so that you can make it anywhere from rugged mountains to gently rolling hills.

0 Comments On This Entry

 

Trackbacks for this entry [ Trackback URL ]

There are no Trackbacks for this entry

June 2019

S M T W T F S
      1
2345678
9101112131415
16 17 1819202122
23242526272829
30      

Tags

    Recent Entries

    Search My Blog

    0 user(s) viewing

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