Improving Pathfinding for Large Armies

[causative]

I want to talk about some problems with pathfinding for large armies and proposed solutions.  I would implement these solutions and submit a patch.

If you have a big group of units gathered together with no formation, and select them and click for them to move somewhere across the map (or even relatively nearby), two things happen.

1. The units in front start moving immediately, but it takes a long time before the entire group is moving.
2. The group narrows into a single-file column as each unit tries to follow exactly along the planned long-range path.

Neither of these things is what the player wants.  The army would get to the destination faster if every unit started moving immediately, and it would be more effective once the fighting starts if it stayed together as a clump.  The more spread out the army is, the more vulnerable it is.

I want to pause here and say that I don't intend to do anything with formations.  These changes can be accomplished through individual unit pathfinding alone.

I want to compare this to other RTS games such as Starcraft II.  In Starcraft II, if you have a clump of units and tell them to move, the entire clump instantly start moving, and stays together as a clump.  You can see examples of Starcraft II pathfinding here:  https://www.youtube.com/watch?v=x0gSVKVZ4YU.  Throughout the video, notice how units stay in tight groups, even as they move around and change direction a lot.  If they split up, that's generally because the player manually split them up by telling part of the group to go one way and another part to go another way.  Starcraft II has no formations.

So how can 0ad work like this?  I plan on the following changes.  For reference, this is the current pathfinder doc:  http://trac.wildfiregames.com/browser/ps/trunk/docs/pathfinder.pdf

1. Add additional information to units giving their expected direction.  This is a vector saying where and how fast the unit is probably going to move in the next turn.  It doesn't have to be perfect.  If you give a unit a walk order, its expected direction would be immediately set to be parallel to the long-range path to the destination.  Otherwise, a unit's expected direction would be set to the direction it moved in the previous turn.  This information would only be updated once per turn.
2. For the purpose of short-range pathfinding, units ignore units whose expected direction would move away from them fast enough that there is no expected collision during the next turn.  This should solve the issue where it takes a long time for a group to get moving because of units treating units in front of them as obstructions.  As a side benefit, this would improve performance because the short-range pathfinder would have fewer edges to consider!!
3. After short-range paths have been selected for units, units with short-range paths that are nearly parallel to allied units adjacent to them, should have their paths adjusted to be exactly parallel.  This would prevent units from converging into a single-file column over long distances, by keeping a group moving in a parallel direction.
4. A unit is considered to have passed a waypoint (but not a final destination) if the closest point on the long-range path is at or beyond the waypoint.  This is necessary in combination with change 3, to keep units from insisting on stepping directly on every waypoint even when other allies who were going in the same direction are in the way.

edit: After further examination, I see there's another major reason for why groups of units take a long time to fully start moving.  Units ask for a new short term path as soon as they encounter an obstacle, even if the obstacle is moving.  Asking for a short term path causes the unit to stop for a bit.  You can see this by ordering a cluster of stationary units to move with the speed set to Turtle (0.1x).  You can see units freeze in place for a second, waiting for a path, before starting to move in a direction perpendicular to where they were ordered.  To fix this, units should keep trying to move for a short period of time if they were obstructed by a moving unit, and only ask for a new path if this doesn't work.  This would be in addition to the other changes.  As it would result in fewer calls to the pathfinder, this would also improve performance.

staticsliding.diff

Edited May 22, 2016 by causative
attached recent code

[causative]

Still working on this.  So far I have implemented the following changes:

1. When a unit tries to move and is obstructed by another unit, instead of stopping and asking for a short-range path, it will just walk all the way up to the second unit.  From there it will attempt to "slide" along the side of the other unit's obstruction square.  This "sliding" allows units to walk around each other without having to invoke the short-range pathfinder, which means they don't have to stop and can keep walking.  Units only ask for short-term paths if the "sliding" is failing to make progress (unit is stuck and cannot slide).
2. When a unit is following a long-range path, it only attempts to move parallel to the path instead of passing through every waypoint.  This reduces the tendency for groups of units to travel single-file over long distances.  Units will still follow short-range paths exactly, and will travel to the destination exactly.

The combination of these two changes allows groups of units to get moving faster, and as they move they group together much better instead of narrowing to a single-file line.  It also improves performance, because the "sliding" dramatically reduces the number of calls to the short-range pathfinder.  I tested performance in the "combat demo (huge)" scenario.

There are also some bugs where units get stuck - I've been working on figuring out how this happens and preventing it.  It happens rarely.

There's another issue.  The groups of units are still not sticking together closely enough for my liking.  They still bump into each other and don't all start moving instantly.  To make units move together as closely as Starcraft marines, it will be necessary to have the units in front of the group move first, to open a space so that the ones behind them can walk forward without bumping into them.

My plan for that is to let units wait for up to one other unit before they start moving.  Here's a scenario illustrating how it would work.

Unit A wants to move
If A can freely move, it does so, and is finished for this turn.
If A is obstructed by a unit B, and B is moving but has not yet
moved this turn, then B remembers "A waits for B."
  Then A is done for now, but will try again later.

Now unit B wants to move
If B can freely move, it does so.  Then B remembers "A waits for B"
  and tells A to try moving again.

Unit A tries to move again (on the same turn, because B told it 
  to try again).
If A can freely move, it does so.
If A still can't freely move because a unit C obstructs it, then
  A just moves as far as it can.  It will not wait for C; it may
  wait for only one other unit per turn.

However, I don't know if this kind of detailed ordering is possible with the component message passing framework.  There is an alternative, which would be to sort units by their distance from the goal, and have units that are closer to their goal move first.  However, that has its own problems and might be slower because it's O(n log n) instead of O(n).

Edited May 4, 2016 by causative

[causative]

Well, here is the rough code I have so far.  It achieves what I wanted it to do - large armies can stick together fairly easily without formations as long as they are in an open area, and it does reduce short range pathfinder use in those situations.  However, there is still a problem, which is that units can get stuck against static obstructions.  I think that may have something to do with the short range pathfinder being too optimistic about being able to walk around static obstacles when the navcells block the way (and the units have been bumped off the long range path by sliding).  I'll still be tweaking it to see if I can solve that problem.  Meanwhile please give it a try!

For the most part this is 2 changes.  First, units slide against each other parallel to the path, as I mentioned above.  Second, units move in an order determined by their long-range path length - units with shorter paths move first to make room for those behind them, who usually have longer paths.

A note - one interesting thing Starcraft II pathfinding does, is allow moving units to push stationary allied units out of the way.  It might give a nice aesthetic to try that as well.

Another note - this patch is far from polished.  "It compiles" is about what can be said for it!  Please don't murder me over the coding style, which I'll clean up a bit before submitting on trac if I can fix the units-get-stuck problem.

sliding.diff

Edited May 13, 2016 by causative

[causative]

I'm back on this again.  I have an update:  I believe I've more or less fixed the stuck units problem, by making units slide only if they are following long paths.  When following short paths, they behave as before.  Here is the latest diff for trunk:

 

I might want to try implementing flocking as well, to make the units more responsive.  Units tend to pack too close together and a large group doesn't stop all at once.  Instead, units wander around at the destination.  Flocking could solve both of these problems.  Flocking would also mean only one long path needs to be computed when you select a bunch of units and tell them to move, instead of one long path per unit.

mergedslidingdiffmar2017_2.diff

Edited March 7, 2017 by causative
updated diff