I need some broad phase algorithm for my 2d game (shmup, bullet hell). Does one or another solution have any major advantages?
-
\$\begingroup\$ I think you should start with just using uniform grid spatial partitioning if the amount of vertices in your game is in the order of hundreds simulated per frame. If this is too slow after profiling, then tryout quad tree. Don't optimize prematurely... \$\endgroup\$– XiaoChuan YuDec 10, 2012 at 0:33
1 Answer
The two algorithms you have named are designed for arbitrarily large 3d worlds. While they can be adapted to a 2d shooter, there are simpler methods for the simpler environment.
For a 2d shooter I would use some variation of the blockmap concept used in DOOM - a grid of lists of objects that intersect each cell in the grid. Update the grid on each frame, and you only need to to collision detection on each set of objects in each cell.