game-physics - 当行进物体不是点时，有什么好的寻路方式？

Question

我正在开发一个游戏，其中有一个充满岛屿的海洋。我想要一艘船(它有一个大的矩形边界框)在这片海中航行而不撞到任何岛屿。在某些情况下，这些岛屿非常靠近地聚集在一起(并且有很多)。理想情况下，我希望最终得到一个航点列表，船可以遵循这些航点来避开岛屿。

在我发现的大多数寻路文献中，路径都被假定为一个点——在我的情况下情况并非如此(它是一个大矩形)。我可以将什么好的算法应用于这种情况？ A*搜索适用于这种情况吗？

Answer 1

您需要将“正常”拓扑路径查找与几何约束相结合。

这可以通过首先定义网络拓扑然后检查链路是否适用于船舶来完成。

作为第一次切割，假设您定义了一个分辨率合适的正方形网格，比如船的宽度。从岛上移除所有小于一半船宽的顶点。

在网格中的每个顶点和邻居之间创建一个链接，包括对角线。

(*) 为每个链接创建由船舶沿链接直线行驶时创建的矩形。移除任何与岛屿重叠的部分。

您现在只剩下一个“可导航”网络 - 不允许转弯半径等。

您可以使用网格分辨率或键入以获得更好的结果。

($) 此外，初始链接集可以包含非相邻顶点之间的链接，从而提供更平滑的路径。除非我们在初始集合中允许相当长的链接，否则这种方法仍然会给出相当不均匀的路径。

因此，采用生成的路径并尝试查看该路径中的哪些节点可以在不与岛碰撞的情况下被移除，如步骤 (*) 中所示。也许这意味着我们不需要为步骤 ($) 或任何对角线烦恼？