利用领域特性扩展的kd-tree及其查找算法

计算场景中数量庞大的各种对象间的距离以判断交互与否是游戏系统中兴趣管理功能的一类主要计算工作。kd-tree作为一种最近邻查找工具已被应用于游戏空间的分割,在一定程度上保证了兴趣管理的效率。但目前对kd-tree的应用仅利用了各个子空间被一分为二的特点,查找时需从起始叶节点先向上遍历找到一个包含兴趣域的非叶节点,然后再向下遍历树结构以找到与兴趣域相交的所有叶节点,在处理兴趣域跨越多棵子树深层叶节点的情况时,由于查找路径很长,性能下降明显。 注意到相交于兴趣域的叶节点均与起始叶节点在空间上相邻,存在建立更短连接路径的可能,以及游戏中分割得到的最小子空间大于兴趣域的特点,提出了邻域特性概念。邻域特性体现了节点在空间上的各种邻接特征,利用这些特征可使查找过程根据兴趣域与起始叶节点的位置以更短的路径抵达周边子空间,减缓由于单纯靠层次遍历造成的查找路径过长的问题。利用邻域特性扩展了传统的kd-tree结构,利用分割维度体现邻域特性,在节点间层次关系基础上补充空间邻接关系,设计了新的从起始叶节点向四周扩展的查找算法。经过对传统算法和新算法在原理和关键计算步骤上的分析,并通过仿真实验证明,新的算法比传统算法有约40%的性能提升且更稳定。