计算机科学 ›› 2011, Vol. 38 ›› Issue (3): 257-262.
• 人工智能 • 上一篇 下一篇
徐建民,李欢,刘博宁
出版日期:
发布日期:
基金资助:
XU Jian-min,LI Huan,LIU Bo-ning
Online:
Published:
摘要: 处理场景中数量庞大的各种对象间的交互是游戏的一类主要计算工作。将kd-tree用于组织场景,提高了这类计算的效率。传统算法采用树的层次遍历方式进行查找,处理跨节点情况时性能下降明显。提出了邻域特性概念以扩展传统kd-tree结构,增添了树节点间的平面部接关系,且考虑了游戏对kd-tree的一些限定,设计了从起始节点向四周扩展的查找算法。经分析与实验证明,新算法比传统算法有约40%的性能提升且更稳定。
关键词: 邻域特性,kd-tree,查找,场景分割,游戏
Abstract: 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 situalion of node-crossings as traditional algorithm uses hierarchically recursive way to search. The concept of neighbor fealure 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.
Key words: Neighbor feature, kd-tree, Searching, Scene partitioning, Game
徐建民,李欢,刘博宁. 在游戏中利用邻域特性扩展的kd-tree及其查找算法[J]. 计算机科学, 2011, 38(3): 257-262. https://doi.org/
XU Jian-min,LI Huan,LIU Bo-ning. Neighbor Feature Extended kd-tree and Searching Algorithm for Game[J]. Computer Science, 2011, 38(3): 257-262. https://doi.org/
0 / / 推荐
导出引用管理器 EndNote|Reference Manager|ProCite|BibTeX|RefWorks
链接本文: https://www.jsjkx.com/CN/
https://www.jsjkx.com/CN/Y2011/V38/I3/257
Cited