来源：http://blog.codingnow.com/2006/10/quadtree.html
周末一直在考虑怎样在游戏服务器中保存和管理那些有平面坐标的对象。希望能方便的查到每个对象附近的东西。以往用过的方法是给（平面）场景打上格子，然后再把每个对象放入相应的格子中。

这次又遇到这个问题，却不想用网格的方法来解决问题了。

原因主要是这么几点：一，用网格对于大场景特别消耗内存，而且不太适合做无限延展的场景。二，查询每个对象周围的东西时，不太方便。格子的粒度越小，速度越慢。

虽然这两个问题，都可以通过改进算法来回避。不过这次，我想尝试一下用四叉树解决这个问题。

用四叉树的话，内存占用量应该 O(n) 。如果定死了四叉树的扩展深度，可以推算出节点的最大可能消耗量。我想，如果只是为了解决 AOI 的计算，5 级深度已经足够。这样，大约预分配出 20 * n 个节点，几乎肯定够用了。

我希望场景是从坐标原点向四周无限延展开，没有什么具体的尺寸限制。所以，这次实现的时候对四叉树做了改造。第一级的划分是一个特例，它将平面分成四块，每一块都可以向某个方向无限延伸。

接下来，把各种可供切割的平面分为 9 类：

2 6 1
7 5 9
3 8 4
我给这些类别编了号，5 号类型的平面有固定大小，可以被明确切割成四块，这四块依然是类型 5 。而类型 1 的块，被切割成四块后，四块的类型(按四个象限分布)分别是 1,6,5,9 。同理，类型 2,3,4 的平面，也会被切割成不同类型的四块。

类型 6,7,8,9 的平面由于他们只向一个方向延伸，所以只能被切割成 2 块，一块固定大小的正方型（类型 5），一块保留它原来的类型。

这样，我的数据结构不是一个完整的四叉树，有个支干上就只有两个分支了。如果一个对象被放到了离坐标原点过远的地方，树的深度可能很大（超过 5），但是宽度会减半。如果大多数对象都在原点附近的话，查找是很快的。

今天化了一通宵的时间来实现这个东西，写了四百多行 C 程序。因为要实际用到项目中去，效率上的考虑比较多，顾而时间用了近 8 个小时；而且篇幅也比我想象的长的多。

一般，我们会在四叉树的每个节点上保存父节点的指针。这样，遍历这棵树就不需要用递归实现。好久没有写纯算法的程序了，平时递归写惯了，今天为了实现个用回溯法遍历树的算法还颇费了点工夫。为了提高查找一个节点附近节点的效率，最后也做了特别的实现。

另外，因为树节点总数可以估算出来，我用了个预分配的大节点池，并内部实现了 gc 算法。这样，从四叉树上拿掉节点非常简单，分配新节点也很容易。事后想了一下，不用 gc 的话，用一个 freelist 来管理也慢不到哪去。

在四叉树的叶子上，存放一个对象链表即可。可以用一个备用链表，分配，释放，移动位置都不需要重新构造。估算了一下，对象在四叉树描述的场景中移动，处理过程应该是常数时间了。查询 AOI 区域的对象也是一个常数时间。总的来说，对今天的工作成果还是挺满意的 :)

隔日补充：

其实，通过动态增加层次来向边界延展的算法实现起来更简单，也没有增加太多储存和查询的负担。昨天晚上把问题想复杂了。睡一觉起来后，把程序改了。