This document details the process of writing an A* (pronounced “a-star”) algorithm for QUT SoKoBan.

To find out more about QUT SoKoBan, click here.

If you want to learn about A* and other gaming techniques, consider the subject ITN649 OBJECT MODELLING FOR GAMES.

If you just want the source code, AStarRobot.java.

The A* algorithm is often used to find pathways in a computer game. Some of the reasons for using it are because it can be interrupted and resumed later and because it handles terrain with different traversal difficulty. For the purposes of SoKoBan we don't need either of those features, but we still want an algorithm to find the shortest path to a destination. A* will do this for us.

The purpose of the algorithm is to find the *shortest* path
from a point, **START**, to another point, **GOAL**. A* keeps a
list of all the possible next steps, called the **OPEN** list. It
then chooses a next step that is most likely to lead us to the goal
in the minimum time. In order to accomplish this we need to have a
heuristic that will determine “most likely”. Once that
step has been chosen, it is moved to the **CLOSED** list.

For each step the following information is available:

**g(n)** = the number of steps to
get from **START** to step **n**.

**h(n)** = the heuristic estimate of
the cost of getting from **n** to **GOAL**.

**f(n)** = **g(n)** + **h(n)**;
the minimum possible steps if we take step **n**.

For the record, we use n because in the general case it represents a node in a network data structure.

The algorithm becomes:

Add **START **to
**OPEN** list

while **OPEN**
not empty

get node **n**
from **OPEN** that has the lowest **f(n)**

if **n** is **GOAL**
then return path

move **n** to
**CLOSED**

for each **n'** =
CanMove(**n**, direction)

**g(n')**
= **g(n)** + 1

calculate **h(n')**

if **n'** in
**OPEN** list and new **n' ** is not better, continue

if **n'** in
**CLOSED** list and new **n'** is not better, continue

remove any **n'**
from **OPEN** and **CLOSED**

add **n**
as **n'**s parent

add **n'** to
**OPEN**

end for

end while

if
we get to here, then there is *No Solution*

In our case, the heuristic **h(n)** will be the minimum number
of moves to get to the goal if a clear path is possible between this
tile and the goal tile. Since we can only move in four directions,
that number is going to be the sum of the horizontal distance and the
vertical distance.

The
diagram above shows the minimum number of moves possible from the red
robot to the green box (if the wall weren't in the way).

For the green step in the diagram above,

**g(n)** = 1

**h(n)** = 6

**f(n)** = 1 + 6
= 7

To begin with we need to have a structure for our nodes:

class Node implements Comparable {

public Node parent;

public int move;

public Location where;

public int g;

public int h;

public int f(){return g+h;}

public Node(Location where, Node parent, int move);

public int compareTo(Object o);

}

The first problem that we face is that we would like to keep the
**OPEN** list sorted so that we
can quickly find our best guess. Originally I tried to use a
SortedList (TreeMap), but it doesn't allow duplicate keys. Since we
are sorting on **f(n)**
we need to be able to support duplicates. So instead I discovered
this neat little trick:

int index = Collections.binarySearch(list, n);

add(index<0?-index-1:index, n);

This adds an object to a list in a sorted way, which is exactly
what we need. The other problem is that we need to be able to find
nodes in the list by their location on the board. This is so that we
can determine if **n'** is
already in **OPEN **or
**CLOSED**. To do this we
declare a simple function:

public Node findByWhere(Location l) {

Iterator it = iterator();

while (it.hasNext()) {

Node element = (Node)it.next();

if (element.where.isSame(l))

return element;

}

return null;

}

The algorithm is implemented closely to what the pseudo code given previously says. The areas where it tends to diverge are:

for (int mov = Move.First; mov <= Move.Last; ++mov ) {

if (mov == Move.TurnBack(n.move)) // avoid backtracking

continue;

if (!gi.canMove(n.where, mov)) // avoid running into walls

continue;

...

}

The *for each* in the pseudo code is implemented by using
mov, which is an enumeration of moves, to progress through each one.

Remember that the move that is made to go from **n**
to **n'** is given by
n.move. Since we know this, we can trivially avoid backtracking to
our previous move, which gives us a speed improvement. Think of it
this way: it is theoretically possible to move forwards, then come
back, then go forwards again. Even though that is possible we know
that it will never be the shortest path so we can eliminate it from
consideration. The Move.TurnBack() function gives us the opposite
direction to the one we pass in.

Finally, there are two terminating conditions:

The goal was reached, return the list of moves as an array

No solution is possible, return null

We know there is no solution possible
when we have exhausted all our options. We know we have exhausted all
our options when we have no **OPEN** nodes left.

This implementation is not the best implementation of a Robot! If another robot is clever, it can block your path, which results in a

*no solution*.There are smarter uses for this algorithm than trying to run into boxes. Try figuring out how to get the robot to push the box onto the goal...

You might want to cache the moves list instead of re-calculating it every time.

The algorithm can be modified to only calculate

*x*moves at a time. This is what you would do if you were concerned about execution time. To do this, keep your**OPEN**and**CLOSED**lists between calls. Remember what**g(n)**was when called and calculate until (**g(n)**now –**g(n)**then) >*x,*then return the best option from the**OPEN**list.There are plenty of A* resources on the web. A google search might turn up more efficient implementations.

This source code is provided for learning purposes. You are welcome to use it in your bots. If you have any suggestions for improvements, please let me know!

To go back to the page on QUT SoKoBan, click here.