A Procedurally Generated Cavern System in JavaScript

The JavaScript code below, when run, procedurally generates and displays a map of a random cavern system. To see it in action, copy it into an .html file and open that file in a web browser that runs JavaScript. Or, for an online version, visit https://thiscouldbebetter.neocities.org/proceduralcaverns.html.

The algorithm works by seeding the map with a large number of “nuclei”, which are spheres with a random center position and an initial radius of 1. Each of these nuclei are then placed into a single-member “network” of connected spheres. A random network and a random nucleus within that network are selected, such that the current radius of the nucleus is less than the maximum allowed radius. The radius of the selected nucleus is increased by one. The selected network is then tested against all of the other networks to see if it overlaps with any of them. If it does, the overlapping networks are merged into a single network. This process continues until there is only a single network remaining. This final network is written to the map cells. To make the resulting map look somewhat more organic, random noise is introduced, then partially smoothed away.

It’s not perfect. The code has a lot of inefficiencies, and the resulting cavern tends to be one large space, which might be more interesting if it had more internal walls. More work may be done in the future to increase the aesthetic appeal of the generated map.

ProcedurallyGeneratedCaverns

<html>
<body>

<div id="divMain"></div>

<script type="text/javascript">

// main

function CavernBuilderTest()
{
	this.main = function()
	{
		var mapTerrains = 
		[
			new MapTerrain("Blocked", "x", "Gray"),
			new MapTerrain("Open", ".", "LightGray"),
		];

		var mapGenerated = new MapGenerator().cave
		(
			mapTerrains,
			new Coords(128, 128), // sizeInCells
			32, // numberOfSpaceNuclei
			10, // spaceRadiusMax
			8096, // numberOfNoisySwaps
			.7 // smoothingFactor
		);

		mapGenerated.draw
		(
			new Coords(128, 128) // sizeInPixels
		);
	}
}

// extensions

function ArrayExtensions()
{}
{
	Array.prototype.addLookups = function(keyName)
	{
		for (var i = 0; i < this.length; i++)
		{
			var item = this[i];
			var key = item[keyName];
			this[key] = item;
		}
	}

	Array.prototype.append = function(other)
	{
		for (var i = 0; i < other.length; i++)
		{
			this.push(other[i]);
		}
	}
}

// classes

function Bounds(min, max)
{
	this.min = min;
	this.max = max;
	this.size = this.max.clone().subtract(this.min);
}
{
	Bounds.prototype.containsPoint = function(pointToCheck)
	{
		var returnValue = 
		(
			pointToCheck.x >= this.min.x
			&& pointToCheck.x <= this.max.x
			&& pointToCheck.y >= this.min.y
			&& pointToCheck.y <= this.max.y
		);

		return returnValue;
	}
}

function CollisionHelper()
{
	// static class
}
{
	CollisionHelper.doGroupsCollide = function(group0, group1)
	{
		var returnValue = false;

		for (var i = 0; i < group0.length; i++)
		{
			var colliderThis = group0[i];

			for (var j = 0; j < group1.length; j++)
			{
				var colliderOther = group1[j];

				var doCollidersCollide = colliderThis.collidesWithOther
				(
					colliderOther
				);

				if (doCollidersCollide == true)
				{
					returnValue = true;
					break;
				}
			}
		}

		return returnValue;
	}
}

function Coords(x, y)
{
	this.x = x;
	this.y = y;
}
{
	Coords.prototype.add = function(other)
	{
		this.x += other.x;
		this.y += other.y;
		return this;
	}

	Coords.prototype.clone = function()
	{
		return new Coords(this.x, this.y);
	}

	Coords.prototype.divide = function(other)
	{
		this.x /= other.x;
		this.y /= other.y;
		return this;
	}

	Coords.prototype.floor = function()
	{
		this.x = Math.floor(this.x);
		this.y = Math.floor(this.y);
		return this;
	}

	Coords.prototype.isInRange = function(max)
	{
		var returnValue = 
		(
			this.x >= 0
			&& this.x <= max.x
			&& this.y >= 0
			&& this.y <= max.y
		);

		return returnValue;
	}

	Coords.prototype.magnitude = function()
	{
		return Math.sqrt(this.x * this.x + this.y * this.y);
	}

	Coords.prototype.multiply = function(other)
	{
		this.x *= other.x;
		this.y *= other.y;
		return this;
	}

	Coords.prototype.multiplyScalar = function(scalar)
	{
		this.x *= scalar;
		this.y *= scalar;
		return this;
	}

	Coords.prototype.overwriteWith = function(other)
	{
		this.x = other.x;
		this.y = other.y;
		return this;
	}

	Coords.prototype.randomize = function()
	{
		this.x = Math.random();
		this.y = Math.random();
		return this;
	}

	Coords.prototype.subtract = function(other)
	{
		this.x -= other.x;
		this.y -= other.y;
		return this;
	}
}

