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.

Leave a Reply

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