JavaScript Maze Solver Algorithm

Question

HTML

<div id="labirinth">
    <form style="text-align:center" name="forma1" autocomplete="on">
        <table style="margin:0 auto;">
            <tr>
                <td style="float:right;">Height:</td>
                <td><input type="text" id="height" name="height" autofocus="autofocus" maxlength="2" size="6" /></td>
            </tr>
            <tr>
                <td style="float:right;">Width:</td>
                <td><input type="text" id="width" name="width"  maxlength="2" size="6" /></td>
            </tr>
        </table>
    </form>
    <input type="button" alt="submit" onClick="datas();" value="New" style="margin-top:10px;" />
</div>
<pre id="out"></pre>

JavaScript

function datas() {

    var height = parseInt(document.getElementById("height").value);
    var width = parseInt(document.getElementById("width").value);

    document.getElementById('out').innerHTML = display(maze(height,width));
}

function maze(x,y) {
    var n=x*y-1;
    if (n<0) {alert("Bad numbers!");return;}
    var horiz=[]; 
        for (var j= 0; j<x+1; j++) horiz[j]= [];
    var verti=[]; 
        for (var j= 0; j<y+1; j++) verti[j]= [];

    var here= [Math.floor(Math.random()*x), Math.floor(Math.random()*y)];
    var path= [here];
    var unvisited= [];
    for (var j= 0; j<x+2; j++) {
        unvisited[j]= [];
        for (var k= 0; k<y+1; k++)
            unvisited[j].push(j>0 && j<x+1 && k>0 && (j != here[0]+1 || k != here[1]+1));
    }
    while (0<n) {
        var potential= [[here[0]+1, here[1]], [here[0],here[1]+1],
            [here[0]-1, here[1]], [here[0],here[1]-1]];
        var neighbors= [];
        for (var j= 0; j < 4; j++)
            if (unvisited[potential[j][0]+1][potential[j][1]+1])
                neighbors.push(potential[j]);
        if (neighbors.length) {
            n= n-1;
            next= neighbors[Math.floor(Math.random()*neighbors.length)];
            unvisited[next[0]+1][next[1]+1]= false;
            if (next[0] == here[0])
                horiz[next[0]][(next[1]+here[1]-1)/2]= true;
            else 
                verti[(next[0]+here[0]-1)/2][next[1]]= true;
            path.push(here= next);
        } else 
            here= path.pop();
    }
    return ({x: x, y: y, horiz: horiz, verti: verti});
}

function display(m) {
    var text= [];
    for (var j= 0; j<m.x*2+1; j++) {
        var line= [];
        if (0 == j%2)
            for (var k=0; k<m.y*4+1; k++)
                if (0 == k%4) 
                    line[k]= 'X';
                else
                    if (j>0 && m.verti[j/2-1][Math.floor(k/4)])
                        line[k]= ' ';
                    else
                        line[k]= 'X';
        else
            for (var k=0; k<m.y*4+1; k++)
                if (0 == k%4)
                    if (k>0 && m.horiz[(j-1)/2][k/4-1])
                        line[k]= ' ';
                    else
                        line[k]= 'X';
                else
                    line[k]= ' ';
        if (0 == j) line[1]=line[3]=' ',line[2]= '1';
        if (m.x*2-1 == j) line[4*m.y]= '2';
        text.push(line.join('')+'\r\n');

    }
    return text.join('');
}

I'm trying to create fully working maze generator in JavaScript without using HTML table cells. Now I have problems with creation solver for this maze.

Question: Which maze-solving algorithm do I need to use for my code? What should I start with? I don't need the whole algorithm--I just need advice on whether it is possible to have a maze solver in this maze generator.

JSbin - http://jsbin.com/uwoyon/1

Answer 1

My recommendation for a solver that should work for the mazes you are generating would be Dijkstra's algorithm. While I'm unsure how the horiz and verti parameters define the maze structure, Dijkstra's algorithm would work in your situation by starting at the cell next to '1' and building out from there.

The way it operates is to label each cell with the number of cells between it and the starting cell. For a 3x3 maze the first cell would be:

x 1 xxxxxxxxx
x 1         x
x   xxxxxxxxx
x           x
x   xxxxxxxxx
x           2
xxxxxxxxxxxxx

Working from a labeled cell check if there is an empty adjacent cell (one not blocked by a wall), increment the cell value by 1. Repeat this process for all empty cells:

x 1 xxxxxxxxx
x 1   2   3 x
x   xxxxxxxxx
x 2   3   4 x
x   xxxxxxxxx
x 3   4   5 2
xxxxxxxxxxxxx

Now work backwards from the cell adjacent to the end '2'. This shows that the solution has a path of length 5 steps, so start at 5, find the adjacent 4, then the 3, etc. back to 1.

Note: I recommend a recursive solution using queues for labeling the cells:

1- Label first cell with a '1' and place it in the queue.

2- Take cell from queue: - check if a legal neighbor (the ones that aren't blocked by a wall) is unlabelled. - If a neighboring cell is unlabelled, then label it with current cell+1. - Add neighboring cell to the queue. - Repeat for all 4 potential neighbors

3- Repeat steps 1 and 2 until there are no more unlabelled cells.

EDIT: Here's the fiddle for a solver using what I suggested, it doesn't pertain to the maze generator in the question so unless asked, I won't go into detail about how it operates (it's a bit rough, but its implementation should be easy enough to follow).