Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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();
        }



    }
share|improve this question
3  
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

1 Answer 1

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.