I finally got it working.
The algorithm will keep dividing space into smaller and smaller parts until the parts are small enough or they don't contain any objects (=boxes).
But searching the octree sucks too many CPU cycles. Performance is much better with octree disabled.
There are usually 0-17 collision tests done with octree enabled, and without octree its 229 (the number of boxes).
"Dumb" collision testing outperforms octree even when there are 120000+ boxes! (and btw: building octree takes almost 2 minutes with that box count on my cpu)
Pseudocode for my octree search function:
struct Octree{ int is_leaf; union { struct { float centre[3]; float min[3]; float max[3]; Octree *sub_oc[2][2][2]; } branch; struct { int num_boxes; Box **boxes; } leaf; } data;};void search_octree_recursive( octree, player_aabb, callback ){ if octree.is_leaf: for each box in octree: if box.has_not_tested: callback( box ) box.has_not_tested = 0 return for each subcell: if player_aabb intersects subcell: search_octree_recursive( octree, player_aabb, callback )}void search_octree( player_aabb, callback ){ for each box: box.has_not_tested = 1 search_octree_recursive( octree_root )}
Testing if player's AABB intersects the subcells of octree is expensive. How can I get rid of those collision tests?
And BTW, the map is 100% static, and the only moving objects are players (and hitscan bullets). I'm not going to need any dynamic data structures.
