Following a path – Pathfinding 3


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


Following a path

Up until now we’ve shown how to generate a path using Jump Point Search, a variant of the A* search algorithm that is much faster, but has a big limitation – that it only works on flat maps.

The final piece is to decide how to navigate the path. The path itself will be our Path class, which is a wrapper around an array of Steps. Each Step represents one coordinate on the map that we want to move towards (and they are in order).

However, they are not uniformly spaced apart, so we can’t just step from one to the next. We can’t say “go to step 1, then to step 2, then to step 3 etc”. Instead, think of it like this: “move in the direction of step 1, then once you have reached it, move in the direction of step 2” at the same pace. For this, we use a little vector calculation, which I will explain below.

 

Creating the path

You might remember the method from a previous tutorial, where we tell the PlayerCharacter where it should be moving towards. This was:

public void setDestination(Pair destination)

This is where we create our path, as we want to calculate a new one each time we touch somewhere on the screen to move towards.

This now looks like this:

public void setDestination(Pair destination) {

if (destination.isWater()) {
return;
}

pointAt(destination.asVector());

Pair currentLocation = new Pair((int)pos.x, (int)pos.y, true);

JPS landJps = new JPS(screen.getWorld(), currentLocation, destination);

path = new Path(landJps.search());
}

 

Here we tell make sure the destination is valid (i.e. not water), make sure we’re pointing at it, then generate our path. Now, our PlayerCharacter has a path to follow.

Update the PlayerCharacter’s position

public void update(float delta) {
   if (null == path || path.isEmpty()) { // we have no valid path, so just return
      return;
   }

   pos = getNextPosition(delta);
   updateOrientation();

   if (nextPathNodeIndex > path.getLength()) { // then we've arrived
      path = null;
      nextPathNodeIndex = 0;
   }
}

First off, no path means no movement.

Then we determine our next position (the method for which we’ll look at below), move towards it, and point towards it, so that the PlayerCharacter is always pointing in the direction it is moving.

Then we work out if we have arrived at our destination, and if so, nullify the path so that we stop moving.

getNextPosition()

private Vector2 getNextPosition(float delta) {
   if (nextPathNodeIndex == 0) {
      currentPN.set(stepToV2(path.getStep(0)));
      nextPathNodeIndex ++;
   } else {
      float amountToMove = 3*delta;
      do {
         nextPN.set(stepToV2(path.getStep(nextPathNodeIndex)));
         moveVec.set(nextPN);
         moveVec.sub(currentPN);

         if (moveVec.len() > amountToMove) {
            moveVec.setLength(amountToMove);
            currentPN.add(moveVec);
            amountToMove = 0;
         } else {
            amountToMove -= moveVec.len();
            currentPN.set(nextPN);
            nextPathNodeIndex++;
            if (nextPathNodeIndex>path.getLength()) {
               break;
            }
         }
      } while (amountToMove > 0);
   }
   return currentPN;
}

private Vector2 stepToV2(Step step) {
   return tmp.set((float)step.getX(),(float)step.getY());
}

This is the most complicated part of it, and to be honest even I am having to concentrate to remember how it works (always a sign of great code). The purpose of this method is always to move the same amount in one update. So if your next Step is further away than you are allowed to move (which we’ll call X), then you only move by X amount. If the next Step is less than that – e.g. it is only a quarter of X away – we move to that next Step, then work out where the Step after that is, and move the remaining distance (three-quarters of X) in that direction.

Here is the pseudocode interpretation of it:

  • If we haven’t moved yet, move to the first step (which should be where you are already, it’s just to advanced along the path).
  • Else, determine what the vector between our position and the next step is.
  • If this vector is longer than the amount we are allowed to move, reduce it until it is the maximum length we can move in one go.
  • If this vector is less than or equal to the amount we are allowed to go, move in that direction, then move in that direction, and subtract that distance from the amountToMove – so if you are allowed to move 10 units, and you have moved 2, then you have 8 units of movement left to go.
  • While amountToMove is greater than zero, repeat this process.

This might seem a bit convoluted – perhaps you will come up with a better way of doing it – but for your purposes, you might not even need to edit this method. Just remember, the point of it is to keep the PlayerCharacter moving at a constant speed along the Path that it has created.

Conclusion

If you have read the last three tutorials, you should now have Jump Point Search working and an understanding of what it is doing. The code is all provided in the repository so go ahead and play around with it. If anything is unclear, just leave a comment below the line.

We’re doing with path-finding now – next up, we will introduce some zombies to run towards the player, then after that we will work out how to shoot them.



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.

Pathfinding with Jump Point Seach 2


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 2

In the last tutorial, I described how Jump Point Search works (at a high level). In this tutorial, we will look at some of the key parts of the code. Specifically, we will look at the parts of code which you might want to change. If you’re creating your own project instead of following the project int this tutorial, you will be able to see what to edit.

