我有一个在3D环境中手动创建的导航图。 我理解（并且之前已经实现过）一个A*寻路算法，可以在“进入导航图”后，找到通过图的路径。

我现在感兴趣的是，找到进入和“离开”图的最佳方式。

例如：
流程大致如下：
从起点向终点发射一条射线，如果没有障碍物，就直接走过去。

如果存在障碍物，我们就需要使用导航图。为了“进入导航图”，我们需要找到图上离起点最近的可视节点。（为了做到这一点，我之前是根据节点与起点的距离对导航图进行排序，然后从最近的节点开始，依次发射射线，直到找到一个没有障碍物的节点。）

然后运行标准的A*算法…

然后通过与进入导航图相同的方法“退出”导航图（用于计算上述A*算法的终点），所以我从终点向最近的导航图节点发射射线。

因此，当一切结束后，除非我的导航图非常密集，否则我花费在进入/退出导航图上的时间，比计算路径的时间还要多…

肯定有更好/更快的方法吧？（是否有某种空间划分技巧？）

回答：

你可以构建一个包含所有节点的 四叉树，以快速找到给定位置最近的节点。