特别声明:
建议使用google游览器,火狐也可以
论坛处于测试阶段,一切资料都为测试资料,在论坛正式运行的时候,会尽量保存网友的劳动成果!
HelloWorld论坛秉持互惠互利,共同学习与进步,一个人的梦想大家实现的理想,一直坚持着,望广大网友多多支持,提供宝贵意见
来论坛做什么?
可以先转载你平时学习查找的资料(先论坛查找),自己可以写写体会
把平时碰到的问题,如何解决可以先记录在论坛,以备后来的人学习
可以和会员一起参加一些开源项目的学习,汉化,推广,甚至可以加入团队
|
|
来源:http://blog.codingnow.com/2006/10/quadtree.html 这次又遇到这个问题,却不想用网格的方法来解决问题了。 原因主要是这么几点:一,用网格对于大场景特别消耗内存,而且不太适合做无限延展的场景。二,查询每个对象周围的东西时,不太方便。格子的粒度越小,速度越慢。 虽然这两个问题,都可以通过改进算法来回避。不过这次,我想尝试一下用四叉树解决这个问题。 用四叉树的话,内存占用量应该 O(n) 。如果定死了四叉树的扩展深度,可以推算出节点的最大可能消耗量。我想,如果只是为了解决 AOI 的计算,5 级深度已经足够。这样,大约预分配出 20 * n 个节点,几乎肯定够用了。 我希望场景是从坐标原点向四周无限延展开,没有什么具体的尺寸限制。所以,这次实现的时候对四叉树做了改造。第一级的划分是一个特例,它将平面分成四块,每一块都可以向某个方向无限延伸。 接下来,把各种可供切割的平面分为 9 类:
2 6 1 类型 6,7,8,9 的平面由于他们只向一个方向延伸,所以只能被切割成 2 块,一块固定大小的正方型(类型 5),一块保留它原来的类型。 这样,我的数据结构不是一个完整的四叉树,有个支干上就只有两个分支了。如果一个对象被放到了离坐标原点过远的地方,树的深度可能很大(超过 5),但是宽度会减半。如果大多数对象都在原点附近的话,查找是很快的。 今天化了一通宵的时间来实现这个东西,写了四百多行 C 程序。因为要实际用到项目中去,效率上的考虑比较多,顾而时间用了近 8 个小时;而且篇幅也比我想象的长的多。 一般,我们会在四叉树的每个节点上保存父节点的指针。这样,遍历这棵树就不需要用递归实现。好久没有写纯算法的程序了,平时递归写惯了,今天为了实现个用回溯法遍历树的算法还颇费了点工夫。为了提高查找一个节点附近节点的效率,最后也做了特别的实现。 另外,因为树节点总数可以估算出来,我用了个预分配的大节点池,并内部实现了 gc 算法。这样,从四叉树上拿掉节点非常简单,分配新节点也很容易。事后想了一下,不用 gc 的话,用一个 freelist 来管理也慢不到哪去。 在四叉树的叶子上,存放一个对象链表即可。可以用一个备用链表,分配,释放,移动位置都不需要重新构造。估算了一下,对象在四叉树描述的场景中移动,处理过程应该是常数时间了。查询 AOI 区域的对象也是一个常数时间。总的来说,对今天的工作成果还是挺满意的 :) 隔日补充: 其实,通过动态增加层次来向边界延展的算法实现起来更简单,也没有增加太多储存和查询的负担。昨天晚上把问题想复杂了。睡一觉起来后,把程序改了。 |
[挂载人]初学MPEG |
|
|
Please Login (or Sign Up) to leave a comment |