Some Initial Path-Finding Attempts

If the environment is flat with no obstacles, path finding is no problem: The bot can just move in a straight line to its destination. But when obstacles occur between point A and point B, things get a little hairy. For example, in Screenshot, if the bot just moves straight toward the player, it will end up just hitting a wall and getting stuck there.

This behavior might be fine for some games because it doesn't really matter what the bots do; it matters only what they appear to do. In a 3D world from the player's perspective, it might look like the bot is just waiting behind the wall for the player instead of being stuck. A bird's-eye perspective is a different story. Path finding is virtually required for games with bird's-eye perspectives, such as real-time strategy games or for games like The Sims. You wouldn't want to tell a team of fighters to attack something but have the team not be able to do it because the destination was on the other side of the wall! Come on now, use the door. Also, making a bot smart enough to find a path around an obstacle makes it more interesting for the player and harder to "trick" the bot into doing something or moving a certain way. Several techniques can be used to get around obstacles. A randomized algorithm finds a solution eventually, if there is one. This technique makes the bot walk around randomly, like in Screenshot, until it finds what it is looking for.

Of course, the randomized algorithm doesn't give the best-looking results or the shortest path. Who wants to watch a bot move around randomly like it's missing a circuit or two? This random algorithm could be modified to move randomly only occasionally and at other times move directly toward the player, which would make the bot's movement appear slightly more intelligent. Another solution can be found when the environment is a simple maze with no loops, like in Screenshot. Here, the path-finding algorithm is the "right hand on the wall" algorithm (or the "left hand on the wall" algorithm, if you're into that sort of thing). Just keep your right hand on the wall as you move through the maze, and eventually you'll find the destination.

If a bot follows the "right hand" algorithm literally, it will rarely find the shortest path from A to B. Alternatively, the path could be calculated ahead of time, before the bot makes any moves. Then any backtracking (such as when venturing into the lower-right hall in the figure) could be removed from the path, leaving a shortest-path solution. However, this algorithm works only for the simple case of a maze with no loops. If a loop was in the path, the bot would veer to the right forever. Also, if rooms had wide spaces, the bot might never find its destination in the middle of a room because the bot is always next to a wall. Ideally, you'll probably want to create more intricate environments than this. Instead of looking at the environment as a grid, we'll look at it as a graph, like in Screenshot. A graph is simply a bunch of nodes grouped by various edges.

Each node of the graph could be anything. For example, a node could be a cell in a 2D grid. Or, a node could be a "city," with the edges of the graph representing highways. And remember, when finding the path from A to B, any node can be the start or goal node. A graph is similar to a tree, as discussed in , "3D Scene Management Using BSP Trees," except that, instead of each node having up to two children, each node can have an indefinite number of children, or neighbors. Some graphs are directed, meaning that an edge between two nodes can be traversed in only one direction. Looking at the example in Screenshot, all the edges are bidirectional except for one. A unidirectional edge could be useful in such situations as when traveling involves jumping down a cliff that is too high to jump back up. In this example, you want to find the shortest path from node A to node B, or the fewest number of traversed edges to get to the goal. Looking at the figure, the solution is easy to determine, but how would you find the solution in a computer program? An easy solution is to use a breadth-first search.

Breadth-First Search

Like traversing BSP trees, a breadth-first search involves visiting nodes one at a time. A breadth-first search visits nodes in the order of their distance from the start node, where distance is measured as the number of traversed edges. So, with a breadth-first search, first all nodes one edge away from the goal are visited, then those two edges away are visited, and so on until all nodes are visited. This way, you find the path from the start to the goal with the minimum number of traversed edges. Another way to word it is like this: Visit the neighbor nodes, then the neighbor's neighbor nodes, and so on until the goal node is found. An example of a breadth-first search is in Screenshot, in which the nodes are numbered in the order they are visited.

Later in this chapter, you'll use the A* search algorithm, which has several similarities to a breadth-first search. But first, to better understand A*, you'll implement the easy-to-understand breadth-first search algorithm. First, start with a basic node, which has references to all its neighbors:

public class Node {
 List neighbors;
 Node pathParent;
}

The neighbors list is simply a list of all the nodes' neighbors. The pathParent node is used for searching only. Think of the path from the start node to the goal node as a tree, with each node having only one child. The pathParent node is the node's parent in the path tree. When the goal is found, the path can be found by traversing up the path tree from the goal node to the start node, like this:

private List constructPath(Node node) {
 LinkedList path = new LinkedList();
 while (node.pathParent != null) {
 path.addFirst(node);
 node = node.pathParent;
 }
 return path;
}

Of course, this assumes that the start node has no parent in the path. Okay! Now you're ready to implement the breadth-first search algorithm. One thing to keep in mind is that you want to be sure to only visit each node once. For example, if A has neighbors B and C, and B has neighbor A, you don't want to visit A again or you'll end up in an infinite loop. So, you'll keep track of all nodes that have been visited by putting them in a "closed" list. If a node shows up in the search that's already in the closed list, you'll ignore it. Likewise, you'll keep track of all the nodes you want to visit in an "open" list. The open list is a first in, first out list, effectively sorting the list from smallest number of edges from the start goal to the largest. Here's the full code:

public List search(Node startNode, Node goalNode) {
 // list of visited nodes
 LinkedList closedList = new LinkedList();
 // list of nodes to visit (sorted)
 LinkedList openList = new LinkedList();
 openList.add(startNode);
 startNode.pathParent = null;
 while (!openList.isEmpty()) {
 Node node = (Node)openList.removeFirst();
 if (node == goalNode) {
 // path found!
 return constructPath(goalNode);
 }
 else {
 closedList.add(node);
 // add neighbors to the open list
 Iterator i = node.neighbors.iterator();
 while (i.hasNext()) {
 Node neighborNode = (Node)i.next();
 if (!closedList.contains(neighborNode) &&
 !openList.contains(neighborNode))
 {
 neighborNode.pathParent = node;
 openList.add(neighborNode);
 }
 }
 }
 }
 // no path found
 return null;
}

This function returns a list of nodes that represent the path, not including the start node. If a path can't be found, it returns null. That's all there is for breadth-first search. However, taking a step back, it's easy to notice one problem with this search: You found the path with the least number of edges, but edges could have different "costs" associated with them. For example, the cost of one edge could be 10km, while the cost of another could be 100km. Obviously, traversing two 10km edges would be faster than traversing a single 100km edge. Breadth-first search assumes all edges have the same cost, which isn't good enough. This is where the A* algorithm comes in.