Computer Science ›› 2011, Vol. 38 ›› Issue (3): 257-262.
Previous Articles Next Articles
XU Jian-min,LI Huan,LIU Bo-ning
Online:
Published:
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
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.
0 / / Recommend
Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks
URL: https://www.jsjkx.com/EN/
https://www.jsjkx.com/EN/Y2011/V38/I3/257
Cited