Game Character Path Finding in Java
- Breadth-First Search
- A* Search
- Applying the A* Search
- Enhancing the A* Search
- About This Article
This article is adapted from Developing Games in Java by David Brackeen (New Riders Publishing[http://www.newriders.com, 2003, ISBN 1-5927-3005-1).
So you need a creature or one of the player's characters to move from place to place in your game world. How do you do it?
Path finding can be reduced to answering the question "How do I get from point A to point B?" Generally, the path from one location to another location could potentially have several different solutions, but ideally, we want a solution that attains these goals:
How to get from A to B.
How to get around obstacles in the way.
How to find the shortest possible path.
How to find the path quickly.
In some cases no algorithm could attain any of these goals—for example, point A could be on an island completely isolated from point B. For every other case, we can use the A* algorithm—pronounced "A-star"—to attain all of these goals. It will find the shortest possible path from A to B (around obstacles too), and is fairly quick to compute.
The A* algorithm is a close relative to the simpler Breadth-first search algorithm and both are algorithms for searching a graph. A graph is a bunch of nodes grouped together by various edges, like in Figure 1.
)
Figure
1 A simple graph.
Each node in a graph 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 Figure 1, all the edges are bi-directional except for one.
The nodes can be interpreted as anything you wish. 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." A unidirectional edge could be useful in situations such as when it's possible to jump down a cliff but not possible to jump back up. I'll show you how to interpret a typical game environment as a graph later. But first, let's go over the easy-to-understand breadth-first search.
Breadth-First Search
We 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 Figure 1, the solution is easy to determine, but how would you find the solution in code? An easy solution is to use a breadth-first search.
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 start node are visited, then two edges away, and so on until all nodes are visited. This way, we'll 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 was found. An example of a breadth-first search is in Figure 2, where the nodes are numbered in the order they are visited.
)
Figure
2 An example breadth-first search. The nodes are numbered in the order of
the search.
To implement the breadth-first search algorithm, we'll first start with a basic node, which has a list of all its neighbors:
public class Node {
List neighbors;
Node pathParent;
}
The pathParent node is used for searching only. Think of the path from the start node to the goal node as a linked-list. The pathParent node is the node's parent in the path list. Once the goal is found, the path can be found by traversing up the path list from the goal node to the start node, like this:
protected List constructPath(Node node) {
LinkedList path = new LinkedList();
while (node.pathParent != null) {
path.addFirst(node);
node = node.pathParent;
}
return path;
}
Of course, this assumes the start node has no parent in the path.
Okay, now we're ready to implement the breadth-first search algorithm. One thing to keep in mind is that we want to be sure to only visit each node once. For example, if A has neighbors B and C, and B has neighbor A, we don't want to visit A again or we'll end up in an infinite loop.
So we'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, we'll ignore it. Likewise, we'll keep track of all the nodes we 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 to breadth-first search. However, taking a step back, it's easy to notice one problem with this search: We found the path with the least number of edges, but edges could have different "costs" associated with them. For example, the cost of traversing one edge could be 10 kilometers while the cost of traversing another could be 100 kilometers. Obviously, traversing two 10 km edges would be faster than a single 100 km edge. Breadth-first search assumes all edges have the same cost, which isn't good enough. This is where the A* algorithm comes in.