不规则网格的数据结构

Question

我想知道什么是包含不同大小的矩形/正方形作为游戏地图部门的网格的最佳数据结构。我需要通过简单的xyz坐标来访问该网格中的对象。

搜索KdTrees，但他们似乎找到最近的对象，我也发现部分树木/间隔树木，有关于他们 干杯一点信息。

Answer 1

您可以使用八叉树。也就是说，您可以从包含整个区域（（0,0,0），（x，y，z））（它是树的根）的矩形平行六面体开始。 （（0,0,0），（x/2，y/2，z/2）），（（0,0，z/2），（x/2，y/2，z））等）。这8个直角平行六面体是根的孩子。继续为它们中的每一个递归地构建树。当一个矩形平行六面体完全位于一个区域内时，递归应该停止（因此它变成树的一片叶子）。

要回答查询，请从八叉树的根开始，然后转到合适的孩子，直到到达树叶。

也可以修改k-d树来解决这个问题。这个想法与上面描述的相似：将空间分成两个半空间，为它们中的每一个递归地构建一棵树。递归的基本情况也是一样的：一旦当前子空间仅在一个区域内，递归就应该停止。