路径查找javascript算法无法正常工作'他应该这样做
Pathfinding javascript algorithm not working as it's supposed to
我正在编写寻路算法,但有一件事我被卡住了。算法获取起始单元格并将其添加到队列中,将其标记为已访问,并在屏幕上打印单元格中的数字(数字显示当前单元格与起始单元格的距离)。然后,对于队列的第一个元素,它检查它的邻居。若邻居不是墙或还并没有被拜访,他会被添加到队列中。然后从队列中移除第一个元素,并重复整个函数,直到队列长度等于0。
我不能让一件事起作用,当用单元格填充队列并给出单元格的距离号时,结果应该是这样的:
S12
1#2
22E
其中#是一堵墙,S是起点,E是终点。然而,当算法运行时,它会产生以下结果:
S12
2#3
33E
似乎有些细胞的距离数增加了不止一次,这是不应该发生的。在代码中,我添加了额外的布尔标志,无论单元格距离数是否已经增加,以及只有在距离数尚未增加时才增加距离数的额外条件。请帮忙指出我犯的错误,我们将不胜感激。寻路功能:
function findPath(startCell, goalCell) {
var queue = [];
queue.push({
cell: startCell,
hasBeenIncremented: true,
hasBeenSearched: false,
searchDistance: undefined
});
queue[0].searchDistance = 0;
fillPath();
function fillPath() {
queue[0].cell.hasBeenSearched = true;
pointColor(queue[0].cell.x, queue[0].cell.y, 'darkred');
setInnerHTML(queue[0].cell.x, queue[0].cell.y, queue[0].searchDistance);
for (var i = -1; i <= 1; i++) {
if (queue[0].cell.x + i < 0 || queue[0].cell.x + i > boardHeight - 1) {
continue;
}
for (var j = -1; j <= 1; j++) {
if (queue[0].cell.y + j < 0 || queue[0].cell.y + j > boardWidth - 1) {
continue;
}
if (i == 0 && j == 0) {
continue;
}
if (getCell(queue[0].cell.x + i, queue[0].cell.y + j).hasWall == true || getCell(queue[0].cell.x + i, queue[0].cell.y + j).hasBeenSearched == true) {
continue;
}
if (queue[0].cell.x == goalCell.x && queue[0].cell.y == goalCell.y) {
pointColor(goalCell.x, goalCell.y, 'darkred');
setInnerHTML(goalCell.x, goalCell.y, '*');
return 'path completed';
}
queue.push({
cell: getCell(queue[0].cell.x + i, queue[0].cell.y + j),
hasBeenSearched: false,
searchDistance: undefined,
hasBeenIncremented: false
});
if(queue[queue.length - 1].hasBeenIncremented != true) {
queue[queue.length - 1].searchDistance = queue[0].searchDistance + 1;
queue[queue.length - 1].hasBeenIncremented = true;
}
}
}
queue.shift();
if (queue.length > 0) {
setTimeout(fillPath, 1000);
}
}
}
JS fiddle链接:https://jsfiddle.net/s8texvxa/2/(这不是一个完整的算法,只是它的第一部分)。
您在排队前执行检查,但它可能通过其他路径在队列中,但尚未检查,因此它仍然被视为未访问。
请注意,如果可以通过多条路径到达一个单元格,则必须确保使用最短的距离。
看起来你使用的是广度优先算法,所以在排队时将单元格标记为已访问就足够了,这样它就不会再次被添加。
相关文章:
- 页面在我的javascript执行后重新加载,我不希望它这样做
- 如何在将鼠标悬停在提交/锚点上时检查复选框是否已选中,并显示提示用户这样做的警报
- JavaScript 如果数组包含名称,则不要这样做
- 我用脚本创建了一个按钮.我可以通过点击按钮调用其他函数吗?我这样做,但失败了
- Jquery语法;也这样做”;
- 如果我不这样做会发生什么;t在javascript中的变量中分配新的Image
- 如果他们不这样做,就从我的数组中删除东西't没有前缀
- 如何使用“;这个“;在javascript中?这样做的目的是什么
- 如果我不这样做会发生什么;t有页码吗?继续循环帖子..为什么需要分页,对于页脚
- 禁用 ALT+F4,是的,我知道不建议这样做
- 使用默认值定义构造函数.我这样做对吗?
- 我刚刚开始使用 MEAN 堆栈.我试图将我的表单提交数据存储到 mongo 数据库,但我无法这样做
- 为什么不这样做
- Node.JS/Javascript - 将字符串转换为整数正在返回 NaN,而我不希望它这样做
- 在angularjs中拥有$sce或严格上下文转义有什么好处,为什么反应不需要这样做
- 如何分解此代码以减少重复(以及应该这样做)
- 嵌套的 if/else 语句讨论了分配变量.我已经这样做了,但它仍然不起作用
- blur() 无法以编程方式工作 |但在从用户启动时会这样做
- Webkit 似乎不支持层上的 $.focus(),而 IE9 支持.无论如何,让webkit浏览器也这样做
- 路径查找javascript算法无法正常工作'他应该这样做