服务器3D场景建模（七）：四叉树的邻居关系

本文主要是介绍服务器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)的时间复杂度，完成需要处理的节点定位。

图3，A上的红色区域的AOI：

只要遍历A节点及其所有邻居节点，按红色区域是否与节点区域有相交或包含作为条件，遍历之；A的每个邻居节点递归重复操作。

以上操作与Tile上的AOI操作是同时间复杂度的。且比经典四叉树实现高效。

图4，若N节点已经知道自己的邻居关系：

图5，那么N节点分裂时，只要维护下孩子节点与邻居节点的关系即可：

以上。

前提假设：游戏对象间有碰撞

算法	占用内存	Add	Leave	Move	AOI	说明
Tile算法	$O(W*H)$	$O(1)$	$O(1)$	$O(T)$	$O(T)$	2维数组。第1维表达所有Tile；第2维表达每个Tile上的游戏对象列表
QuadTree算法	$O(N)$	$O(logN)$	$O(1)$	通常 $O(L)$ ；跨边界 $O(logN)+O(L)$	$O(logN) + O(L)$	四叉树。叶子节点上有游戏对象列表；叶子节点游戏对象超过指定数量限制，则分裂子节点叶子节点有游戏对象Leave，可能触发4兄弟节点合并节点边界上的游戏对象放在父节点上 AOI从Root节点开始做广度遍历
QuadTree带邻居关系	$O(N)$	$O(logN)$	$O(1)$	$O(L)$	$O(L)$	四叉树并带有邻居关系。叶子节点上有游戏对象列表，邻居列表；叶子节点游戏对象超过指定数量限制，则分裂子节点叶子节点有游戏对象Leave，可能触发4兄弟节点合并 AOI从始发叶子节点开始，遍历邻居节点