一个好的基于2D网格的路径规划算法是什么？

Question

一个好的基于2D网格的路径规划算法是什么？

15

我目前正在使用HTML5的<canvas>元素和Javascript编写一款2D游戏。它进展顺利，但我遇到了一个问题。

我的游戏级别设计是一个网格（所以从一个单元格到北/南/东/西单元格的路径成本为1），各种障碍占据着网格中的不同位置 - 很像迷宫，但有更多的波动余地。每个独立的关卡大约有400×200个单元格。

我正在尝试实现一个敌人，无论玩家身在何处，都会寻找到玩家，但我在尝试将各种寻路算法之一转换以适应我的情况时遇到了问题。我遇到的大部分算法（如A*和Dijkstra）似乎更适合3D或更复杂的2D情况。我想知道是否可能大大简化这些算法以更好地适应我的目的，或者如果考虑到关卡大小，深度优先搜索是否是更有效的替代方案。

- creXALBO

如果没有提前了解可能的路径（例如将地图分成具有已知连接性的段），则您不会比A*更好。深度优先比广度优先慢得多（多得多）。 - Dave

这并不是Stackoverflow / Stack Exchange的主旨; 提出一个明确答案的问题，而不是购物问题。当然，可以使用人们建议的内容，但是在遇到编程问题时请回来寻求帮助。 - Amelia

@Dave：嗯，当限制在一个网格内时，你可以很容易地找到比普通的A更好的解决方案；但是，JPS+A比单纯的A*更复杂，通常并不必要。 - BlueRaja - Danny Pflughoeft

3个回答

8

看看这个：https://github.com/qiao/PathFinding.js。它有很多演示和路径查找算法。

- Rezigned

3

EasyStar.js是一个看起来不错的库，似乎可以满足你的需求。虽然我自己没有使用过它，但这个项目在github页面上的文档看起来很好，并且在你的位置上，这可能是我会选择的。

- TwentyMiles

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Skrivener · Accepted Answer

A*是一个非常常见的二维路径规划算法。如果路径规划不熟悉，可能需要一些时间来理解发生了什么，但它并不是非常复杂。您可能只是在查看其他人开发的针对比您打算更复杂的应用程序的示例代码。这里有一个很好的教程，可以帮助您理解该算法。