Flavius Alecu

I’ve been playing around a bit with random number generators and heightmaps. My goal is at some point to procedurally generate as much of a limited landscape as possible. I haven’t done much work as I’m currently setting up the renderer at the same time too. But I did make some progress with the heightmaps.

I currently have three different algorithms that generate the heightmaps, with some additions and hybrids planned for later. The fault formation algorithm is the one I’m most pleased with so far. It creates pretty varied generations that end up looking pretty good in 3D.

The algorithm for the above results is as follows:

// Allocate a buffer for the height map.
// Iterate a pre-define number of times over this array and...
//        Generate a random line (two points) in the height map.
//        Calculate the height modifier for this iteration.
//        For all the points in the height map on ONE side of the line
//                Add the modifier value to the height.
//        (optional) Filter the height map.
// (optional) Apply a final filter pass.
// Normalize height map.

I store the heightmap as an array of floats. I don’t care much about memory at the moment though so it might be worth thinking about other formats. The height modifier is changed every fault iteration as

modifier = max – ( ( iteration * ( max – min ) ) / numIterations )

in order to gradually smooth it out. This won’t be enough though, hence the filtering. For filtering I use a simple FIR filter applied to every band of the heightmap in all four directions. For the random lines I use a Mersenne Twister implementation that has a great distribution and gives some kick-ass random numbers.

The perlin results I’m not so proud over, but that’s mainly my fault. I still need to find some proper values for the seeds. The implementation is fairly naive and at core uses a simple pseudo random number generator instead of proper lookup tables. The algorithm goes as follows:

// Allocate a buffer for the height map.
// For every element of the array...
//        For every octave...
//                Modify the frequency by a pre-defined modifier.
//                For the current (floating) point and its 3 discreet neighbors in the other quadrants...
                          Sample the 8 points around the current point and average the result.
                  Use the fractions of the coordinates of the (floating) point to bilinearly interpolate the four values.
//                Amplify the result of the interpolation by the current amplitude.
//                Accumulate the result.
//                Modify the amplitude by a pre-defined value.
//        Save the final value as the height at the current element in the heightmap.
// Normalize height map.

When “sampling” the 8 points the algorithm actually generates 8 pseudo random numbers with the given coordinates. Since the coordinates are effectively the seed, the result will always be the same and we don’t need to store lookup tables. The interpolation is a bilinear cosine interpolation. I tested linear and cubic too but in the end stuck with cosine. I don’t believe I have a reason for that though.

The plasma algorithm is a vanilla midpoint displacement implementation. I’m not going to bother writing it down since I’m not doing anything special, other than applying some heavy filtering to smoothen out the results.

At the moment the results are OK but I’m not terribly impressed. The generated meshes look tame and I’d like to expand them a bit more. Perhaps blend between different heightmaps or otherwise use some sort of heuristics to mix different types. I can imagine a low octave perlin map could be used to blend between other heightmaps to create cliffs and the like. More on this later…