什么是一个好的2D网格路径寻找算法？ [英] What is a good 2D grid-based path-finding algorithm?
问题描述
我目前正在使用HTML5< canvas>>编写Javascript游戏，元件。这是非常好的，但我遇到了问题。
我的游戏关卡设计是一个网格（所以路径成本从一个单元格移动到北/南/东/西单元格为1），各种障碍物占据网格中的各个位置;很像迷宫，但有更多的摆动空间。每个级别大约为400次; 200细胞。
我试图实现一个敌人，无论他们在哪里都可以找到玩家，但是我在尝试翻译其中一个各种路径寻找算法，以适应我的情况。我遇到的大多数（如A *和Dijkstra）似乎最适合3D或更复杂的2D情况。我想知道是否有可能大大简化这些算法以更好地适合我的目的，或者如果像深度优先搜索这样的东西在给定关卡尺寸的情况下是更有效的替代方案。
A *是一种非常常见的2D寻路算法。如果寻路不熟悉，可能需要一点时间来围绕正在发生的事情，但这并不是非常复杂。您可能只是在查看别人的代码，这些代码是针对比您想要的更复杂的应用程序而开发的。有一个很好的教程，用于理解这里的算法。
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.
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.
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* 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.
这篇关于什么是一个好的2D网格路径寻找算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
