8 Directional Pathfinding (A*) - Inconsistently Finding Path
Newbie here so sorry if I don't describe the problem well.
I'm attempting to create an 8 directional pathfinding script. I've followed the majority of a tutorial but wanted to change it up to work in a way that's easier for me to understand.
The GetNeighbours method works in 4 directions but not diagonally. I'm using a Dictionary to index the x and y value in a node (cell). I know this is not efficient but it's easier for me to understand and more flexible.
Anyway, the pathing works only sometimes. Seems like I can't get the neighbouring cells whenever I need to move to the top or left row. If I put holes in the tilemap it also messes up the pathing but only when I go behind the holes sometimes, see image: not working:
working:
Any help would be amazing!
public List<Node> GetNeighbours(Node node)
{
List<Node> neighbours = new List<Node>();
int checkX = node.gridX;
int checkY = node.gridY;
//left
if (nodes.ContainsKey(new Vector2Int(checkX-1, checkY)))
{
neighbours.Add(nodes[new Vector2Int(checkX-1, checkY)]);
}
//right
if (nodes.ContainsKey(new Vector2Int(checkX +1, checkY)))
{
neighbours.Add(nodes[new Vector2Int(checkX + 1, checkY)]);
}
//up
if (nodes.ContainsKey(new Vector2Int(checkX, checkY + 1)))
{
neighbours.Add(nodes[new Vector2Int(checkX, checkY +1)]);
}
//down
if (nodes.ContainsKey(new Vector2Int(checkX, checkY - 1)))
{
neighbours.Add(nodes[new Vector2Int(checkX, checkY - 1)]);
}
//top left
if (nodes.ContainsKey(new Vector2Int(checkX - 1, checkY - 1)) && nodes.ContainsKey(new Vector2Int(checkX, checkY + 1)) && nodes.ContainsKey(new Vector2Int(checkX - 1, checkY - 1)));
{
neighbours.Add(nodes[new Vector2Int(checkX -1, checkY + 1)]);
}
//top right
if(nodes.ContainsKey(new Vector2Int(checkX + 1, checkY)) && nodes.ContainsKey(new Vector2Int(checkX, checkY + 1)) && nodes.ContainsKey(new Vector2Int(checkX + 1, checkY + 1)))
{
neighbours.Add(nodes[new Vector2Int(checkX + 1, checkY + 1)]);
}
//bottom left
if(nodes.ContainsKey(new Vector2Int(checkX-1, checkY)) && nodes.ContainsKey(new Vector2Int(checkX, checkY -1 )) && nodes.ContainsKey(new Vector2Int(checkX - 1, checkY - 1)))
{
neighbours.Add(nodes[new Vector2Int(checkX - 1, checkY - 1)]);
}
//bottomright
if (nodes.ContainsKey(new Vector2Int(checkX +1, checkY)) && nodes.ContainsKey(new Vector2Int(checkX, checkY -1)) && nodes.ContainsKey(new Vector2Int(checkX + 1, checkY - 1)))
{
neighbours.Add(nodes[new Vector2Int(checkX + 1, checkY - 1)]);
}
// Debug.Log("number of neighbours added is: " + neighbours.Count);
return neighbours;
}
The Pathfinding Class
public class Pathfiding
{
public static List<Vector2Int> FindPath(Grid grid, Vector2Int startPos, Vector2Int endPos)
{
List<Node> nodes_path = _ImpFindPath(grid, startPos, endPos);
if (!grid.nodes.ContainsKey(startPos) || !grid.nodes.ContainsKey(endPos))
{
return null;
}
else
{
//get nodes and return a list of points
List<Vector2Int> ret = new List<Vector2Int>();
if (nodes_path != null)
{
foreach (Node n in nodes_path)
{
ret.Add(new Vector2Int(n.gridX, n.gridY)); //load all nodes to check
}
}
return ret;
}
}//end FindPath////
private static List<Node> _ImpFindPath(Grid grid, Vector2Int startPos, Vector2Int endPos)
{
Node startNode;
Node targetNode;
startNode = grid.nodes[startPos];
targetNode = grid.nodes[endPos];
List<Node> openSet = new List<Node>();
HashSet<Node> closedSet = new HashSet<Node>();
openSet.Add(startNode);
while (openSet.Count > 0)
{
Node currentNode = openSet[0];
for (int i = 1; i < openSet.Count; i++)
{
//only check nodes with better f costs
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)
{
return RetracePath(grid, startNode, targetNode);
}
foreach (Node neighbour in grid.GetNeighbours(currentNode))
{
if (neighbour.walkPenalty <= 0 || closedSet.Contains(neighbour))
{
continue;
}
int newMovementCostToNeighbour = currentNode.gCost + GetDistance(currentNode, neighbour) * (int)(10.0f * neighbour.walkPenalty);
if (newMovementCostToNeighbour < neighbour.gCost || !openSet.Contains(neighbour))
{
neighbour.gCost = newMovementCostToNeighbour;
neighbour.hCost = GetDistance(neighbour, targetNode);
neighbour.parent = currentNode;
if (!openSet.Contains(neighbour))
openSet.Add(neighbour);
}
}
}
return null;
}
There are three errors in the //top left condition:
-
There should be no semicolon at the end of the
ifstatement. It makes theifstatement useless and even worse it always executes the block below. So a diagonal path option towards top-left is always present. -
Once you fix the first error, you need to change
checkY - 1tocheckYin the first predicate of theifcondition. -
And you need to change
checkY - 1tocheckY + 1in the last predicate.
//top left
if (nodes.ContainsKey(new Vector2Int(checkX - 1, checkY)) &&
nodes.ContainsKey(new Vector2Int(checkX, checkY + 1)) &&
nodes.ContainsKey(new Vector2Int(checkX - 1, checkY + 1)))
{
neighbours.Add(nodes[new Vector2Int(checkX -1, checkY + 1)]);
}
It would be even better to use TryGetValue to avoid one more struct construction and lookup:
//top left
if (nodes.ContainsKey(new Vector2Int(checkX - 1, checkY)) &&
nodes.ContainsKey(new Vector2Int(checkX, checkY + 1)) &&
nodes.TryGetValue(new Vector2Int(checkX - 1, checkY + 1), out var n))
{
neighbours.Add(n);
}
I am not sure if these are all the direct errors in your code, just try it.
There is one more indirect error related to the diagonal movement. I do not understand why you need to check the 4-neighborhood path along with the diagonal check. If the 4-neighbors must be present anyhow, why do you explicitly add the diagonal movement? Or is it another error, that for diagonal movement the non-diagonal predicates should be actually omitted?