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.