Ein * Implementierungsproblem

Ich gebe eine Niederlage zu, ich muss der Community dieselbe Frage stellen, die sie schon millionenfach gestellt hat: "Was ist falsch an MEINER Implementierung des A * -Algorithmus?"

Ich erhalte einige sehr wackelige Ergebnisse, insbesondere bei Zielpositionen, deren x-Koordinate gleich oder kleiner als die x-Koordinate des Schauspielers ist. Es muss etwas los sein, wie ich die Nachbarn durchsuche, etwas mit meiner Heuristik oder sogar etwas mit der Verwendung meiner Datenstrukturen ...

Hier ist ein Beispiel für einige seltsame Pfade, die es generiert:

Hier ist meine eigene Version des A *, die an mir stirbt:

/// <summary>
/// Tries to get a path from the start to the end.
/// </summary>
/// <param name="start">Start of the path.</param>
/// <param name="end">End of the path.</param>
/// <param name="grid">Grid of values indicating whether grid squares are open or closed.</param>
/// <param name="path">Path from start to end.</param>
/// <returns>Whether a valid path could be found.</returns>
public bool TryGetAStarPath(Point start, Point end, out List<Point> path)
{
    // setup the path
    path = new List<Point>();

    // if either start or end is bad then don't find a path
    if (!this.IsSquareOpen(start) || !this.IsSquareOpen(end))
    {
        return false;
    }

    // setup sets
    var closed = new Dictionary<Point, AStarNode>();
    var cameFrom = new Dictionary<Point, AStarNode>();
    var open = new LinkedList<AStarNode>();
    open.InsertNode(new AStarNode(start, null, end));

    // keep going until the open set has nothing in it
    while (open.Count > 0)
    {
        // node currently being examined
        var current = open.GrabAndRemoveFirst();

        // if the end was found then reconstruct the path and return it
        if (current.Position == end)
        {
            // construct the path
            var currentPathNode = current;
            while (currentPathNode != null && currentPathNode.Position != start)
            {
                // add node position to the path
                path.Add(currentPathNode.Position);

                // get the node this node came from
                cameFrom.TryGetValue(currentPathNode.Position, out currentPathNode);
            }

            // the path is currently reversed, correct it
            path.Reverse();

            // successfully found a path
            return currentPathNode.Position == start;
        }

        // add current to the closed set
        closed.Add(current.Position, current);

        // iterate through all the neighbors
        foreach (var neighbor in this.GetNeighbors(current, end))
        {
            // if the neighbor is already in the closed set or the square is not open then skip it
            if (!this.IsSquareOpen(neighbor.Position) || closed.ContainsKey(neighbor.Position))
            {
                continue;
            }

            // if the neighbor is in the open set then compare the g-score
            var testAgainstNode = open.Find(neighbor);
            if (testAgainstNode == null || testAgainstNode.Value.FScore < neighbor.FScore)
            {
                // set the came-from node
                if (cameFrom.ContainsKey(neighbor.Position))
                {
                    cameFrom.Remove(neighbor.Position);
                }

                cameFrom.Add(neighbor.Position, current);

                // add or replace the neighbor on the open set
                if (open.Contains(neighbor))
                {
                    open.Remove(neighbor);
                }

                open.InsertNode(neighbor);
            }
        }
    }

    // if we are here then the path was never found
    return false;
}

Ich verwende eine Suche nach Nachbarn, die so aussieht:

/// <summary>
/// Gets all the neighboring grid squares to the current grid square based on its location.
/// </summary>
/// <param name="current">Current grid square to find the neighbor locations for.</param>
/// <param name="endPoint">Location of the end-point.</param>
/// <returns>Neighboring grid square locations.</returns>
private IEnumerable<AStarNode> GetNeighbors(AStarNode current, Point endPoint)
{
    // setup the search space
    var searchspace = new int[] { -1, 0, 1 };

    // find the neighbors
    foreach (var x in searchspace)
    {
        foreach (var y in searchspace)
        {
            // skip 0, 0
            if (x == y && x == 0)
            {
                continue;
            }

            // test if in bounds
            var testPoint = new Point(current.Position.X + x, current.Position.Y + y);
            if (testPoint.WithinBounds(this))
            {
                yield return new AStarNode(testPoint, current, endPoint);
            }
        }
    }
}

Und schließlich ist mein AStarNode-Objekt definiert als:

/// <summary>
/// A-Star node.
/// </summary>
class AStarNode
{
    // Variable declarations elided

    /// <summary>
    /// Instantiates a new instance of the <see cref="AStarNode"/> class.
    /// </summary>
    /// <param name="position">Position of the node on the grid.</param>
    /// <param name="parent">Node that this node comes from.</param>
    /// <param name="endPoint">The goal.</param>
    public AStarNode(Point position, AStarNode parent, Point endPoint)
    {
        // set the position
        this.Position = position;

        // calculate the scores
        this.CalculateScores(parent, endPoint);
    }

