Currently, I'm simulating physics impact forces for local avoidance of units but this method sometimes pushes units out of formation and has very undesirable effects when units clump up.

For RTS games like Starcraft 2, how is local avoidance done? Are physics simulated or an omnicient controller decides where everything should be? I know this question might be a little broad so I'm asking specifically for how to achieve the local avoidance behaviors of Starcraft 2; though anything that works will be very appreciated.

I'm not looking for any code - just useful resources or explanations of how Starcraft 2 (or similar games) handles local avoidance.

Currently, I have collision detection (with penetration vector), collision forces, and movement by velocity implemented. Every unit is checked against another for a collision - if they collide, the objects are immediately offset by the penetration vector then the collision force is applied. Then another loop moves the objects by their velocities and applies drag to the velocities. The offset mitigates the problem of excessive collision forces applied on clumped units, but units still sometimes shoot out.

The solution I'm looking for needs to satisfy the following requirements (as in Starcraft 2):

  • Objects musn't overlap; or at least overlaps must be eventually resolved.
  • Objects don't push each other away more than necessary so 2 units can stand and move next to each other in a formation.
  • There should not be any weird behaviors when objects clump towards the same destination.
  • Can support units of different sizes, and even different convex shapes.

What I've been thinking of so far is instead of detecting for collisions, detect for future collisions so the overlap never happens. Then apply the constraint, making sure the 2 units' velocities don't cause them to overlap. I'm still tinkering with the algorithm for restricting movement beyond the overlap.

  • \$\begingroup\$ "flocking behavior" (google term) is a very wide problem, \$\endgroup\$ Apr 22, 2015 at 9:34
  • \$\begingroup\$ This was in the close votes queue as "too broad"—I'm inclined to agree. Attempting to narrow: What have you tried? What "undesirable effects" are you looking to avoid? Am I right in saying you want units to stay in formation? \$\endgroup\$
    – Anko
    Apr 22, 2015 at 13:30
  • \$\begingroup\$ RTS games often work by each client running the same deterministic simulation on each machine. So basically, if you can solve it for a single machine, you can apply the same solution to the multiplayer situations, whatever local avoidance technique you end up going with. \$\endgroup\$
    – Alan Wolfe
    Apr 23, 2015 at 4:55
  • \$\begingroup\$ Thanks for the feedback on the question. I narrowed the question down a bit and explained specifically what I'm trying to accomplish. \$\endgroup\$
    – JPtheK9
    Apr 23, 2015 at 16:39
  • \$\begingroup\$ This is a great resource: red3d.com/cwr/steer \$\endgroup\$
    – tbkn23
    Apr 27, 2015 at 3:50

3 Answers 3


It seems like what you're looking for is the Optimal Reciprocal Collision Avoidance algorithm. The preceding paper is also worth a read. Although the paper may be a bit involved the theory behind the algorithm is fairly straightforward:

Assume that you already have a simulation (game) with agents (units) that have some sort of bounding volume around them. This bounding volume is likely what you're already using to perform the collision detection and response. For each agent, define a preferred velocity v_p that may or may not be based on the agent's goal.

Now, to perform the simulation:

  1. For each agent, assuming that it is stationary, calculate all of the velocities that would cause it to collide at any point in the future with any of the other moving agents. This can be represented in "velocity space" as a set of of intersecting half-planes (also known as a velocity obstacle).
  2. Determine the point in this space closest to v_p, this is the new velocity of the unit.

If all of the agents are running the same algorithm, then they will choose velocities that mutually complement each other and will avoid other agents. In some situations, you can cause oscillations like that awkward thing that happens when you walk directly into someone in the hall and you both try to move out of the way in the same direction, but the papers cover how to avoid that.

For computing the two stages of the algorithm above, you can use Minkowski Sums to determine what the velocity obstacle is, and then use a linear programming model (such as the Simplex Algorithm) to determine the closest point to v_p that avoids the velocity obstacle. Also, code for doing collision avoidance is available for your perusal and has been ported to C# to be used in game engines like Unity. This technique has been used at least in Warhammer 40,000: Space Marine, and maybe other games.


I do not know how your units works but I assume that they are like a state machine :

Possible states

  • Running to (x,y,z)
  • Attaking (enemy_id)
  • Collecting ressource (ressource_id)

If you pay attention at how starcraft approaches this problem, you will find that :

  1. If there is space to move in a direction, the charachter moves in that direction.
  2. If there is no space the unit in the way will move to make space
  3. If the unit that needs to move to make space already has a command, it will keep the command, but modify it slightly to eventually make place.

