Have you ever played Starcraft, or games like it? Notice when you tell a group of air units to attack a target, they bunch up and move towards it, but once they're in range, they spread out around the target. They don't all just bunch up together, occupying the same spot, even though the game allows them to pass through each other.

How would you approach this problem?

I went with a "occupation grid": It's just a low-resolution 2D boolean array (640x480). Each ship (my game only has ships) has one, and updates it every frame. When attacking, they refer to the grid to figure out where they should move to. It works pretty good: The ships are nice and spread out, and don't just all occupy the same space, looking like they merged into one ship.

The problem is is that this way is pretty inefficient. Just updating every ship's grid sometimes takes 24-31% of the CPU time. Using Bresenham line-drawing algorithm for every ship is the culprit.

I'm thinking of having one shared grid for all the ships on a team, and instead of using a simple boolean 2D array, allow each square of the grid to keep track of every ship that is using it, by using a data structure with a linked list of references to the ships using that square. That way, I wouldn't have to update a grid for each and every ship.

Maybe the solution would be to use a much simpler grid, minus the bresenham line drawing, just: a bunch of squares, try to stay in your grid square. Maybe allow larger ships to occupy more than one square.

Another solution might be evading me completely, one that doesn't involve grids at all. Any thoughts?

44 minutes ago, EGDEric said:

Another solution might be evading me completely, one that doesn't involve grids at all. Any thoughts?

Boids uses a simple and elegant solution. A range check to see if they are near each other, then move away.

So I would give the Units a "Take Position" phase after they reach a destination. At the start of the phase I would check collisions with objects in a X range. Then I would move away from all the objects collided with.

Then I would have some kind of timer, that if no new collisions where found in the time, it would end the "Take Position" phase to free the resources.

So, a flocking algorithm? I suppose I could make it so that they pick a direction to move away from their friend, one that's perpendicular to the vector from them to their target. I like the idea of stopping once collisions are done with.

Hello,

I have played all of Stracraft and I'm a fan LOL ... you will notice that if you group them together in the air they squeeze on the spot you want them to be... but "OVERTIME" they will move independently to not collide on each other and spread out... this true most on the air units but not on ground units.

"Another solution might be evading me completely, one that doesn't involve grids at all. Any thoughts?"

Exactly I will not use the girds at all, for all the Air units, I'll us the world space position grid and some collision response "OVERTIME", a unit sphere bounding collision response will be suffice I think until they spread out and not colliding to other ships.

I also read somewhere they do some hack to ship their product by removing the collision on SCV, Probe and Drone when they are mining : - D

Cheers ^_^Y