请问现在有什么数据结构用来管理动态场景会比较合适啊

sjinny

《游戏编程精粹》里提到的两个技术，一个是逐维分组，一个是球形树；后者我一直弄不懂，前者虽然管理大量运动的物体很好，但是做碰撞检测时却不是很合适……
我想了几天，觉得凡是基于“静态空间分割”思想的方法（比如八叉树）都有一个问题，就是一个运动的物体，在运动的过程中会不断的从一个空间区域运动到另一个空间区域，这样物体一多效率就很低，而且当物体同时存在于两个空间区域时（或者说是物体正好在空间区域的边界上时）管理起来很麻烦。所以我就猜想，如果能有一种基于“动态空间分割”思想的数据结构就好了，但是却一直没有头绪……
另外，目前的方法似乎大多都是树形结构，这对于管理大量运动的物体也是不利的，因为当物体从一个空间区域运动到一个相邻区域时，可能要从树的最深层搜索到根节点，然后在深入搜索下去，这样运行效率就很成问题。

sjinny

我顶～～ [em6]

lingjingqiu

逐维分组是用来做碰撞侦测用的，不是拿来管理用。八叉树效率没有你想象的那么低，而且，从最低层搜索到根节点的情况也很少发生。不过你可以看看GPG2的一篇关于定深的4叉树位置快速查询的文章，或许会对你有帮助。

sjinny

lingjingqiu，你说的是不是那个直接计算出目标节点的地址的那个？那个好像是要用数组实现，觉得不爽啊……而且仍然有个问题，就是运动的物体经常会跨越边界而同时出现在两个空间区域里，这种情况处理起来很麻烦，不知道又什么办法避免这种情况的发生，或者减少这种情况的发生……