Here scenario 1 :

enter image description here

Do I have space to go there? Yes ? Then go

Scenario 2 :

enter image description here

Do I have space to go there? No ? Hey can you make some space for me, you are blocking me. I already have an order to move foward but I will accomodate you.

So what you will need to implement :

  • Units must be aware of their surroundings
  • Units must have a way to communicate with each other
  • You must implement a way to keep executing a command while acomodating an another unit
  • \$\begingroup\$ Thanks for the info and visualization. Right now I'm using collision detection to find out if a unit can move to another place or if another unit is occupying it. The main thing I'm trying to figure out is an algorithm of some sort to tell the other unit what distance to move or what velocity to adjust by. In other words, how the blocking unit will accommodate the unit trying to pass. \$\endgroup\$
    – JPtheK9
    Apr 23, 2015 at 18:54
  • \$\begingroup\$ Since this behaviour is calculated every physics update, you don't really have to tell the distance, it will move until it's out of the way. For the direction, you scan simply multiply the velocity of the two units, this will give you the point halfway so that it keeps moving while accommodating. After that you can play around with that to make it so that it sticks more to the order or move out of the way faster. \$\endgroup\$
    – ESD
    Apr 23, 2015 at 19:03
  • \$\begingroup\$ What do you mean by "moves until it's out of the way"? How does the unit move in the first place? \$\endgroup\$
    – JPtheK9
    Apr 23, 2015 at 19:10
  • \$\begingroup\$ Sorry I forgot mention: Unit's aren't state machines. They have many abilities in their locker that are simulated every frame - except these abilities only have effect when activated, whether by the destination being X distance away or with the existence of a target. Movement of a unit is a result of its velocity which can be changed by an ability. \$\endgroup\$
    – JPtheK9
    Apr 27, 2015 at 20:48

One way to do it is to have the units auto-form formations, and have them attempt to stay in a position relative to the center of the formation. Then, instead of moving each unit individually move the center of the formation around.

Here's a basic way to do it using a box formation and simple springs to keep the units at their appropriate positions:

// Defines a phalanx (box) formation
class Formation
    // Center of the box in the world
    Position center;
    // Width in # of units
    int width;
    // Height in # of units
    int height;
    // Space between units
    float scale;
    // How much force units will apply to stay near
    // their assigned spot.
    float springforce;

    // Return a position of a unit at the given row and column
    // Todo: add a rotation to this formation so it can rotate when moving.
    Position GetUnitPhalanxPosition(int row, int column)
        return new Position(center.X + column * scale - width * scale /2, 
                            center.Y + row * scale    - height* scale / 2);

// Represents a simple point object with a velocity and position;
// it belongs to a formation.
class Unit
    Position pos;
    Velocity vel;
    Formation formation;
    // What's our assigned spot in the formation?
    int row;
    int column;

    void Update(float dt)
        // Get the desired target position in the formation
        Position target = formation.GetUnitPhalanxPosition(row, column);
        // Apply a spring force toward the position (todo: you might want to damp this)
        vel += (target - position) * dt * formation.springforce;
        // Move along the velocity vector.
        pos += vel * dt;
  • \$\begingroup\$ Thanks! This is a really interesting and creative solution. I've implemented something similar to this for crowd behavior/formations but I still have the problem of units overlapping. What should happen if 2 formations run into each other? \$\endgroup\$
    – JPtheK9
    Apr 23, 2015 at 21:32
  • \$\begingroup\$ I think it depends on the design. The easiest thing would just to be apply another steering force away from nearby units in other formations like in this image. Another thing you could do is merge formations together when they are selected by the player, or even form "meta-formations" \$\endgroup\$
    – mklingen
    Apr 23, 2015 at 21:39
  • \$\begingroup\$ Meta-formations sounds really complicated and buggy :C. The image you linked might be exactly what I need though. I'm going to do some more research on steering forces away. Do you have the link to the image's article? \$\endgroup\$
    – JPtheK9
    Apr 23, 2015 at 21:43
  • \$\begingroup\$ I have a similar problem to yours, would be interesting to know how did you solve it. One shot of idea came to mind after eeading this article: maybe combining Pathfinding (A*) for a macro path planning while using the reppel force for the micro collision avoidance: \$\endgroup\$ Dec 29, 2017 at 2:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .