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)).

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!)

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.

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

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!

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.

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

actully projectiles do need to collide unless they get shot over all other places and then land at the target tile.

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.