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.

Leave a Reply

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