A* algorithm

[zjames]

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:

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

[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?

[zjames]

I don't get an error, but the output is as follows:

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.

[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?

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

[zjames]

Thanks for the advice, I have now used more methods in th ecode and have easily found where it went wrong

[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 :)