进入/退出NavGraph寻径

Question

我有一个在3D环境中手动创建的NavGraph。我理解(并且之前已经实现了)一个A*例程，一旦你“上了图”，它就会找到我在图中的方法。

我感兴趣的是，获得和“离开”Graph的最佳方式。

例程是这样的:从源点到目标点发射一条射线，如果没有什么阻碍，就走过去。

如果有什么阻碍，我们需要使用图形，所以要进入图形，我们需要在图形上找到最近的可见节点。(为了做到这一点，我之前根据距离源的距离对图形进行了排序，然后从近距离向最远发射光线，直到我找到一个没有障碍物的光线。)

然后运行标准的A*...

然后“退出”图形，方法与我们在图形上得到的方法相同(用于计算上述A*的端点)，因此我从端点到最近的导航图节点发射射线。

所以，到了这个时候，除非我的导航图非常密集，否则我花在上/下图上的时间比我计算路径的时间还要多。

必须有更好/更快的方法吗？(是否存在某种空间细分技巧？)

Answer 1

您可以构建所有节点的Quadtree，以便从给定位置快速找到最近的节点。

Answer 2

对世界进行空间细分是很常见的。像四叉树或八叉树这样的东西在3D世界中很常见，尽管你也可以覆盖网格，或者跟踪任意区域，等等。基本上这是一个简单的数据结构问题，让你自己访问N个导航图节点，而不需要O(N)搜索来查找你所在的位置，你的选择往往归结为某种树或某种哈希表。