I’m reading AI Application Programming and it’s pretty interesting. All the examples are in C so I decided to implement them in Java and share them here. The first chapter is on the A-Star algorithm. The A-Star algorithm is a technique for finding the best path through a maze given a starting point and a known destination. Because the destination is known via a linear path the A-star algorithm can use a heuristic to identify which node to test next, rather then move blindly through the state space like a DFS or BFS.
Here is the source for the A-Star algorithm in Java. astar.tar.gz
My code differs slightly from the example in the book. First off there are only 2 main classes Maze.java and Square.java. There is a 3rd class called RunMaze.java that contains the main() function for execute the program. RunMaze is pretty simple, we create a Maze, tell it to draw itself, and then ask it to find the best path to our goal.
public class RunMaze {
/**
* @param args
*/
public static void main(String[] args) {
Maze maze = new Maze(20, 20);
maze.draw();
maze.findBestPath();
}
}
The example in the AI book requires that you provide a maze manually and then run the algorithm against the maze and it will find a solution. I though it would be cool to have the Maze generate itself randomly and choice a goal node on the fly. The Maze class does all this and it even knows how to draw itself.
When you create a new Maze object the init() method is called and a Square object representing an x/y coordinate is created for each position in the Maze.
public Maze(int rows, int columns) {
this.rows = rows;
this.columns = columns;
elements = new Square[rows][columns];
init();
}
private void init() {
createSquares();
setStartAndGoal();
generateAdjacenies();
}
private void setStartAndGoal() {
elements[0][0].setStart(true);
Random random = new Random();
int goalX = 0, goalY = 0;
while (goalX == 0 && goalY == 0) {
goalX = random.nextInt(rows);
goalY = random.nextInt(columns);
}
goal = elements[goalX][goalY];
goal.setEnd(true);
}
private void generateAdjacenies() {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
elements[i][j].calculateAdjacencies();
}
}
}
private void createSquares() {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
elements[i][j] = new Square(i, j, this);
}
}
}
Each square then randomly calculates if it has an adjacent square to its' bottom and right. If an adjacency is found, then the square adds a references to the adjacent square to itself and adds itself as an adjacent square to it's neighbor.
public void calculateAdjacencies() {
int top = x - 1;
int bottom = x + 1;
int left = y - 1;
int right = y + 1;
if (bottom < maze.getRows()) {
if (isAdjacent()) {
maze.getSquare(bottom, y).addAdjacency(this);
this.addAdjacency(maze.getSquare(bottom, y));
}
}
if (right < maze.getColumns()) {
if (isAdjacent()) {
maze.getSquare(x, right).addAdjacency(this);
this.addAdjacency(maze.getSquare(x, right));
}
}
}
As previously mentioned we use heuristics to test each Square to represent the cost of moving throughout our problem space in relation to a given square. The three values are the localCost, the parentCost, and the passThrough cost.
private double localCost; // cost of getting from this Square to goal
private double parentCost; // cost of getting from parent Square to this Square
private double passThroughCost; // cost of getting from the starting Square to the
// goal via this Square
The text describe the localCost as being a standard Manhattan distance function, providing a grid distance between 2 points. The local cost defines the cost of moving along one axis, which we'll define as 1.0. The equation for calculating the local cost looks like this.
public double getLocalCost(Square goal) {
if (isStart()) {
return 0.0;
}
localCost = 1.0 * (Math.abs(x - goal.getX()) + Math.abs(y - goal.getY()));
return localCost;
}
The parentCost value uses 2 contants, The first being once again assumes a minimum cost of 1.0. and adds that to our alpha (for our example we will use an alpha of 0.5) and is multiplied by our parent square's parentCost - 1.0. Here is the code for the parentCost
public double getParentCost() {
if (isStart()) {
return 0.0;
}
if (parentCost == 0.0) {
parentCost = 1.0 + .5 * (parent.getParentCost() - 1.0);
}
return parentCost;
}
Finally the passThrough cost represents the cost of going through this given Square from the starting square en route to our goal square. The passThrough cost is simply, passThroughCost = localCost + parentCost.
public double getPassThrough(Square goal) {
if (isStart()) {
return 0.0;
}
return getLocalCost(goal) + getParentCost();
}
So, moving on to the algorithm, the A-Star begins with 2 lists, they are the opened and closed lists. The open list contains squares that are to be examined and the closed list contains squares that have already been examined. We start by grabbing the squares adjacent to our starting square and placing them on the opened list.
Next while there are items left to examine on the opened list, we retrieve the square with the best passThroughCost from the opened list. That square is then removed from the opened list and added to our closed list.
We then check to see if this Square is the goal node. If so great then we are done. We then reconstruct the path back to the start via each squares parent reference and draw out the maze again showing the best path to the goal. If this isn't the goal node we have a bit more work to do.
First we get it's adjacent squares. Then for each square we check to see if the adjacent square is on the opened or closed list. If so we check to see if the passThroughCost of the square currently on the list is less then the passThroughCost of that square if we were to use our current best square as the parent. If the cost is less, we simply continue and do nothing else with this adjacent square, but if the cost is more we do the following.
- Set the parent of the adjacent square to be to be our current best square.
- Remove the neighbor from our opened and closed list
- Add the neighbor back to our opened list in the first position
public void findBestPath() {
System.out.println("Calculating best path...");
Set adjacencies = elements[0][0].getAdjacencies();
for (Square adjacency : adjacencies) {
adjacency.setParent(elements[0][0]);
if (adjacency.isStart() == false) {
opened.add(adjacency);
}
}
while (opened.size() > 0) {
Square best = findBestPassThrough();
opened.remove(best);
closed.add(best);
if (best.isEnd()) {
System.out.println("Found Goal");
populateBestList(goal);
draw();
return;
} else {
Set neighbors = best.getAdjacencies();
for (Square neighbor : neighbors) {
if (opened.contains(neighbor)) {
Square tmpSquare = new Square(neighbor.getX(),
neighbor.getY(), this);
tmpSquare.setParent(best);
if (tmpSquare.getPassThrough(goal) >= neighbor
.getPassThrough(goal)) {
continue;
}
}
if (closed.contains(neighbor)) {
Square tmpSquare = new Square(neighbor.getX(),
neighbor.getY(), this);
tmpSquare.setParent(best);
if (tmpSquare.getPassThrough(goal) >= neighbor
.getPassThrough(goal)) {
continue;
}
}
neighbor.setParent(best);
opened.remove(neighbor);
closed.remove(neighbor);
opened.add(0, neighbor);
}
}
}
System.out.println("No Path to goal");
}
When you run the program it will generate the maze and draw it, it will then attempt to find the best path to the goal. If no path is found the program will terminate saying "No Path to goal". Otherwise if the best path is found, the program will redraw the maze showing the best path to the goal.
Drawing maze + - + - + - + - + - + - + - + - + - + - + | S | | | | | | | | | + + + - + + - + + - + + + + | | | | | | | + + + - + + + - + + - + + + | | | | | | | + + - + + + - + - + + + - + + | | | | | | | | + + - + - + + + - + + + - + - + | | | | | | | | | + - + - + - + + + - + - + - + + + | | | | | | | | | + - + - + + - + + + - + + + - + | | | | | | | + + + - + + + + - + - + + + | | | | | | + + - + + - + + - + - + + - + + | | G | | | + - + - + - + + + + + + - + + | | | | | | + - + - + - + - + - + - + - + - + - + - + Calculating best path... Found Goal Drawing maze + - + - + - + - + - + - + - + - + - + - + | S | | | | | | | | | + + + - + + - + + - + + + + | . | | | | | | + + + - + + + - + + - + + + | . . . | | | | | | + + - + + + - + - + + + - + + | | | . . . | | | | | + + - + - + + + - + + + - + - + | | | | . | | | | | + - + - + - + + + - + - + - + + + | | | | | . | | | | + - + - + + - + + + - + + + - + | | | . . | | | | + + + - + + + + - + - + + + | | | | . . . | | + + - + + - + + - + - + + - + + | | G | . . | | + - + - + - + + + + + + - + + | | | | | . . | + - + - + - + - + - + - + - + - + - + - +
good work!
i’ll get back if i have some problems….