Basics of the A* Algorithm

An A*—pronounced "A-star"—search works like a breadth-first search, except with two extra factors:

  • The edges have different "costs," which is 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 that you'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 bot to sneak up on the player, having the bot 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—such as 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. 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.

Because 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 is, the faster the search is. Of course, you need to define the cost and the estimated cost. If the cost is distance, this is easy: The cost between nodes is their distance, and the cost from one node to the goal is simply a calculation of the distance from that node to the goal. Note that this algorithm works only 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, you'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. You'll start with an A* node, shown in Listing 12.1.

Listing 12.1 AStarNode.java
package com.brackeen.javagamebook.path;
import java.util.List;
import com.brackeen.javagamebook.util.MoreMath;
/**
 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 otherValue = ((AStarNode)other).getCost();
 float thisValue = this.getCost();
 return MoreMath.sign(thisValue - otherValue);
 }
 /**
 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
 efficient 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 subclassed to provide any search functionality. Like the node used for the breadth-first search, it contains the pathParent node used during the search process only. costFromStart and estimatedCostToGoal are also filled in during the search because these vary depending on where the start and goal nodes are. The getCost(node) abstract method returns the cost between the node and a neighbor node. The getEstimatedCost(node) abstract method returns the estimated cost between the node and the specified goal node. Remember, you have to create these functions, depending on what you want the cost to be. Now you'll implement the A* search, shown here in Listing 12.2.

Listing 12.2 AStarSearch.java
package com.brackeen.javagamebook.path;
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 removed only from the front of the list (lowest cost). 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 you 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.

Screenshot


   
Comments