The A* algorithm in XNA

The A* search algorithm ("A star") is used for path finding and graph traversal. The following is my implementation in XNA.

The A* algorithm itself is very similar to Dijkstra's algorithm but the A* uses heuristics to achieve better performance.

Screenshots

Usage

Left Mouse Click - Create a barrier
CTRL + Left Mouse Click - Set the source
ALT + Left Mouse Click - Set the destination
Space - Toggle grid lines
Enter - Start pathfinding!
` - Open the developer console

Heuristics

The A* algorithm uses a heuristic to improve performance by trying to "guess" the best path, although this will not, unlike Dijkstra's which does not use a heuristic, guarantee the shortest path.

Diagonal Distance

public int GetEstimate(Point source, Point destination)
{
    return Math.Max(Math.Abs(destination.X - source.X), Math.Abs(destination.Y - source.Y));
}

Manhattan Distance

public int GetEstimate(Point source, Point destination)
{
    return Math.Abs(destination.X - source.X) + Math.Abs(destination.Y - source.Y);
}

Euclidean Distance

public int GetEstimate(Point source, Point destination)
{
    return (int)Math.Sqrt(Math.Pow(source.X - destination.X,2) + Math.Pow(source.Y - destination.Y,2));
}

Dijkstra

When the heuristic is 0, the A* algorithm turns into Dijkstra's algorithm

public int GetEstimate(Point source, Point destination)
{
    return 0;
}

Try it!

The source can be found on github: https://github.com/dreasgrech/AStarXNA