# A* algorithm

• 11-23-2010, 07:57 PM
zjames
A* algorithm
Hi, I am trying to create a program which uses the A* pathfinding algorithm, and I really don't know what is wrong with my code. At the moment, is set up to just print the x y co-ordinates of the path it produces. Here is my code:
Code:

```public void goTo (int x, int y){     List<Square> openList = new ArrayList<Square>();     List<Square> closedList = new ArrayList<Square>();     Square start = new Square(this.x, this.y);     openList.add(start);     List<Square> d = getAdjCent(start.x, start.y, start);     for (int i = 0; i<d.size(); i++){         openList.add(d.get(i));     }     closedList.add(openList.get(0));     openList.remove(0);     int f;     Square min;     int f1=openList.get(0).getF(x, y);     min = openList.get(0);     for (int i =1; i<openList.size(); i++){         f=openList.get(i).getF(x, y);         if (f<f1){             f1=f;             min = openList.get(i);         }     }     closedList.add(min);     List<Square> route = new ArrayList<Square>();     int c =0;   Algorithm:     for ( ; !(closedList.get(closedList.size()-1).x == x && closedList.get(closedList.size()-1).y == y); ){     openList.remove(min);     d = getAdjCent(closedList.get(closedList.size()-1).x, closedList.get(closedList.size()-1).y, closedList.get(closedList.size()-1));     for (int i = 0; i<d.size(); i++){         for (int j = 0; j<openList.size(); j++){             if (d.get(i).x == openList.get(j).x && d.get(i).y == openList.get(j).y){                 Square a = d.get(i);                 int f2 = openList.get(j).getF(x, y);                 if (a.getF(x, y)>f2){                     openList.remove(openList.get(j));                 } else {                     d.remove(a);                 }             }         }     }     openList.clear();     for (int i = 0; i<d.size(); i++){         openList.add(d.get(i));     }     f1=openList.get(0).getF(x, y);     min = openList.get(0);     for (int i =1; i<openList.size(); i++){         f=openList.get(i).getF(x, y);         if (f<f1){             f1=f;             min = openList.get(i);         }     }     closedList.add(min);   c++;       if (c>100000){         break Algorithm;     }     }     System.out.println("Done");         route.add(closedList.get(closedList.size()-1));   Following:     for (int i = 0; ; i++){         if (route.get(i).parent != null){         route.add(route.get(i).parent);         } else {             break Following;         }     }     for (int i = 0; i<route.size(); i++){       System.out.println("(" + route.get(i).x + "," + route.get(i).y + ")");     } } public List<Square> getAdjCent(int x, int y, Square parent){     List<Square> adjSes = new ArrayList<Square>();     int c = 0;   if (!barriers[x-1][y-1]){       adjSes.add(new Square(x-1, y-1, parent));       c++;   }     if (!barriers[x][y-1]){       adjSes.add(new Square(x, y-1, parent));       c++;   }     if (!barriers[x+1][y-1]){       adjSes.add(new Square(x+1, y-1, parent));       c++;     }     if (!barriers[x-1][y]){       adjSes.add(new Square(x-1, y, parent));     c++;     }     if (!barriers[x+1][y]){       adjSes.add(new Square(x+1, y, parent));     c++;       }     if (!barriers[x-1][y+1]){       adjSes.add(new Square(x-1, y+1, parent));     c++;         }     if (!barriers[x][y+1]){       adjSes.add(new Square(x, y+1, parent));     c++;         }     if (!barriers[x+1][y+1]){       adjSes.add(new Square(x+1, y+1, parent));     c++;         }         return adjSes; } public class Square {     int x, y, f, g, h;     Square parent;     public Square(int x, int y){         this.x = x;         this.y = y;     }     public Square(int x, int y, Square parent){         this.x = x;         this.y=y;         this.parent = parent;     }     public int getF (int targetX, int targetY){         if (this.x==this.parent.x || this.y==this.parent.y){             this.g = 10;         } else {             this.g = 14;         }         this.h = (targetX-this.x) + (targetY-this.y);         this.f = this.g+this.h;         return f;     } }```
A description of the A* algortithm can be found here GameDev.net - A* Pathfinding for Beginners
• 11-23-2010, 08:09 PM
KevinWorkman
It would help if we knew what your code did wrong. Do you get an Exception? Weird behavior? What did you expect to happen? What is happening instead?
• 11-23-2010, 08:14 PM
zjames
I don't get an error, but the output is as follows:
Code:

```Done (22,40) (21,40) (22,40) (21,40) (22,40) (21,40) (22,40) (21,40) (22,40) (21,40) (22,40) (21,40)```
From initial co-ordinates of (16,40) and destination of (16,80)
The barriers[][] array is a boolean array representing whether each tile is passable or not.
• 11-24-2010, 02:48 PM
KevinWorkman
What output were you expecting? Have you gone through the program with a debugger? Or at least put in a ton of print statements to figure out what's going on?
• 11-24-2010, 03:09 PM
m00nchile
One piece of advice, clean up your code and break it down into more methods, that makes it easier do track down non-syntactic errors. You even used goto statements which are a definite no no. Try to go through your code step by step, and see if it does what it's supposed to do.
• 11-24-2010, 09:29 PM
zjames
Thanks for the advice, I have now used more methods in th ecode and have easily found where it went wrong
• 11-25-2010, 01:02 PM
m00nchile
Good job. I've implemented the A* algorithm myself, and went through a very similar experience to yours. So I just advised you to do the same as I have :)