Hello. I’ve been trying to make A Star path finding, but unfortunately, failed. I looked at the pseudo code in this site: http://wiki.gamegardens.com/Path_Finding_Tutorial and tried to make it in java. Here is what I got:
private void findPath(){
float startX = x, startY = y; //start position is player position
float destX = destination.getX(), destY = destination.getY();
//create the open list of nodes, initially containing only our starting node
openList.clear();
openList.add(new Tile(0, false, startX, startY));
//create the closed list of nodes, initially empty
closedList.clear();
boolean reachedGoal = false;
while(!reachedGoal){ //while we have not reached our goal
//consider the best node in the open list (the node with the lowest f value)
Tile lowest = lowestFInOpen();
if(lowest.getX() == destX && lowest.getY() == destY){ //if this node is the goal
//then we're done
reachedGoal = true;
}else{
//move the current node to the closed list and consider all of its neighbors
closedList.add(lowest);
ArrayList<Tile>neighbors = getNeighbors(lowest);
for(Tile neighbor : neighbors){ //for each neighbor
if(closedList.contains(neighbor)){ //if this neighbor is in the closed list
if(lowest.G < neighbor.G){ //and our current g value is lower
//then update the neighbor with the new, lower, g value
//change the neighbor's parent to our current node
double dx = lowest.getX() - neighbor.getX();
double dy = lowest.getY() - neighbor.getY();
double G = Math.abs(Math.sqrt((dx * dx) + (dy * dy)));
neighbor.G = G;
neighbor.parent = lowest;
}
}else if(openList.contains(neighbor)){ //this neighbor is in the open list
if(lowest.G < neighbor.G){ //and our current g value is lower
//then update the neighbor with the new, lower, g value
//change the neighbor's parent to our current node
double dx = lowest.getX() - neighbor.getX();
double dy = lowest.getY() - neighbor.getY();
double G = Math.abs(Math.sqrt((dx * dx) + (dy * dy)));
neighbor.G = G;
neighbor.parent = lowest;
}
}else{ //this neighbor is not in either the open or closed list
//add the neighbor to the open list and set its g value
double dx = lowest.getX() - neighbor.getX();
double dy = lowest.getY() - neighbor.getY();
double distance = Math.abs(Math.sqrt((dx * dx) + (dy * dy)));
neighbor.G = distance;
openList.add(neighbor);
}
}
}
}
}
private ArrayList<Tile>getNeighbors(Tile tile){
ArrayList<Tile>neighbors = new ArrayList<Tile>();
for(Tile temp : World.getInstance().getTiles()){
//32 cost - orthogonal, 45.25 - diagonal, so if from parent tile to other tile distance is < 50, it's neighbor
double dx = temp.getX() - tile.getX();
double dy = temp.getY() - tile.getY();
double distance = Math.abs(Math.sqrt((dx * dx) + (dy * dy)));
if(distance < 50)
neighbors.add(temp);
}
return neighbors;
}
private Tile lowestFInOpen(){
Tile lowest = new Tile(0, false);
lowest.F = Double.MAX_VALUE;
for(int i=0; i<openList.size(); i++){
if(openList.get(i).F < lowest.F){
lowest = openList.get(i);
}
}
return lowest;
}
And nothing happens, this loop goes forever. I just noticed that openList size increases to 5, and closedList size increases to the infinity. Where is the problem?
And actually in that pseudo code I didn’t noticed where the F value of nodes is being updated, maybe this is the problem? :