%0 Journal Article
%T Neighbor Feature Extended κd-tree and Searching Algorithm for Game<br>在游戏中利用邻域特性扩展的kd-tree及其查找算法
%A XU Jian-min
%A LI Huan
%A LIU Bo-ning
%A <br>徐建民
%A 李欢
%A 刘博宁
%J 计算机科学
%D 2011
%I 
%X 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.
%K Neighbor feature
%K kd-tree
%K Searching
%K Scene partitioning
%K Game<br>邻域特性，kd-tree，查找，场景分割，游戏
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=8E2688795432BFBDDAA16D09248547C0&yid=9377ED8094509821&vid=16D8618C6164A3ED&iid=38B194292C032A66&sid=4290346F7268639E&eid=30897FA31CA3354D&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=9