xna - 如何优化 A* (AStar) Search for Concave Shapes？ (包括截图)

Question

我正在编写一个相当简单的自上而下的 2D 游戏。它对所有碰撞数据使用均匀间隔的 2D 瓷砖网格。网格中的每个图块要么是实心的，要么是空的。

对于路径查找，我使用 A*(A 星)，并尝试了曼哈顿和对角线(又名切比雪夫距离)启发式方法。

它在大多数情况下运行良好，但在尝试路径查找到位于凹形(例如 U 形)凹槽中的目标时会变得非常昂贵。

例如，在下图中，右边的人会通过路径找到左边的人。所有的草(绿色、深绿色和黄色)都是空的。唯一的实心砖是棕色的“木”砖和灰色的“石”砖，形成一个侧面的“U”形。



现在这里是路径搜索的结果(在这种情况下是带有曼哈顿启发式的 A*):



红色和绿色调试绘制方块显示在 A* 搜索期间访问了哪些图块。红色在“关闭”列表中，绿色在“打开”列表中(按照 A* 规范)。选择的最终路径中的蓝线(正确)。

如您所见，搜索相当详尽，访问了许多瓷砖，创建了一个几乎完美的圆圈。

我理解为什么会发生这种情况基于 A* 算法和我选择的启发式(当你沿着墙壁移动经过目标时，更远的瓷砖开始具有更好的 F 值，导致它们在回到正确的位置之前被探索小路)。我不知道如何使它变得更好:)

关于可能的改进的任何建议？可能是不同的启发式？也许是一种不同的路径搜索算法？

谢谢!

根据一些建议，我倾向于更新我的 A* 实现以包含在 HPA* 中发现的改进。 .根据一些初步阅读，它似乎可以很好地解决上面的情况，因为层次结构中有适当的粒度。一旦我完成调查，我会更新。

Answer 1

您需要break ties towards the endpoint .


(没有打破与端点的联系)


(打破对端点的联系)


(有障碍物的例子)