math - 在任意非矩形物体上寻路

Question

我有各种表面为 3D 且非矩形的对象，例如球体、金字塔以及由网格表示的各种其他对象。网格不是由相同大小和分布在对象表面上的多边形组成，它们也不是像圆柱体、球体和圆锥体的理想形状那样都是半/对称的对象。

因此，我将如何设计或改进一种寻路算法，该算法采用任意网格并生成可以以多种方式环绕自身的节点？

Answer 1

一个（可能是最简单的）选项是使用基于网格的搜索技术——有一些非常简单的方法可以生成多分辨率网格分解，将单元标记为“自由”或“碰撞”并使用类似 A* 的方法搜索生成的网格（正如Theran提到的）。

通常，您可能需要使用更强大的运动规划技术，例如概率路线图(PRM) 或快速探索随机树(RRT)。在这些领域有相当多的学术工作。

作为介绍，您可能想查看一份像这样的调查报告(PDF)。

Answer 2

A* 搜索在此应用程序中应该可以正常工作。它需要一个不会高估两点之间距离的函数，但直线距离永远不会高估沿曲面的距离。

Answer 3

我意识到您可能没有在这里告诉我们更大的图景，而是试图将您的问题归结为 3d 场景 => 有向图 => ??? => 寻路，但您是否考虑过从不同的方向来解决这个问题？

有没有办法预先组成你的有向图？大多数游戏（我假设这是一款游戏）在构建搜索路径时不会考虑场景中每个对象的完整几何形状。也许还有另一种方式？

无论如何，您可能会发现此链接对您的研究很有用。