Creating an A* algorithm Robot for QUT SoKoBan

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

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



The SoKoBan Case

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



Implementation Discussion




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:

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

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



Notes



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