Supreme Commander 2 pathfinding

[Ykkrosh]

Since I happened to play Supreme Commander 2 recently, I thought it'd be interesting to reverse-engineer its pathfinding algorithm (as with Age of Mythology, though SupCom2 is entirely different). Their promotional material (

etc) talks about it being based on crowd continuum pathfinding, but as far as I can tell that's basically nonsense (though I could certainly be mistaken; it'd be good if anyone had more precise technical details) - it doesn't appear to do any kind of dynamic potential field, it just does a basic static vector field plus local steering behaviour (with perhaps a little bit of lookahead to discourage units walking straight into each other).

I don't think this is of much direct relevance to 0 A.D., since we have very different requirements and constraints, but it's interesting as a point for comparison.

So, this is my current poorly-organised understanding of how it really works (with a few links to pictures hidden in the text, for people who don't like reading):

Units have an EPathMoveType, which is one of a hardcoded list:

* PMT_Land_Small_Water_Surface

* PMT_Land_Medium

* PMT_Land_Large_Water_Abyss

* PMT_Land_Large_Water_Floor

* PMT_Land_Medium_Water_Surface

* PMT_Air

determining what kind of terrain it can move over.

Terrain rendering is not tile-based - the world is just a collection of meshes (one for ground plus separate meshes for walls and custom scenery etc) - but it's converted to a 2D tile-based heightmap for pathfinding and for computing heights of units. Tiles are about the same size as a small unit. The world is about 1024x1024 tiles on the 2-player map I tested.

Buildings are aligned to the tile grid (they can't be rotated or fractionally offset). Buildings have a square outline, and you're not allowed to build so that it overlaps any other building's outline. Also you're not allowed to construct too close to an impassable terrain tile. Buildings block tiles in an arbitrary pattern (typically a square, but factories have holes cut out the middle so units can walk out of them). There is always a one-tile-wide border inside the outline that is not blocked. The consequence is that it's impossible to block off any areas - there's always a gap for units to squeeze between buildings, or between buildings and blocked terrain. That means it can't support defensive walls that keep enemies out. (Also you can't accidentally set up factories where there's no space for units to spawn.)

To be more specific about impassability, see two screenshots: small unit, large unit. The red tiles are impassable due to terrain, and the purple tile are impassable due to buildings. Red tiles block off roughly 2 tiles around the steep walls for small units, and an extra 4 tiles for large units. (The red tiles gives an octagonal pattern around sharp corners.) But buildings take precedence - if a tile within a building's outline is defined to be passable by that building (e.g. the one-tile border), then it will never be marked as red. (That means even the huge units can squeeze between buildings and blocked terrain. (Or they can try, at least - sometimes they get permanently jammed for some reason.))

Given that passability grid, a unit can pathfind to a single goal tile, using a flowfield algorithm. That algorithm computes a vector for every tile, such that a unit can follow the vectors and will end up at the goal. See another screenshot which makes it clearer (the goal is the bottom-centre of the screen).

It starts with the goal tile. For any tile within about 64 tiles of the goal, if there is a straight line to the goal that doesn't cross any impassable tiles, then the flowfield vector points directly at the goal. Those vectors are drawn in light blue. Beyond that, it expands outwards in 45/90 degree angles (like normal A* pathfinding), and the vectors (drawn in green) point in 45/90 degree angles towards the predecessor tile. (In a few cases it gets some intermediate (presumably 22.5/67.5 degree) vectors too as a shortcut, but it seems pretty random in when it decides to do that (probably a bug).) It stops generating the vector field a little bit after it's reached the source unit. (I don't know why some of the vectors in the earlier screenshots are dark blue; it only seems to happen for short paths. Maybe a visualisation bug?)

The point of doing that work is that multiple units with the same goal can use the same flowfield - moving a group of 100 units has the same flowfield-generation cost as moving 1 unit, and the units can still move independently of each other (so they move as a swarm, not as a formation).

Each tile will either have one of 16 directions (rendered green), or will be pointing directly at the goal (rendered light blue), or will be unexplored and have no vector, so it needs to be stored with 5 bits per tile. It needs to be memory-efficient since each flowfield is stored for as long as any unit is still using it.

Given a flowfield, each unit does some kind of steering behaviour: try to move in the direction of the vector of the tile you're currently on; if you hit a unit bigger than you, or an equally-sized unit that's also moving, then try to wobble left or right a bit until you get around it (or get stuck); if you hit a stationary equally-sized or a smaller unit then shove it out of the way and carry on straight.

When you tell a group to move to a goal, they try to spread out in a grid formation around some target (i.e. some position and direction). It computes the desired formation offset for each unit, then casts a ray out from the target to each of those offsets, and stops when the ray hits an impassable tile and puts the real formation offset there. (That means if you move a group to a tile adjacent to a cliff, the units on one side of the formation will get jammed up against the inside edge of the cliff, instead of letting the formation get split across the cliff.) It then computes a single flowfield for the entire group of units. Each unit follows that flowfield, until they reach a point where there's an unobstructed straight line to their own formation offset, and then they head straight towards that new position.

The target for a group of units is determined in some unknown way; it seems to depend mainly on the average position of the units, and jumps around a lot every sim turn. At some point it snaps to the goal tile and stays there forever. (That means the units often don't remain in any kind of formation - they squash up into a narrow snaking column until they get in sight of the goal and spread out again.)

I think that's about it.

[Android_]

I am surprised noone has commented on this yet. I find it most interesting, especially this video, very impressive. Why do you think that advertising SupCom2's pathfinding as being based on this is nonsense, Philip?

[Ykkrosh]

The Continuum Crowds research seems to be all about using a 'dynamic potential field' that represents both global navigation (planning routes around static obstacles) and moving obstacles (avoiding running into other people). It's an expensive computation since the potential field needs to be a large high-resolution grid, and the whole grid needs to be updated several times per second to cope with moving obstacles, but it can result in nice congestion-avoidance behaviour (forming lanes and vortexes).

SupCom2's behaviour (based on observing the gameplay and its debug visualisations) can be understood without any of that - its global navigation is fundamentally just standard RTS static A* (but run backwards, with the results shared between multiple units), and it deals with moving obstacles largely by having them run into each other and then slide around and hope they eventually slip past each other. If you tell two groups of units to cross each other at 90 degrees, there's no lane formation - they turn into a giant mess. (You do get lanes if the two groups are moving directly towards each other, but that's the only case where it works nicely, and that's just a consequence of groups being box formations with wide separation between units.)

So they're, like, totally different, and claiming that one is based on the other (as anything more than just a vague inspiration) is therefore nonsense

[Android_]

I see . I guess Continuum Crowds are no option for 0AD either though? Too complicated?

[Ykkrosh]

It's probably too slow, and we don't want crowds anyway (we want units to move in relatively rigid formations), as well as it being complicated, so it's not very suitable at all

[Android_]

Ok. It's funny though that actual university researchers study stuff like this - where science meets games haha.

[MattDoerksen]

It's probably too slow, and we don't want crowds anyway (we want units to move in relatively rigid formations), as well as it being complicated, so it's not very suitable at all

Ok. It's funny though that actual university researchers study stuff like this - where science meets games haha.

Where is the code for pathfinding? Although it's not directly applicable, I'm working on parallel computing for my M.Sc. (using OpenCL on GPUs and APUs) which could help with potential speed problems (particularly if the user has a very fast PC where they could choose how good to make the pathfinding AI among other parameters [or we could build some tests and see how long they take to execute and choose the most appropriate one]).

[Ykkrosh]

The code is all here (the files with "Pathfinder" in their names).

particularly if the user has a very fast PC where they could choose how good to make the pathfinding AI among other parameters

My current perspective is that users with very fast PCs are the least important when optimising the game - in general it's best to focus on optimising the bottlenecks, so users with very slow PCs are the much more interesting problem . We want the gameplay to work well for every player; and to support multiplayer and replays (and to preserve sanity when debugging problematic behaviour) we really need the pathfinder to give identical results for every player; so performance is constrained by the slowest player we want to bother supporting (which nowadays is probably still (just about) single-core CPU and middling Intel GPU, i.e. not much opportunity for parallel computing).

I've seen some interesting demos like ATI's Froblins of doing pathfinding on the GPU (just using D3D10 in that case) - that's more like the Continuum Crowds paper than SupCom2 is, in that it uses the crowd density when computing the potential field (and has to update it each time everyone moves). I don't know how practical it'd be for a game though - their demo seems to have few distinct pathfinding goals ("go to any gold" and "go to any temple" and not much else), and a uniform unit size and no formations etc, which cuts down the need for many distinct potential fields, so it'd be interesting to know if there are other clever parallelisable ways to do pathfinding that could work well in practice.

[chaosislife]

The code is all here (the files with "Pathfinder" in their names).

My current perspective is that users with very fast PCs are the least important when optimising the game - in general it's best to focus on optimising the bottlenecks, so users with very slow PCs are the much more interesting problem . We want the gameplay to work well for every player; and to support multiplayer and replays (and to preserve sanity when debugging problematic behaviour) we really need the pathfinder to give identical results for every player; so performance is constrained by the slowest player we want to bother supporting (which nowadays is probably still (just about) single-core CPU and middling Intel GPU, i.e. not much opportunity for parallel computing).

From someone who doesn't live on the bleeding edge, thanks. It's annoying when new games come with insane system requirements just to run with everything at the lowest settings.