A* Pathfinding Problems

Question

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
        
        
        
        astar.openList.add(start);
        
        
        
        while(!astar.openList.isEmpty())
        {
            currentTile = astar.getTileWithLowestF();
            
            if(currentTile==endTile)
                break;
            
            astar.openList.remove(currentTile);
            astar.closedList.add(currentTile);
            
            AdjacentTiles adjacentTiles = getAdjacentTiles2(currentTile);
            
            
            //Assign G and H costs:
            adjacentTiles.aboveRight.node.g = 10 + currentTile.node.g;
            adjacentTiles.right.node.g = 14 + currentTile.node.g;
            adjacentTiles.belowRight.node.g = 10 + currentTile.node.g;
            adjacentTiles.below.node.g = 14 + currentTile.node.g;
            adjacentTiles.belowLeft.node.g = 10 + currentTile.node.g;
            adjacentTiles.left.node.g = 14 + currentTile.node.g;
            adjacentTiles.aboveLeft.node.g = 10 + currentTile.node.g;
            
            ArrayList<Tile> adjacentTilesList = new ArrayList<>();
            
            adjacentTilesList.add(adjacentTiles.aboveRight);
            adjacentTilesList.add(adjacentTiles.right);
            adjacentTilesList.add(adjacentTiles.aboveRight);
            adjacentTilesList.add(adjacentTiles.belowRight);
            adjacentTilesList.add(adjacentTiles.below);
            adjacentTilesList.add(adjacentTiles.belowLeft);
            adjacentTilesList.add(adjacentTiles.left);
            adjacentTilesList.add(adjacentTiles.aboveLeft);
            
            for(Tile t:adjacentTilesList)
            {
                t.node.h = astar.getHeuristic(t.getCoordinates(), endTile.getCoordinates());
            }
            
            
            for(Tile t:adjacentTilesList)
            {
               //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
               {
                   astar.openList.add(t);
               }
               
            }
            
           
        }
        
        Tile startingTile = start;
        Tile currentTile2 = endTile;
        ArrayList<Tile> path = new ArrayList<>();
        path.add(currentTile2);
        
        while(currentTile2 != start)
        {
            path.add(currentTile2.node.parent);
            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
– mdkess, Commented Feb 21, 2012 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
– DampeS8N, Commented Feb 21, 2012 at 16:28

krolth · Accepted Answer · 2012-02-21 01:16:41Z

2

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;
        astar.openList.add(t);
        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.

edited Feb 21, 2012 at 1:16

answered Feb 20, 2012 at 23:46

krolth

8916 silver badges9 bronze badges

\$\begingroup\$ Wow, I think you fixed it. Could you tell me what existingNode is? And could you explain some of your comments a little more? \$\endgroup\$

Alex
– Alex

2012-02-21 00:15:51 +00:00
Commented Feb 21, 2012 at 0:15
\$\begingroup\$ 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. \$\endgroup\$

krolth
– krolth

2012-02-21 01:14:14 +00:00
Commented Feb 21, 2012 at 1:14

Add a comment |

Stack Exchange Network

A* Pathfinding Problems

1 Answer 1

You must log in to answer this question.

Hot Network Questions

A* Pathfinding Problems

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions