Really Fast Pathfinding, an Assignment

As you probably know at this point, I'm currently a college student majoring in Game Programming. As this semester wraps up, I have to research and explain an AI programming technique here for my final assignment. In this post, I'll be explaining how to use jump points to make a ridiculously fast grid pathfinder.

Note: This tutorial expects that you already understand the basics of the A* pathfinding algorithm. If you don't know it, I recommend looking here. It's the best and easiest resource on the subject that I know of.

 The Problem:

When pathfinding speed can often arise as an issue. A*, the most common pathfinding algorithm, can be fairly slow in numerous cases, especially when dealing with large open spaces. Obviously, this means that games can put A* into it's worst cases on a pretty regular basis. For this reason, a huge number of techniques have sprung up to try and improve A*'s speed when dealing with such areas. I'm going to be talking about one such technique: The Jump-Point Search, or JPS for short.

Turns out, both of these are of equal length.

JPS is based on  the notion of path symmetry, where multiple similar paths have the same length. This mostly occurs when dealing with grids. With A*, hitting a wall or corner often leads to unnecessarily checking a large number of tiles. Thus, the goal is to only check tiles that are important, and ignore the all of the empty space. JPS does just that, by turning small steps into huge leaps.

Introducing JPS

JPS is a surprisingly simple technique that only alters one stage of the process. When the time comes to get the neighors of the last checked node, JPS makes each neighbor 'jump' before adding it. To do this, JPS makes the neighbor move away from the original node until it reaches a turn of some kind. How does it do that? That's the interesting part.

A diagram from the original paper, demonstrating how JPS ignores neighbors. Anything greyed out can easily be reached by the original node, and is ignored.

When 'jumping', JPS acts under the assumption that most of a nodes neighbors can be reached by the original node, and so it ignores them. If a jumping node runs directly into a wall, it returns nothing, since that particular line contains nothing useful.
To find walls, JPS does two things. First, it checks certain neighbors for walls. As you can see in the above diagram, walls can only block out a node's neghbors from the original position if the node is moving orthogonally, and they are perpendicular to its movement, or the node is moving diagonally, and the wall is slightly behind it.

The horizontal and vertical jumps, as illustrated by the original paper. Dashed lines indicate a failed jump.

The second check is only made if a node is moving diagonally. To ensure that a far off but accessible turn isn't missed, the node sends out two more node 'jumps' on its vertical and horizontal movement.
When one of these cases is found, the node stops and is added to the list. Also, if the endpoint is found at any point then that gets added as well. This effectively leaves the list of nodes to check with only potentially important ones, leaving out the filler.

So, Why Care?

There's one simple reason to care about JPS: it's better than regular A*. It's proven to still find the shortest path, it requires no additional preprocessing, and best of all, it's pretty much always faster. The paper mentiona that their worst case had JPS finding paths at around 3 times the speed of A*, and their best had JPS doing so 30x faster. No, the 0 is not a typo. That's immense! I've implemented my own version, and it's still a rather buggy, but still usually outperforms A* by a noticeable margin. In other words, I see no downside to using this in any game that ca, on whatever platform you want. One thing to note is that this only works on on grid-based graphs. If your pathfinding graph is more freeform, then the technique won't be of much use. Of course, at that point you can probably just add your own optimizations anyway.

My Attempt

I've written my own A*/JPS implementation in C++ using Drunkard's Walk-generated random areas and ncurses output. Here's how it looks(Highlighting added after):

Red areas indicate where nodes have been checked/added to the open list. Note that the full path is quite long, so most of it is missing. Rest assured that it's pretty much just like this the whole way.

As you can see, JPS changes things quite a bit. One thing to note is that a JPS path will mostly only have nodes at turns, so you'll have to fill paths in if you plan to snap movement to the grid. I decided not to other in my demo, as I don't really need to do anything more with the path. I've decided not to include my demo here, as it's fully exclusive to Linux, poorly coded, lacks comments entirely, and features a a very draconian vim-like interface that would make most normal people uncomfortable. If you really want it, though, feel free to send me an email or comment, and I'll be happy to make it available on an individual basis, source and all.


Well, that's it. I find JPS a bit difficult to explain, so I hope I've done a decent job of it. I recommend taking a look at the original paper, linked below, if you're confused. It contains psuedocode for the entire jump function, which makes implementation easier. I should warn you now, though, that the language is very academic, so it can be a pain to read. My third reference below has an online demo, so if you just want to see the algorithm run without making your own implementation you should head there.


References:

1. http://www.aaai.org/ocs/index.php/SOCS/SOCS12/paper/viewFile/5396/5212 - This is the original article that describes the JPS technique. A very useful source of information, if you can decipher the academic writing.
2. http://aigamedev.com/open/tutorial/symmetry-in-pathfinding/ - This is where I first encountered JPS. I was researching some things for another project(I'll be posting about that one later), and I ran into this. It looked like a cool technique, so I bookmarked it for later use. This particular resource talks about another technique as well, but doesn't go too in-depth into either.
3. http://zerowidth.com/2013/05/05/jump-point-search-explained.html - Another resource that I used to help me figure out what was going on in the paper. It has some useful diagrams and an interactive demo, making it a really great reference.