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.

どうしたの！

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; }内にフィールドとして追加することで修正し、暫定的な方が良い場合に呼び出される新しいものを追加します:-NodeInfoList<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 に答える