A* Search
An A* search works like breadth-first search, except with two extra factors:
The edges have different "costs," which are how much it costs to travel from one node to another.
The cost from any node to the goal node can be estimated. This helps refine the search, so we're less likely to go off searching in the wrong direction.
The cost between nodes doesn't have to be distance. The cost could be time, if you wanted to find the path that takes the shortest amount of time to traverse. For example, when you are driving, taking the back roads might be a shorter distance, but taking the freeway usually takes less time (freeways in Los Angeles excluded). Another example is terrain—traveling through overgrown forests could take longer than traveling through a grassy area.
Or, you could get more creative with the cost. For instance, if you want a creature to sneak up on the player, having the creature appear in front of the player could have a high cost, but appearing from behind could have little or no cost. You could take this idea further and assign a special tactical advantage to certain nodes—like getting behind a crate—which would have a smaller cost than just appearing in front of the player.
The A* algorithm works the same as breadth-first search, except for a couple of differences:
The nodes in the "open" list are sorted by the total cost from the start to the goal node, from smallest to largest cost. In other words, it's a priority queue. The total cost is the sum of the cost from the start node and the estimated cost to the goal node.
A node in the "closed" list can be moved back to the "open" list if a shorter path (less cost) to that node is found.
Since the "open" list is sorted by the estimated total cost, the algorithm checks nodes that have the smallest estimated cost first, so it searches the nodes that are more likely to be in the direction of the goal. Thus, the better the estimate, the faster the search.
Of course, the cost and the estimated cost need to be defined by you. If the cost is distance, this is easy: The cost between nodes is their distance, and the estimated cost from one node to the goal is simply a calculation of the distance from that node to the goal.
Note that this algorithm only works when the estimated cost is never more than the actual cost. If the estimated cost were more, the path found wouldn't necessarily be the shortest.
All right, let's get started on some code. First, we'll create a generic, abstract A* search algorithm that can be used for any type of A* search. The idea is that you'll be able to use this generic abstract class for lots of different situations, and because it's generic, the code will be easier to read. We'll start with an A* node, shown in Listing 1.
Listing 1 AStarNode.java
import java.util.List;
/**
The AStarNode class, along with the AStarSearch class,
implements a generic A* search algorithm. The AStarNode
class should be subclassed to provide searching capability.
*/
public abstract class AStarNode implements Comparable {
AStarNode pathParent;
float costFromStart;
float estimatedCostToGoal;
public float getCost() {
return costFromStart + estimatedCostToGoal;
}
public int compareTo(Object other) {
float thisValue = this.getCost();
float otherValue = ((AStarNode)other).getCost();
float v = thisValue - otherValue;
return (v>0)?1:(v<0)?-1:0; // sign function
}
/**
Gets the cost between this node and the specified
adjacent (AKA "neighbor" or "child") node.
*/
public abstract float getCost(AStarNode node);
/**
Gets the estimated cost between this node and the
specified node. The estimated cost should never exceed
the true cost. The better the estimate, the more
effecient the search.
*/
public abstract float getEstimatedCost(AStarNode node);
/**
Gets the children (AKA "neighbors" or "adjacent nodes")
of this node.
*/
public abstract List getNeighbors();
}
The AStarNode class is an abstract class that needs to be sub-classed to provide any search functionality. Like the node we used for breadth-first search, if contains the pathParent node used during the search process only. The costFromStart and estimatedCostToGoal are also filled in during the search, because these vary depending on which nodes are the start and goal nodes.
The getCost() abstract method returns the cost between the node and a neighbor node. The getEstimatedCost() abstract method returns the estimated cost between the node and the specified goal node. Remember, these functions have to be created by you, depending on what you want the "cost" to be.
Now, we'll implement the A* search, shown here in Listing 2.
Listing 2 AStarSearch.java
import java.util.*;
/**
The AStarSearch class, along with the AStarNode class,
implements a generic A* search algorithm. The AStarNode
class should be subclassed to provide searching capability.
*/
public class AStarSearch {
/**
A simple priority list, also called a priority queue.
Objects in the list are ordered by their priority,
determined by the object's Comparable interface.
The highest priority item is first in the list.
*/
public static class PriorityList extends LinkedList {
public void add(Comparable object) {
for (int i=0; i<size(); i++) {
if (object.compareTo(get(i)) <= 0) {
add(i, object);
return;
}
}
addLast(object);
}
}
/**
Construct the path, not including the start node.
*/
protected List constructPath(AStarNode node) {
LinkedList path = new LinkedList();
while (node.pathParent != null) {
path.addFirst(node);
node = node.pathParent;
}
return path;
}
/**
Find the path from the start node to the end node. A list
of AStarNodes is returned, or null if the path is not
found.
*/
public List findPath(AStarNode startNode, AStarNode goalNode) {
PriorityList openList = new PriorityList();
LinkedList closedList = new LinkedList();
startNode.costFromStart = 0;
startNode.estimatedCostToGoal =
startNode.getEstimatedCost(goalNode);
startNode.pathParent = null;
openList.add(startNode);
while (!openList.isEmpty()) {
AStarNode node = (AStarNode)openList.removeFirst();
if (node == goalNode) {
// construct the path from start to goal
return constructPath(goalNode);
}
List neighbors = node.getNeighbors();
for (int i=0; i<neighbors.size(); i++) {
AStarNode neighborNode =
(AStarNode)neighbors.get(i);
boolean isOpen = openList.contains(neighborNode);
boolean isClosed =
closedList.contains(neighborNode);
float costFromStart = node.costFromStart +
node.getCost(neighborNode);
// check if the neighbor node has not been
// traversed or if a shorter path to this
// neighbor node is found.
if ((!isOpen && !isClosed) ||
costFromStart < neighborNode.costFromStart)
{
neighborNode.pathParent = node;
neighborNode.costFromStart = costFromStart;
neighborNode.estimatedCostToGoal =
neighborNode.getEstimatedCost(goalNode);
if (isClosed) {
closedList.remove(neighborNode);
}
if (!isOpen) {
openList.add(neighborNode);
}
}
}
closedList.add(node);
}
// no path found
return null;
}
}
The PriorityList inner class is a simple LinkedList that adds nodes using an insertion sort. In this case, only AStarNode instances are added, keeping the list sorted from lowest cost to highest. Nodes are only removed from the front of the list (lowest cost first).
The findPath() function is very similar to the breadth-first search implementation, except for a couple of changes. The costFromStart and estimatedCostToGoal fields are calculated as we go along. Also, a node is moved from the "closed" list to the "open" list if a shorter path to that node is found. Other than that, they're pretty much the same.
That's it for the basics of the A* algorithm. The next step is to actually apply this algorithm in a game.