path-finding - 如何在寻路情况下处理不同大小的物体（A*、A-star）

Question

我正在开发一款使用 A-star (A*) 进行路径查找的游戏，但我已经到了这样一个地步，即我有一些大于单个网格正方形的对象。

我在 16*16px 的网格上运行。墙段为 16*16，因此使单个正方形无法通过。我的一些坏人是 32*32，所以他们需要检查一个间隙是否至少有 2 个方格宽，以便能够通过它。

我不能简单地将网格设置为 32*32，因为设计需要薄壁（16 像素），并且有几个较小的坏蛋只占用一个 16*16 的正方形。

如何实现这种多分辨率环境？A-star 仍然是正确的工具吗？

Answer 1

对于一个相对简单的解决方案，我会坚持使用与 16x16 大小的对象相同的 A* 算法，但评估正方形是否可步行的方式略有不同。

• 一个 16x16 大小的物体可以在一个正方形上行走，如果该正方形是可行走的。
• 一个 32x32 大小的物体可以在一个正方形上行走，如果该正方形和它的邻居都可以行走的话。