Generic Path Finding

The A* search function you created returns a list of AStarNodes, which is great for generic implementation but isn't too friendly when you need something more concrete. Really, you want something like a list of locations, as in the PathFinder interface in Listing 12.6.

Listing 12.6 PathFinder.java

/**
 The PathFinder interface is a function that finds a path
 (represented by a List of Vector3Ds) from one location to
 another, or from one GameObject to another. Note that the
 find() method can ignore the requested goal, and instead
 give an arbitrary path, like patrolling in a set path or
 running away from the goal.
*/
public interface PathFinder {
 /**
 Finds a path from GameObject A to GameObject B. The path
 is an Iterator of Vector3Ds, not including the start
 location (GameObject A) but including the goal location
 (GameObject B). The Vector3D objects may be used in
 other objects and should not be modified.
 Returns null if no path found.
 */
 public Iterator find(GameObject a, GameObject b);
 /**
 Finds a path from the start location to the goal
 location. The path is an Iterator of Vector3Ds, not
 including the start location, but including the goal
 location. The Vector3D objects may be used in other
 objects and should not be modified. Returns null if no
 path found.
 */
 public Iterator find(Vector3D start, Vector3D goal);
}

In this interface, two methods are provided: one to find a path between two points, and another to find a path between two objects. The specification of the interface says that these functions should return Iterator objects that iterate over a list of Vector3D locations. So, if you use PathFinder, it doesn't matter what the underlying algorithm is, whether it is A*, random, or some other idea. Also, you can use this interface for other types of paths, such as simple paths that follow the perimeter of a room or a flocking bird pattern as a background effect. You'll use the PathFinder interface a lot in the next chapter. But, hey, we're getting ahead of ourselves here! First, let's create an implementation of the PathFinder interface for finding the shortest path between two points in a BSP tree using the A* algorithm. Sound like a mouthful? Well, at least the AStarSearchWithBSP class in Listing 12.7 is straightforward.

Listing 12.7 AStarSearchWithBSP.java

package com.brackeen.javagamebook.path;
import java.util.*;
import com.brackeen.javagamebook.game.GameObject;
import com.brackeen.javagamebook.math3D.Vector3D;
import com.brackeen.javagamebook.bsp2D.BSPTree;
import com.brackeen.javagamebook.bsp2D.Portal;
/**
 The AStarSearchWithBSP class is a PathFinder that finds
 a path in a BSP tree using an A* search algorithm.
*/
public class AStarSearchWithBSP extends AStarSearch
 implements PathFinder
{
 private BSPTree bspTree;
 /**
 Creates a new AStarSearchWithBSP for the specified
 BSP tree.
 */
 public AStarSearchWithBSP(BSPTree bspTree) {
 this.bspTree = bspTree;
 }
 public Iterator find(GameObject a, GameObject b) {
 return find(a.getLocation(), b.getLocation());
 }
 public Iterator find(Vector3D start, Vector3D goal) {
 BSPTree.Leaf startLeaf = bspTree.getLeaf(start.x, start.z);
 BSPTree.Leaf goalLeaf = bspTree.getLeaf(goal.x, goal.z);
 // if start and goal are in the same leaf, no need to do
 // A* search
 if (startLeaf == goalLeaf) {
 return Collections.singleton(goal).iterator();
 }
 AStarNode startNode = new LeafNode(startLeaf, start);
 AStarNode goalNode = new LeafNode(goalLeaf, goal);
 // temporarily add the goalNode we just created to
 // the neighbors list
 List goalNeighbors = goalNode.getNeighbors();
 for (int i=0; i<goalNeighbors.size(); i++) {
 Portal portal = (Portal)goalNeighbors.get(i);
 portal.addNeighbor(goalNode);
 }
 // do A* search
 List path = super.findPath(startNode, goalNode);
 // remove the goal node from the neighbors list
 for (int i=0; i<goalNeighbors.size(); i++) {
 Portal portal = (Portal)goalNeighbors.get(i);
 portal.removeNeighbor(goalNode);
 }
 return convertPath(path);
 }
 /**
 Converts path of AStarNodes to a path of Vector3D
 locations.
 */
 protected Iterator convertPath(List path) {
 if (path == null) {
 return null;
 }
 for (int i=0; i<path.size(); i++) {
 Object node = path.get(i);
 if (node instanceof Portal) {
 path.set(i, ((Portal)node).getMidPoint());
 }
 else {
 path.set(i, ((LeafNode)node).location);
 }
 }
 return Collections.unmodifiableList(path).iterator();
 }
}

The actual searching in the find() method is just like we said it would be: First, you create temporary nodes representing the start and goal nodes, add them to the graph, and then perform the search. After the search, you clean up by removing those temporary nodes from the graph. Also, if the start location and the goal location are in the same leaf of the BSP tree, no search needs to be performed, so the method just returns an Iterator over the goal location. The convertPath() method converts a list of AStarNodes to actual locations. Here, you use the midpoint of each portal as the location to use. Another idea instead of using the midpoint is to use a point within the portal that is closest to the location on either side of it, as long as you leave room for the size of the object. But midpoints work well, so you can stick with that simpler solution.