我正在编写一个相当简单的自上而下的 2D 游戏。它对所有碰撞数据使用均匀分布的 2D 瓦片网格。网格中的每个图块要么是实心的，要么是空的。
对于寻路，我使用 A*（A 星），并尝试了曼哈顿和对角线（又名切比雪夫距离）启发式方法。
它在大多数情况下运行良好，但在尝试找到位于凹形（例如 U 形）凹槽中的目标时变得非常昂贵。
例如，在下图中，右边的人会找到左边的人。所有的草（绿色、深绿色和黄色）都是空的。唯一的实心瓷砖是棕色的“木”瓷砖和灰色的“石头”瓷砖，形成了一个侧面的“U”形。
现在这里是路径搜索的结果（在本例中为曼哈顿启发式的 A*）：
红色和绿色的调试绘制方块显示在 A* 搜索期间访问了哪些图块。红色在“关闭”列表中，绿色在“开放”列表中（根据 A* 规范）。选择的最终路径中的蓝线（正确）。
如您所见，搜索相当详尽，访问了许多图块，创建了一个几乎完美的圆圈。
我理解为什么会发生这种情况，基于 A* 算法和我选择的启发式方法（当你沿着墙壁移动经过目标时，更远的瓷砖开始具有更好的 F 值，导致它们在返回正确之前被探索小路）。我不知道如何使它变得更好:)
关于可能的改进有什么建议吗？可能是不同的启发式方法？也许一起使用不同的路径搜索算法？
谢谢！
根据一些建议，我倾向于更新我的 A* 实现以包含HPA*中的改进。根据一些初步阅读，它似乎可以很好地解决上述情况，只要层次结构中的粒度适当。一旦我完成调查，我会更新。
