任意非矩形体上的寻路
我有各种表面为 3D 且非矩形的对象，例如球体、金字塔和由网格表示的各种其他对象。 网格不是由物体表面大小和分布相同的多边形组成，也不是像圆柱体、球体和圆锥体的理想形状那样都是半/对称的物体。
因此，我将如何设计或改造一个寻路算法，该算法采用任意网格并生成可以以多种方式缠绕自身的节点？
I have various objects whose surfaces are 3D and non rectangular, such as spheres, pyramids, and various other objects represented by meshes. The mesh is not composed of polygons of equal size and distribution across the surface of the object, nor are they all semi/symmetrical objects like the ideal shapes of cylinders, spheres and cones.
Thus how would I go about engineering or retrofitting a pathfinding algorithm that took arbitrary meshes and generated nodes which could wrap around on themselves in any number of ways?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
一种（可能是最简单的）选择是使用基于网格的搜索技术——有一些非常简单的方法来生成多分辨率网格分解，将单元格标记为“自由”或“碰撞”，并使用 A* 之类的东西搜索结果网格（正如 Theran 提到的）。
一般来说，您可能需要使用更强大的运动规划技术，例如概率路线图 (PRM) 或快速探索随机树 (RRT)。 这些领域有相当多的学术工作。
作为介绍，您可能需要查看一份调查论文，例如此< /a> (PDF)。
One (likely the simplest) option is to use a grid based search technique---there are some pretty simple ways to generate multiresolution grid decompositions, label cells as "free" or "collision" and search the resulting grid using something like A* (as Theran mentions).
In general, you may need to use more powerful motion planning techniques, such as probabilistic roadmaps (PRMs) or Rapidly-exploring Random Trees (RRTs). There is quite a lot of academic work in these areas.
As an introduction, you may want to check out a survey paper like this one (PDF).
A* 搜索在此应用程序中应该可以正常工作。 它需要一个不会高估两点之间距离的函数，但直线距离永远不会高估沿表面的距离。
A* search should work just fine in this application. It requires a function which does not overestimate the distance between two points, but the straight-line distance will never be an overestimate of the distance along your surfaces.
我意识到您可能没有在这里告诉我们更大的图景，而是试图将您的问题归结为 3D 场景 => 有向图 => ??? => 探路，但你有没有考虑过从不同的方向来解决这个问题？
没有办法预先构建有向图吗？ 大多数游戏（我假设这是一个游戏）在构建搜索路径时不会考虑场景中每个对象的完整几何形状。 也许还有另一种方法？
无论如何，您可能会发现此链接对您的研究有用。
I realize that you're probably not telling us the bigger picture here and are trying to boil your problem down to 3d scene => directed graph => ??? => pathfind, but have you considered approaching this from a different direction?
Is there no way to pre-compose your directed graph? Most games (I assume this is for a game) don't take the full geometry of every object in a scene into account when they build their search paths. Maybe there's another way?
Anyway, you might find this link useful for your research.