Recursive Backtracking mazes in Javascript

Maze Generation

This method create mazes using Recursive Backtracking in Javascript.

View example

First, we use a Maze object to store dimensions, map data, and directional constants:


function Maze(w, h)
{
	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.dirs = ['n', 's', 'e', 'w'];
	this.modDir = {
		'n' : { y : -1, x : 0, o : 's' },
		's' : { y : 1, x : 0, o : 'n' },
		'e' : { y : 0, x : -1, o : 'w' },
		'w' : { y : 0, x : 1, o : 'e' }
	};

	this.build(0, 0);
}

Next, we use a build method that specifies the starting point of the maze:


Maze.prototype.build = function(x, y)
{
	var x = 0;
	var y = 0;

	this.explore(x, y);
	this.toGrid();
};

The build method then recursively calls the explore method. From the starting tile, we move in a random direction that falls within map bounds and hasn't already been explored. We then flag the new tile as explored, and continue from there, until all tiles we can reach are already explored.


Maze.prototype.explore = function(ex, ey)
{
	this.dirs = sortRand(this.dirs);

	for(d in this.dirs)
	{
		var nx = ex + this.modDir[this.dirs[d]].x;
		var ny = ey + this.modDir[this.dirs[d]].y;

		if(nx >= 0 && nx < this.w && ny >= 0 && ny < this.h && this.map[ny][nx].v==0)
		{
			this.map[ey][ex][this.dirs[d]] = 1;
			this.map[ey][ex].v = 1;
			this.map[ny][nx][this.modDir[this.dirs[d]].o] = 1;

			this.explore(nx, ny);
		}
	}
};

Finally, we have a method for converting the maze we generate to a tile map, suitable for tile based games:


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;

			if(this.map[y][x].v==1) { grid[py][px] = 1; }

			for(d in this.dirs)
			{
				if(this.map[y][x][this.dirs[d]]==1) { grid[(py+this.modDir[this.dirs[d]].y)][(px+this.modDir[this.dirs[d]].x)] = 1; }
			}
		}
	}

	this.gridMap = grid;
	this.gridW	= grid.length;
	this.gridH	= grid[0].length;
};

Page loaded in 0.012 second(s).