15

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

我正在尝试在不使用 HTML 表格单元格的情况下在 JavaScript 中创建完全正常工作的迷宫生成器。现在我对这个迷宫的创建求解器有问题。

问题：我的代码需要使用哪种迷宫解决算法？我应该从什么开始？我不需要整个算法——我只需要关于是否有可能在这个迷宫生成器中有一个迷宫求解器的建议。

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

4

3 回答 3

6

我对适用于您正在生成的迷宫的求解器的建议是 Dijkstra 算法。虽然我不确定 horiz 和 verti 参数如何定义迷宫结构，但 Dijkstra 的算法可以通过从“1”旁边的单元格开始并从那里开始构建来适应您的情况。

它的操作方式是用每个单元格与起始单元格之间的单元格数量来标记每个单元格。对于 3x3 迷宫，第一个单元格将是：

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

从标记的单元格检查是否有一个空的相邻单元格（一个没有被墙挡住的单元格），将单元格值增加 1。对所有空单元格重复此过程：

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

现在从与结尾“2”相邻的单元格向后工作。这说明解的路径长度为 5 步，所以从 5 开始，找到相邻的 4，然后是 3，以此类推回到 1。

注意：我推荐使用队列来标记单元格的递归解决方案：

1- 用“1”标记第一个单元并将其放入队列中。

2- 从队列中取出单元： - 检查合法邻居（未被墙壁阻挡的邻居）是否未标记。- 如果相邻单元格未标记，则将其标记为当前单元格+1。- 将相邻单元格添加到队列中。- 对所有 4 个潜在邻居重复

3- 重复步骤 1 和 2，直到没有更多未标记的细胞。

编辑：这是使用我建议的求解器的小提琴，它与问题中的迷宫生成器无关，所以除非被问到，否则我不会详细介绍它是如何操作的（它有点粗糙，但它的实现应该很容易理解）。

于 2014-10-04T10:05:58.190 回答
0

如果它是一个完美的迷宫（任何两个单元之间只有一条路径），那么你只需要一个递归的墙跟随器。从第一个单元格开始，按给定顺序检查所有周围的单元格，通常是顺时针或逆时针。如果单元格可以输入，请输入它。如果它是结束，你就完成了。如果不是，递归。当您检查了所有其他 3 条路径并且没有一条是结束时，只需返回。当你到达终点时，你的调用堆栈就有了解决方案:) 我通常做的是为“我在这里没有找到解决方案”返回“false”，或者为“这是解决方案”返回“true”。

您可以在 github 上查看我的迷宫算法是如何解决的：

https://github.com/mdchaney/jsmaze

如果您查看 jsmaze2.html，函数“find_depth”实际上是一个求解器。

jsmaze4.html 要复杂得多，但它实际上是在使用递归算法构建迷宫的同时构建解决方案。它通过在构建过程中“进入”单元格时跟踪哪个墙被击倒来做到这一点。由于还有其他算法，我还包括了“find_depth”，它为任何迷宫设置了入口墙。

这足以让你开始。

于 2014-10-06T14:59:03.347 回答
0

非递归方式将为您解决迷宫。使用递归（回溯算法），您可能会碰运气。

请参阅本文档：- http://cs.stanford.edu/people/eroberts/courses/cs106b/chapters/07-backtracking-algorithms.pdf

如果这个问题会一直开放到周末。我会发布一个编码的答案。

谢谢

于 2014-10-06T17:06:41.083 回答