寻找任意非矩形体

Question

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

因此，我将如何去设计或改造一个寻找任意网格和生成节点的寻路算法，这些算法可以通过多种方式自行环绕？

Answer 1

一个（可能是最简单的）选项是使用基于网格的搜索技术---有一些非常简单的方法来生成多分辨率网格分解，将单元格标记为“空闲”或“碰撞”并使用搜索结果网格像A *（如Theran提到）。

通常，您可能需要使用更强大的运动计划技术，例如probabilistic roadmaps（PRM）或Rapidly-exploring Random Trees（RRT）。在这些领域有相当多的学术工作。

作为介绍，您可能想查看一份调查报告，如this one（PDF）。

Answer 2

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

Answer 3

我意识到，你可能不会告诉我们这里的大图，并试图将你的问题归结为3D scene => directed graph => ??? => pathfind，但你有没有考虑从不同的方向接近这个？

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

无论如何，您可能会发现this link对您的研究有用。