Terramorphic Genesis Algorithms (or Terrain Generation)

My fascination with the game Scorched Earth knows no bounds. One might say I am the Mother of All Scorched Earth Fans. One of my earliest fascinations with the game (keep in mind, I was like 10) was that I could play for hours and hours and never play the same level twice. The ground was all shifty! I tried writing my own “Terrain Genesis System,” as I dubbed it, in the mighty QBasic, but most of my terrains ended up looking mysteriously similar to a straight line (this was shortly after I tried to write my own Zork-inspired adventure in QBasic–I had a great story but fleeting gameplay…).

Well guess what? You can shove it, 1991, because I’ve finally caught up with you! I can now generate TWO different types of terrain! I dub my creation: the Terramorphic Genesis Algorithms.

There are two very basic types of terrain generation I have found to be useful, particularly if you’re looking for Scorched Earth-style terrain. The first is called limited-random, the second: circle-hill (I didn’t come up with these uninspired names; definitely not enough mythological references for my taste).

Limited Random

Limited random terrains are characterized by pointyness, much like the common greyhound. The algorithm is below, presented in technicolor javascript, but it’s easy enough to translate these to AS3 or… really any other language.

function generateLimitedRandom() {
	// create a two-dimensional array
	var heightMap = new Array2(_that.width, _that.height);

	// iterate over every index
	for(var i = 0; i < width - 1; i++){
		for(var j = 0; j < height - 1; j++){
			var a = 0;

			// grab a previous value
			if(i != 0 && j != 0){
				a = (heightMap.get(i - 1, j) + heightMap.get(i, j - 1)) / 2;
			}
			else if( i != 0 && j == 0 ){
				a = heightMap.get(i - 1, j);
			}
			else{
				a = Math.random() * height;
			}

			// add a random number, capped my a maximum increase
			var h = a + maximumHeightIncrease * (Math.random() - 1 / 2);

			// set the value at that index, between predefined boundaries
			heightMap.set(i, j, Math.max(minimumHeight, Math.min(h, maximumHeight)));
		}
	}

	return heightMap;
};

Pretty simple, eh? You’re basically just adding a random number to each value, but you’re making it behave by grabbing a previous value. The next type is much more interesting, I swear.

Circle-Hill

In circle-hill generation, the algorithm picks random coordinates on the two dimensional array and adds a randomly sized hill to each spot.

function generateCircleHill() {
	var circleRadiusSquared = circleRadius * circleRadius;

	// make + fill a 2D array
	var heightMap = new Array2(width, height);
	heightMap.fill(50);

	// iterate once per hill you want to add (given by numCircles)
	for(var pd_i = 1; pd_i < numCircles; pd_i++){
		// ~~ is moderately faster than converting these to integers
		var pd_x = ~~(Math.random() * width);
		var pd_y = ~~(Math.random() * height);

		// no iterate over all the values around the hill
		for(var pd_j = 0; pd_j < width - 1; pd_j++){
			for(var pd_k = 0; pd_k < height - 1; pd_k++){
				// only edit those within a certain distance
				var pd_d = (pd_x - pd_j)*(pd_x - pd_j) + (pd_y - pd_k)*(pd_y - pd_k);
				if(pd_d < circleRadiusSquared){
					// change the height trigonometrically
					var pd_a = (circleHeightIncrease / 2) * (1 + Math.cos(Math.PI * pd_d / (circleRadiusSquared)));
					heightMap.set(
						pd_j,
						pd_k,
						Math.min(heightMap.get(pd_j, pd_k) + pd_a, maximumHeight));
				}
			}
		}
	}

	return heightMap;
};

Circle-hill generation generally produces much more pleasing terrain than limited-random, but they each have their uses.

Take a look at the demo page if you’re interested in seeing what these two algorithms can do. You’ll need a browser that supports the canvas tag–sorry if it doesn’t work on your browser, I did not take the time to test it everywhere. I should note, these algorithms actually create 3D terrain, but in the demo page I am taking cross sections to get the Scorched Earth-style result:

for (var i = 0; i < width; i++) {
	var value = map.get(i, CONSTANT);
}

If you want the source, head over to github.