data-structures - 不规则网格的数据结构

Question

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

搜索了 KdTrees，但他们似乎找到了最近的对象，我还发现了分段树/间隔树，但关于它们的信息很少，干杯。

Answer 1

您可以使用八叉树。也就是说，您可以从包含整个区域 ((0, 0, 0), (x, y, z)) 的长方体开始（它是树的根）。下一步，将其拆分为8个长方体(((0, 0, 0), (x / 2, y / 2, z / 2)), ((0, 0, z / 2), (x / 2, y / 2, z)) 等等)。这 8 个长方体是根的子项。继续为它们中的每一个递归地构建树。当一个长方体完全在一个区域内时，递归应该停止（所以它变成了树的叶子）。

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

也可以采用kd树来解决这个问题。这个想法类似于上面描述的：将一个空间分成两个半空间，递归地为每个空间构建一棵树。递归的基本情况也是相同的：一旦当前子空间仅在一个区域内，递归应该停止。