Recursive Backtracking mazes in Javascript

Fri May 02 2025 15:06:07 GMT+0100 (British Summer Time) canvas gamedev function maze maps javascript archived

Maze Generation

This method create mazes using Recursive Backtracking in Javascript.

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;
};

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);
    });
};

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)
{
    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);
}
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;
};
Maze.prototype.build = function(x, y)
{
    var x = 0;
    var y = 0;

    this.explore(x, y);
    this.toGrid();
};
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);
        }
    }
};

function sortRand(a)
{
    var out = new Array();
    var l    = a.length;

    for(x in a)
    {
        do { var p = Math.floor(Math.random() * (l * 1000)) % l; } while(typeof out[p]!='undefined');

        out[p] = a[x];
    }

    return out;
}
</script>
</head>
<body>

<p>Recursive Backtracking maze.</p>
<p>If you cannot see the maze below, check you have Javascript enabled and that your browser supports the Canvas element.</p>
<input id="reset" type="button" value="Reset maze"><br>
<canvas id="game" width="800" height="400"></canvas>

</body>
</html>