本文主要是介绍服务器3D场景建模（七）：四叉树的邻居关系，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
实测，经典四叉树效率比本中所述效率高！因此本文请无视之
四叉树的邻居节点？
常见的AOI使用Tile为基础，来实现。
每个Tile周围有8个邻居。因此在游戏对象移动或AOI时，可以O(1)的时间复杂度，定位8个邻居Tile。
而经典的四叉树代码实现，是没有邻居节点概念的。
图1，A节点的邻居节点：
A节点有B、C、D、E、F、G邻居节点。
经典的四叉树代码实现，是需要从根节点开始遍历，才能够访问到邻居节点E、F、G。
图2，某AOI操作：
红色区域的AOI，经典四叉树实现上，从根节点宽度优先遍历，按红色区域是否与节点区域有相交或包含作为条件，遍历之。时间复杂度为O(logN)。
如果A节点知道自己的邻居节点，那么可以O(1)的时间复杂度，完成需要处理的节点定位。
有邻居关系的四叉树的AOI操作
图3，A上的红色区域的AOI：
只要遍历A节点及其所有邻居节点，按红色区域是否与节点区域有相交或包含作为条件，遍历之；A的每个邻居节点递归重复操作。
以上操作与Tile上的AOI操作是同时间复杂度的。且比经典四叉树实现高效。
如何创建四叉树的邻居关系
图4，若N节点已经知道自己的邻居关系：
图5，那么N节点分裂时，只要维护下孩子节点与邻居节点的关系即可：
- L为N节点的邻居节点列表
- 遍历L，删除邻居节点对N的邻居信息
- N节点变成非叶节点，不再需要邻居信息，删除这些信息之
- N节点分裂为A、B、C、D4个孩子节点
- 对每个孩子节点，遍历L，根据节点区域是否相邻，构建孩子节点与L列表中节点的邻居信息
以上。
3种AOI对比
前提假设：游戏对象间有碰撞
| 算法 | 占用内存 | Add | Leave | Move | AOI | 说明 |
|---|---|---|---|---|---|---|
| Tile算法 | O(W∗H) O ( W ∗ H ) | O(1) O ( 1 ) | O(1) O ( 1 ) | O(T) O ( T ) | O(T) O ( T ) | 2维数组。 第1维表达所有Tile； 第2维表达每个Tile上的游戏对象列表 |
| QuadTree算法 | O(N) O ( N ) | O(logN) O ( l o g N ) | O(1) O ( 1 ) | 通常 O(L) O ( L ) ； 跨边界 O(logN)+O(L) O ( l o g N ) + O ( L ) | O(logN)+O(L) O ( l o g N ) + O ( L ) | 四叉树。 叶子节点上有游戏对象列表； 叶子节点游戏对象超过指定数量限制，则分裂子节点 叶子节点有游戏对象Leave，可能触发4兄弟节点合并 节点边界上的游戏对象放在父节点上 AOI从Root节点开始做广度遍历 |
| QuadTree带邻居关系 | O(N) O ( N ) | O(logN) O ( l o g N ) | O(1) O ( 1 ) | O(L) O ( L ) | O(L) O ( L ) | 四叉树并带有邻居关系。 叶子节点上有游戏对象列表，邻居列表； 叶子节点游戏对象超过指定数量限制，则分裂子节点 叶子节点有游戏对象Leave，可能触发4兄弟节点合并 AOI从始发叶子节点开始，遍历邻居节点 |
上图，
- N为游戏对象数量。
- W为地图宽
- H为地图长
- T为Tile上能容纳的游戏对象数量
- L为叶子节点区域能容纳的游戏对象数量
可以看出，理论上，地图越大，QuadTree优势越明显。
对于QuadTree带邻居关系，还忽略了一个重要问题，就是 非平衡数的邻居数量问题
非平衡数的邻居数量问题
比如下图中，在极端情况，F节点及其子节点持续分裂，一直分裂到4单位长宽大小的区域，才停止分裂（不好画自己想象）
则E节点会有很多邻居。
如果是1024*1024的地图，则E节点会有128个邻居；如果是8192*8192的地图，则E节点会有1024个邻居。
因此，算法中，要对这种情况做特殊处理。
比如，如果E节点邻居数超过8个，则这里的AOI处理，使用经典四叉树算法。
这篇关于服务器3D场景建模（七）：四叉树的邻居关系的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
