Midpoint Displacement in One Dimension

I decided to redo a demo I did back in 2008/9 on the midpoint displacement algorithm. For those of you who do not know what Midpoint Displacement is, it is the name of a fractal algorithm which generates shapes that are usually used for terrain height maps. This is a 1D implementation, the 2D one can be found here.

I ended up doing a full re-write, as I lost the previous code, using the same resource as last time. This article by Paul Martz, regarding terrain generation, is the best explanation I have found so far. His explanation is clear and he makes use of psuedo code to explain the algorithm. He also starts off in the 1st dimension, to keep things simple, and then scales up to the 2nd dimension. Here is a quick demo of the algorithm I put together.

The frame-rate is intentionally set to 1, to allow for the animation to make sense. Otherwise it is far too fast to see what is going on.

Here is the psuedo code by Paul Martz:

Start with a single horizontal line segment.
Repeat for a sufficiently large number of times {
 Repeat over each line segment in the scene {
  Find the midpoint of the line segment.
  Displace the midpoint in Y by a random amount.
  Reduce the range for random numbers.
 }
}

The code for the generation is:

/**
 * If a width is provided that does not conform to the pattern 2n + 1,
 * then the next highest value conforming to the pattern is chosen,
 * and the result is then clipped to the desired size. 
 * 
 * @param	width 
 * @param 	smoothness
 * @param	seed
 * @return
 */
public static function generate1DHeightmap(width:int, smoothness:Number = 1, seed:Number = Number.NaN):Vector. {
	if (isNaN(seed)) {
		seed = Math.random() * 0xFFFFFF;
	}
	smoothness = Math.max(Math.min(1, smoothness), 0);

	var i:int;
	var heightmap:Vector. = new Vector.();
	var size:int = isPowerOfTwo(width - 1) ? width : adjustUp(width);

	// init
	for (i = 0; i < size; i++) {
		heightmap.push(0);
	}

	// setup
	Rndm.seed = seed;
	heightmap[0] = Rndm.random();
	heightmap[size-1] = Rndm.random();

	var toProcess:Vector. = new Vector.();
	toProcess.push(0, size-1, smoothness);

	// process
	var min:Number = Math.min(heightmap[0], heightmap[size-1]);
	var max:Number = Math.max(heightmap[0], heightmap[size-1]);
	while (toProcess.length != 0) {
		var low:int = toProcess.shift();
		var high:int = toProcess.shift();
		var offset:Number = toProcess.shift();
		var midPoint:int = (low + high) / 2;

		heightmap[midPoint] = ((heightmap[low] + heightmap[high]) / 2) + Rndm.float( -offset, offset);
		min = Math.min(heightmap[midPoint], min);
		max = Math.max(heightmap[midPoint], max);

		// terminating condition
		if (high - midPoint != 1) {
			toProcess.push(low, midPoint, offset / Math.pow(2, smoothness));
			toProcess.push(midPoint, high, offset / Math.pow(2, smoothness));
		}
	}

	// clip length
	heightmap = heightmap.slice(0, width);

	// normalize
	var range:Number = max - min;
	for (i = 0; i < heightmap.length; i++) {
		heightmap[i] = (heightmap[i] - min) / range;
	}

	return heightmap;
}

Here are the two helper functions that were used:

/**
 * Determines if a value is a power of 2
 * 
 * @param	val
 * @return
 */
private static function isPowerOfTwo(val:uint):Boolean {
	return (val != 0) && ((val & (val - 1)) == 0);
}

/**
 * Calculates returns a number that will contain val
 * which is of the pattern 2n +1
 * 
 * @param	val
 * @return
 */
private static function adjustUp(val:int):int {
	var size:int = 2;

	while (size + 1 < val) {
		size *= 2;
	}

	return size + 1;
}