Manhattan Heuristic function for A-star (A*)
- by Shawn Mclean
I found this algorithm here.
I have a problem, I cant seem to understand how to set up and pass my heuristic function.
static public Path<TNode> AStar<TNode>(TNode start, TNode destination,
Func<TNode, TNode, double> distance,
Func<TNode, double> estimate) where TNode : IHasNeighbours<TNode>
{
var closed = new HashSet<TNode>();
var queue = new PriorityQueue<double, Path<TNode>>();
queue.Enqueue(0, new Path<TNode>(start));
while (!queue.IsEmpty)
{
var path = queue.Dequeue();
if (closed.Contains(path.LastStep))
continue;
if (path.LastStep.Equals(destination))
return path;
closed.Add(path.LastStep);
foreach (TNode n in path.LastStep.Neighbours)
{
double d = distance(path.LastStep, n);
var newPath = path.AddStep(n, d);
queue.Enqueue(newPath.TotalCost + estimate(n), newPath);
}
}
return null;
}
As you can see, it accepts 2 functions, a distance and a estimate function.
Using the Manhattan Heuristic Distance function, I need to take 2 parameters. Do I need to modify his source and change it to accepting 2 parameters of TNode so I can pass a Manhattan estimate to it? This means the 4th param will look like this:
Func<TNode, TNode, double> estimate) where TNode : IHasNeighbours<TNode>
and change the estimate function to:
queue.Enqueue(newPath.TotalCost + estimate(n, path.LastStep), newPath);
My Manhattan function is:
private float manhattanHeuristic(Vector3 newNode, Vector3 end)
{
return (Math.Abs(newNode.X - end.X) + Math.Abs(newNode.Y - end.Y));
}
