4 
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);
    }
}

实现 A* 算法也是如此，当它找到目标时，它会转到 ReconstructPathRecursive 应用程序崩溃并抛出此异常An unhandled exception of type 'System.StackOverflowException' occurred in mscorlib.dll

和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怎么了！

4

2 回答 2

1

它实际上不必是递归的，因为它是尾递归的。所以你可以像这样重写它：

private void ReconstructPathIterative(Location2D current_node)
{
    Location2D temp;
    while (came_from.TryGetValue(current_node, out temp))
    {
        path.Add(temp);
        current_node = temp;
    }
    path.Add(current_node);
}

这仅在路径太长而无法放入堆栈时才有帮助，如果它是无限的，则无济于事。

于 2012-04-09T20:06:37.900 回答
1

NodeInfo Parent {get; set; }我通过在类中添加一个文件来修复它，并在暂定更好时NodeInfo添加新的List<NodeInfo>调用：-Nodes

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

然后当它找到目标时：-

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

哪里ReconstructPath： -

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

现在工作正常。

于 2012-04-10T10:32:30.090 回答