**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. |

### 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. |

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):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:**

- 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.
- 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.
- 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.

## No comments:

Post a Comment