    /// <summary>
    /// Calculates the f, g, and h scores for this node.
    /// </summary>
    /// <param name="parent">Node that this node comes from.</param>
    /// <param name="endPoint">The goal.</param>
    private void CalculateScores(AStarNode parent, Point endPoint)
    {
        // h-score is the estimated distance to the end-point
        this.HScore = (float)Math.Sqrt(Math.Pow(endPoint.X - this.Position.X, 2) + Math.Pow(endPoint.Y - this.Position.Y, 2)) * HSCORE_MULTIPLIER;

        // g-score is the actual distance from the start
        if (parent == null)
        {
            this.GScore = 0;
        }
        else
        {
            this.GScore = parent.GScore + (parent.Position.X == this.Position.X || parent.Position.Y == this.Position.Y ? CARDINAL_MOVEMENT_COST : DIAGONAL_MOVEMENT_COST);
        }

        // f-score is g + h
        this.FScore = this.GScore + this.HScore;
    }

    public static bool operator ==(AStarNode left, Point right) => left.Position == right;
    public static bool operator !=(AStarNode left, Point right) => !(left == right);
    public override int GetHashCode() => -425505606 + EqualityComparer<Point>.Default.GetHashCode(Position);
    public override bool Equals(object obj)
    {
        var node = obj as AStarNode;
        return node != null &&
               Position.Equals(node.Position);
    }
}

Oh, und ich denke, es ist auch wichtig zu wissen, wie ich das LinkedList-Objekt einfüge und daraus entferne. Warum verwende ich eine verknüpfte Liste? Damit steht der Knoten mit dem kürzesten Weg immer am Anfang mit winzigen Einfügungs- und Entfernungskosten.

/// <summary>
/// Inserts the provided node into the linked list based on it's f-score value.
/// </summary>
/// <param name="list">Linked list to instert into.</param>
/// <param name="node">Node to insert.</param>
public static void InsertNode(this LinkedList<AStarNode> list, AStarNode node)
{
    // if the list is empty then just insert
    if (list.Count == 0)
    {
        list.AddFirst(node);
    }
    else
    {
        // start at the front of the list and move toward the end looking for the right spot to insert
        var compareNode = list.First;
        while (compareNode != null && compareNode.Value.FScore <= node.FScore)
        {
            compareNode = compareNode.Next;
        }

        // if the compare node is null then add to the end, otherwise add before the compare node
        if (compareNode == null)
        {
            list.AddLast(node);
        }
        else
        {
            list.AddBefore(compareNode, node);
        }
    }
}

/// <summary>
/// Grabs and removes the first node from the linked list.
/// </summary>
/// <param name="list">Linked list.</param>
/// <returns>First node.</returns>
public static AStarNode GrabAndRemoveFirst(this LinkedList<AStarNode> list)
{
    // if the list is empty then return null
    if (list.Count == 0)
    {
        return null;
    }

    // get the value to return and remove it from the list
    var toReturn = list.First;
    list.RemoveFirst();

    // return the node
    return toReturn.Value;
}

Da Ihr Ziel eher die Implementierung als die Entwicklung von Spielen ist, empfehle ich dringend, Tools zu schreiben, um Ihre Implementierung zu testen.

Wie jemand im Kommentarbereich betonte, ist es besser, wenn Sie eine nachvollziehbare "Ausführung auf Papier" in irgendeiner Form von "Ich kann sehen und sehen, wo etwas schief geht" hatten.

Ich bin sicher, dass einige von uns den Schmerz durchstehen könnten, Ihren Code zu betrachten, aber ich bezweifle die Möglichkeit.

Ich kann Ihnen nur helfen, "Ihren Code zu betrachten und ihn dann in meinem Kopf auszuführen, um zu verstehen, wie der Code funktioniert", und das klingt nur schmerzhaft.

Ich empfehle Ihnen dringend, etwas wie das Folgende zu erstellen, um sich eine bessere Vorstellung davon zu machen, wie Ihr Code funktioniert.

Auf den ersten Blick kann ich jedoch einige Dinge sagen, die mit Ihrer Implementierung nicht in Einklang stehen.

Dort machen Sie eine diagonale Kurve, bewegen sich dann vorwärts und drehen dann. Es scheint, als ob Ihr Ding "diagonale Bewegungen" nicht richtig handhabt.

WENN Ihre diagonale Bewegung so viel kosten würde wie das angrenzende Plättchen, sollte Ihr Pfad so etwas wie ...

Wenn Sie die gleichen Bewegungskosten für die diagonale Bewegungsrichtung anwenden, kann dies den zweiten Fehlerfall Ihres Screenshots erklären.

Es gibt keinen Kostenunterschied zwischen blauem und violettem Pfad, da Sie die diagonale Bewegung so einstellen, dass sie genauso viel kostet wie die benachbarte Bewegung.

Aber bei Ihrem zweiten Debug-Schuss kann ich nicht einmal verstehen, was hier vor sich geht. Es gibt mehr als drei Möglichkeiten, diese Ausgabe zu lesen. In welche Richtung und Reihenfolge geht Ihr Programm? Du musst es mir sagen.

Also im Grunde genommen,

1. Ich kann mir vorstellen, was los ist. Ich hoffe meine Vermutung hilft.
2. Wenn Sie tatsächlich Hilfe erhalten und dieses Problem angehen möchten, benötigen Sie ein besseres Debug-Ergebnis, damit Sie und andere Personen sehen und verstehen können, was mit Ihrem Code nicht stimmt. Andernfalls muss sich jemand Ihren Code ansehen und ihn "im Kopf ausführen".