Question posted in 
I have a 2D grid in my game made up of nodes. I have enemies which follow players using the A* pathfinding algorithm (using the diagonal distance heuristic for H as diagonal movement is allowed).
The pathfinding works nearly all of the time however, when a player and an enemy are on exactly opposite (diagonally, vertically, or horizontally) sides of a wall, the enemy becomes stuck and stops moving.
From the below screenshot you can see the path found in this scenario, for some reason, a node in the opposite direction of the path is also being added to the path:
Below is my code for my F, G and H calculations (in my node class):
// Calculates distance cost from current node to an adjacent node.
public void CalculateG(Node nodeTarget)
{
// If the node is diagonal to the current node, its cost of movement is higher.
if (TileX != nodeTarget.TileX && TileY != nodeTarget.TileY)
{
intG = 14;
}
else intG = 10;
}
// Calculates H cost using the diagonal shortcut method.
public void CalculateH(Node nodeTarget)
{
int intXDiff = Math.Abs(TileX - nodeTarget.TileX);
int intYDiff = Math.Abs(TileY - nodeTarget.TileY);
if (intXDiff > intYDiff)
intH = 14 * intYDiff + 10 * (intXDiff - intYDiff);
else intH = 14 * intXDiff + 10 * (intYDiff - intXDiff);
}
public void CalculateF()
{
intF = intG + intH; // F = G + H
}
The code for my pathfinding class is shown below:
public class Path
{
private List<Node> PathOfNodes; // Stores the path of nodes to follow to the destination.
public List<Node> NodePath
{
get { return PathOfNodes; }
}
// Constructor takes the starting node, destination and the grid to generate the path.
public Path(Node Start, Node Destination, GridLayer grid)
{
List<Node> openNodes = new List<Node>(); // Creates a list of possible nodes for the path.
List<Node> closedNodes = new List<Node>(); // Creates a list of nodes confirmed for the path.
openNodes.Add(Start); // Step 1: Adds the current node to the possibilities list.
// Loops while the destination is not on the closed list and while the open nodes list is not empty.
while (!closedNodes.Contains(Destination) && openNodes.Any())
{
// Sorts the open list according to f scores.
openNodes.Sort((node, otherNode) => node.F.CompareTo(otherNode.F));
Node nodeCurrent = openNodes[0]; // The node with the lowest F score is set as the current node.
openNodes.Remove(nodeCurrent);
closedNodes.Add(nodeCurrent); // The current node is moved to the closed list.
// Creates a list containing all the nodes adjacent to the current node.
List<Node> adjacentNodes = AddAdjacentNodes(grid, nodeCurrent);
CheckAdjacentNodes(adjacentNodes, ref closedNodes, ref openNodes, nodeCurrent, Destination);
}
EstablishPath(closedNodes);
}
// Adds all the adjacent nodes from above the current node turning clockwise.
public List<Node> AddAdjacentNodes(GridLayer grid, Node nodeCurrent)
{
int intCol = nodeCurrent.TileX / nodeCurrent.TileWidth;
int intRow = nodeCurrent.TileY / nodeCurrent.TileHeight; // Gets the current node's indices.
List<Node> adjacentNodes = new List<Node>(); // Stores the nodes adjacent to the current node.
// The if statements check whether the node is within the grid before adding the node.
if (intRow - 1 >= 0)
adjacentNodes.Add(grid.Nodes[intCol, intRow - 1]); // Above
if ((intCol + 1 < 21 && intRow - 1 >= 0) && (grid.Nodes[intCol + 1, intRow].Traversable) && (grid.Nodes[intCol, intRow - 1].Traversable))
adjacentNodes.Add(grid.Nodes[intCol + 1, intRow - 1]); // Diagonally Right Up
if (intCol + 1 < 21)
adjacentNodes.Add(grid.Nodes[intCol + 1, intRow]); // Right
if (intCol + 1 < 21 && intRow + 1 < 12 && (grid.Nodes[intCol + 1, intRow].Traversable) && (grid.Nodes[intCol, intRow + 1].Traversable))
adjacentNodes.Add(grid.Nodes[intCol + 1, intRow + 1]); // Diagonally Right Down
if (intRow + 1 < 12)
adjacentNodes.Add(grid.Nodes[intCol, intRow + 1]); // Below
if (intCol - 1 >= 0 && intRow + 1 < 12 && (grid.Nodes[intCol - 1, intRow].Traversable) && (grid.Nodes[intCol, intRow + 1].Traversable))
adjacentNodes.Add(grid.Nodes[intCol - 1, intRow + 1]); // Diagonally Left Down
if (intCol - 1 >= 0)
adjacentNodes.Add(grid.Nodes[intCol - 1, intRow]); // Left
if (intCol - 1 >= 0 && intRow - 1 >= 0 && (grid.Nodes[intCol - 1, intRow].Traversable) && (grid.Nodes[intCol, intRow - 1].Traversable))
adjacentNodes.Add(grid.Nodes[intCol - 1, intRow - 1]); // Diagonally Left Up
return adjacentNodes;
}
// Checks the adjacent node list for nodes to be added to the open list/closed list.
private void CheckAdjacentNodes(List<Node> adjacentNodes, ref List<Node> closedNodes, ref List<Node> openNodes, Node nodeCurrent, Node destinationNode)
{
foreach (Node node in adjacentNodes)
{ // Checks each node to see if it is traversable and not already on the closed list.
if (node.Traversable && !closedNodes.Contains(node))
{
// If the node is not on the open list, add it, set its parent as the current node and calculate its F, G, and H values.
if (!openNodes.Contains(node))
{
openNodes.Add(node);
node.Parent = nodeCurrent;
node.CalculateG(nodeCurrent);
node.CalculateH(destinationNode);
node.CalculateF();
}
else // If the node was already on the open list...
{
// If its G cost of the node is lower than its parent + its own...
if (node.G < node.G + node.Parent.G)
{
// Make the node's parent the current node and recalculate its values.
node.Parent = nodeCurrent;
node.CalculateG(nodeCurrent.Parent);
node.CalculateF();
}
}
}
}
}
private void EstablishPath(List<Node> closedNodes)
{
PathOfNodes = new List<Node>(); // Stores the path for the entity to follow to its target.
for (int intNodeIndex = closedNodes.Count - 1; (intNodeIndex > 1); intNodeIndex--)
{
// Starting from the top of the closed list, add each node's parent to the path
// until the starting node is reached (index is 0).
PathOfNodes.Add(closedNodes[intNodeIndex].Parent);
}
PathOfNodes.Remove(null); // Remove the final null node (as the final node has no parent).
}
}
I believe there is a problem with the comparision between a node’s G score and the G score of itself and its parent. I’m not sure if I am recalculating the G score using the correct adjacent node after the comparsion. If someone could make this clearer it would be really helpful. The article I followed was:
https://www.gamedev.net/resources/_/technical/artificial-intelligence/a-pathfinding-for-beginners-r2003
however, I don’t think I have implemented this step into my code correctly:
If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square.
Please let me know of any additional information needed for this problem.
Thanks in advance.
Edit: I don’t have any collision detection set up for enemies colliding with walls. The path is followed by the enemy moving towards the last node in the node path list.
Edit: My G calculation is wrong, the scores are not accumulated.
After correctly accumulating the G scores, it’s now finding paths in all 4 directions (with the heuristic set to 0). I’m guessing this means that all the closed list nodes are being added to my final path meaning a problem in my establish path method.
The red numbers show the f score of the node, the blue numbers show the f score of the parent of the node (so you can tell which node is its parent).
After correctly accumulating the G scores, it’s now finding paths in all 4 directions (with the heuristic set to 0).
Edit: I’ve fixed the problem. I’ll submit an answer shortly but basically, my establish path method didn’t do what it should. Instead of adding everything from the closed list, it was supposed to start at the end of the closed list follow through the chain of parents from the end until the starting node was added.
2
Answers
First of all, thanks to J4stM4rt for identifying that I was making a useless comparison (integerA < integerA + positive integer) and Eric Lippert for suggesting that I should set the heuristic to 0 to identify the problem.
My first problem was that I was not accumulating the g-scores for the path. In my G score calculation method I needed to have intG = 10 (or 14) + targetNode.G.
The second problem was the problem mentioned by J4stM4rt in that I was checking if the node's g score was greater than itself + another node's g score which would always be true.
The final problem was in the establish path method, I was adding the parent of every node in the closed list to the path instead of starting at the end and adding each subsequent parent to the path until I reached the start. Below you can see the corrections to my code:
G-Score calculation:
Establish path method:
G score comparison (this may still actually be wrong, I tried changing it to (node.G (cost of moving from the current node's parent to this node) < nodeCurrent.G (cost of moving from the current nodes parent to the current node) + calculation of g for moving from current node to this node) however, this resulted in my enemies becoming stuck again so I changed it to the following and it works seemingly ok:
I do see some flaws in your code. This might not be the problem, but let’s hope it is.
When you’re checking if the node is better than other node in the openlist, you’re doing something weird. That if-statement never even triggers, because something is never smaller than itself + a positive integer. Also you didn’t even set the G-cost of the node yet. So therefore you can’t check it either. This piece of code probably would result in a error (unless G has a standard value).
However I think this piece of code doesn’t even get reached. Because I suspect that this piece of code allways triggers:
You know why?
I can see the idea your trying to achieve, but there isn’t another exact copy of the node in the openset. First of all because the nodes in the openset have their G, H and F cost set, and the node you’re checking doesn’t (so they’re not the same). Thereby if the had the same data in them, I think it still wouldn’t trigger because both nodes have another location in your computer (not 100% sure about this part). This also goes for checking if the node is in the closedset.
What you should be doing is check if there is a node in the openlist with the same location as the node you’re checking. If the node is already in the list, than you should calculate the G-cost of the node we’re dealing with. And check if the G-cost is smaller than the G-cost currently in the list, and change parent etc accordingly.
For the rest your code seems fine, although it’s often hard to see mistakes in pathfinder. Hope this help, if you have any questions don’t hesitate to ask.