Growing tree maze algorithm in Javascript

Example source code


<!DOCTYPE html>
<html>
<head>

<script type="text/javascript">
var ctx = null, game = null;
var mazeMap = null, mazeW = 19, mazeH = 9;

window.onload = function() {
	game = document.getElementById('game');
	ctx = game.getContext('2d');
	ctx.font = "bold 10pt sans-serif";

	mazeMap = new Maze(10,10);

	requestAnimationFrame(drawGame);

	document.getElementById('reset').addEventListener('click', function() {
		mazeMap = new Maze(10,10, document.getElementById('next-cell').value);
	});
};

function drawGame()
{
	if(ctx==null) { return; }

	ctx.fillStyle = "#ffffff";
	ctx.fillRect(0, 0, 800, 400);

	ctx.fillStyle = "#000000";

	for(var y = 0; y < mazeMap.gridH; ++y)
	{
		for(var x = 0; x < mazeMap.gridW; ++x)
		{
			if(mazeMap.gridMap[y][x]==0) { ctx.fillRect(10 * x, 10 * y, 10, 10); }
		}
	}

	requestAnimationFrame(drawGame);
}

function Maze(w, h, nextCell, startX, startY)
{
	this.w = (isNaN(w) || w < 5 || w > 999 ? 20 : w);
	this.h = (isNaN(h) || h < 5 || h > 999 ? 20 : h);
	this.map = new Array();
	for(var mh = 0; mh < h; ++mh) { this.map[mh] = new Array(); for(var mw = 0; mw < w; ++mw) { this.map[mh][mw] = {'n':0,'s':0,'e':0,'w':0,'v':0}; } }

	this.nextCell = (typeof nextCell=='undefined' || (nextCell!='first' && nextCell!='last' && nextCell!='random') ? 'random' : nextCell);

	this.startX = (isNaN(startX) || startX<0 || startX>=w ? 0 : startX);
	this.startY = (isNaN(startY) || startY<0 || startY>=h ? 0 : startY);

	this.build();
}
Maze.prototype.toGrid = function()
{
	var grid = new Array();
	for(var mh = 0; mh < (this.h * 2 + 1); ++mh) { grid[mh] = new Array(); for(var mw = 0; mw < (this.w * 2 + 1); ++mw) { grid[mh][mw] = 0; } }

	for(var y = 0; y < this.h; ++ y)
	{
		var py = (y * 2) + 1;

		for(var x = 0; x < this.w; ++x)
		{
			var px = (x * 2) + 1;

			grid[py][px] = 1;

			if(this.map[y][x]['n']==1) { grid[(py-1)][px] = 1; }
			if(this.map[y][x]['s']==1) { grid[(py+1)][px] = 1; }
			if(this.map[y][x]['e']==1) { grid[py][(px+1)] = 1; }
			if(this.map[y][x]['w']==1) { grid[py][(px-1)] = 1; }
		}
	}

	this.gridMap = grid;
	this.gridW	= grid.length;
	this.gridH	= grid[0].length;
};
Maze.prototype.build = function(dir)
{
	var c = new Array();
	c.push({x:this.startX, y:this.startY});
	this.map[this.startY][this.startX]['v'] = 1;

	var modDir = {
		'n' : { y : -1, x : 0, o : 's' },
		's' : { y : 1, x : 0, o : 'n' },
		'w' : { y : 0, x : -1, o : 'e' },
		'e' : { y : 0, x : 1, o : 'w' }
	};

	while(c.length>0)
	{
		var i = (this.nextCell=='first' ? 0 : (this.nextCell=='last' ? c.length-1 : Math.floor((Math.random()*10000)%c.length)));
		var cell = c[i];

		// Check for neighbours
		var n = new Array();
		if(cell.x>0 && this.map[cell.y][(cell.x-1)]['v']==0) { n.push('w'); }
		if(cell.x<(this.w-1) && this.map[cell.y][(cell.x+1)]['v']==0) { n.push('e'); }
		if(cell.y>0 && this.map[(cell.y-1)][cell.x]['v']==0) { n.push('n'); }
		if(cell.y<(this.h-1) && this.map[(cell.y+1)][cell.x]['v']==0) { n.push('s'); }

		if(n.length==0) { c.splice(i, 1); continue; }

		var dir = n[Math.floor((Math.random()*10000)%n.length)];

		var destX = (cell.x + modDir[dir].x);
		var destY = (cell.y + modDir[dir].y);

		this.map[cell.y][cell.x][dir] = 1;
		this.map[destY][destX][modDir[dir].o] = 1;
		this.map[destY][destX]['v'] = 1;
		c.push({x:destX, y:destY});
	}

	this.toGrid();
};

</script>
</head>
<body>

<p>Binary Tree maze.</p>
<p>If you cannot see the maze below, check you have Javascript enabled and that your browser supports the Canvas element.</p>
Grow cells from <select id="next-cell">
	<option value="last">Last added</option>
	<option value="random">Random</option>
</select><input id="reset" type="button" value="Reset maze"><br>
<canvas id="game" width="800" height="400"></canvas>

</body>
</html>

Page loaded in 0.014 second(s).