1. Member
Join Date
Nov 2010
Posts
20
Rep Power
0

## 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);
List<Square> d = getAdjCent(start.x, start.y, start);
for (int i = 0; i<d.size(); i++){
}

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);
}
}
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);
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++){
}
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);
}
}
c++;

if (c>100000){
break Algorithm;
}
}
System.out.println("Done");

Following:
for (int i = 0; ; i++){
if (route.get(i).parent != null){
} 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){
int c = 0;
if (!barriers[x-1][y-1]){
c++;
}
if (!barriers[x][y-1]){
c++;
}
if (!barriers[x+1][y-1]){
c++;

}
if (!barriers[x-1][y]){
c++;

}
if (!barriers[x+1][y]){
c++;

}
if (!barriers[x-1][y+1]){
c++;

}
if (!barriers[x][y+1]){
c++;

}
if (!barriers[x+1][y+1]){
c++;

}

}

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. 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. Member
Join Date
Nov 2010
Posts
20
Rep Power
0
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. 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. Senior Member
Join Date
Feb 2010
Location
Ljubljana, Slovenia
Posts
470
Rep Power
11
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.

6. Member
Join Date
Nov 2010
Posts
20
Rep Power
0
Thanks for the advice, I have now used more methods in th ecode and have easily found where it went wrong

7. Senior Member
Join Date
Feb 2010
Location
Ljubljana, Slovenia
Posts
470
Rep Power
11
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 :)

#### Posting Permissions

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