7
\$\begingroup\$

I admit defeat, I must ask the community the same question it has been asked a million times before: "What is wrong with MY implementation of the A* algorithm?"

I am getting some very wonky results, especially with goal locations which have a x-coordinate equal to or less than the actor's x-coordinate. There's gotta be something going on with how I'm searching through the neighbors, something with my heuristic, or even something with the use of my data structures...

Here is an example of some strange paths that it generates: enter image description here enter image description here

Here is my own version of the A* that is dying on me:

/// <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;
}

I am using a search for neighbors that looks like this:

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

And finally my AStarNode object is defined as:

/// <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, and I guess it is also important to know how I'm inserting and removing from the LinkedList object. Why do I use a linked list? So that the node with the shortest path is always at the beginning with tiny insert and remove costs.

/// <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;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Can you include some examples of the "wonky" results you get? Sometimes the symptoms can help narrow down the problem. Also, your rationale for using a linked list sounds more like a reason to use a min-heap, as is more typical for Djikstra & A* implementations. It gives you O(log n) insertion rather than O(n) as you have now. \$\endgroup\$ – DMGregory Apr 17 '18 at 8:23
  • \$\begingroup\$ @DMGregory I added some images, each show something odd. The second image shows back-tracking. You're right about the min-heap; if .NET doesn't already have an implementation then I can do that next. \$\endgroup\$ – Timothy Eckstein Apr 17 '18 at 13:53
  • \$\begingroup\$ A* is the kind of algorithm that is easy to debug on simple cases by "executing on paper", you should keep trying to correct it yourself IMHO (would make you feel better to accomplish this on your own) \$\endgroup\$ – Guiroux Apr 17 '18 at 13:55
  • 1
    \$\begingroup\$ @Sidar moving diagonally through gaps is currently expected behavior. What's concerning is that the path only starts bending around the wall right before it reaches the wall - then it back-tracks (that's the four highlighted squares forming a larger square). \$\endgroup\$ – Timothy Eckstein Apr 17 '18 at 14:43
  • 1
    \$\begingroup\$ On a side note as I cannot see the definition of HSCORE_MULTIPLIER. Mind that for A* to be optimal, if I remember correctly, the HScore should never be higher than the actual value needed to reach the target and so, in this case, HSCORE_MULTIPLIER shouldn't be more than 1, or you could overstimate the cost. \$\endgroup\$ – Liuka Apr 21 '18 at 18:17
3
\$\begingroup\$

Since your goal is implementation rather than game dev, I highly recommend writing tools to test out your implementation.

As someone in comment section pointed out, it is better if you had traceable "executing on paper" some form of "I can look at and see where things are going wrong".

I am sure some of us could go through the pain of looking at your code but I doubt the possibility.

Only way for me to help you is "looking at your code then executing it in my head to understand how the code works" and that sounds just painful tbh.

I highly recommend for you to create something like below to help yourself to get a better idea on how your code works.

enter image description here

Though from the quick glance I can tell a few things that are wrong with your implementation.

enter image description here

There you are making a diagonal turn, then moving forward ahead then turning. It seems like your thinging doesn't properly handle "diagonal moving".

IF your diagonal moving would cost as much as to the adjacent tile then your path should be something like... enter image description here

If you are applying the same movement cost for diagonal movement direction, it can explain the 2nd error case of your screenshot. enter image description here

There is no cost difference between blue path and purple path because you set diagonal movement to cost as much as the adjacent movement.

But your 2nd debug shot, I can't even understand what is going on here. enter image description here There are more than three ways you can read this output. What is the direction and order in which your program is taking? I need you to tell me.

So basically,

  1. I can guess what is wrong. I hope my guess helps.
  2. If you actually want to get help and tackle this thing, you need better debug result for yourself and other people to look at and understand what is wrong with your code. Otherwise someone needs to look at your code and "run it in their head".
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.