Pathfinding with Jump Point Search

 


Code for this tutorial is on this git branch:

git clone -b Jump_point_search https://dglencross@bitbucket.org/dglencross/zombiegametutorial.git

Have a look here for help setting it up


Path-finding

This is where things start to get interesting, as we introduce some more complex behaviour. So far our little character walks in whichever direction you tell him. If you are standing on one island and click on another island, he will travel in a straight line, over water, towards that other island.

Instead, we want our character to travel only on land. If there is water in the way of our destination, we should walk around this water (if possible).

Excuse the shitty graphics
Path-find towards the X

There are a few different algorithms for path-finding, and most already have examples in Java.

This is part of our Libgdx tutorial series, but neither the algorithm nor the implementation are dependent on it.

 A* Search

You may have heard of A* search – if you have done anything to do with path-finding then you almost certainly have.

There are many examples of A* search tutorials in Java, and we implemented one of them originally in Dinowar. A* search tries to find the ‘cheapest’ path from one node to another, considering the costs of nodes in between. For example, if you have a map with mountains on it, any tile/node which is on a mountain will be more expensive than one on flat ground.

Imagine that you want the character from move from A to B. The path-finding algorithm will look at the surrounding tiles/nodes from A, see which is the cheapest one to move to, where its cost is defined as approximately its cost to move to (higher/lower depending on terrain of the map) added to its estimated cost to B – so the closer the node is to B, the lower this cost would be.

This is a wildly simple explanation – if you want more technical info, these resources are pretty good for explaining it:

http://web.mit.edu/eranki/www/tutorials/search/

https://en.wikipedia.org/wiki/A*_search_algorithm

Speaking of mountainous areas, an early version of Dinowar looked like this:

We implemented A* search, so you would often see the dinosaur characters move around the outside of a mountain in an attempt to get to their destination move quickly.

So, why did we go with Jump Point Search instead of A* search?

A* Search in Dinowar

When running the game on Android, we found A* search to be too slow. Dinowar can have up to 10 different bases, with each one having paths between them for both land and water dinosaurs. In theory, that can be 10! x 2 different paths. In practice, we needed the path generation to be so fast as to be unnoticeable by the player. When running on a phone, generating a path could take up to half a second, which made the game unplayable in practice.

We experimented with generating all potential paths when creating the map, but again this lead to slowness on map generation. We wanted the player to be able to press the refresh button as many times as they wanted, until they got a map they were happy to play on.

After some research, we discovered a lesser-known algorithm:

Jump Point Search

JPS is a faster version of A* search, with one major drawback – it assumes that all tiles are the same ‘cost’. No more mountains, but much, much better speed. This is why Dinowar ended up looking like this:

Paths are generated at map-creation time, and it is so fast as to be irrelevant.

How does it work? Essentially, it does the same as A* search, but because all tiles/nodes cost the same, the algorithm knows that it only has to consider its neighbours in the direction of the destination. For example, think of A -> B again. In A* search, if there is a mountain between A and B, it might actually make sense for the path to start backwards, as long as the route is still cheaper than going across the mountain. In JPS, we assume the ground is flat, and there is no need to consider the possibility of going backwards.

Check out this picture from an excellent explanation that you can find here: https://harablog.wordpress.com/2011/09/07/jump-point-search/

The arrow represents the direction of movement. On the left, you see what happens when you are moving along a straight line (straight up or straight sideways). You only have to consider the tile in front of you.

On the right, we see what happens when moving diagonally – we only have to consider three nodes.

This represents a huge saving in effort when generating paths. This is especially important in our tutorial – we will be generating a path every time the player character is told to move around the map, so we really want our path-finding to be instantaneous.


Conclusion

Try playing with the tutorial – this is the first section which uses the path-finding code that we’ve uploaded. In the next part of the tutorial, we’ll go into depth on the actual code implementation of Jump Point Search.



If you like these tutorials, or want to see a game that was written in much the same way, please download Dinowar from the Google Play Store. It costs nothing and is ad-free.

One thought on “Pathfinding with Jump Point Search”

Leave a Reply

Your email address will not be published. Required fields are marked *