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

• 作者: 刘博宁 徐建民 李欢
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 邻域特性 kd-tree 查找 场景分割 游戏
• 年，卷（期）: 2011,（3）
• 所属期刊栏目: 人工智能
• 页码范围: 257-262
• 分类号: TP391
• 字数: 5243字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2011.03.058

摘要

处理场景中数量庞大的各种对象间的交互是游戏的一类主要计算工作.将κd-tree用于组织场景,提高了这类计算的效率.传统算法采用树的层次遍历方式进行查找,处理跨节点情况时性能下降明显.提出了邻域特性概念以扩展传统κd-tree结构,增添了树节点间的平面邻接关系,且考虑了游戏对κd-tree的一些限定,设计了从起始节点向四周扩展的查找算法.经分析与实验证明,新算法比传统算法有约40%的性能提升且更稳定.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐建民	河北大学数学与计算机科学学院	65	462	12.0	18.0
2	刘博宁	河北大学工商学院	5	6	2.0	2.0
3	李欢	河北大学数学与计算机科学学院	11	13	2.0	3.0