[ Contents | Who Am I? | Resume | Jokes | Products | A* Tutorial | Programmers book shelf | Java | Win95 | Guestbook | Send Email ]

Visitors Jan'00

Updated Jul'01

Site hosted on

Game Programming Gems

Amazon.com associate
In Association with amazon.com
Amazon.co.uk associate
In Association with amazon.co.uk
NEW I have updated the programmers book shelf page.


A* algorithm tutorial

Contents

  • Introduction
  • State space search
  • 8 Puzzle
  • Map route finding
  • Implementing A*
  • Priority Queues
  • Linked lists

Feedback is welcome... Let me know how this page could be improved.
Email : justinhj@hotmail.com
Author : Justin Heyes-Jones BSc


Click for my home page

Introduction

This document contains a description of the AI algorithm known as A*, and two example programs showing the kind of problems it can solve.

Since many people have requested the source code to the example programs that were on here (and in fact are still on the downloads page), I have included C++ source code and two example problems.

Please have a look at Steven Woodcock's great and large site at this address... http://www.gameai.com

http://tawny.cs.nott.ac.uk/~sbx/winnie/aim/search/search3.htm#ASTAR is also a good resource.

Also the pseudo code I found most helpful for implementing the algorithm, as well as some very good explanations of how to use it, can be found on the Game Developer Mag site, http://www.gdmag.com/stout.htm. Brian Stout, the author of this article, also created a useful PC program that allows you to experiment with types of search including the A* search, and watch them in real time.

State space search

Almost any problem can be solved (given infinite resources) by using a search program. You have to find a way to describe the problem in terms of a set of states, and rules you can apply to get between those states. Imagine the state space as being a tree with the start of your problem as the root, and expanding downwards branching at each point depending on how many rules you can apply at each point.

To solve a problem described like this you just find the first goal state in this tree and make a path back up to the start.

The problem is that even quite simple problems create huge trees for you to search. The A* algorithm requires help to search the tree in the most efficient way. You provide it with a heuristic. This returns an evaluation of how good each state is, so that the search can go down the most promising routes first.

8 Puzzle

A good example of a search problem is the 8 puzzle. This is a simple sliding tile puzzle on a 3*3 grid where one tile is missing and you can move the other tiles into the gap until you get the puzzle into the goal position.

Although not exactly a real life problem, or even the kind of problem your video game enemies are likely to need to do, it is a great example of how to represent the states and rules for the purpose of example. It is also quite hard to solve. There are 362,880 different states that the puzzle can be in, and to find a solution the search has to find a route through them.

The 8 puzzle game state is as simple as representing a list of the 9 squares and what's in them. Here are two states for example; the last one is the GOAL state, at which point we've found the solution. The first is a jumbled up example that you may start from.

A start state [ C, E, H, D, G, F, B, A, SPACE ]
Goal state [ A, B, C, H, SPACE, D, G, F, E ]

The rules that you can apply to the puzzle are also simple. If there is a blank tile above, below, to the left or to the right of a given tile, then you can move that tile into the space. To solve the puzzle you need to find the path from the start state, through the "OR graph" as the tree is known, down to the GOAL state. We've reduced the abstract problem of how to do a puzzle to a simple search.

What makes the problem useful from an academic point of view is that it is hard to write a good heuristic function. The heuristic I used here is to add the distances together that each tile is from where it should be. Then, since the tiles are clockwise around the centre in the goal state, tiles get 2 points added to the heuristic (low is good in heuristic terms) if they are not followed by the tile they should be followed by in a clockwise direction.
Although usually effective this does not work for every arrangement.

The example program puzzle.zip (Win95 DirectX only) shows this particular problem being solved using the algorithm. The puzzle is solved, then the program walks through the solution on screen for you. When it's done you can mess it up and watch it solve the puzzle from the new position. The program shows how many states it has evaluated giving some idea of the size of the search space for even such a simple puzzle.

Map route finding

The most common use for A* in games is pathfinding. For clarity the example program is pretty simple but should show you the basic principles of using A* to move your enemies intelligently around objects and mazes.
Each state is simply where you are, stored as say a grid co-ordinate. The rules that you can apply to each state are similar to the 8-puzzle. At each point you can move up to 4 directions depending on whether you're at the edge of the map and whether walls block your path.

The example program can be downloaded here map.zip. (Win95 DirectX only)

Implementing A*

The idea is to search the state space and find the shortest route to the goal state. I'll refer to the demo program through-out and include bits of code where appropriate.

