Day 15 of Pathfinding Work news - 0 A.D. Empires Ascendant

Day 15

Worked on various minor fixes to make the pathfinding less broken, and updated the JPS A* to work with the real technical requirements (correct diagonal movement, non-point goal areas, etc), so it's nearly possible to test performance in a proper gameplay environment.

Some more thoughts on JPS:

Intuitively (i.e. very informally and maybe wrongly), JPS works because of two observations:
* Shortest paths will wrap tightly around the corners of obstructions. (Imagine the path is a piece of string from the source to the destination, winding around various obstructions, then pull the string tight. It will get pulled until it's going in straight lines between the corners of the obstructions. If it's not already tight around the corners, it's not a shortest path.)
* In a grid (only allowing horizontal/vertical/diagonal steps), when there are multiple equal-length paths between the same two points, you have to make an arbitrary choice between them, and you can always prefer the one that moves diagonally as early as possible.

Therefore, if the pathfinding algorithm is extending a path in a horizontal/vertical direction, it can continue in a straight line until it reaches a corner to wrap around. If there is no corner, there's no point turning diagonally or 90 degrees from the current direction, because it would always be possible (and preferable) to have turned diagonally on an earlier step. (That continuance in a straight line is the "jump" in "JPS", and is what makes JPS a worthwhile optimisation.)

If the algorithm is extending a path in a diagonal direction, it can continue in that direction; or it can turn 45 degrees and go horizontally/vertically (since that might still be a most-preferred shortest path); or it can wrap around a corner and turn 90 degrees.

The definition of "corner" depends on how you define connectivity between grid cells. The original JPS paper says that any horizontally/vertically/diagonally adjacent passable cells are connected. Here's some diagrams of the shortest paths (in blue) from the red blob to every other cell, where black cells are impassable:

In the second diagram, note that the paths can squeeze through the diagonal gap between the two impassable areas. That's a bit nasty because unit movement is not tile-based: units move along the path in arbitrary-length steps, and they might end up standing precisely on the impassable tiles' corners or (due to non-infinitely-precise maths) actually stand inside an impassable tile, which is bad. But we don't want to forbid diagonal movement entirely, because it allows much higher quality paths than purely horizontal/vertical movement.

To fix that, we can declare that diagonal moves are only allowed between two passable cells (i, j) and (i+1, j+1) if the other two adjacent cells (i+1, j) and (i, j+1) are also passable. This means the diagonals do not connect any two cells unless they are already connected by horizontal/vertical steps (which incidentally simplifies other tasks like reachability testing). Now the shortest paths are like:

This means the paths always stay at least half a tile away from the obstructions, so we won't suffer from numerical precision problems as before. Interestingly, the path around the corner in the very first diagram has two turns (from horizontal to diagonal, then to vertical), whereas in the new approach it only has one turn (from horizontal to vertical), so the new version might result in fewer processed A* nodes and work a bit faster.

The changes to the original JPS algorithm are straightforward (unless I'm misunderstanding it and introducing bugs) - horizontal/vertical jump points occur one cell later, and have 2 forced neighbours instead of 1, while diagonals have no forced neighbours at all, so it just needs small tweaks to the code.

-- Philip [aka Ykkrosh]