In this tutorial we will look at how to find a path – in the next tutorial, we will look at how to follow it. That part has a bit of vector maths, but is much simpler than the JPS algorithm.

Basic elements of Jump Point Search

To get from A -> B:

  • from node A, look at surrounding nodes and decide which ones are in the correct direction
  • look at each of these potential nodes and decide if we can move to them (whether they are ‘walkable’)
  • repeat until we get to B
Pathfinding in Dinowar. The red cross shows where the dinosaur turns.

JPS.java, Heap.java and Path.java

These are the most complicated classes for JPS, and these were provided by Kevin Glass (as credited in code). They have been edited to a minimum, just to insert our own custom code.

The basic algorithm is described in the previous tutorial – if you are very interested, go back and reread it while looking at these implementations. I’m not going to go into it any further (unless anyone gets in touch to say they want it).

What is a node?

In our case, a node means a tile on the map. Our base class for the nodes is Pair.java. If we’re to integrate this into our pathfinding, we need to include some more logic. Each pair/tile/node needs to keep track of its costs – defined as:

f = g + h

for tile X, where g is the distance from the current node to tile X, and h is the distance from X to the target destination. So the JPS algorithm needs the nodes to keep track of their costs, and so they need variables to hold f, g and h, and a method to update them:

public void updateGHFP(float g, float h, Pair parent){
   this.parent = parent;
   this.g = g;
   this.h = h;
   f = g+h;
}

We also include some code to reset these values to 0, which we use when creating a new map (just to wipe out all previous values).

World.java

This is the existing class that we have modified the most. I want to highlight some methods that will interest you most if you want to change anything:

/**
 * Tests an x,y node's passability
 *
 * @param x (int) node's x coordinate
 * @param y (int) node's y coordinate
 * @return (boolean) true if the node is obstacle free and on the map, false otherwise
 */
public boolean walkable(int x, int y){

   if (MapTools.outsideTheWorld(x, y, getMap())) {
      return false;
   }

   if (getMap()[x][y].isWater()) {
      return false;
   }

   return true;
}

I hope you can get the idea here. At this stage of the project, we can still click outside of the world map (something we will later change), so first we check that the user has clicked in a valid place.

Then we check if the place the user has clicked is water. If so, our character cannot walk there!

If we passed both these checks, then our tile is ‘walkable’.

This is used by the following method, to return our valid neighbours:

/**
 * returns all adjacent nodes that can be traversed
 *
 * @param node (Pair) finds the neighbors of this node
 * @return (int[][]) list of neighbors that can be traversed
 */
public int[][] getNeighbors(Pair node){
   int[][] neighbors = new int[8][2];
   int x = node.x;
   int y = node.y;
   boolean d0 = false; //These booleans are for speeding up the adding of nodes.
   boolean d1 = false;
   boolean d2 = false;
   boolean d3 = false;

   if (walkable(x,y-1)){
      neighbors[0] = (tmpInt(x,y-1));
      d0 = d1 = true;
   }
   if (walkable(x+1,y)){
      neighbors[1] = (tmpInt(x+1,y));
      d1 = d2 = true;
   }
   if (walkable(x,y+1)){
      neighbors[2] = (tmpInt(x,y+1));
      d2 = d3 = true;
   }
   if (walkable(x-1,y)){
      neighbors[3] = (tmpInt(x-1,y));
      d3 = d0 = true;
   }
   if (d0 && walkable(x-1,y-1)){
      neighbors[4] = (tmpInt(x-1,y-1));
   }
   if (d1 && walkable(x+1,y-1)){
      neighbors[5] = (tmpInt(x+1,y-1));
   }
   if (d2 && walkable(x+1,y+1)){
      neighbors[6] = (tmpInt(x+1,y+1));
   }
   if (d3 && walkable(x-1,y+1)){
      neighbors[7] = (tmpInt(x-1,y+1));
   }
   return neighbors;
}

The JPS algorithm should only be considering tiles which are ‘walkable’. This method takes a tile, looks at all its neighbours, and returns only those which are valid.

Walkability in Dinowar

I just wanted to highlight how you could modify this for other things. In Dinowar, we have the concept of ‘border tiles’ which surround territories. These are also not walkable.

We also have dinosaurs that can travel over water (but not land). In this case, we have to pass in a variable telling the method the type of dinosaur – and the method takes this into account when determining if a tile is ‘walkable’ for a particular dinosaur.

Running JPS

In our tutorial game, we generate a path when a player clicks, so the launching of JPS is done in PlayerCharacter.java. We will look at this in more depth next time.

Conclusion

We have seen how we are generating paths, and what to change if you want to integrate this code into your own project. In the next tutorial we will look at how we use the paths that this JPS algorithm has generated for us – how to follow them, and how to point our character in the right direction.



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.

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.