Generating a Random Maze in JavaScript

The JavaScript code shown below generates a random maze and displays it as an HTML canvas. (Also included is functionality to display the same maze as an HTML table element.)

To see the code in action, paste it into a .html file and open that file in a web browser that runs JavaScript.

<html>
<body>
<script type='text/javascript'>

function MazeGeneratorTest()
{
	this.main = function()
	{
		var mazeCellSizeInPixels = new Coords(4, 4);
		var mazeSizeInCells = new Coords(64, 64);

		var maze = Maze.generateRandom
		(
			mazeCellSizeInPixels,
			mazeSizeInCells
		);

		document.body.appendChild(maze.htmlElementBuildCanvas());
	}
}

// classes

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.divideScalar = function(scalar)
	{
		this.x /= scalar;
		this.y /= scalar;

		return this;
	}

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

		return returnValue;
	}

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

		return this;
	}

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

		return this;
	}

	Coords.prototype.overwriteWithDimensions = function(x, y)
	{
		this.x = x;
		this.y = y;

		return this;
	}

}

function Maze(cellSizeInPixels, sizeInCells, cells)
{
	this.cellSizeInPixels = cellSizeInPixels;
	this.sizeInCells = sizeInCells;
	this.cells = cells;
}
{
	// static methods

	Maze.generateRandom = function(cellSizeInPixels, sizeInCells)
	{
		var cells = [];

		var numberOfCells = sizeInCells.x * sizeInCells.y;

		for (var i = 0; i < numberOfCells; i++)
		{
			var cell = new MazeCell();
			cells.push(cell);
		}

		var neighborOffsets = Maze.neighborOffsets_Get();

		var numberOfNeighbors = neighborOffsets.length;

		var cellPos = new Coords(-1, -1);
		var cellPosNeighbor = new Coords(-1, -1);

		var numberOfCellsInLargestNetworkSoFar = 0;

		while (numberOfCellsInLargestNetworkSoFar  < numberOfCells)
		{
			for (var y = 0; y < sizeInCells.y; y++)
			{
				cellPos.y = y;

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

					var numberOfCellsInNetworkMerged = Maze.generateRandom_ConnectCellToRandomNeighbor
					(
						cells,
						sizeInCells,
						cellPos, 
						neighborOffsets, 
						numberOfNeighbors,
						cellPosNeighbor
					);

					if (numberOfCellsInNetworkMerged > numberOfCellsInLargestNetworkSoFar)
					{
						numberOfCellsInLargestNetworkSoFar = numberOfCellsInNetworkMerged
					}
				}
			}			
		}

		var returnValue = new Maze
		(
			cellSizeInPixels,
			sizeInCells,
			cells
		);

		return returnValue;
	}

	Maze.generateRandom_ConnectCellToRandomNeighbor = function
	(
		cells, 
		sizeInCells,
		cellPos, 
		neighborOffsets, 
		numberOfNeighbors, 
		cellPosNeighbor
	)
	{
		var numberOfCellsInNetworkMerged = 0;

		var cellCurrent = cells[cellPos.y * sizeInCells.x + cellPos.x];

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

		var neighborOffset = neighborOffsets[neighborOffsetIndex];

		cellPosNeighbor.overwriteWith(cellPos).add(neighborOffset);

		if (cellPosNeighbor.isWithinRange(sizeInCells) == true)
		{
			if (cellCurrent.connectedToNeighborsNESW[neighborOffsetIndex] == false)
			{
				var cellNeighbor = cells[cellPosNeighbor.y * sizeInCells.x + cellPosNeighbor.x];

				if (cellCurrent.network.networkID != cellNeighbor.network.networkID)
				{
					cellCurrent.connectedToNeighborsNESW[neighborOffsetIndex] = true;

					var neighborOffsetIndexReversed = (neighborOffsetIndex + 2) % numberOfNeighbors;
					cellNeighbor.connectedToNeighborsNESW[neighborOffsetIndexReversed] = true;

					var networkMerged = Network.MergeNetworks
					(
						cellCurrent.network,
						cellNeighbor.network
					);

					numberOfCellsInNetworkMerged = networkMerged.cells.length;
				}
			}
		}	

		return numberOfCellsInNetworkMerged;	
	}

	Maze.neighborOffsets_Get = function()
	{
		var returnValue = 
		[
			new Coords(0, -1),
			new Coords(1, 0),
			new Coords(0, 1),
			new Coords(-1, 0)
		];

		return returnValue;
	}

	// instance methods

	Maze.prototype.cellAtPos = function(cellPos)
	{
		var cellIndex = this.indexOfCellAtPos(cellPos);
		return this.cells[cellIndex];
	}

	Maze.prototype.htmlElementBuildCanvas = function()
	{
		var cellSizeInPixels = this.cellSizeInPixels;
		var cellSizeInPixelsHalf = cellSizeInPixels.clone().divideScalar(2);
		var sizeInPixels = this.sizeInCells.clone().multiply
		(
			this.cellSizeInPixels
		);

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

		graphics.fillStyle = "#000000";

		graphics.fillRect(0, 0, sizeInPixels.x, sizeInPixels.y);

		graphics.fillStyle = "#ffffff";

		var cellPos = new Coords(-1, -1);
		var numberOfNeighbors = 4;
		var neighborOffsets = Maze.neighborOffsets_Get();

		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 cellCurrent = this.cellAtPos(cellPos);

				graphics.fillRect
				(
					cellPos.x * cellSizeInPixels.x,
					cellPos.y * cellSizeInPixels.y, 
					cellSizeInPixelsHalf.x, 
					cellSizeInPixelsHalf.y
				);

				for (var n = 1; n <= 2; n++) // e and s only
				{
					var isConnectedToNeighbor = cellCurrent.connectedToNeighborsNESW[n];

					if (isConnectedToNeighbor == true)
					{
						var neighborOffset = neighborOffsets[n];

						graphics.fillRect
						(
							(cellPos.x + neighborOffset.x / 2) * cellSizeInPixels.x,
							(cellPos.y + neighborOffset.y / 2) * cellSizeInPixels.y,
							cellSizeInPixelsHalf.x, 
							cellSizeInPixelsHalf.y
						);
					}
				}
			}
		}

		this.htmlElement = returnValue;

		return returnValue;
	}

	Maze.prototype.htmlElementBuildTable = function()
	{
		var returnValue = document.createElement("table");
		returnValue.style.fontFamily = "Courier New"; 
		returnValue.cellSpacing = 0;
		returnValue.cellPadding = 0;

		var cellPos = new Coords(-1, -1);
		var numberOfNeighbors = 4;
		var neighborOffsets = Maze.neighborOffsets_Get();
		var innerTableCellPos = new Coords(-1, -1);

		var trForNorthWall = document.createElement("tr");
		for (var x = 0; x < this.sizeInCells.x + 1; x++)
		{
			var tdForNorthWall = document.createElement("td");
			tdForNorthWall.innerHTML = "[]";
			tdForNorthWall.style.backgroundColor = "#000000";
			trForNorthWall.appendChild(tdForNorthWall);
		}
		returnValue.appendChild(trForNorthWall);

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

			var trForRow = document.createElement("tr");			

			var tdForWestWall = document.createElement("td");
			tdForWestWall.innerHTML = "[]";
			tdForWestWall.style.backgroundColor = "#000000";
			trForRow.appendChild(tdForWestWall);

			for (var x = 0; x < this.sizeInCells.x; x++)
			{
				cellPos.x = x;
				var cellCurrent = this.cellAtPos(cellPos);

				var tableInnerForCell = document.createElement("table");
				tableInnerForCell.cellPadding = 0;
				tableInnerForCell.cellSpacing = 0;

				for (var yy = 0; yy < 2; yy++)
				{	
					var trInnerForCell = document.createElement("tr");

					for (var xx = 0; xx < 2; xx++)
					{
						var tdInnerForCell = document.createElement("td");
						tdInnerForCell.innerHTML = "[]";
						tdInnerForCell.style.backgroundColor = "#000000";
						trInnerForCell.appendChild(tdInnerForCell);
					}

					tableInnerForCell.appendChild(trInnerForCell);
				}

				tableInnerForCell.children[0].children[0].style.backgroundColor = "#ffffff";

				for (var n = 1; n <= 2; n++) // e and s only
				{
					var isConnectedToNeighbor = cellCurrent.connectedToNeighborsNESW[n];

					if (isConnectedToNeighbor == true)
					{
						var neighborOffset = neighborOffsets[n];
						innerTableCellPos.overwriteWith(neighborOffset);

						tableInnerForCell.children[innerTableCellPos.y].children[innerTableCellPos.x].style.backgroundColor = "#ffffff";
					}
				}

				var tdForCell = document.createElement("td");
				tdForCell.appendChild(tableInnerForCell);
				trForRow.appendChild(tdForCell);
			}

			returnValue.appendChild(trForRow); 
		}

		this.htmlElement = returnValue;

		return returnValue;
	}

	Maze.prototype.indexOfCellAtPos = function(cellPos)
	{
		var cellIndex = cellPos.y * this.sizeInCells.x + cellPos.x;

		return cellIndex;
	}
}

function MazeCell()
{
	this.connectedToNeighborsNESW = new Array(false, false, false, false);
	this.network = new Network();
	this.network.cells.push(this);
}

function Network()
{
	this.networkID = Network.MaxIDSoFar;
	Network.MaxIDSoFar++;
	this.cells = new Array();
}
{
	Network.MaxIDSoFar = 0;

	Network.MergeNetworks = function(network0, network1)
	{
		var networkMerged = new Network();

		var networksToMerge = new Array(network0, network1);

		var numberOfNetworks = networksToMerge.length;

		for (var n = 0; n < numberOfNetworks; n++)
		{
			var network = networksToMerge[n];
			for (var c = 0; c < network.cells.length; c++)
			{
				var cell = network.cells[c];
				cell.network = networkMerged;
				networkMerged.cells.push(cell);
			}
		}

		return networkMerged;
	}

}

// run

new MazeGeneratorTest().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