[geno]

Hello, my A* implementation have been giving me a headache for the past hours and am now turning here for help.

Here are 2 snippets of my code, 1 snippet is the part of my code that searches through the nodes and do the open/closed list operations and the second snippet is the part that constructs the path by going from parent to parent till it finds the start node. However, for some reason, when the construct path method gets called it's stuck in an infinite loop and I can't figure out why or if something is wrong with snippet 1.

Snippet 1:

private ArrayList<WebNode> findPath(Tile destination)
{
ArrayList<WebNode> openList = new ArrayList<WebNode>();
ArrayList<WebNode> closedList = new ArrayList<WebNode>();
WebNode startNode = closestReachableNodeOnMap();
WebNode destinationNode = closestNodeToDestination(destination);
System.out.println("Start Node: " + startNode.tile.toString());
System.out.println("Destination Node: " + destinationNode.tile.toString());
openList.add(startNode);

WebNode currentNode;
int iterations = 0;
while(!openList.isEmpty()) // Loop till we have a path :){
iterations++;
if(iterations > 100000) break;
currentNode = findCurrentNode(openList);
if(currentNode == destinationNode) return constructPath(currentNode, startNode); // We have our path constructed.openList.remove(currentNode);
closedList.add(currentNode);
for(WebNode edge : currentNode.edges)
{
edge.setParent(currentNode);
updateCostForNode(edge, destinationNode.tile);
}

for(WebNode edge : currentNode.edges)
{
if(edge == destinationNode) return constructPath(edge, startNode);
// Optimization: Use boolean flag instead of 2 lists later. // If there is a node with the same parent in open or closed list but with lower f, skip.updateCostForNode(edge, destinationNode.tile);
boolean betterAvailable = false;
for(WebNode node : openList)
{
if(node.getParent() == edge.getParent())
{
if(node.f < edge.f)
{
betterAvailable = true;
}
}
}
for(WebNode node : closedList)
{
if(node.getParent() == edge.getParent())
{
if(node.f < edge.f)
{
betterAvailable = true;
}
}
}
// Else add to open listif(!betterAvailable)
{

openList.add(edge);
}
}
}
System.out.println("Failed to find path :(");
return null; // Failure}

Snippet 2:

private ArrayList<WebNode> constructPath(WebNode endNode, WebNode startNode)
{
System.out.println("Path is possible :)");
ArrayList<WebNode> path = new ArrayList<WebNode>();
WebNode currentNode = endNode;
while(!currentNode.equals(startNode))
{
path.add(currentNode);
currentNode = currentNode.getParent();
}
path.add(startNode);
// Path is in reverse order.Collections.reverse(path);
// Return the constructed path :)return path;
}

Thanks for help / suggestions

 

[frazboyz]

Why are you using Tiles? Did you find this on the web?

 

[geno]

Why are you using Tiles? Did you find this on the web?

No, read some research papers. I use tile position for the heurestic and more.

 

[frazboyz]

No, read some research papers. I use tile position for the heurestic and more.

Hm Sketchy, well i would recomend not starting with A* try write a path finding algorithm using BFS or Djkstras, both are easier.

 

[geno]

Hm Sketchy, well i would recomend not starting with A* try write a path finding algorithm using BFS or Djkstras, both are easier.

Why is it sketchy to use the manhattan distance between 2 tiles to evaluate the cost of g and h?
I believe the search works since it calls the construct path which then leads to an infinite loop. I think I do something wrong when I set a nodes parent, which is an error Id do same with both algorithms you suggested since its not the heuristic im having problems with.

 

[arbiter]

On a sidenote, I would recommend joining our Skype development chat. We love discussing stuff like this in detail. PM me if you're interested.

 

[geno]

Managed to fix the problem, a node would reset all the edges parents even if they already have one, resulting in a node having a parent that had their Child as the parent -> infinite loop.
simply changed
edge.setParent(currentNode);
To:
if(edge.getParent() == null) edge.setParent(currentNode);