Hi all,
I’m fairly new so I hope this isn’t a repost, however i came across this extremely useful article while I was trying out some different collision detection methods: https://0fps.net/2015/01/23/collision-detection-part-3-benchmarks/
It’s an author that benchmarks different types of collision detection against each other. I hope it helps someone out in the future, because I was very close to implementing a quadtree until I came across this info 
Optimal collision detection (as noted in link) is going to be a function of the distribution of objects and how it evolves over time combined with chosen method and how it’s actually implemented. So a quad-tree can be the best choice…but it actually very quite hard to implement a good quad-tree (or forest of them more likely). And in the case where it would be “best” something much simpler to correctly implement is likely to be approaching the same performance.
I don’t see a case where the quadtree can be good, especially with the difficulty of it’s implementation versus much more simple and efficient algorithms. Going through the uniform figures for quadtree, it seems that anything past 1000 entities quickly starts to show the flaws of quadtree overhead and efficiency. For non-uniform data we can still see clear winners that far surpass quadtree efficiency.
That’s why I liked the SAT algorithm for collision detection…
@VoidBuffer - It all depends on how you can move less data (and not cache-thrash) and keep the local neighborhood ‘n’ small.
@bmanmcfly - different topic…this is broad-phase. SAT’s only claim to fame is it’s easy to implement (that’s not a bad thing).
And here is Java’s Achilles heel… many structures designed to work with known memory contiguity of C fall over in Javaland, leading to nightmarishly complex implementations in Java using bodges like struct libraries etc. etc.
Cas
Yeap…
/muses how forthcoming value types implementation in Java might solve this…
Cas
Obviously it depends wildly on what you’re designing, but do you all have a general go to collision optimization strategy? Looking into the topic a little more, it seems that a static grid-like algorithm should be enough without too much overhead. Store static non-moving entities and only update the moving entities capable of dynamic collision.
Yeah, it depends too much on data. For wide-open areas then a uniform grid is a nice easy choice and will perform reasonably. Couple that with sweep-and-prune for the broad pass.
Grids and pooled lists for me. Most my my entities are roughly uniform in size, and the median number of entities in a grid cell is 1 when there are any entities at all. With a grid I’m computing collisions between about 5-6000 entities in next to no time at all.
Cas
Can confirm, uniform grids are awesome for collision detection!
My bad… easy to implement??? god damn, it took me about 3 weeks trying to write my own before I figured out how to use libgdx intersector class…
For broad phase, I just made large collision boxes and if a box is both within the screen box and is in collision with another collision box then check with SAT. Probably not ideal by any stretch, but THAT was easy to wrap my head around and easy to implement.
Does that sound like sweep and prune?
+1 for Grid.
However i implemented it as a array with linear probing when i have 2 things in the same place. It works super fast even for area quires.
For more advanced cases and scales i have used Vantage Point Trees. These however tend to come into there own with much more than 3 dimensions. ie k nearest quires for things like case based reasoning.
In the past i have tried kd trees, quad tree etc. I end up with similar performance access the the board.
BSP isnt bad if you want to have some sick FPS maps :). The BSP tree is very good for other things as well like rendering, lightmapping, and pathfinding
What are some efficient ways of storing entities within grids for broad-phase collision? I’m working on implementing grids for broad phase collision detection and I’m dealing with a large variety of entities that will have different reactions depending on what they collide with.
My current structure is a GridMap which holds Grids. The grids hold their own dimensions as well as Arrays of all the different types of entities that they could ‘potentially’ hold. This seems pretty inefficient though which is why I’m asking.
Option 1 - Have Grids store many Arrays of different sub-classed entities. Check collisions between these entities if they’re in the same grid. This may obviously lead to lots of empty and unused Arrays which seems wasteful.
Option 2 - Have one generic Entity array in each grid, and iterator over it in a n^2 fashion checking for collision against different types of entities.
Option 3 - insert here :point:
Empty cells in an array are cheap in terms of space. So i wouldn’t worry about it. However depending on size i suspect both will mostly work most of the time.
There is always some extreme case that can break it. But will this case even be possible in your game?
I guess we’ll find out! I’m looking to support ‘hopefully’ ~1000 players on my network however the AI bodies will be in magnitudes. I realize I won’t have to worry about the AI that players can’t see, but I’m just trying to get it semi-right the first time around.
Right now I’m clearing my old GridMap, then creating a new GridMap every frame. After running a profiler, everything seems fine and dandy. Just being wary