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
    3,956
    Rep Power
    8

    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
    3,956
    Rep Power
    8

    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, 02:08 AM
  2. Need some help in an algorithm
    By ea09530 in forum New To Java
    Replies: 3
    Last Post: 04-04-2010, 01:13 PM
  3. Help with an Algorithm
    By Manfizy in forum New To Java
    Replies: 22
    Last Post: 07-03-2009, 07:16 AM
  4. O(log n) algorithm help !!!!!!
    By itseeker87 in forum New To Java
    Replies: 8
    Last Post: 09-09-2008, 05:12 PM
  5. Help with algorithm
    By susan in forum New To Java
    Replies: 1
    Last Post: 07-13-2007, 10: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
  •