javascript - 什么是好的基于 2D 网格的寻路算法？

Question

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

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

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

Answer 1

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

Answer 2

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

Answer 3

EasyStar.js是一个看起来很漂亮的库，看起来可以做你想做的事。我自己没有用过，但是项目的github页面上的文档看起来还不错，大概是我在你的位置上会选择的。