递归函数(迷宫求解器)-找不到bug;((( [英] Recursive function (maze solver) - can't find a bug;(((
问题描述
我正在学习javascript，除了诸如递归函数之类的东西外，其他一切对我来说都很容易.我确实了解它们的工作方式，但是在处理示例时，我意识到我无法捕获导致其无法正常运行的错误...
I am studying javascript and all is pretty easy to me except for some things like recursive functions. I do understand the way they work but while working with an example, I realized I can't capture the bug that prevents it from functioning...
我在下面有一个数组(映射)(0是一个封闭的单元格，1表示路径是打开的)，而我尝试使用的递归函数通过从其左上方"转到迷宫"中查找路径单元格到右下角.基本上，只需使函数查找"此1s路径即可.但是失败了；(
I have an array (map) below (0 is a closed cell, 1 means path is open) and the recursive function I am trying to use to "find" path out of this "maze" by going from its top left cell to the bottom-right one.. Basically just make the function to "find" this path of 1s. But it fails;(
var map = [
[1,1,0,0],
[0,1,1,0],
[0,0,1,0],
[0,0,1,1]
]
function findpath(x,y) {
if (x<0 || x>3 || y<0 || y>3) return false; //if it is outside of map
if (x==3 && y==3) return true; // if it is the goal (exit point)
if (map[y][x]==0) return false; //it is not open
map[y][x]=9; //here marking x,y position as part of solution path outlined by "9"
if (findpath(x,y-1) == true) return true;
if (findpath(x+1,y) == true) return true;
if (findpath(x,y+1) == true) return true;
if (findpath(x-1,y) == true) return true;
map[y][x]=8; //unmark x,y as part of solution path outlined by "8"
return false;
};
findpath(0,0);
推荐答案
快速解答:
由于检查的顺序而将其锁定在循环中.
Its locking in a loop because the order of the checks.
从0:0开始，然后尝试0:1.然后从0:1开始-嗯... 0:0看起来很有希望.让我们去那里."所以回到0:0 ...所以它锁定了... 尝试最后离开回溯:
Start from 0:0 then try 0:1. Then from 0:1 --"Ummm... 0:0 looks promising. Let's go there". So go back to 0:0... so it locks... Try leaving backtracking last :
if(findpath(x+1,y)) return true;
if(findpath(x,y+1)) return true;
if(findpath(x,y-1)) return true;
if(findpath(x-1,y)) return true;
这可以使您摆脱困境，只需交换问题即可.如果您从3:3开始尝试达到0:0，您将再次被锁定. 遗漏了一种标记访问过的正方形的方法.
This get you out of the lock just by swapping the issue around. If you start from 3:3 trying to reach 0:0 you'll be locked again. Whats missing its a way to mark visited squares.
我认为您正在尝试实施 a *算法
I think you are trying to implement an a* algorithm
更新:
您的想法在这里起作用.刚刚添加了您几乎实施的回溯检查.
Here is your idea working. Just added the backtracking checks you almost implemented.
<html>
<head>
</head>
<body>
<script>
var map = [
[1,1,0,0],
[0,1,1,0],
[1,1,1,0],
[1,0,1,1]
]
var goalx = 0;
var goaly = 3;
console.log();
function findpath(x,y) {
// illegal move check
if (x < 0 || x > (map[0].length -1) || y < 0 || y > (map.length - 1)) return false; //if it is outside of map
if (map[y][x]==0) return false; //it is not open
// end move check
if (x== goalx && y== goaly){
console.log('Reached goal at: ' + x + ':' + y);
return true; // if it is the goal (exit point)
}
if(map[y][x] == 9 || map[y][x] == 8)
return false;
console.log('Im here at: ' + x + ':' + y);
map[y][x]=9; //here marking x,y position as part of solution path outlined by "9"
if(findpath(x+1,y))
return true;
if(findpath(x,y+1))
return true;
if(findpath(x,y-1))
return true;
if(findpath(x-1,y))
return true;
map[y][x]=8; //unmark x,y as part of solution path outlined by "8"
return false;
};
findpath(3, 3);
</script>
</body>
</html>
这篇关于递归函数(迷宫求解器)-找不到bug;(((的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
