Archived

This topic is now archived and is closed to further replies.

facefaceface

Mass Collision Detection

Recommended Posts

Here is something that i''ve been pondering for a wiggitty while now... in a game like StarCraft (yes i know it''s old) how do they do so much collition detection without killing the processor? I mean, in a game w/ 6 people, each guy can get around 200 units (not including buildings) for a total of 1200 units. as far as i can tell, if you use standard rectangle collision detection (min max blah blah blah) each object would have to check every other object. That''s over a million collision detections a frame. That can''t be possible. So instead i was thinking that they use a grid system... the playing field is divided into grid spaces. When an object moves it sets the grid spaces it moves into as ''occupied''. But before it actually moves, it checks the grid spaces that it is moving to, to see if they are already occupied. If so, it either doesn''t move, or moves around them. Does anyone know how they did this?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
they probably do break up the map into some form of zones, or rooms, or even a complete grid (if you look really carefully, you will notice that there is a grid system going on -- a marine, for example, can''t be made to stop at an arbitrary point).

You wouldn''t necessarily have to do this for only a million tests, however. If you had a *really* fast (let''s say optimized assembly code) to handle a possible collision, then a million objects might only take 6 million instructions. If you doing 20 frames a second on a 600 Mhz cpu, you can do 30 million instructions per frame, so after collision detection you could still do 24 million instructions. It isn''t like StarCraft has a huge AI overhead (at least, it doesn''t strike me that the AI is so incredible it couldn''t be easily implemented as a small lookup table of goals and behaivours to achieve those goals)...or even really Graphics overhead (bitmap animations aren''t exactly cpu intensive -- bandwidth intensive (between the video card and ram, if you have more textures than fit in video ram)). So perhaps dedicating such a large chunk of processer time would be acceptable.

And perhaps that is why there is, in fact, a 200 unit limit, and an 8 person limit. Although I doubt it. I seem to recall that was more of a game balance decision. You are probably completely correct that they simply have a grid which stores air occupied, air free, ground occupied, ground free. (air occupied doesn''t stop an air unit from entering, but would be useful for juding whether or not an attack could be hitting an air unit (like turrets or psi storms or what have you) and also, for implementing the ''spreading'' effect that happens to air units. (take a bunch of air units, order them all to the same place. leave them alone -- watch them spread out radially from the point they were all stacked on)).
If i was implementing it i''d also store the index of the unit that was occupying that place, or the index of the building occupying that space. Or a pointer to the object, whatever was easiest. (space vs time consideration -- storing a lookup to the unit would take more space, but would save time (don''t have to go searching for the unit)).

Share this post


Link to post
Share on other sites
The key to large scale simulation is trivial rejection. You want as many of your cases as possible to be unambiguous and have no need for actual processing. How? For one thing, don''t test collisions if their coordinates aren''t within a certain distance of each other. For another, it''s usually unlikely that a single soldier will stray terribly far from his regiment, so don''t test any members of regiments that are far from each other.

Most importantly, though, what the user can''t see doesn''t irritate him. Don''t do any collision detection for off-screen entities, except projectiles/weapons. (If two soldiers walk through each other offscreen no harm is done, but if your homing missile does no damage because the target was offscreen - well!)

Share this post


Link to post
Share on other sites
If you are working in 2d, you can also do a radix sort only one axis. Only items in the same bucket can be overlapping. For example, you could radix sort along the x axis tiles. Now for each non empty tile bucket, you need check each sprite only against the y axis of sprites in the same bucket (or you could do another radix sort on the y axis and buckets with more than one item idicate a collision). With some amount work in presorting and trivial rejection, you can greatly cut the number of comparisons necessary.

Share this post


Link to post
Share on other sites
Ok, everybody is making this a lot more complicated than it needs to be! You have a grid. Each tile contains pointers to the units standing on it. When you're walking from tile A to tile B, you only have to test for collisions in tile B. In short, collision detection has a near constant time; it only varies with the number of units on the destination tile (about 4 or 8 at max), and not the total number of units.

Edited by - TerranFury on December 10, 2001 5:23:24 PM

Share this post


Link to post
Share on other sites
quote:
Original post by TerranFury
you''re walking from tile A to tile B, you only have to test for collisions in tile B. In short, collision detection has a near constant time; it only varies with the number of units on the destination tile (about 4 or 8 at max), and not the total number of units.

Scale that by the total number of moving units and all their destination tiles.

[ GDNet Start Here | GDNet FAQ | MS RTFM | STL | Google ]
Thanks to Kylotan for the idea!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
MASSIVE harm is done if two marines walk through each other. Starcraft (and nearly all other RTS games) are peer to peer. SC is deterministic with only a small amount of controlled randomness in damage. When you play a game of SC with someone both computers do exactly the same thing. The only information that is shared are the commands that you give to your units. From the point of view of the physics and game rule stuff, your opponent is no different from an AI player. You are no different either. That is why it is impossible to make a hack to get more money, if you try to spend money that my copy doesn''t think you have then a desynch results ending the game. That also makes it easy to save replays. SC games an hour long with commands issued every second have replay files only a few hundred kb, and most of that is because it stores a copy of the map in the replay. So no, you have to have deterministic results that do not depend on the point of view, if you are making a game like SC.

Also marines can stand on arbitrary points, however it is very hard to give them commands to do so. If you tell a marine to move one pixel he won''t. I eventually learned to just let them do what they want, it is much easier that way.

To answer the original question, I don''t know how they do it. However I assume that they only check areas near the unit, not the entire map. Break your map into tiles. If tiles are bigger than the biggest unit then when you check for collision you only need to check against units in the square you are moving two and the eight surrounding it. If units can be twice as big as tiles you need to check a five by five grid centered on the tile you''re moving to. If 3 times, 7x7.

Share this post


Link to post
Share on other sites
While grids, x-axis/y-axis rejections are all great way to speed things up, the most important concept to remember is that only a very few units are moving given any one point in time! You don''t need to check stationary objects!

Next, you don''t need to do collision detection as often as you update frames. Many objects don''t move signifgantly per frame, so many objects are updated less then a few times per second.

Projectiles generally don''t do collision detection as they move, only to the the destination tile. Units associated with that tile recieve results.

"So little time, so much fun."
~Michael Sikora

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
well it really depends on your game, he was asking about SC which does not have tiles in its gameplay. Yes it has a tile based implementation but the gameplay does not involve tiles (building placement is the only exception), the basic unit of distance it the pixel. They probably do everything every frame, but SC has a slow framerate. At the normal game speed SC runs at only 15 FPS. At fastest is is a little over 20, which is still pretty low.

Share this post


Link to post
Share on other sites
Anon, even though the units can move pixel by pixel, how do you know there''s no underlying grid structure for collision? Unless you have some inside information there''s no way.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
oh I assume there is, but you can''t just check to see if things are in the same tile and leave it at that. You need to go a step further and check for a collision based on the size/shape of the unit. I think they use ellipses but I''m not sure. If you use StarDraft (a program that lets you do change so much) there are a couple parameters that get into size and stuff like that. I am sure about the peer to peer and deterministic thing though.

Share this post


Link to post
Share on other sites