云风的 BLOG: 用四叉树管理散布在平面上的对象

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

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

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

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

用四叉树的话，内存占用量应该 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 区域的对象也是一个常数时间。总的来说，对今天的工作成果还是挺满意的 :)

隔日补充：

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

Comments

把问题想复杂了。

Posted by: asaja | (25) January 5, 2016 11:47 PM

将坐标为（X，Y）的对象保存到 [X%N，Y%N]格子的List中. 这个数据结构能方便的查到每个对象附近的东西。 --------- 请问一下这个的原理是什么？

Posted by: Zhong | (24) June 27, 2014 10:44 AM

用链表太慢了吧，为何不用stl里面的map或者set

Posted by: 人杰地灵 | (23) December 5, 2011 01:20 PM

我不太明白你想表达的意思。 “用网格对于大场景特别消耗内存，而且不太适合做无限延展的场景。” 的确使用穷举来遍历网格的顺序表是很慢，难道不可以查找当前观察原点，做偏移的方式。为什么整张地图就一定yao装进一张表呢? @_@

Posted by: 12345 | (22) March 27, 2010 01:40 PM

这个有具体代码么？

Posted by: ljw | (21) March 20, 2010 07:37 PM

网游中的对象体积相对于地图都比较小,R树有些大材小用了. 返到是朴素的打格子效率最高,空间占用可以做到O(N),其中N是世界内总的角色数. 单次查询视野可以做到O(M+N),其中N是世界内的平均角色密度,M是平均视野大小.

Posted by: Robird | (20) June 23, 2009 07:50 PM

最近在用四叉树的划分方法，对A*算法的节点数据结构的连通进行预处理

Posted by: 灏忛潰鑳″瓙 | (19) November 17, 2008 05:07 PM

想法特别好，有一个问题，如果周围所有的物体都是大小不一的小动物（假设为球形小颗粒好了），并且各自有独立活动（三维活动），该采用什么数据结构保存他们以方便最好的存储并且怎么保证他们不会重叠或者说你怎么检测他们有没有碰撞呢？

Posted by: yong | (18) June 12, 2007 11:55 PM

我觉得，如果不需要精确的定位的话，用自定义的数据结构几乎总是比4叉树好的。比如对于2D游戏，可以把每一块的大小分成屏幕的1/4，每一个玩家关心他自己周围的9块地形，可以肯定比屏幕范围稍大，虽然实际处理的范围并非正好以玩家为中心，但是这种误差无所谓的。并不需要精确的选出玩家附近方圆XXX米的东西。大块的网格用数组查找，里面具体的元素用链表就行。总查找次数几乎可以肯定要比四叉树少

Posted by: Atry | (17) May 5, 2007 11:52 PM

每个节点需要的内存是固定的，而且四叉树总的需求也可以估算，所以直接分配一个数组就够了。预分配只需要用 freelist, 把可用的空间串起来即可。

Posted by: Cloud | (16) April 18, 2007 01:01 PM

请教一下：我最近做一个非游戏图形项目用到四叉树，深度大概在10－12左右，发现时间浪费主要在内存的分配释放上(因为主要操作就是对象移动和旋转)。如果我预分配内存，用查找可用预分配内存替代分配内存，但是发现查找过程同样费时。不知道楼主说的“预分配的大节点池”是怎么实现的。我需要把对象的一次移动时间降到毫秒级以下，一个对象约几十到几百个叶节点不等。现在做到的是在深度为7的时候在毫秒级，深度为8就过了毫秒级了。

Posted by: alansh | (15) April 18, 2007 11:27 AM

用四叉树基本是用于2D游戏吧? 3D游戏中的包围体层次结构也是用数实现的.不过通常使用8叉树,因为3D中有8个卦限,基本用于物体剔除和碰撞检测,效果非常好.当然还可以用来做可见性测试.编写的时候都是递归的方式做的.

Posted by: dReAmsUn | (14) December 7, 2006 07:28 PM

