什么是好的基于二维网格的寻路算法？

Question

我目前正在使用 HTML5 元素用 Javascript 编写 2D 游戏。它进展顺利，但我遇到了问题。

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

我正在尝试实现一个敌人，无论他们身在何处都会寻找玩家，但我在尝试转换各种寻路算法中的一种以适应我的情况时遇到了麻烦。我遇到的大多数（如 A* 和 Dijkstra）似乎最适合 3D 或更复杂的 2D 情况。我想知道是否有可能大大简化这些算法以更好地满足我的目的，或者考虑到级别大小，深度优先搜索之类的东西是否会是更有效的替代方案。

原文由 creXALBO 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

A* 是一种非常常见的二维寻路算法。如果您不熟悉寻路，您可能需要一些时间来了解正在发生的事情，但它并不是非常复杂。您可能只是在查看其他人的示例代码，这些示例代码是为比您预期的更复杂的应用程序开发的。这里有 一个很好的理解算法的教程。

原文由 Skrivener 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

检查一下 https://github.com/qiao/PathFinding.js 它有很多演示和路径查找算法。

原文由 Rezigned 发布，翻译遵循 CC BY-SA 3.0 许可协议