## Thursday, December 23, 2010

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

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