在游戏中利用邻域特性扩展的kd-tree及其查找算法  

Neighbor Feature Extended kd-tree and Searching Algorithm for Game

作　　者：徐建民[1] 李欢[1] 刘博宁[2] 

机构地区：[1]河北大学数学与计算机科学学院,保定071002 [2]河北大学工商学院,保定071002

出　　处：《计算机科学》2011年第3期257-262,共6页Computer Science

基　　金：中国博士后科学基金(20070420700)资助

摘　　要：处理场景中数量庞大的各种对象间的交互是游戏的一类主要计算工作。将kd-tree用于组织场景,提高了这类计算的效率。传统算法采用树的层次遍历方式进行查找,处理跨节点情况时性能下降明显。提出了邻域特性概念以扩展传统kd-tree结构,增添了树节点间的平面邻接关系,且考虑了游戏对kd-tree的一些限定,设计了从起始节点向四周扩展的查找算法。经分析与实验证明,新算法比传统算法有约40%的性能提升且更稳定。Processing the interactions among large numbers of objects is the main computation task in game system.Using kd-tree to organize the game scene improves such computation.There＇s a obvious performance degradation in situa-tion of node-crossings as traditional algorithm uses hierarchically recursive way to search.The concept of neighbor feature was proposed to extend traditional kd-tree structure,so the planar adjacent relationship of hierarchical nodes was added.A new algorithm searching the tree in a 4-sides expanding way from the standing node as the center was devised.The analysis and simulation showed that the new algorithm improves the performance by about 40% and is more stable than the traditional one.

关 键 词：邻域特性 KD-TREE 查找 场景分割 游戏 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]