Boolean checks with a single quadtree, or multiple quadtrees?
- by Djentleman
I'm currently developing a 2D sidescrolling shooter game for PC (think metroidvania but with a lot more happening at once). Using XNA.
I'm utilising quadtrees for my spatial partitioning system.
All objects will be encompassed by standard bounding geometry (box or sphere) with possible pixel-perfect collision detection implemented after geometry collision (depends on how optimised I can get it).
These are my collision scenarios, with < representing object overlap (multiplayer co-op is the reason for the player<player scenario):
Collision scenarios (true = collision occurs):
Player <> Player = false
Enemy <> Enemy = false
Player <> Enemy = true
PlayerBullet <> Enemy = true
PlayerBullet <> Player = false
PlayerBullet <> EnemyBullet = true
PlayerBullet <> PlayerBullet = false
EnemyBullet <> Player = true
EnemyBullet <> Enemy = false
EnemyBullet <> EnemyBullet = false
Player <> Environment = true
Enemy <> Environment = true
PlayerBullet <> Environment = true
EnemyBullet <> Environment = true
Going off this information and the fact that were will likely be several hundred objects rendering on-screen at any given time, my question is as follows:
Which method is likely to be the most efficient/optimised and why:
Using a single quadtree with boolean checks for collision between
the different types of objects.
Using three quadtrees at once (player, enemy, environment), only testing the player and enemy trees against each other while testing both the player and enemy trees against the environment tree.
