Correct order of entity updates and collision detection

Question

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?

Answer 1

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.