# A* Pathfinding Problems

I'm trying to implement the a* pathfinding algorithm in my game. I've looked at dozens of tutorials but I can't seem to get it right. My code is below, and It's not working... does anybody see something I'm doing wrong? Mainly, I followed these tutorials: Tutorial 1 Tutorial 2

I'm sure you will be able to understand all of the classes/methods I've created. If you can look over this code and just tell me if it looks remotely correct that would be great.

public void highlightPath(Tile start, Tile end)
{

AStar astar = new AStar();

Tile currentTile = start;
Tile endTile = end;

start.node.g = 0;
start.node.h = astar.getHeuristic(start.getCoordinates(), endTile.getCoordinates());

start.node.parent = null;//for the loop

while(!astar.openList.isEmpty())
{
currentTile = astar.getTileWithLowestF();

if(currentTile==endTile)
break;

astar.openList.remove(currentTile);

//Assign G and H costs:

{
t.node.h = astar.getHeuristic(t.getCoordinates(), endTile.getCoordinates());
}

{
//Check traversability:
if(t.exists == false)//Change this to test segments/elevation
continue;//skips everything below...

if(astar.closedList.contains(t) && currentTile.node.g < t.node.g)
{
t.node.g = currentTile.node.g;
t.node.parent = currentTile;
}
else if(astar.openList.contains(t) && currentTile.node.g < t.node.g)
{
t.node.g = currentTile.node.g;
t.node.parent = currentTile;
}
else
{
}

}

}

Tile startingTile = start;
Tile currentTile2 = endTile;
ArrayList<Tile> path = new ArrayList<>();

while(currentTile2 != start)
{
currentTile2 = currentTile2.node.parent;
}

for(Tile t:path)
{
t.highlight();
}

}

• General advice for debugging this sort of thing is to add animation as you go. Add a Thread.currentThreadSleepMillis() inside the while loop, and highlight the current tile. Output lots of debug information too - the current tile, which tiles are getting added, and so on. – mdkess Feb 21 '12 at 1:26
• @mdkess is right. I once spent several hours trying to figure out why my A* was circling around what I thought was the starting point, thinking it failed. Added in a color tile on each step and slapped my face when I remembered I had intentionally reversed the look up direction (from end to start) and the A* was working fine but not kicking out and then circling around the end point back and forth in an ever growing circle. – DampeS8N Feb 21 '12 at 16:28

I think you messed up your if-statement. It should be something like this:

for(Tile t:adjacentTilesList)
{
// if the node doesn't exist, or is not walkable, or we have already traversed it ignore it
if(!IsWalkable(t) || astar.closedList.contains(t))
continue;

// If we don't have this node as a candidate node then add it. Make sure you signal where we are coming from
if(!astar.openList.contains(t))
{
t.node.parent = currentTile;
continue;
}
else
{
//We already identified this node before so compare it to the previous cost and switch if it can be reached cheaper/faster
var existingNode = astar.openList.Find(t);

if (t.g < existingNode.g)
{
existingNode.g = t.node.g;
existingNode.g = t.node.parent;
}
}
}


Note that you'll need to define the IsWalkable function.

• Wow, I think you fixed it. Could you tell me what existingNode is? And could you explain some of your comments a little more? – Alex Feb 21 '12 at 0:15
• It was just pseudocode for the candidate node that is already part of your open list. I'm not even sure if Java has the "var" keyword. – krolth Feb 21 '12 at 1:14