COMPARISON OF SPATIAL DATA STRUCTURES IN OPENMP–PARALLELIZED STEERING

With the invent of multicore CPUs, parallelization be-comes an important issue in the programming of com-puter games. We consider steering, i.e., the coordina-tion of a large number of agents to simulate swarm-like behavior. Steering and in particular its neighbor-hood search component are compute-intensive and profit from parallelization. In this paper, we combine OpenMP threads with the use of spatial data structures, consider-ing three structures: k-d tree, grid, and cell array with binary search. In addition to parallelization, we tuned the performance by e.g. optimizing cache usage. The focus of the paper is an experimental comparison of the three structures, based on a parallel version of the Open-Steer library. In nearest-neighbor search and updates, we found none of the structures to be superior to the others, and provide a detailed account of their pros and cons. 1