Fault Line Algorythm

A few days ago the “More OpenGL Game Programming” book was posted through my letter box.  This book is awesome, and I have so far loved reading it.  At some point there was a description of the “Fault Line” algorithm for terrain generation, which really managed to grab my attention, as I have been particularly interested in procedural generation recently.  However, I realized that I have read about this method before on the great Hugo Elias website, as part of an article which can be found here.  At first I dismissed the algorithm when described by Hugo since he presents it in the context of spherical landscapes, and in this case the algorythm seemed computationally horrible. This book applied presented the algorithm in 2D space at which point I kicked myself for not realizing that it can also be applied in 2D space.

The fault line algorithm is generally employed in the first stages of height map construction during terrain generation.  The algorithm is extremely simple and a mode complete explanation can be found here.  The basic idea, is to generate two points that form a line that lies across the texture with a random position and orientation.  Each pixel of the texture that lies on the positive side of this line can be incremented a tiny amount.  After hundreds of iterations nice cloudy fractal noise is produces, that in theory should be free from any pattern or statistical bias.  This of course is only true if care is taken while constructing various elements of the algorithm.

Looking at the example images and source provided by the book however I realized that the terrain generation was sub optimal because statistically the fault line start and end points are biased towards the corners of the texture map.  I fixed this using a method I described in a previous post, by discarding fault lines that lie outside of a circle encompassing the texture space.  The results are pretty great actually, and what you see below is the output from four consecutive runs of my generator program.  These noisy maps will serve as a great base for farther manipulation, resulting in a terrain generator.