function Map(terrains, cellsAsStrings)
{
	this.terrains = terrains;
	this.cellsAsStrings = cellsAsStrings;
	this.sizeInCells = new Coords
	(
		this.cellsAsStrings[0].length,
		this.cellsAsStrings.length
	);	

	this.sizeInCellsMinusOnes = this.sizeInCells.clone().subtract
	(
		new Coords(1, 1)
	);

	this.terrains.addLookups("name");
	this.terrains.addLookups("symbol");
}
{
	Map.prototype.cellAtPos = function(cellPos)
	{
		var returnValue = this.cellsAsStrings[cellPos.y].charAt(cellPos.x);
		return returnValue;
	}

	Map.prototype.cellAtPosSet = function(cellPos, cellValueToSet)
	{
		var cellRow = this.cellsAsStrings[cellPos.y];
		cellRow = 
			cellRow.substr(0, cellPos.x) 
			+ cellValueToSet
			+ cellRow.substr(cellPos.x + 1);
		this.cellsAsStrings[cellPos.y] = cellRow;
	}

	Map.prototype.draw = function(sizeInPixels)
	{
		var cellSizeInPixels = sizeInPixels.clone().divide
		(
			this.sizeInCells
		);

		var canvas = document.createElement("canvas");
		canvas.width = sizeInPixels.x;
		canvas.height = sizeInPixels.y
		
		var graphics = canvas.getContext("2d");

		graphics.fillStyle = "White";
		graphics.fillRect
		(
			0, 0,
			sizeInPixels.x, sizeInPixels.y
		);

		var cellPos = new Coords(0, 0);
		var drawPos = new Coords(0, 0);

		for (var y = 0; y < this.sizeInCells.y; y++)
		{
			cellPos.y = y;

			for (var x = 0; x < this.sizeInCells.x; x++)
			{
				cellPos.x = x;
	
				var cellSymbol = this.cellAtPos(cellPos);
				var cellTerrain = this.terrains[cellSymbol];
				var cellColor = cellTerrain.color;
				graphics.fillStyle = cellColor;

				drawPos.overwriteWith
				(
					cellPos
				).multiply
				(
					cellSizeInPixels
				);

				graphics.fillRect
				(
					drawPos.x, 
					drawPos.y,
					cellSizeInPixels.x, 
					cellSizeInPixels.y
				);
				
			}
		}

		var divMain = document.getElementById("divMain");
		divMain.appendChild(canvas);
	}
}

