As mentioned previously, we need two separate pathfinders (one for planning long-range paths that avoid rivers and buildings and walls etc, and one for finding short-range diversions around other units while following the long-range paths), and there are problems (like units getting stuck) when the two pathfinders disagree on whether a unit can fit through a gap.
What the game currently does is like this: (click for larger image)
The grid pattern on the terrain shows the tiles (each split into 4x4 small cells). The cavalry unit has been told to walk from by the water up to the flag.
The long-range pathfinder works with tiles: the red-shaded tiles are impassable (blocked by buildings or water or steep terrain), and the green- and yellow-shaded tiles are where the pathfinder has searched to find the shortest path. It's finding a path that travels through a piece of wall, because the wall is too narrow to have blocked an entire tile.
The short-range pathfinder works with the cyan squares. Each building (and each tile that is blocked by water or steep terrain) has a square around it. Instead of using tiles, it moves between the corners of the squares, making sure it never crosses one of the cyan edges (since then it would collide with an obstacle). The thin red line indicates the path it's found, walking around the edges of the walls and then heading towards the flag. In this case it luckily doesn't have to diverge too much from the long-range path (which went straight through the wall) so it works okay, but in other cases the inconsistency is a problem.
I've been changing it to instead look like:
The long-range pathfinder is basically as before, but instead of using whole tiles it uses the small cells, so the red/green/yellow-shaded regions are a much higher resolution. That means it can fairly accurately represent small obstacles like the wall, without hugely over-estimating or under-estimating its size.
The short-range pathfinder no longer uses a single square around a building(/wall/etc) - it computes the cyan edges to exactly match the boundary of the red-shaded (impassable) cells. The little yellow circles indicate corners that the path can go between. If the long-range pathfinder found a path, it's guaranteed that the short-range pathfinder will be able to find the same path (or a better one), assuming no dynamic obstacles (i.e. other units) get in the way, because they're using the same cell-based view of passability.
I think that's good - it means the pathfinders now have some better correctness guarantees, and can make some simplifying assumptions (e.g. the long-range pathfinder doesn't have to worry about the short-range pathfinder moving a unit onto an impassable tile), and that makes it easier to implement optimisations to improve performance without worrying about breaking everything.
Philip Taylor [aka Ykkrosh]
WFG Programming Team
This was a most interesting article for a... non developer to read. Thanks for explaining! :)
Thank you
Cool :)
With going from 4x4 cells to 1x1, doesn't this mean that the pathfinder now is 16 times as expensive with calculations?
sexy