Question

我拥有各种表面为三维非矩形的物体，如球体、金字塔和其他由网格表示的物体。网格不是由等大小和分布的多边形组成的，也不都是半对称的物体，如理想形状的圆柱、球体和圆锥体。

那么我该如何设计或改进路径规划算法，使其能够处理任意网格，并生成能以任意方式互相包裹的节点呢？

Answer 1

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

通常情况下，您可能需要使用更强大的运动规划技术，例如随机路标（PRM）或快速探索随机树（RRT）。这些领域有相当多的学术研究。

作为介绍，您可能会想查看像这篇文章（PDF）这样的调查报告。

Answer 2

A*搜索在这个应用程序中应该可以很好地工作。它需要一个不会高估两个点之间距离的函数，但是直线距离永远不会高估您表面上的距离。

Answer 3

我意识到你可能没有向我们展示更大的图片，并且试图将你的问题简化为3D场景=>有向图=>???=>路径寻找，但你有没有考虑从不同的方向来解决这个问题？我认识到你可能不会在此告诉我们更大的方案，并且试图将你的问题简化为3D场景=>有向图=>???=>路径查找，但你是否考虑从不同的角度来接近这个问题？

有没有办法预先组合你的有向图？大多数游戏（我假设这是针对游戏的）在构建搜索路径时并不考虑场景中每个物体的完整几何形状。也许还有其他方法？

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