During the search we need to keep track of two lists of states (referred to as nodes as well from now on, as they are nodes in a tree). The first list is the OPEN list. This stores nodes which we have generated by using the rules from an existing node, but we don't yet know where they lead to.
The second list is nodes that we have generated and we have also explored where they go.

Each state is stored along with some extra data required to help us in our search. The first thing that is required is a parent pointer. We need to know how we got to this node, as the end result of finding the GOAL state will be to generate a path back to the start. Tracking which node parented this node allows to do this.

The node also has three ratings used during the search which are the cost of the node, the heuristic estimate of this node and 'f' which is the total of the other two.

The cost of a node is easy to work out. Each move can usually be assigned a cost. In the example program on a simple grid, the cost is always one, but since we want to know the cost of the path all the way from the start to this node, when we generate a node we add its cost to the cost of its parent.

The heuristic estimate can be much more complexas we have seen. We can guess how good the node is by how near it is to the GOAL. This works well on the tiled maze. In practice though the more help you give the algorithm the better. For example, if you know that all your enemies are going to go through a door on the map to get into a certain area, then the heuristic would need to support that.
In the case of my grid I'm using the x and y difference between the node and the GOAL as a heuristic.

Finally the 'f' rating of a node, which represents how good it is in terms of how much it cost to get there and how near to the goal we are, is used throughout the search to always follow the most promising path.

Here's the "Pseudo C" for the search as I implemented it.

ascode.txt

Simple as that. If you run the demo you can move the pacman about with the cursor keys and watch the generated path change. If you hold down the Ctrl key you can move the target cherries around with the same cursor keys.

The best way to really understand the algorithm is to watch it working. Run the demo with the command line argument 'showsearch' and it will slowly step through a search, and show squares that are on the OPEN list with O, and squares on the CLOSED list as C.

Most A* implementations I've seen on the web use a simple linked list to do the OPEN list of nodes. This is a bad idea because you need to retrieve the lowest 'f' valued item, and doing that in an un-ordered list is slow. The next section will describe the way I implemented the Priority Queue data structure which is used instead. A priority queue is a neat algorithm based on a heap, which is perfect for our purposes.

Another important issue is the data structure and algorithm you select for the CLOSED list. As pointed out by Aneel Nazareth, a hash table is very useful for this purpose. When I next spend some time on this tutorial I will implement the CLOSED list in this way and provide more of the source code for the project.

Thanks to Steve Rabin for pointing out an error in my pseudo code which may have caused problems in implenetation. I'd forgotten to point out that in the end of NodePushSuccessors you must not add the new_node that you've created to the OPEN list, if it is already on it. Don't worry the algorithm as stated should work fine now.

Priority Queues and Heaps

References? I got this info on heaps and in particular the stuff on using them from "Dr Dobb's Essential Books on Algorithms and Data Structures" which should be in every programmers libarary as it iss extremely useful. The Heap and PQueue stuff is the whole of Chapter 9 in the book "Data structures from arrays to Priority Queues". I've included my own source for the PQueue algorithm pqueue.cpp, because it's reasonably short, and I'll describe in this section briefly how the code works. I recommend you read up the formal theory somewhere but the provided code should explain them pretty well.

A heap is a 'leftist-tree'. The heap always grows like this ...

A    add a node      A       
                    B        



add another  A  and another  A
            B C             B C
                           D                             

If you remove nodes you must maintain this structure. Another thing that makes them cool for the priority queue is that they are sorted from top to bottom. If you sort them so that the top item has the lowest value then they are perfect for the A* algorithm which sorts on lowest f values.

A useful thing about this data structure is that if we know how big our open list is going to get we can store the queue as an array. The array represents the tree. We leave element 0 blank because then we have the useful property that any nodes children are at the array of the index parent *2 and *2+1.
In the same way a nodes parent is at the index given by the nodes array index /2;
The push and pop functions in the source files add and take away nodes from the tree making sure that the tree is still leftist (all the layers above the bottom layer are filled and the bottom layer is filled left to right), and making sure that from top to bottom the nodes are sorted in descending order. You provide an application specific routine to return the rating of a node.

Linked lists

I won't go into detail here. The code is here if you want a look, list.c, but otherwise, linked lists are pretty simple. Your node has a next pointer to the node following it, and my list structure maintains a head (start of list) and a tail (end of list).


Copyright 1998 Justin Heyes-Jones
All rights Reserved.
Linking to this site is welcome and encouraged, but reproduction in whole or in part either on the WWW or other media is prohibited under appropriate copyright laws. Please ask for permission first.

No warranty provided for use of software, either expressed or implied.

1