0 A.D. is a free, open-source, cross-platform real-time strategy (RTS) game of ancient warfare. It's a historically-based war/economy game that allows players to relive or rewrite the history of twelve ancient civilizations, from Iberia to Mauryan India, each depicted at their peak of economic growth and military prowess. Developed using Pyrogenesis, a ground-breaking new game engine custom-built to suit this project, 0 A.D. will give players a rich and entertaining real-time gaming experience.

Report article RSS Feed Day 15 of Pathfinding Work

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.

Posted by Mythos_Ruler on Feb 24th, 2012

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]

Post comment Comments
Drakkheim
Drakkheim Feb 25 2012, 10:57pm says:

The other, less computationally intensive approach, is to just make sure that your obstacle assets have a 1 cell border around them that's passable for that annoying diagonal passthru. This is what the old Command and Conquer games did .. even a things like starcraft and TA do it.
Granted you've got more processing time to work with than they did so It'll be interesting to see how it works out. :-D.
Nice bit of work and enjoyed the post, will be following this game.

+3 votes     reply to comment
Post a Comment
click to sign in

You are not logged in, your comment will be anonymous unless you join the community today (totally free - or sign in with your social account on the right) which we encourage all contributors to do.

2000 characters limit; HTML formatting and smileys are not supported - text only

Icon
0 A.D. Empires Ascendant
Platforms
Windows, Mac, Linux
Developer & Publisher
Wildfire Games
Engine
Pyrogenesis
Contact
Send Message
Official Page
Play0ad.com
Release Date
TBD
Game Watch
Track this game
News
Browse
News
Report Abuse
Report article
Related Games
0 A.D. Empires Ascendant
0 A.D. Empires Ascendant Single & Multiplayer Real Time Strategy
Related Engines
Pyrogenesis
Pyrogenesis GPL TBD
Related Groups
Wildfire Games
Wildfire Games Developer & Publisher with 21 members