Broadphase Algorithms
Author
I'm looking for a broadphase algorithm with a fast insertation/removal time, that performs well otherwise (fast queries/raycasts, low pair counts, high cache coherency). I'm using box2d, which has a great implementation of SAP, but the insertation and removal speeds are killing my game. Is it possible to do better? Which broadphase algorithms should I look into? Just looking for some advice to get me started.
Here are some options I've considered:
* quadtree
* loose quadtree
* dynamic AABB trees
* dynamic sphere trees
* simple grids
* hashed grids
* hierarchical hashed grids
in a 2D game, if memory is not an issue, I'd go with a simple grid. Then you can do fast insertion / removal, and fast ray-casting (for AI and such).
I'd also consider a sphere tree, but implementing one would require quite a bit of work (comparatively).
I'd also consider a sphere tree, but implementing one would require quite a bit of work (comparatively).
Author
Thanks. I'll look into both of those. What are the benefits of sphere trees over AABB trees though?
I assume you are talking about the Sphere tree from the GPG 2 (or is it GPG 3). Can't remember exactly why they used a sphere, I think it was to do with fitting the smallest sphere around a collection of spheres, with an AABB, you would have no alternative but take the obvious best-fitting box. But I don't know if that would actually make it less efficient, or in fact better.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
