如何做一个QuadTree上的导航

Question

我想在QuadTree上做导航/ A *。

我已经实现了QuadTree，或者至少我认为是QuadTree。同时我也看到了一些内部节点也包含元素的地方。通过我的内部节点只链接到他们的孩子，元素存储在叶节点的集合中。 虽然每个节点链接到它的父节点，但是（当前）没有到邻居的链接，也没有其他分支的兄弟节点或节点。元素是区域而不仅仅是点。

我也在网格上看过A *的相当一段时间，甚至在QuadTree上演示过一段时间，但没有详细说明。

我想主要的问题是如何快速找到我的邻居？

我不确定我是否应该保持叶片相互连接。但是当这些元素更新他们的位置时，这棵树会变成动态的，所以这将是一个糟糕的工作。它还需要根据节点大小需要一些动态收集链接的王，一个大叶子可以在一个方向上有很多小叶子（例如东）。更新这个的努力似乎相当巨大，即使目前不知道我会怎么做。

THXÑRGDS

Answer 1

A *是用于查找到一个结束节点从一个起始节点的最短路径的算法。这对于树木来说并没有什么意义，因为最短路径总是从开始到上升到最后。

如果由于某种原因，您无法在树内找到完成位置，则必须将该树视为正常图形并执行广度优先搜索（或者A *，如果您有一些种类的启发式）

我想主要的问题是我该如何快速找到我的邻居？

存储指向树中每个节点的父节点的指针。然后，可以通过查看其父母的所有子女来查看节点的兄弟姐妹。

Answer 2

这是可能的，但它肯定不是最佳的。 A *在图形数据结构上完成。 “图”意味着节点可以非常快速地访问 - 最好通过直接指针/引用。

通过四叉树获取邻居的正常方法是explained on wikipedia - 因此，如果子条目在查询范围内，则检查递归。这也是already implemented。

如果你另外需要A *，你可以绕过另一个方向：使用正常图形，对其执行A *并执行最近邻搜索​​。