Making a cave-like structure

Cave like algorithmThere are a lot of tutorials on the net that make use of cellular automata to generate cave-like structures. Cellular automata are easy to program and I found a C & C# implementation which I used as a base for this method. The relevant method to generate the cave is at the end of this post. The demo allows fiddling with the input parameters.

Inputs

  • Cave width: width in blocks (rendered here as a 3×3 pixel)
  • Cave height: height in blocks
  • Cave smoothness: iterations to run the cellular automata for, higher = smoother, but longer
  • Cave density: the percentage of the space to be filled initially
  • Cave continuous: is there a pre-pass filter to fill in empty regions to try and enforce a more connected cave e.g. less isolated cave areas. It is better to start off with a less dense cave when this is enabled.

The algorithm

Seed the 2D matrix with random values, with density chance (1 = wall, 0 = floor)

var map:Vector.<Vector.<int>> = new Vector.<Vector.<int>>();
for (var y:int = 0; y < height; y++)
{
	var row:Vector.<int>> = new Vector.<int>>();
	for (var x:int = 0; x < width; x++)
		row.push(rnd.bit(density));
	map.push(row);
}

The above code creates a matrix of ints and randomly assigns a 1 to each cell with a chance of “density”. If continuous? then runs the pre-filter for smoothness iterations and sets each cell to

mapBuffer[y][x] = (isBorder || atLeast5Walls || atMost2Walls) ? 1 : 0;

Then always smooth with the following automata for smoothness iterations and set each cell to

mapBuffer[y][x] = (isBorder || atLeast5Walls) ? 1 : 0;

That is all there is to the algorithm. The rendering is handled separately (email me if you would like to know more).

The code

package net.avdw.generate
{
	import net.avdw.array.createIntVectorMatrix;
	import net.avdw.number.SeededRNG;

	/**
	 * http://roguebasin.roguelikedevelopment.org/index.php?title=Cellular_Automata_Method_for_Generating_Random_Cave-Like_Levels
	 * 
	 * @param	width
	 * @param	height
	 * @param	smoothness
	 * @param	density (continuous) ? .35 : .5
	 * @param	continuous reduces isolated caves
	 * @param	seed
	 * @return
	 */
	public function makeCave(width:int, height:int = 0, smoothness:int = 4, density:Number = 0.35, continuous:Boolean = true, seed:int = 0):Vector.<Vector.<int>>
	{
		seed = seed == 0 ? Math.random() * int.MAX_VALUE : seed;
		height = height == 0 ? width : height;
		var rnd:SeededRNG = new SeededRNG(seed);

		var map:Vector.<Vector.<int>> = new Vector.<Vector.<int>>();
		for (var y:int = 0; y < height; y++)
		{
			var row:Vector.<int>> = new Vector.<int>>();
			for (var x:int = 0; x < width; x++)
				row.push(rnd.bit(density));
			map.push(row);
		}

		var calcNumWallsNStepsFromPoint:Function = function(map:Vector.<Vector.>, px:int, py:int, steps:int):int
		{
			var xRange:Object = {low: Math.max(0, x - steps), high: Math.min(width - 1, x + steps)};
			var yRange:Object = {low: Math.max(0, y - steps), high: Math.min(height - 1, y + steps)};
			var wallCount:int = 0;

			for (var xi:int = xRange.low; xi <= xRange.high; xi++)
				for (var yi:int = yRange.low; yi <= yRange.high; yi++)
				{
					if (xi == x && yi == y)
						continue;

					wallCount += map[yi][xi];
				}

			return wallCount;
		};

		var oneStepWallCount:int;
		var twoStepWallCount:int;
		var isBorder:Boolean;
		var atLeast5Walls:Boolean;
		var atMost2Walls:Boolean;
		var mapBuffer:Vector.<Vector.>;
		var i:int;

		// fill in gaps and smooth
		if (continuous)
			for (i = 0; i < smoothness; i++)
			{
				mapBuffer = createIntVectorMatrix(height, width, 0);
				for (y = 0; y < height; y++)
				{
					for (x = 0; x < width; x++) 					{ 						oneStepWallCount = calcNumWallsNStepsFromPoint(map, x, y, 1); 						twoStepWallCount = calcNumWallsNStepsFromPoint(map, x, y, 2); 						 						isBorder = x == 0 || y == 0 || x == width - 1 || y == height - 1; 						atLeast5Walls = oneStepWallCount >= 5 || (oneStepWallCount + map[y][x]) >= 5;
						atMost2Walls = (twoStepWallCount + map[y][x]) <= 2;

						mapBuffer[y][x] = (isBorder || atLeast5Walls || atMost2Walls) ? 1 : 0;
					}
				}
				map = mapBuffer;
			}

		// smooth edges
		for (i = 0; i < smoothness; i++)
		{
			mapBuffer = createIntVectorMatrix(height, width, 0);
			for (y = 0; y < height; y++)
			{
				for (x = 0; x < width; x++) 				{ 					oneStepWallCount = calcNumWallsNStepsFromPoint(map, x, y, 1); 					twoStepWallCount = calcNumWallsNStepsFromPoint(map, x, y, 2); 					 					isBorder = x == 0 || y == 0 || x == width - 1 || y == height - 1; 					atLeast5Walls = oneStepWallCount >= 5 || (oneStepWallCount + map[y][x]) >= 5;

					mapBuffer[y][x] = (isBorder || atLeast5Walls) ? 1 : 0;
				}
			}
			map = mapBuffer;
		}

		return map;
	}

}