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

Answer 2

If it's a perfect maze (only one path between any two cells) then you just need a recursive wall follower. Start with the first cell and check all surrounding cells in a given order, typically clockwise or counterclockwise. If the cell can be entered, enter it. If it's the end, you're done. If not, recurse. When you've checked all 3 other paths and none are the end simply return. When you reach the end your call stack has the solution :) What I typically do is return "false" for "I didn't find the solution here" or "true" for "this is the solution".

You can see how I solve in my maze algorithms on github:

https://github.com/mdchaney/jsmaze

If you look at jsmaze2.html the function "find_depth" is actually a solver.

jsmaze4.html is very much more complex but it actually builds the solution while building mazes with the recursive algorithm. It does this by keeping track of which wall was knocked down when a cell is "entered" during building. Since there are other algorithms I've also included "find_depth" which sets the entry wall for any maze.

That's enough to get you started.

Answer 3

Non recursive way would solve the maze for you. With recursion (backtracking algo), you may ride your luck.

Refer to this document :- http://cs.stanford.edu/people/eroberts/courses/cs106b/chapters/07-backtracking-algorithms.pdf

If this question would be open till weekend. I would post a coded answer.

Thanks