Hi I am trying to to make a pathfinding system with the A* algorithm and I have tried to make my own but that didn’t seem to work so I tried to make the one from the coding challenge by The coding train. I am close to make it work but it seems like i have a problem. I have used an ArrayList in order to remove and add objects to the array more effecient instead of using append(). Down below is my code and i think the problem has to do with the g, h and f-values, because the algorithm the spots it’s not supposed to do
int rows=20;
int cols=20;
int startx=0;
int starty=0;
float bred=10;
float hoj=10;
Cell[][] grid=new Cell[cols][rows];
//til pathfinding
ArrayList<Cell> openSet = new ArrayList<Cell>(); // brug arraylist da dette et bedre end append (mere effektivt)
ArrayList<Cell> closedSet = new ArrayList<Cell>();
ArrayList<Cell> path = new ArrayList<Cell>();
Cell start;
Cell end;
//tjek om element er i arraylist
boolean includes(ArrayList<Cell> grid2, Cell x){
return grid2.contains(x);
}
//distanse funktion
float heuristic(Cell grid1, Cell grid2){
//float d=abs(grid1.i-grid2.i)+abs(grid1.j-grid2.j);
float d=dist(grid1.i, grid1.j,grid2.i,grid2.j);
return d;
}
void setup(){
frameRate(20);
size(1500,1000);
//fullScreen(P2D);
for(int i=0;i<cols;i++){
for(int j=0;j<rows;j++){
grid[i][j]=new Cell(startx+i*bred,starty+j*hoj,bred,hoj);
}
}
start=grid[0][0]; //start
end=grid[cols-1][0]; //end
start.wall=false;
end.wall=false;
openSet.add(start);
//tilføjer alle naboer
for(int i=0;i<cols;i++){
for(int j=0;j<rows;j++){
grid[i][j].addneighbors(i,j);
}
}
}
void draw(){
//println(frameRate);
//viser grid og detect
Cell current;
for (int i=0; i<cols;i++){
for(int j=0; j<rows;j++){
grid[i][j].display(255,255,255);
}
}
if (openSet.size() > 0) {
// Best next option
int winner = 0;
for (int i = 0; i < openSet.size(); i++) {
if (openSet.get(i).f < openSet.get(i).f) {
winner = i;
}
}
current = openSet.get(winner);
// Did I finish?
if (current == end) {
noLoop();
Cell temp=current;
path.add(temp);
while(! (temp.previous==null)){
path.add(temp.previous);
temp=temp.previous;
}
println("Done");
}
openSet.remove(current);
closedSet.add(current); // bliver måske
// Check all the neighbors
Cell[] neighbors = current.neighbors;
for (int i = 0; i < neighbors.length; i++) {
Cell neighbor = neighbors[i];
// Valid next spot?
if (!includes(closedSet,neighbor) && !neighbor.wall) {
float tempG=current.g+1;
// Is this a better path than before?
if (includes(openSet,neighbor)) {
if (tempG < neighbor.g) {
neighbor.g = tempG;
// newPath = true;
}
} else {
neighbor.g = tempG;
//newPath = true;
openSet.add(neighbor);
}
neighbor.h = heuristic(neighbor, end);
neighbor.f = neighbor.g + neighbor.h;
neighbor.previous = current;
}
}
// no solution
} else {
noLoop();
return;
}
// closedSet is red
for (int i=0; i< closedSet.size(); i++){
closedSet.get(i).display(255,0,0);
}
//openSet is green
for (int i=0; i< openSet.size(); i++){
openSet.get(i).display(0,255,0);
}
// the path is blue
for(int i=0; i<path.size(); i++){
path.get(i).display(0,0,255);
}
}
class Cell{
// til pathfinding
float f=0;
float g=0;
float h=0;
// til kontruktion
float i;
float j;
float bredde;
float hojde;
boolean pressed=false;
boolean wall=false;
//farve
int rod=255;
int gron=255;
int bla=255;
//previous
Cell previous = null;
//neighbors
Cell[] neighbors = new Cell[0];
Cell(float x, float y,float b, float h){
i=x;
j=y;
bredde=b;
hojde=h;
//wall or not
//if (random(0,1)<0.4){
//wall=true;
//}
}
void display(int x, int y, int z){
if (wall){
fill(0);
rect(i,j,bredde,hojde);
}else{
fill(x,y,z);
rect(i,j,bredde,hojde);
}
}
void addneighbors(int i, int j){ // tilføjer naboerne
if (i < cols - 1) {
neighbors= (Cell[])append(neighbors,grid[i + 1][j]);
}
if (i > 0) {
neighbors= (Cell[])append(neighbors,grid[i - 1][j]);
}
if (j < rows - 1) {
neighbors= (Cell[])append(neighbors,grid[i][j + 1]);
}
if (j > 0) {
neighbors= (Cell[])append(neighbors,grid[i][j - 1]);
}
}
}