# A* script not returning the correct path

This topic is 997 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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));


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

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

if(currentNode == targetNode) // path found
{
Node curNode = targetNode;

while (curNode != startNode)
{
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))
{
}
}
}
}
}
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]);
}
}
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 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 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 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 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 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 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 on other sites

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 :)

##### Share on other sites

Mystery solved :)

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

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 10
• 11
• 13
• 9
• 9
• ### Forum Statistics

• Total Topics
634085
• Total Posts
3015407
×