Hello

I've been working on a simple A* path finder for Unity in C# from various tutorials. But i don't know why mine is not working as desired - it seems to return no valid path.

My grid is setup different to most so i had to tweak it which might be why it doesn't work. My grid structure is setup in a list of a class rather than a 2D grid that most people use. Like so:

tile.Add(new Grid(0,0));
tile.Add(new Grid(-1,0));
tile.Add(new Grid(-2,0));
tile.Add(new Grid(1,0));
tile.Add(new Grid(2,0));

So my test data was like this:

Start Pos: -2,0
End Pos     2,0
Debug.Log(path.Count); = 0; //essentially no path was found

This is clearly incorrect. This is my path finding function:

public List<Grid> FindPath(Grid startPos, Grid endPos)
{ 
    Node            startNode       = new Node(startPos);
    Node            targetNode      = new Node(endPos);
    List<Node>      openSet         = new List<Node>();
    HashSet<Node>   closedSet       = new HashSet<Node>();
    List<Grid>      path            = new List<Grid>();
 
    openSet.Add(startNode);
 
while(openSet.Count > 0)
{
     Node currentNode = openSet[0];

     for(int i = 1; i < openSet.Count; i++)
     {           
        if(openSet[i].fCost < currentNode.fCost || openSet[i].fCost == currentNode.fCost && openSet[i].hCost < currentNode.hCost)
        {
          currentNode = openSet[i];
        }
     }
 
     openSet.Remove(currentNode);
     closedSet.Add(currentNode);
 
 
     if(currentNode == targetNode) // path found
     {
           Node curNode = targetNode;

           while (curNode != startNode) 
           {
               path.Add(curNode.tile);
               curNode = curNode.parent;
           }
           path.Reverse(); //switch it around to get the path in the correct order
           break; // exit main while loop
       
     } else {
           
     foreach(Node neighbour in GetNeighbours(currentNode))
     {           
          if(!neighbour.walkable || closedSet.Contains(neighbour))
          {
            continue;
          }
           
         int newMovementCostToNeighbour = currentNode.gCost + Heuristic(currentNode,neighbour);
  
         if(newMovementCostToNeighbour < neighbour.gCost || !openSet.Contains(neighbour))
         {
               neighbour.gCost     = newMovementCostToNeighbour;
               neighbour.hCost     = Heuristic(neighbour, targetNode);
               neighbour.parent    = currentNode;
               
               if(!openSet.Contains(neighbour))
               {
                   openSet.Add(neighbour);
               }           
         }
     }
     }
}
    return path;
}

EDIT: My GetNeighbours function which might help:

private List<Node> GetNeighbours(Node n)
{
    List<Node> neighbours = new List<Node>();
    Node node;
    for(var i = 0; i < map.tile.Count; i++)
    {
        if(map.tile[i].x == n.tile.x-1 || map.tile[i].x == n.tile.x+1) //currently only looking horizontally
        {
            node = new Node(map.tile[i]);
            neighbours.Add(node);
        }
    }
    return neighbours;
}

I've gone through it a few times and just cannot see where my logic is failing me. And am hoping some one who knows A* really well might detect some mistake in my logic that i have missed.

1. Step through the function with your debugger and check what it's doing. Have you set 'walkable' to true?

2. Make sure you come up with a better way of getting neighbors. That loop is going to have dramatically worse performance the larger your graph gets.

1) I dunno what i did but it seems to just infinite loop and crashes unity. But it seems that currentNode doesn't change to the next node. Would it help if i provided my Node class ?

2) I'll optimise when i have it working :P I might look into heap after but one step at a time!

After stepping through, it seems it just goes back and forth between nodes rather than progress forward. But i don't know why =/

Your indenting is messed up, so it's hard to see the structure.

However, I seem to be missing a break or return.

When you pull the target node from the open set "if(currentNode == targetNode){" case

you walk backwards to get the path, reverse it, and then?

It looks to me that you loop back to get a new node from the open set.

Your indenting is messed up, so it's hard to see the structure.

However, I seem to be missing a break or return.

When you pull the target node from the open set "if(currentNode == targetNode){" case

you walk backwards to get the path, reverse it, and then?

It looks to me that you loop back to get a new node from the open set.

Ah yeah good spot, i added a break but it still seems to infinite loop. Which seems to suggest current node never becomes target node.

I have edited the question to fix some indents i guess i'm the only one who likes that kind of indentation lol.

1. Node targetNode = new Node(endPos);

2. if(currentNode == targetNode)

3. node = new Node(map.tile[i])

I am pondering about these lines, in particular, is the == an identity check, or an equality check? If it is identity, line 3 creates new identities while exploring, so you never reach the end point.

1. Node targetNode = new Node(endPos);

2. if(currentNode == targetNode)

3. node = new Node(map.tile[i])

I am pondering about these lines, in particular, is the == an identity check, or an equality check? If it is identity, line 3 creates new identities while exploring, so you never reach the end point.

if (currentNode.tile == targetNode.tile)

Ah darn that was the issue and it works now! Guess i know now to be more careful with stuff like that in C# ! Thanks guys :)

Mystery solved :)

This morning I realized your closed set would have the same problem too in that case, so that should be fixed too.