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('');
}
我正在尝试在JavaScript中创建完全可用的迷宫生成器，而不使用HTML表单元格。现在，这个迷宫的创建求解器出现了问题。
问题:我的代码需要使用哪种迷宫求解算法？我应该从什么开始呢？我不需要整个算法-我只需要有关此迷宫生成器中是否可以有迷宫求解器的建议。
JSbin-http://jsbin.com/uwoyon/1
最佳答案
我对应该对正在生成的迷宫起作用的求解器的建议是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，直到不再有未标记的单元格为止。
编辑:这是使用我建议的求解器的fiddle，它与问题中的迷宫生成器无关，因此，除非询问，否则我不会详细介绍其运行方式(虽然有点粗略，但实现应该足够容易遵循)。
关于javascript - JavaScript迷宫求解器算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16173259/