Midpoint Displacement in Two Dimensions

Moving on from one dimensional midpoint displacement, we get the following in two dimensions. You can read up more about the algorithm on wikipedia and there is a C# implementation, at least I think it is C#. Haven’t looked at the code. You can see the well known improvement to this algorithm, called the Diamond-Square algorithm, here on my blog.

 

Code

The following code is recursive (not true recursive) and simple to understand, provided you understand the algorithm.

package avdw.generate.terrain.dimension.two {
	import flash.geom.Point;
	import com.gskinner.utils.Rndm;
	import avdw.generate.terrain.dimension.MathUtil;

	/**
	 * ...
	 * @author Andrew van der Westhuizen
	 */
	public class MidpointDisplacement {
		/**
		 *
		 * @param	size
		 * @param	smoothness
		 * @param	seed
		 * @return
		 */
		public static function generate(size:int, smoothness:Number = 1, seed:Number = Number.NaN):Vector.<Vector.<Number>> {
			if (isNaN(seed)) {
				seed = Math.random() * 0xFFFFFF;
			}
			smoothness = Math.max(Math.min(1, smoothness), 0);

			var i:int, j:int;
			var heightmap:Vector.<Vector.<Number>> = new Vector.<Vector.<Number>>();
			var length:int = MathUtil.isPowerOfTwo(size) ? size : MathUtil.adjustUp(size);

			// init
			for (i = 0; i < length; i++) {
				var rowData:Vector.<Number> = new Vector.<Number>();
				for (j = 0; j < length; j++) {
					rowData.push(0);
				}
				heightmap.push(rowData);
			}

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

			// new Point(row, col);
			var toProcess:Vector.<Object> = new Vector.<Object>();
			toProcess.push(new Point(0, 0), new Point(length - 1, length - 1), smoothness);

			// process
			var min:Number = Math.min(heightmap[0][0], heightmap[0][length - 1], heightmap[length - 1][length - 1], heightmap[length - 1][0]);
			var max:Number = Math.max(heightmap[0][0], heightmap[0][length - 1], heightmap[length - 1][length - 1], heightmap[length - 1][0]);
			while (toProcess.length != 0) {
				var topLeft:Point = toProcess.shift() as Point;
				var bottomRight:Point = toProcess.shift() as Point;
				var offset:Number = toProcess.shift() as Number;
				var midpoint:Point = new Point((topLeft.x + bottomRight.x) / 2, (topLeft.y + bottomRight.y) / 2);

				heightmap[topLeft.x][midpoint.y] = (heightmap[topLeft.x][topLeft.y] + heightmap[topLeft.x][bottomRight.y]) / 2;
				heightmap[midpoint.x][bottomRight.y] = (heightmap[topLeft.x][bottomRight.y] + heightmap[bottomRight.x][bottomRight.y]) / 2;
				heightmap[bottomRight.x][midpoint.y] = (heightmap[bottomRight.x][bottomRight.y] + heightmap[bottomRight.x][topLeft.y]) / 2;
				heightmap[midpoint.x][topLeft.y] = (heightmap[bottomRight.x][topLeft.y] + heightmap[topLeft.x][topLeft.y]) / 2;
				heightmap[midpoint.x][midpoint.y] = ((heightmap[topLeft.x][topLeft.y] + heightmap[topLeft.x][bottomRight.y] + heightmap[bottomRight.x][bottomRight.y] + heightmap[bottomRight.x][topLeft.y]) / 4) + Rndm.float(-offset, offset);

				min = Math.min(heightmap[midpoint.x][midpoint.y], min);
				max = Math.max(heightmap[midpoint.x][midpoint.y], max);

				// terminating condition
				if (bottomRight.x - midpoint.x != 1) { // square so no need to check column diff
					offset = offset / Math.pow(2, smoothness); // reduce randomness
					toProcess.push(topLeft, midpoint, offset);
					toProcess.push(new Point(topLeft.x, midpoint.y), new Point(midpoint.x, bottomRight.y), offset);
					toProcess.push(midpoint, bottomRight, offset);
					toProcess.push(new Point(midpoint.x, topLeft.y), new Point(bottomRight.x, midpoint.y), offset);
				}
			}

			// clip length
			heightmap = heightmap.slice(0, size);
			for (i = 0; i < size; i++) {
				heightmap[i] = heightmap[i].slice(0, size);
			}

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

			return heightmap;
		}

	}

}