风云还是把东西发出来吧, 大家都很喜欢看的 :D

Posted by: mike | (13) November 7, 2006 03:17 PM

我们不准备做那么大的场景，所以就没采用这篇 blog 采取的方案。把这个发表出来的理由只是，或许有人以后会这么做，留下来万一可以给人点启发就挺好。 btw, 我最近还写了一些东西，觉得既没有现在的实用价值，以后也不会有什么用，就不发出来了 :D

Posted by: Cloud | (12) November 5, 2006 08:50 PM

刚看了回复，原来你们现在也是用这种方法，那当我没说:D 很难想象，大到夸张的场景到底有多大。按照64m×64m的范围来维护，像wow那么大的地图也不会超过100km^2，也不过24K个区域啊。难道网易准备做个长征online?

Posted by: N/A | (11) November 5, 2006 03:21 PM

如果仅仅是为了知道周围的对象，只需要划分大的区域即可，一般在几十米的线度上。而不需要做精细的划分，更不需要去遍历网格来获取其上的对象。这种情况下，内存耗费是非常少的，搜索速度也非常快。而如果是需要记录地表的信息，我也曾经考虑过采用类似的方法。但是地表每个单元的信息才那么几个字节，而串连这些单元的指针也要4个字节、甚至8个字节，实在是太不合算了。而且这样还降低了移动时候障碍判断的速度，障碍判断的频度应该在万级到十万级，虽然不是很高，还是觉得得不偿失

Posted by: N/A | (10) November 5, 2006 03:13 PM

R 树了解有限，不过感觉上查询空间上的临近节点，和频繁改变空间结构时，R 树的实现还是缺乏效率。我们需要保证的不仅仅是静态的查询效率，还有动态变更的效率。我看中四叉树的一点是，算法足够简单。

Posted by: Cloud | (9) November 2, 2006 08:37 PM

我觉得你说的问题可以不用四叉树做空间索引，而改用R树，这也是被广泛采用的空间索引方式

Posted by: Ricepig | (8) November 2, 2006 08:25 PM

我觉得如果你是出于场景管理考虑，还不如是传统自顶往下分的四叉树好，就是整个场景是根节点，4个指针分别指向四个象限。每个节点存储本身的范围、本节点的对象、父指针。通过坐标对半查找很容易定义到某节点，然后向上找多少层然后再全范围搜索都很容易实现。这样的好处是坐标可以无限细分，不过游戏里面，网格其实很好用。网格的管理你可以参考一下地理里面关于地形图号（例如1：500地形图）的命名模式，也许会有启发。

Posted by: Aug | (7) November 2, 2006 11:57 AM

这个方法和场景的大小关系不大,和场景中的对象数量关系更大. 云风真是难得,总是把知识和大家共享.

Posted by: mike | (6) November 1, 2006 06:26 PM

to mike, 我们现在的实现就是这样的 :) 如果场景不是大到很夸张的地步，这样是比四叉树好的。 to 牛牛, 的确算起来很复杂，我花了几个小时才写好这段程序。

Posted by: Cloud | (5) October 31, 2006 10:40 PM

试试对网格方法扩展一下。用N*N的格子保存对象。每个格子有一个List. 将坐标为（X，Y）的对象保存到 [X%N，Y%N]格子的List中. 这个数据结构能方便的查到每个对象附近的东西。

Posted by: mike | (4) October 31, 2006 08:24 PM

这样利用四叉树，真是有创意。原来我只在地形程序里面用过传统的四叉树。发现做游戏的确需要非常精巧的底层数据结构。今天又学到东西了。感谢云风的分享！

Posted by: slashspirit | (3) October 31, 2006 06:11 PM

如果不全是类型 5 的方块,实现"可视检测"(判断地图上的两点之间是否畅通无阻)将变的非常复杂吧?

Posted by: 牛牛 | (2) October 30, 2006 05:42 PM

从你的文章中,让我感觉到写游戏是一件富有创意的事.我也非常喜欢跟算法相关的设计.