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.

UPDATE 2018/03/02: I have updated this code to add an input interface and to clean it up somewhat. I removed the code that rendered to an HTML table. I also added a screenshot.

MazeGenerator.png


<html>
<body>

<div id="divUI">
	<p><b>Maze Generator</b></p>
	
	<label>Size in Cells:</label>
	<input id="inputMazeSizeInCellsX" type="number" value="4"></input>
	<label>x</label>
	<input id="inputMazeSizeInCellsY" type="number" value="4"></input>
	<br />
	
	<label>Size in Pixels:</label>
	<input id="inputMazeSizeInPixelsX" type="number" value="64"></input>
	<label>x</label>
	<input id="inputMazeSizeInPixelsY" type="number" value="64"></input>
	<br />

	<button onclick="buttonMazeGenerate_Clicked();">Generate</button>
	
	<div id="divOutput"></div>
	
</div>

<script type="text/javascript">

function buttonMazeGenerate_Clicked()
{
	var d = document;
	var inputMazeSizeInCellsX = d.getElementById("inputMazeSizeInCellsX");
	var inputMazeSizeInCellsY = d.getElementById("inputMazeSizeInCellsY");
	var inputMazeSizeInPixelsX = d.getElementById("inputMazeSizeInPixelsX");
	var inputMazeSizeInPixelsY = d.getElementById("inputMazeSizeInPixelsY");
	
	var mazeSizeInCells = new Coords
	(
		parseInt(inputMazeSizeInCellsX.value),
		parseInt(inputMazeSizeInCellsY.value)
	);
	var mazeSizeInPixels = new Coords
	(
		parseInt(inputMazeSizeInPixelsX.value),
		parseInt(inputMazeSizeInPixelsY.value)
	);
	
	var maze = Maze.random(mazeSizeInCells);
	
	var mazeAsCanvas = maze.toCanvas(mazeSizeInPixels);

	var divOutput = d.getElementById("divOutput");
	divOutput.innerHTML = "";
	divOutput.appendChild(mazeAsCanvas);
}

// 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.divide = function(other)
	{
		this.x /= other.x;
		this.y /= other.y;
		return this;
	}	

	Coords.prototype.divideScalar = function(scalar)
	{
		this.x /= scalar;
		this.y /= scalar;
		return this;
	}

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

	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.overwriteWithDimensions = function(x, y)
	{
		this.x = x;
		this.y = y;
		return this;
	}

}

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

	Maze.random = function(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();
		var numberOfNeighbors = neighborOffsets.length;

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

		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.random_Neighbor
					(
						cells,
						sizeInCells,
						cellPos, 
						neighborOffsets, 
						numberOfNeighbors,
						cellPosNeighbor
					);
					
					var numberOfCellsInNetworkMinusLargest = 
						numberOfCellsInNetworkMerged 
						 - numberOfCellsInLargestNetworkSoFar

					if (numberOfCellsInNetworkMinusLargest > 0)
					{
						numberOfCellsInLargestNetworkSoFar = 
							numberOfCellsInNetworkMerged;
					}
				}
			}			
		}

		var returnValue = new Maze(sizeInCells, cells);

		return returnValue;
	}

	Maze.random_Neighbor = 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.isInRangeMax(sizeInCells) == true)
		{
			var cellConnections = cellCurrent.connectedToNeighborsESWN;
		
			if (cellConnections[neighborOffsetIndex] == false)
			{
				var cellIndex = 
					cellPosNeighbor.y * sizeInCells.x + cellPosNeighbor.x;
			
				var cellNeighbor = cells[cellIndex];
			
				var cellCurrentNetworkID = cellCurrent.network.networkID;
				var cellNeighborNetworkID = cellNeighbor.network.networkID;
				
				var areCellAndNeighborInSameNetwork = 
					(cellCurrentNetworkID != cellNeighborNetworkID);

				if (areCellAndNeighborInSameNetwork == true)
				{
					cellConnections[neighborOffsetIndex] = true;

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

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

					numberOfCellsInNetworkMerged = networkMerged.cells.length;
				}
			}
		}	

		return numberOfCellsInNetworkMerged;	
	}

	Maze.neighborOffsets = function()
	{
		var returnValue = 
		[
			new Coords(1, 0), // east
			new Coords(0, 1), // south
			new Coords(-1, 0), // west
			new Coords(0, -1) // north
		];

		return returnValue;
	}

	// instance methods

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

	Maze.prototype.toCanvas = function(sizeInPixels)
	{
		// Need a border.
		var halves = new Coords(.5, .5);
		var sizeInCellsPlusHalves = this.sizeInCells.clone().add(halves);
		var cellSizeInPixels = sizeInPixels.clone().divide
		(
			sizeInCellsPlusHalves
		); 
		
		var cellSizeInPixelsHalf = cellSizeInPixels.clone().divideScalar(2);

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

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

		graphics.fillStyle = "White";

		var cellPosInCells = new Coords();
		var drawPos = new Coords();
		var neighborOffsets = Maze.neighborOffsets();
		var numberOfNeighbors = neighborOffsets.length;		

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

			for (var x = 0; x < this.sizeInCells.x; x++)
			{
				cellPosInCells.x = x;
				var cellCurrent = this.cellAtPos(cellPosInCells);
				
				drawPos.overwriteWith
				(
					cellPosInCells
				).add
				(
					halves
				).multiply
				(
					cellSizeInPixels
				);

				graphics.fillRect
				(
					drawPos.x, drawPos.y,
					cellSizeInPixelsHalf.x, cellSizeInPixelsHalf.y
				);

				for (var n = 0; n <= 1; n++) // east and south only
				{
					var isConnectedToNeighbor = 
						cellCurrent.connectedToNeighborsESWN[n];

					if (isConnectedToNeighbor == true)
					{
						var neighborOffset = neighborOffsets[n];
						
						drawPos.overwriteWith
						(
							cellPosInCells
						).add
						(
							halves
						).multiplyScalar
						(
							2
						).add
						(
							neighborOffset
						).multiply
						(
							cellSizeInPixelsHalf
						);

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

		return canvas;
	}

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

		return cellIndex;
	}
}

function MazeCell()
{
	this.connectedToNeighborsESWN = [ 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 = [ 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;
	}

}

</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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s