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

Preindicate

can you make this into a JS fiddle so we can see what's going on here? – Diathermy

done, jsbin.com/uwoyon/1 – Rabbinical

js fiddle refers to the site jsfiddle :-P – Hyder

sorry, but i don't know why it doesn't work on jsfiddle, but on jsbin yes – Rabbinical

You're looking for a path finding algorithm. The wiki I linked might help get you started. Looks fun! Good luck! – Mohammedmohammedan

@jmbertucci: Clicking through a few times takes you to this which may be a bit more relevant. – Diathermy

Your solution seems like a degree-k recursive iterative process, like photo processing algorithms, what you really need is a graph search, an A* with ideally h=numberOfStepsTaken(state)+distanceFromSource(state)+distanceToGoal(state) .. good luck – Lunge

I would go for the wall follower algorithm (en.wikipedia.org/wiki/Maze_solving_algorithm) – Kerbela

For language reference, "datas" isn't a word. "data" is the plural form of "datum". – Slapstick

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

Glyceric

Fantastic answer. The bounty was for an implementation but I've gotten pretty far using this advice so if no one else chimes in before expiration I'll award the bounty to you. Thanks a ton. – Boeke

@Boeke I couldn't quite get my head around the elaborate manner in which the horzi and verti parameters define the maze structure, otherwise I would have provided an implementation. If interested I still can, though the maze structure will be defined in a 2D array. – Glyceric

I would honestly take any javascript maze solving example. Doesn't have to be particular to this maze generator (of which I don't particularly like - much prefer canvas). Either my google-fu is terrible or there are not may complete examples out there. – Boeke

@Boeke Simple solver added, let me know if you need anything explained. – Glyceric

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.

Erratic

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

Dillondillow