Making a PathBot

Here's something you might have already thought about: Let's say you have a bot that finds a path to the player and starts to follow it, but by the time the bot reaches the goal location, the player is long gone. Kinda pointless, eh? You could recalculate the path every frame, but what a waste of resources! Performing an A* search makes quite a few temporary objects and takes up a chunk of processor power (including several Math.sqrt() calls), so you don't want a bot to recalculate the path every frame. Also, the player or any other goal location isn't likely to change much from frame to frame, so the path wouldn't need to change much, either. Instead, you can just keep a calculated path around for a while and recalculate it occasionally, every few seconds or so. This way, the path is fairly up-to-date but doesn't hog the processor or waste memory. Another thought along those lines is, what if you have several bots calculating their path at the exact same time? You might see little drops in the frame rate of the game as this happens because several bots are hogging the processor at once. To alleviate this, you can just take the easy route and make sure each bot starts calculating a path after a random amount of time. In this case, you'll make sure bots don't calculate the path until 0 to 1000 milliseconds have passed. Another idea is to cache common A* searches from portal to portal (not including start and goal nodes). This way, two bots in the same room can share a path, and a path that's already been calculated wouldn't need to be calculated again. All right, let's do it. You'll make that bot here in Listing 12.8. The PathBot follows the path given to it from a PathFinder. It has a few default attributes, such as its speed, how fast it can turn, and how high above the floor it "flies." The turn speed is purely cosmetic—the bot will turn to face the direction it's facing, but the turn speed doesn't affect how fast a bot travels along a path.

Listing 12.8
package com.brackeen.javagamebook.path;
import java.util.Iterator;
import com.brackeen.javagamebook.path.PathFinder;
import com.brackeen.javagamebook.math3D.*;
 A PathBot is a GameObject that follows a path from a
public class PathBot extends GameObject {
 // default values
 protected PathFinder pathFinder = null;
 protected Vector3D facing = null;
 protected long pathRecalcTime = 4000;
 protected float turnSpeed = .005f;
 protected float speed = .25f;
 protected float flyHeight = 64;
 // for path following
 protected Iterator currentPath;
 protected Vector3D nextPathLocation = new Vector3D();
 protected long timeUntilPathRecalc;
 public PathBot(PolygonGroup polygonGroup) {
 public boolean isFlying() {
 return (flyHeight > 0);
 Sets the PathFinder class to use to follow the path.
 public void setPathFinder(PathFinder pathFinder) {
 if (this.pathFinder != pathFinder) {
 this.pathFinder = pathFinder;
 currentPath = null;
 // random amount of time until calculation, so
 // not all bot calc the path at the same time
 timeUntilPathRecalc = (long)(Math.random() * 1000);
 Sets the location this object should face as it follows
 the path. This value can change. If null, this object
 faces the direction it is moving.
 public void setFacing(Vector3D facing) {
 this.facing = facing;
 public void update(GameObject player, long elapsedTime) {
 if (pathFinder == null) {
 super.update(player, elapsedTime);
 // update the path to the player
 if (timeUntilPathRecalc <= 0) {
 currentPath = pathFinder.find(this, player);
 if (currentPath != null) {
 timeUntilPathRecalc = pathRecalcTime;
 // follow the path
 if (currentPath != null && currentPath.hasNext() &&
 getTransform().moveTo(nextPathLocation, speed);
 // face either the direction we are traveling,
 // or face the specified face location.
 Vector3D faceLocation = facing;
 if (faceLocation == null) {
 faceLocation = nextPathLocation;
 faceLocation.x - getX(),
 faceLocation.z - getZ(),
 (float)-Math.PI/2, turnSpeed);
 super.update(player, elapsedTime);
 When a collision occurs, back up for 200ms and then
 wait a few seconds before recalculating the path.
 protected void backupAndRecomputePath() {
 // back up for 200 ms
 if (!isFlying()) {
 nextPathLocation.y = 0;
 getTransform().setVelocity(nextPathLocation, 200);
 // wait until computing the path again
 currentPath = null;
 timeUntilPathRecalc = (long)(Math.random() * 1000);
 public void notifyWallCollision() {
 public void notifyObjectCollision(GameObject object) {

PathBot is fairly uncomplicated. It keeps track of how much time is left until the path is recalculated again, and if that amount of time has passed, the path is recalculated in the update() method. The rest of the update() method simply follows the path in this manner:

  1. The bot's transform is set to move to the first location in the path.

  2. When the bot has finished moving, the next location in the path is chosen.

  3. If there are no more locations in the path, the bot stops until the path is recalculated.

Also note that the bot turns to look at the location specified by the facing vector. If this value is null, the bot just looks at the direction it's traveling. You'll use this later when you want a bot to focus its attention on, say, the player. The last thing that PathBot does is handle collisions. If a collision with a wall or an object is detected, the bot backs up, stops, and then waits a few seconds before recalculating the path. That's it for path finding! The source code with this tutorial also includes the PathFindingTest class, which creates a few pyramid-shape PathBots in the same 3D map used in the last couple of chapters. The PathBots follow the player around, no matter where the player is. No matter where you go, the ninjas will find you!