处理场景中数量庞大的各种对象间的交互是游戏的一类主要计算工作.将κd-tree用于组织场景,提高了这类计算的效率.传统算法采用树的层次遍历方式进行查找,处理跨节点情况时性能下降明显.提出了邻域特性概念以扩展传统κd-tree结构,增添了树节点间的平面邻接关系,且考虑了游戏对κd-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 perforrnanee degradation in situation 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.
展开▼
