A* Algorithm System.StackOverflowException

Question

public List<Location2D> Path(Location2D start, Location2D goal)
{
    openset = new List<NodeInfo>(); // The set of tentative nodes to be evaluated, initially containing the start node.
    closedset = new List<NodeInfo>(); // The set of nodes already evaluated.
    path = new List<Location2D>(); // The path result.
    came_from = new Dictionary<Location2D, Location2D>();

    NodeInfo Start = new NodeInfo();
    Start.SetLoction(start.X, start.Y);
    Start.H = GetHValue(start, goal);
    openset.Add(Start);

    while (openset.Count > 0) { // while openset is not empty
        NodeInfo current = CheckBestNode(); //the node in openset having the lowest f_score[] value

        if (current.Location.Equals(goal)) {
            ReconstructPathRecursive(current.Location);
            return path;
        }

        for (int i = 0; i < 8; i++) { // neighbor nodes.
            NodeInfo neighbor = new NodeInfo();
            neighbor.SetLoction((ushort)(current.Location.X + ArrayX[i]), (ushort)(current.Location.Y + ArrayY[i]));

            bool tentative_is_better = false;

            if (closedset.Contains(neighbor))
                continue;
            if (!map.Cells[neighbor.Location.X, neighbor.Location.Y].Walkable) { closedset.Add(neighbor); continue; }

            Double tentative_g_score = current.G + DistanceBetween(current.Location, neighbor.Location);

            if (!openset.Contains(neighbor)) {
                openset.Add(neighbor);
                neighbor.H = GetHValue(neighbor.Location, goal);
                tentative_is_better = true;
            } else if (tentative_g_score < neighbor.G) {
                tentative_is_better = true;
            } else {
                tentative_is_better = false;
            }

            if (tentative_is_better) {
                came_from[neighbor.Location] = current.Location;
                neighbor.G = tentative_g_score;
            }
        }
    }
    return null;
}

private void ReconstructPathRecursive(Location2D current_node)
{
    Location2D temp;
    if (came_from.TryGetValue(current_node, out temp)) {
        path.Add(temp);
        ReconstructPathRecursive(temp);
    } else {
        path.Add(current_node);
    }
}

so am Implementing A* Algorithm and when it find the Goal it goes to the ReconstructPathRecursive and then the app crash and throw this exception An unhandled exception of type 'System.StackOverflowException' occurred in mscorlib.dll

and This thread is stopped with only external code frames on the call stack. External code frames are typically from framework code but can also include other optimized modules which are loaded in the target process.

idk what's wrong!

Answer 1

I fixed it by adding NodeInfo Parent {get; set; } as a filed inside the NodeInfo class, and I add new List<NodeInfo> called Nodes when tentative is better :-

if (tentative_is_better) {
                        neighbor.Parent = current;
                        nodes.Add(neighbor);
                        neighbor.G = tentative_g_score;
                    }

then when it finds the goal :-

if (current.Location.Equals(goal)){
                    ReconstructPath(current);
                    path.Reverse();
                    return path;
                }

where ReconstructPath :-

private void ReconstructPath(NodeInfo current) {
            if (current.Parent == null) return;
            path.Add(current.Parent.Location);
            ReconstructPath(current.Parent);
        }

and it works fine now.