1

我想在 QuadTree 上进行导航/A*。

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

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

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

我不确定我是否应该让叶子相互连接。但这将是一项艰巨的工作，因为随着元素更新它们的位置，树是动态的。它还需要一些用于链接的动态集合之王，因为根据节点大小，一个大叶子可以在一个方向（例如东）有很多小叶子。更新它的努力似乎相当巨大，即使目前不知道我会怎么做。

谢谢你

4

2 回答 2

0

A* 是一种用于查找从开始节点到结束节点的最短路径的算法。这在树中并没有多大意义，因为最短的路径总是从起点上升到最不常见的祖先，然后下降到终点。

如果由于某种原因您无法在树中找到终点，则必须将树视为普通图并进行广度优先搜索（或 A*，如果您有某种启发式）

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

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

于 2012-09-24T19:19:00.000 回答
0

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

维基百科上解释了通过四叉树获取邻居的正常方法- 因此，如果子条目在查询范围内，请递归检查。它也已经实施。

如果您还需要 A*，则可以反过来：使用普通图，在其上执行 A* 并直接在图上实现最近邻搜索。

于 2012-09-28T09:01:05.500 回答