如何优化A*(AStar)搜索凹形？(包括截图)
Goo*_*ose 6 xna pathfinder a-star path-finding hierarchical-data
我正在写一个相当简单的自上而下的2D游戏.它为所有碰撞数据使用均匀间隔的2D网格图块.网格中的每个图块都是实心的或空的.
对于路径寻找我使用A*(A星),并尝试了曼哈顿和对角线(又名切比雪夫距离)启发式.
它在大多数情况下效果很好,但是当试图找到坐在凹形凹陷(例如U形)中的目标时变得相当昂贵.
例如,在下面的图片中,右侧的人将找到左边的人.所有的草(绿色,深绿色和黄色)都是空的空间.唯一的实心瓷砖是棕色的"木材"瓷砖和灰色的"石材"瓷砖,形状为侧面"U"形.
现在这里是路径搜索的结果(在这种情况下A*与Manhattan Heuristics):
红色和绿色调试绘制正方形显示在A*搜索期间访问了哪些图块.红色位于"已关闭"列表中,绿色位于"打开"列表中(根据A*规范).选择最终路径中的蓝线(这是正确的).
正如你所看到的,搜索已经相当详尽,访问了很多瓷砖,创造了一个几乎完美的圆圈.
我理解为什么会发生这种情况,基于A*算法,以及我选择的启发式方法(当你沿着墙壁移动目标时,更远的瓷砖开始有更好的F值,导致它们在回到正确之前被探索路径).我不知道的是如何让这更好:)
有关可能改进的建议吗？可能是一个不同的启发式？也许一条不同的路径搜索算法在一起？
谢谢!
根据一些建议,我倾向于更新我的A*实现,以包括HPA*中的改进.基于一些初步阅读,考虑到层次结构中的适当粒度,它似乎将很好地解决上述情况.一旦我完成了这个,我会更新.
您需要断开与端点的连接。
（不破坏与端点的联系）
（与终点断开连接）
（有障碍物的例子）
- （续）此外，如果您在多个单元上运行此算法，则在它们之间共享寻路信息通常可以大大加快速度。最后，如果这仍然太慢，您可能需要研究近似算法，例如 [HPA*](http://gamedev.stackexchange.com/questions/32813/32831#32831) 或 [A *-Epsilon](http://stackoverflow.com/questions/13075199)（又名。[Anytime A*](http://www.cs.cmu.edu/~maxim/files/ara_nips03.pdf)）。 (2认同)