- Home /
the most efficient way to detect colision between objects in a large scene (Strategy Game)
What's the most efficient way to detect collision between objects. What kind of strategy used to detect the collision between objects in a very large scene like strategy games. I know that I can't use Rigid body for each objects in the scene as physics are quite expensive and not suitable for mobile devices. I saw some tower defense games with more than 50 moving characters in the scenes and also loads of tower shooting them in a very good framerate on iPhone 3G...
How about AI Character avoiding each others? What's gonna be the most efficient way to make sure that the objects are not colliding each other? Does Physics.RayCast() is efficient or distance checking method? Does the steering behaviors used lots of calculations?
Can your characters move in UP/RIGHT/LEFT/DOWN or 360 degrees? If the first is true I would think you could build something with raycasts since it's just a few of them anyway and not a huge distance.
Answer by Anton Petrov · Dec 07, 2010 at 04:26 PM
IMHO, you should approximate all your objects with bounding circles on a 2D plane (ground). I think this is what every one do in their RTS games (like StarCraft :) ) where there are a lot of small units.
Collision tests between 2D circles are very fast. It looks like this (pseudocode!!!):
bool collided = ( Distance( circle1.position, circle2.position ) <=
(circle1.radius + circle2.radius) );
NOTE: Finding distance usually requires Sqrt() which is slow. So it is a good idea to compare squared distance and squared sum of radiuses.
Then you will need some optimizations because you won't like to do tests for each pair of your 50 moving units every frame (I guess it is something like 2,450 tests). The purpose of optimization is to find pairs which most likely collide or to reject those which definitely won't collide.
If you have some sort of space partitioning structures like Quad tree in your game, then it can be handy.
Very simple approach (I invented it just now :) ) is the following:
Let's assume that RMax is a maximal radius of the bounding circle of your in-game unit. Then you can represent your level as a grid of square cells with a cell size of RMax. When your units move you easily define in which cells their centers lie. And knowing that you can test only those pairs of objects which lie in adjacent squares. That's it!
Thanks.... this is what require to know.. I am really keen of making Strategy for mobile devices now... especially for iPad...