Sign in to follow this  
thefollower

A* script not returning the correct path

Recommended Posts

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.

Edited by thefollower

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

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 =/

Edited by thefollower

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.

Edited by thefollower

Share this post


Link to post
Share on other sites
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.

Edited by Alberth

Share this post


Link to post
Share on other sites

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.


That's a good observation; C# will default to reference comparison which will be false in this case. It's generally a bad idea to overload operator== anyway, so it's likely the comparison should be something like:
 
if (currentNode.tile == targetNode.tile)
Edited by Nypyren

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this