游戏开发者联盟

kd tree和quadtree

kd tree

在计算机科学里,k-d树( k-维树的缩写)是在k维欧几里德空间组织点的数据结构。k-d树可以使用在多种应用场合,如多维键值搜索(例:范围搜寻及最邻近搜索)。k-d树是空间二分树(Binary space partitioning)的一种特殊情况。

quadtree

四叉树是一种树状数据结构,在每一个节点上会有四个子区块。四叉树常应用于二维空间数据的分析与分类。 它将数据区分成为四个象限。数据范围可以是方形或矩形或其他任意形状。这种数据结构是由 拉斐尔·芬科尔(Raphael Finkel) 与 J. L. Bentley 在1974年发展出来 。 类似的数据分割方法也称为 Q-tree。 所有的四叉树法有共同之特点:

可分解成为各自的区块
每个区块都有节点容量。当节点达到最大容量时,节点分裂
树状数据结构依造四叉树法加以区分

游戏里的应用

在游戏中,一般用他们做空间划分,方便做空间相关查询,比如查找最近的物体。

  1. kd tree的特点,它是二叉树, 在插入节点时,很可能要做比较多的结点移动,所以,在动态方面不够灵活。查询效率在部分情况下也不是很理想,但是一般来说比直接遍历查询要快的多。
  2. 四叉树,整体式上来说更加灵活,插入元素引发的修改只发生在局部。依赖于切分阀值,阀值较低,那么切分很细,会占用较多额外空间;反之,一个叶子节点内会有较多元素,查询需要遍历很多元素。