# A* implementation issue

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:

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>();
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

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

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

// 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)
{
}
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)
{
}
else
{
}
}
}

/// <summary>
/// Grabs and removes the first node from the linked list.
/// </summary>
/// <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
}

• 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. – DMGregory Apr 17 '18 at 8:23
• @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. – Timothy Eckstein Apr 17 '18 at 13:53
• 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) – Guiroux Apr 17 '18 at 13:55
• @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). – Timothy Eckstein Apr 17 '18 at 14:43
• 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. – Liuka Apr 21 '18 at 18:17

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.

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

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...

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

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. 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".