## 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.