Pretty basic question that I likely could of just googled but I thought I’d make a topic anyway. When dealing with collision, I’ve always checked if a collision box has collided with another by looping through every collision box in a scene and checking to see if there is a collision. Is there a more efficient way of doing this? Something that involves not having to search through every collision each frame, or is this the only possible way of dealing with this type of thing?
You use a structure like a quad tree or something similar so you only have to do collision checks on objects that are actually close enough together to collide
Or just grab a physics system that does that for you
Any recommendations for a physics system that does it for me?
Well I did port bullet a while ago, have a look at that
This is what I use https://archive.codeplex.com/?p=farseerphysics
It’s a port of Box2D so if you need better documentation look up the Box2D documentation and it’s usually fairly similar.
What you are doing is known as a brute force collision check it’s extremely costly.
I recommend you make a simple collision grid first with some points or rectangles that go in it. If you want to understand the basic principle.
Or at least watch this video.
This young man in the video below does a excellent job of describing the problem and it’s resolution with a simple spacial collision grid. While this isn’t the best done its still pretty good for a basic explanation.
My simple explanation would be as follows.
Divide space by a length for x and y so that you get integer index’s for a array that represents a volume of space (a array of bucket). Calculate what the array index is for each body by dividing its position in the same way by the same amount. Place a bodys id in the corresponding bucket. If more then one body is placed in a bucket do a direct check between them with there original current positions (brute force check between only those bodys). If there is only one object in a bucket or less no check needs to be done at all for that object it will not be checked at all.
Thus only objects that are in close proximity will check directly against each other using your current method this can be considered a big optimization. Which is also what a quad tree does reduces checks.
In effect the number of checks for a number of game objects where none of them were near each other would be zero.
The cost would then purely be the number of id’s added to the bucket array.
So typically you want the buckets to encompass a bigger volume of space then the size of the objects since adding id’s or ints to a int array has some cost too with lots of objects.
Though this can also be reduced with simple tricks like having static objects never doing insertions or deletions and other ways of reducing the removal or additions of id’s.
A quad tree is a different maybe harder but conceptually the idea’s are similar.
(getting out of computational and memory transfer work).
1 Like