A Star Path finding endless loop
- by PoeHaH
I have implemented A* algorithm. Sometimes it works, sometimes it doesn't, and it goes through an endless loop. After days of debugging and googling, I hope you can come to the rescue.
This is my code:
The algorythm:
public ArrayList<Coordinate> findClosestPathTo(Coordinate start, Coordinate goal)
{
ArrayList<Coordinate> closed = new ArrayList<Coordinate>();
ArrayList<Coordinate> open = new ArrayList<Coordinate>();
ArrayList<Coordinate> travelpath = new ArrayList<Coordinate>();
open.add(start);
while(open.size()>0)
{
Coordinate current = searchCoordinateWithLowestF(open);
if(current.equals(goal))
{
return travelpath;
}
travelpath.add(current);
open.remove(current);
closed.add(current);
ArrayList<Coordinate> neighbors = current.calculateCoordAdjacencies(true, rowbound, colbound);
for(Coordinate n:neighbors)
{
if(closed.contains(n) || map.isWalkeable(n))
{
continue;
}
int gScore = current.getGvalue() + 1;
boolean gScoreIsBest = false;
if(!open.contains(n))
{
gScoreIsBest = true;
n.setHvalue(manhattanHeuristic(n,goal));
open.add(n);
}
else
{
if(gScore<n.getGvalue())
{
gScoreIsBest = true;
}
}
if(gScoreIsBest)
{
n.setGvalue(gScore);
n.setFvalue(n.getGvalue()+n.getHvalue());
}
}
}
return null;
}
What I have found out is that it always fails whenever there's an obstacle in the path. If I'm running it on 'open terrain', it seems to work.
It seems to be affected by this part: || map.isWalkeable(n)
Though, the isWalkeable function seems to work fine.
If additional code is needed, I will provide it.
Your help is greatly appreciated,
Thanks :)
