Hi, I tried to implement A*-Pathfinding, but it does not work.
It crashes on me, as in the Java-App freezes. It freezes before the render() method is called, so its stuck somewhere in my A*-Algorithm.
Short description of the Map, its a 2D-Array of Integers and a 1 is a wall, 0 is nothing.
Thats why I had to do everything in y,x not x,y.
This is my Pathfinding Class:
public class Pathfinder {
Map map;
ArrayList<Square> open = new ArrayList<Square>();
ArrayList<Square> closed = new ArrayList<Square>();
Pathfinder(Map map) {
this.map = map;
}
public ArrayList<int[]> getPath(int sy, int sx, int gy, int gx) {
open.add(new Square(sy,sx));
boolean found = false;
while (!found) {
Square current;
int minF = 0;
int ind = 0;
if (open.size() > 0) {
for (Square s : open) {
if (minF == 0)
s.F = minF;
if (s.F < minF) {
minF = s.F;
ind = open.indexOf(s);
}
}
} else {
System.out.println("Openlist empty. No Path found.");
return null;
}
closed.add(open.get(ind));
if (open.get(ind).x == gx && open.get(ind).y == gy)
found = true;
open.remove(ind);
current = closed.get(closed.size()-1);
//Get adjacent squares
ArrayList<Square> adjectant = getAdjacent(current);
//Parse adjacent squares
for (Square s: adjectant) {
if (map.getAt(s.y, s.x) == 1 || closed.contains(s)) {
if (!open.contains(s)) {
s.parent = current;
s.H = (int) ( 10*( Math.sqrt(current.x-gx) + Math.sqrt(current.y-gy)));
s.getF();
open.add(s);
} else {
if (s.G < current.G) {
s.parent = current;
s.H = (int) ( 10*( Math.sqrt(current.x-gx) + Math.sqrt(current.y-gy)));
s.getF();
}
}
}
}
}
boolean saved = false;
ArrayList<int[]> nodes_backwards = new ArrayList<int[]>();
ArrayList<int[]> nodes = new ArrayList<int[]>();
Square s = closed.get(closed.size()-1);
while (!saved) {
int[] tmp = {s.y,s.x};
nodes_backwards.add(tmp);
s = s.parent;
if (s.x == sx && s.y == sy) {
saved = true;
}
}
for (int i=nodes_backwards.size()-1; i >= 0; i--) {
nodes.add(nodes_backwards.get(i));
}
return nodes;
}
private ArrayList<Square> getAdjacent(Square current) {
ArrayList<Square> adjacent = new ArrayList<Square>();
int x = current.x;
int y = current.y;
if (y-1 >= 0) {
if (x-1 >= 0)
adjacent.add(new Square(y-1,x-1,true));
adjacent.add(new Square(y-1,x));
if (x+1 <= 10)
adjacent.add(new Square(y-1,x+1,true));
}
if (x-1 >= 0)
adjacent.add(new Square(y,x-1));
if (x+1 <= 10)
adjacent.add(new Square(y,x+1));
if (y+1 <= 10) {
if (x-1 >= 0)
adjacent.add(new Square(y+1,x-1,true));
adjacent.add(new Square(y+1,x));
if (x+1 <= 10)
adjacent.add(new Square(y+1,x+1,true));
}
return adjacent;
}
}
My adjacent finding method is pretty shitty. Because I didn’t know how else to get all the adjacent tiles, without running into problems at the borders.
Square class:
public class Square {
int F,G;
int H;
int x,y;
Square parent;
boolean diag;
Square(int y, int x) {
this.x = x;
this.y = y;
G = 10;
}
Square(int y, int x, boolean diag) {
this.x = x;
this.y = y;
if (diag)
G = 14;
}
public void getF() {
F = G + H;
}
}
And my Map class:
public class Map {
int[][] gitter = new int[10][10];
Map() {
for (int i=0; i < gitter.length; i++) {
for (int f=0; f < gitter.length; f++) {
gitter[i][f] = 0;
}
}
gitter[0][0] = 1;
gitter[5][5] = 1;
gitter[4][5] = 1;
gitter[3][5] = 1;
gitter[3][6] = 1;
gitter[3][7] = 1;
gitter[3][8] = 1;
gitter[7][7] = 1;
gitter[7][8] = 1;
}
public int getAt(int y,int x) {
return gitter[x][y];
}
public int[] getNode(int y,int x) {
int[] pos = {64*(x-1),64*y};
System.out.println(pos[0] +","+pos[1]);
return pos;
}
}
(gitter is german for grid)