3
\$\begingroup\$

I'm trying to simulate a number of units walking in a single file. My update loop looks like this:

for each unit:
    n = compute next position
    if n is empty then move to n

If I start the loop from the foremost unit, it moves first and leaves its current position to the unit behind it. When the loop finishes every unit will be moved one step. However if I start the loop from some other unit, it can't move since its next position is occupied by the unit in front of him. So, in the worst case it would take n-1 ticks for a unit to move one step (where n is the number of units in front of it).

I tried changing my update like this:

for each unit:
    save current position to p
    n = compute next position
    move to n

detect colliding units and move them back to their p positions

In this case the units move fine, as long as we have a single group. But another problem arises when the group collides head-first into another group. In this case, the foremost units will collide and they need to be moved back, but their previous positions will be occupied (by the units behind them) and they also need be moved back. This method also needs too many iterations.

How do RTS games tackle this problem? Is there a standard approach?

\$\endgroup\$
1
\$\begingroup\$

Although not for an RTS, I looked at a similar problem and came up with an idea:

For each unit A, check if it's colliding with the old location of other units B. If it is, then in B, remember that A needs it to move.

Now if B is unable to move, you can go back and mark A as being unable to move. A in turn might cause other units to be unable to move, so you recursively go through and mark all the units that are unable to move.

Unfortunately I never did finish that implementation because I moved to another project, so I don't know if this algorithm runs into any issues.

\$\endgroup\$
  • \$\begingroup\$ Not sure if I'm missing anything but couldnt you simplify this by moving the actor and on collision with another actor ask if that actor has already acted , if not ask that actor to do its move first, (recursively resolving actions) then resolve collisions? \$\endgroup\$ – Niels Mar 23 '16 at 15:28
  • \$\begingroup\$ @amitp this looks promising, however I'm worried about algorithm complexity since moving a unit might start a chain reaction of checks that possibly involves every other unit. I wonder if RTS engines used a simpler trick when cpu power was very limited. \$\endgroup\$ – Can Mar 28 '16 at 7:20

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.