Results 1 to 7 of 7

Thread: A* algorithm

  1. #1
    zjames is offline Member
    Join Date
    Nov 2010
    Posts
    20
    Rep Power
    0

    Default 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:
    Java 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

  2. #2
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    4,041
    Rep Power
    10

    Default

    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?

  3. #3
    zjames is offline Member
    Join Date
    Nov 2010
    Posts
    20
    Rep Power
    0

    Default

    I don't get an error, but the output is as follows:
    Java 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.

  4. #4
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    4,041
    Rep Power
    10

    Default

    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?

  5. #5
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default

    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.
    Ever seen a dog chase its tail? Now that's an infinite loop.

  6. #6
    zjames is offline Member
    Join Date
    Nov 2010
    Posts
    20
    Rep Power
    0

    Default

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

  7. #7
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default

    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 :)
    Ever seen a dog chase its tail? Now that's an infinite loop.

Similar Threads

  1. Algorithm help? :)
    By Mirix in forum New To Java
    Replies: 6
    Last Post: 05-24-2010, 03:08 AM
  2. Need some help in an algorithm
    By ea09530 in forum New To Java
    Replies: 3
    Last Post: 04-04-2010, 02:13 PM
  3. Help with an Algorithm
    By Manfizy in forum New To Java
    Replies: 22
    Last Post: 07-03-2009, 08:16 AM
  4. O(log n) algorithm help !!!!!!
    By itseeker87 in forum New To Java
    Replies: 8
    Last Post: 09-09-2008, 06:12 PM
  5. Help with algorithm
    By susan in forum New To Java
    Replies: 1
    Last Post: 07-13-2007, 11:26 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •