15
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ "flocking behavior" (google term) is a very wide problem, \$\endgroup\$ – ratchet freak Apr 22 '15 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 '15 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 '15 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 '15 at 16:39
  • \$\begingroup\$ This is a great resource: red3d.com/cwr/steer \$\endgroup\$ – tbkn23 Apr 27 '15 at 3:50
10
+50
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ That was an amazing article and I feel like I'd read half of it from your explanation. Thanks for this information. \$\endgroup\$ – JPtheK9 Apr 28 '15 at 18:49
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\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 '15 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\$ – Antoine Apr 23 '15 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 '15 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 '15 at 20:48
0
\$\begingroup\$

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;
\$\endgroup\$
  • \$\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 '15 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 '15 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 '15 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\$ – ColdSteel Dec 29 '17 at 2:52
0
\$\begingroup\$

I know some people frown on link dumping, however I found A Multi-Agent Potential Field Based Approach for Real-Time Strategy Game Bots (ISBN 978-91-7295-160-0) to be a very enlightening paper, and it obviously conveys way more than I could elaborate on. The paper explores using artificial potential fields (a concept originating from robotics), to facilitate local collision avoidance within a game development context.

\$\endgroup\$
  • \$\begingroup\$ Thanks! Research is just as helpful as explanation to me. I'll dive into this paper. \$\endgroup\$ – JPtheK9 Apr 27 '15 at 17:10
  • \$\begingroup\$ I have an influence map already set up but this seems too complicated for my tastes. The main thing is generating potential fields for different units to move them, and also converting data from the potential field into a velocity to move at. Basically, I don't think this would work for units of different sizes. It's a great read though with lots of interesting ideas. \$\endgroup\$ – JPtheK9 Apr 27 '15 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.