function MapGenerator()
{
	// do nothing
}
{
	MapGenerator.prototype.cave = function
	(
		terrains, 
		mapSizeInCells, 
		numberOfSpaceNuclei, 
		spaceRadiusMax,
		numberOfNoisySwaps,
		smoothingFactor
	)
	{
		var mapGenerated = this.cave_1_BuildBlankMap(terrains, mapSizeInCells);

		var margin = new Coords(1, 1).multiplyScalar(spaceRadiusMax);

		var spaces = this.cave_2_GrowSpaces
		(
			mapSizeInCells, numberOfSpaceNuclei, margin
		);

		this.cave_3_WriteSpacesToMap
		(
			spaces, mapGenerated
		);

		this.cave_4_ApplyNoise(mapGenerated, numberOfNoisySwaps);

		this.cave_5_Smooth(mapGenerated, smoothingFactor);
	
		return mapGenerated;
	}

	MapGenerator.prototype.cave_1_BuildBlankMap = function(terrains, mapSizeInCells)
	{
		terrains.addLookups("name");
		var terrainBlocked = terrains["Blocked"];
		var terrainBlockedSymbol = terrainBlocked.symbol;

		var mapCellsAsStrings = [];

		for (var y = 0; y < mapSizeInCells.y; y++)
		{
			var mapRowAsString = "";

			for (var x = 0; x < mapSizeInCells.x; x++)
			{
				mapRowAsString += terrainBlockedSymbol;
			}

			mapCellsAsStrings.push(mapRowAsString);
		}

		var mapBlank = new Map
		(
			terrains,
			mapCellsAsStrings
		);

		return mapBlank;
	}

	MapGenerator.prototype.cave_2_GrowSpaces = function(mapSizeInCells, numberOfNuclei, margin)
	{
		var nucleusNetworks = [];

		var mapSizeMinusMargins = mapSizeInCells.clone().subtract
		(
			margin
		).subtract
		(
			margin
		).subtract
		(
			new Coords(2, 2)
		);

		for (var i = 0; i < numberOfNuclei; i++)
		{
			var nucleusPos = new Coords().randomize().multiply
			(
				mapSizeMinusMargins
			).floor().add
			(
				margin
			);

			var nucleus = new ShapeSphere(nucleusPos, 1);

			nucleusNetworks.push([nucleus]);
		}

		var radiusMax = margin.x;

		while (nucleusNetworks.length > 1)
		{
			var numberOfNetworks = nucleusNetworks.length;

			var network;
			var nucleus;

			var networkIndexRandom = Math.floor
			(
				Math.random() * numberOfNetworks
			);

			for (var i = 0; i < numberOfNetworks; i++)
			{
				var networkIndex = (networkIndexRandom + i) % numberOfNetworks;
				network = nucleusNetworks[networkIndex];

				var numberOfNuclei = network.length;
				var nucleusIndexRandom = Math.floor
				(
					Math.random() * numberOfNuclei
				);

				for (var j = 0; j < numberOfNuclei; j++)
				{
					var nucleusIndex = 
						(nucleusIndexRandom + j) % numberOfNuclei;
					nucleus = network[nucleusIndex];

					if (nucleus.radius < radiusMax)
					{
						i = numberOfNetworks;
						break;
					}
				}
			}

			var networkToEnlarge = network;
			var nucleusToEnlarge = nucleus;

			nucleusToEnlarge.radius++;

			var nucleusNetworkIndicesAnnexed = [];

			for (var i = 0; i < nucleusNetworks.length; i++)
			{
				var networkOther = nucleusNetworks[i];
			
				if (networkOther != networkToEnlarge)
				{
					var doNetworksCollide = CollisionHelper.doGroupsCollide
					(
						networkToEnlarge,
						networkOther
					);

					if (doNetworksCollide == true)
					{
						networkToEnlarge.append
						(
							networkOther
						);

						nucleusNetworkIndicesAnnexed.push(i);
					}
				}
			}

			for (var i = nucleusNetworkIndicesAnnexed.length - 1; i >= 0; i--)
			{
				var networkIndexAnnexed = nucleusNetworkIndicesAnnexed[i];
				nucleusNetworks.splice(networkIndexAnnexed, 1);
			}
		}

		var nucleusNetworkFinal = nucleusNetworks[0];

		return nucleusNetworkFinal;
	}

	MapGenerator.prototype.cave_3_WriteSpacesToMap = function(spaces, mapGenerated)
	{
		var terrainOpenSymbol = mapGenerated.terrains["Open"].symbol;

		var mapBoundsMinusMargins = new Bounds
		(
			new Coords(1, 1),
			mapGenerated.sizeInCells.clone().subtract
			(
				new Coords(2, 2)
			)
		);

		for (var i = 0; i < spaces.length; i++)
		{
			var space = spaces[i];

			var cornerNW = space.centerPos.clone().subtract
			(
				new Coords(1, 1).multiplyScalar(space.radius)
			);

			var cellPos = new Coords(0, 0);
			var cellOffsetFromCorner = new Coords(0, 0);
			var displacementOfCellFromCenter = new Coords(0, 0);

			var diameter = space.radius * 2;

			for (var y = 0; y < diameter; y++)
			{
				cellOffsetFromCorner.y = y;

				for (var x = 0; x < diameter; x++)
				{
					cellOffsetFromCorner.x = x;

					cellPos.overwriteWith
					(
						cornerNW
					).add
					(
						cellOffsetFromCorner
					);

					if (mapBoundsMinusMargins.containsPoint(cellPos) == true)
					{
						displacementOfCellFromCenter.overwriteWith
						(
							cellPos
						).subtract
						(
							space.centerPos
						);

						var distance = displacementOfCellFromCenter.magnitude();

						if (distance <= space.radius)
						{
							mapGenerated.cellAtPosSet
							(
								cellPos, terrainOpenSymbol
							);	
						}
					}
				}
			}
		}

		return mapGenerated;
	}

	MapGenerator.prototype.cave_4_ApplyNoise = function
	(
		mapGenerated, noisySwapsToPerform
	)
	{
		var mapBoundsMinusMargins = new Bounds
		(
			new Coords(2, 2),
			mapGenerated.sizeInCells.clone().subtract
			(
				new Coords(2, 2)
			)
		);

		var cellPos = new Coords();
		var neighborPos = new Coords();
		var ones = new Coords(1, 1);
		var directionsToNeighbors = 
		[
			new Coords(1, 0),
			new Coords(1, 1),
			new Coords(0, 1),
			new Coords(-1, 1),
			new Coords(-1, 0),
			new Coords(-1, -1),
			new Coords(0, -1),
			new Coords(1, -1),
		];
		var numberOfNeighbors = directionsToNeighbors.length;

		for (var i = 0; i < noisySwapsToPerform; i++)
		{
			cellPos.randomize().multiply
			(
				mapBoundsMinusMargins.size
			).floor().add
			(
				mapBoundsMinusMargins.min
			);

			var directionIndexRandom = Math.floor
			(
				Math.random() * numberOfNeighbors
			);

			var directionToNeighbor = directionsToNeighbors[directionIndexRandom];

			neighborPos.overwriteWith
			(
				cellPos
			).add
			(
				directionToNeighbor
			);

			var cellValue = mapGenerated.cellAtPos(cellPos);
			var neighborValue = mapGenerated.cellAtPos(neighborPos);

			mapGenerated.cellAtPosSet(cellPos, neighborValue);
			mapGenerated.cellAtPosSet(neighborPos, cellValue);
		}
	}

	MapGenerator.prototype.cave_5_Smooth = function
	(
		mapGenerated, smoothingFactor
	)
	{	
		var mapBoundsMinusMargins = new Bounds
		(
			new Coords(2, 2),
			mapGenerated.sizeInCells.clone().subtract
			(
				new Coords(4, 4)
			)
		);

		var directionsToNeighbors = 
		[
			new Coords(1, 0),
			new Coords(1, 1),
			new Coords(0, 1),
			new Coords(-1, 1),
			new Coords(-1, 0),
			new Coords(-1, -1),
			new Coords(0, -1),
			new Coords(1, -1),
		];
		var numberOfNeighbors = directionsToNeighbors.length;

		var numberOfNeighborsThreshold = 
			numberOfNeighbors * smoothingFactor;
		var terrainBlockedSymbol = mapGenerated.terrains["Blocked"].symbol;
		var cellPositionsToClear = [];
		var mapSizeMinusMargins = mapBoundsMinusMargins.size;

		var cellPos = new Coords();
		var neighborPos = new Coords();

		for (var y = mapBoundsMinusMargins.min.y; y < mapBoundsMinusMargins.max.y; y++)
		{
			cellPos.y = y;

			for (var x = mapBoundsMinusMargins.min.x; x < mapBoundsMinusMargins.max.x; x++)
			{
				cellPos.x = x;

				var cellValue = mapGenerated.cellAtPos(cellPos);

				var numberOfNeighborsBlocked = 0;
				
				for (var n = 0; n < numberOfNeighbors; n++)
				{
					var directionToNeighbor = directionsToNeighbors[n];

					neighborPos.overwriteWith
					(
						cellPos
					).add
					(
						directionToNeighbor
					);

					var neighborValue = mapGenerated.cellAtPos
					(
						neighborPos
					);

					if (neighborValue == terrainBlockedSymbol)
					{
						numberOfNeighborsBlocked++;
					}
				}

				if (numberOfNeighborsBlocked <= numberOfNeighborsThreshold)
				{
					cellPositionsToClear.push(cellPos.clone());
				}
			}
		}

		var terrainOpenSymbol = mapGenerated.terrains["Open"].symbol;

		for (var i = 0; i < cellPositionsToClear.length; i++)
		{
			cellPos = cellPositionsToClear[i];
			mapGenerated.cellAtPosSet(cellPos, terrainOpenSymbol);
		}

		return mapGenerated;
	}	
}

function MapTerrain(name, symbol, color)
{
	this.name = name;
	this.symbol = symbol;
	this.color = color;
}

function ShapeSphere(centerPos, radius)
{
	this.centerPos = centerPos;
	this.radius = radius;
}
{
	ShapeSphere.prototype.bounds = function()
	{
		var offsetToBounds = new Coords(1, 1).multiplyScalar(this.radius);

		var returnValue = new Bounds
		(
			this.centerPos.clone().add(offsetToBounds),
			this.centerPos.clone().subtract(offsetToBounds)
		);

		return returnValue;
	}

	ShapeSphere.prototype.collidesWithOther = function(other)
	{
		var distanceBetweenCenters = other.centerPos.clone().subtract
		(
			this.centerPos
		).magnitude();

		var sumOfRadii = this.radius + other.radius;

		var returnValue = (distanceBetweenCenters < sumOfRadii);
		
		return returnValue;
	}
}

// run

new CavernBuilderTest().main();

</script>
</body>
</html>

Advertisements
This entry was posted in Uncategorized and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s