0

我有一个八叉树，我想用它在 3D 空间中执行寻路。我正在使用 Morton 代码对节点进行排序，以便能够轻松找到任何给定节点附近的节点。它似乎工作得很好；我抓取的任何节点子集都相对靠近地聚集在一起。我正在努力寻找一种有效的方法来获取节点的直接邻居。

树的早期版本让它细分树，直到叶子都是我想要的大小的相同大小的节点。这使得查找邻居变得容易，因为每个节点之间存在一致的偏移量，因此我可以在我希望找到节点的位置重新计算 Morton 代码，然后根据代码检索节点。但是我试图通过在没有那么多几何图形的区域（例如，我会得到 8 个空孩子的地方）不那么分解它来提高树的效率。结果，我不再知道给定节点可能有多少邻居，也不知道任何邻居的大小（除了它是 2 的幂）。

我最初的想法是在阵列中的任一方向搜索附近的节点，这会起作用，但是我必须撒网太宽才能保证得到所有邻居，而且我会花时间评估大量节点我不需要的。快速测试表明，即使阵列中任一方向的 50 个节点也不能保证获得所有邻居。

树是静态的，所以我也许可以使用上述蛮力方法一次性生成节点的邻居并存储邻居；但我担心这可能会使程序的初始加载时间超出可接受的水平。有没有一种算法可以实时找到邻居？

编辑：改写问题以澄清我在寻找什么以及我尝试过什么。

4

1 回答 1

0

是的。

不要蛮力，直接去你想要的瓷砖。

前提是您有：

  • Tile toMorton(Point3D location)在给定其真实位置的情况下提供 Tile的函数
  • Point3D fromMorton(Tile t)提供 Tile 真实世界坐标的函数（我相信两者都可以从维基百科获得）

这些都是简单的实时操作。

天真的方法

只需转换为真实世界，在那里偏移，然后回到莫顿空间：

Tile originalTile = ...
Point3D originalLocation = fromMorton(original);
Point3D offsetLocation = new Point3D(offsetLocation.x + 1, offsetLocation.y, offsetLocation.y);
Tile offsetTile = toMorton(offsetLocation)

这只需要一些算术运算，因此应该已经适用于实时（比暴力破解更适用）。

优化方法

在 Google 上快速搜索“morton 代码社区”后，我找到了来自volumeseoffun的一篇写得很好的博客文章。

我将在这里提供最好的部分：

对于具有莫顿位置 p 的给定 (x,y,z)；如果我们想要查看 (x+1,y,z)，那么 p 必须增加的量 Δp 仅取决于 x，并且与 y 和 z 无关。同样的逻辑也适用于查看 y 和 z。

这意味着我们不需要toMorton/fromMorton所有三个坐标

此外（尽管博客及其来源都没有支持它）似乎可以通过查找表预先计算所述偏移量。这为您正在寻找的实时功能提供了额外的加速。鉴于 Morton 算法定义明确且可重复，对我来说这是有道理的，所以我相信这个假设。

只需预先计算偏移表，然后从一个起始图块开始，使用该表将您的图块偏移到它的真实邻居：

int[] offsetX = [ ... compute once ... ]
int[] offsetY = [ ... compute once ... ]
int[] offsetZ = [ ... compute once ... ]
Tile[] allTiles = ... // Init 3D world
public Tile neighbour(Tile original, Direction dir){
     switch(dir){
     case DIR_X_PLUS: return allTiles[original.chunkID + offsetX[original.chunkID];
     case DIR_X_MINUS: return allTiles[original.chunkID - offsetX[original.chunkID];
     case DIR_Y_PLUS: return allTiles[original.chunkID + offsetY[original.chunkID];
     [... etc...]
     default: return original;
     }
}

希望这可以帮助。

于 2016-11-07T10:16:38.370 回答