Html 什么是好的基于 2D 网格的寻路算法？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/17128965/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What is a good 2D grid-based path-finding algorithm?
提问by creXALBO
I'm currently writing a 2D game in Javascript using the HTML5 <canvas> element. It's coming along very nicely, but i have run into a problem.
我目前正在使用 HTML5 <canvas> 元素在 Javascript 中编写 2D 游戏。进展非常顺利，但我遇到了一个问题。
The level design for my game is a grid (so path cost moving from one cell to the north/south/east/west cell is 1) with various obstacles occupying various locations in the grid – a lot like a maze, but with a lot more wiggle room. Each individual level is on the order of 400 × 200 cells.
我的游戏的关卡设计是一个网格（因此从一个单元格移动到北/南/东/西单元格的路径成本为 1），各种障碍物占据网格中的不同位置——很像迷宫，但有很多更多的回旋余地。每个单独的级别大约为 400 × 200 个单元格。
I'm trying to implement an enemy that will seek out the player no matter where they might be, but i'm having trouble trying to translate one of the various path-finding algorithms to fit my situation. Most of the ones i've come across (like A* and Dijkstra) seem to be best suited to 3D or much more complicated 2D situations. I was wondering if it is possible to dramatically simplify these algorithms to better suit my purposes, or if something like the depth-first search would be a more efficient alternative given the level size.
我正在尝试实现一个无论玩家身在何处都会寻找玩家的敌人，但是我在尝试翻译各种寻路算法中的一种以适应我的情况时遇到了麻烦。我遇到的大多数（如 A* 和 Dijkstra）似乎最适合 3D 或更复杂的 2D 情况。我想知道是否有可能显着简化这些算法以更好地满足我的目的，或者考虑到级别大小，像深度优先搜索这样的方法是否会是更有效的替代方法。
采纳答案by Skrivener
A* is a very common 2D pathfinding algorithm. It might take a little time to wrap your head around what's happening if pathfinding is unfamiliar, but it's not terribly complex. You may just be looking at someone else's example code that's been developed for a more complex application than you intend. There's a good tutorial for understanding the algorithm here.
A* 是一种非常常见的二维寻路算法。如果不熟悉寻路，可能需要一点时间来了解正在发生的事情，但这并不是非常复杂。您可能只是在查看其他人的示例代码，这些示例代码是为比您预期的更复杂的应用程序开发的。有一个很好的教程来理解这里的算法。
回答by Rezigned
Check this out https://github.com/qiao/PathFinding.jsIt has a lot of demos and path finding algothms.
看看这个https://github.com/qiao/PathFinding.js它有很多演示和路径查找算法。
回答by TwentyMiles
EasyStar.jsis a nice looking library that appears to do what you'd like to. I haven't used it myself, but the documentation on the project's github page looks pretty good, and it's probably what I would choose in your position.
EasyStar.js是一个看起来很漂亮的库，它似乎可以做你想做的事。我自己没用过，但是项目github页面上的文档看起来还不错，大概是我在你这个位置上会选择的。
