I'm attempting to implement A* pathfinding in my game, and it works for most of the iterations I've tested it with, but I've hit a few random cases where it never stops loading items into the Closed and Open lists, making me think I have a leak in my logic somewhere. I think it's caused when there are multiple options that have equal G+H values, and it even happens when the origin and target are only 2-3 steps apart, but I'm not sure how to protect against multiple equal values.
This implementation is based on the Wikipedia pseudocode and some other helpers I've found around the web:
private Point getNextPoint(Point sourceLoc, Point targetLoc)
{
// clear the lists
openList.Clear();
closedList.Clear();
// find direction of targetLoc
GridFacing facing = findFacing(sourceLoc, targetLoc);
// get starting adjacent locations
foreach (Node node in getNeighbors(new Node(sourceLoc.X, sourceLoc.Y), (int)facing, targetLoc))
{
openList.Add(node);
}
Node previous = new Node();
while (openList.Count > 0)
{
// current lowest G+H
int indexS = openList.Min(f => f.F);
// get next node with lowest G+H that is not the previous node
Node node = openList.First(f => f.F == indexS && f != previous);
// check for goal
if (node.Loc == targetLoc)
{
return recurseNextNode(node).Loc;
}
// remove from openset
openList.Remove(node);
// add to closedset
closedList.Add(node);
// get neighbors of current location
List<Node> sortedNeighbors = getNeighbors(node, (int)facing, targetLoc);
foreach (Node neighbor in sortedNeighbors)
{
// not in closed set
if (closedList.Contains(neighbor))
continue;
// steps from source
int tempG = node.G + 1;
// not already in openset or temp g less than existing g;
if (!openList.Any(f => f.Loc == neighbor.Loc && f.G == tempG) || tempG < neighbor.G)
{
neighbor.Parent = node;
neighbor.G = tempG;
neighbor.H = Convert.ToInt32(GetDistance(neighbor.Loc, targetLoc));
if (!openList.Contains(neighbor) && !closedList.Contains(neighbor))
openList.Add(neighbor);
}
}
previous = node;
}
return new Point(0, 0);
}
What in this implementation is allowing for these massive loops, and how do I protect against it?
