Leaderboard

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.