A* pathfinding

Finding one's way from point A to point B can seem like an obvious enough task, but doing it in a way that appears vaguely natural tends to be a little less obvious.

The A* (pronounced "A star") family of algorithms comes from various attempts to improve upon Edsger Dijkstra's algorithm for solving the shortest path problem on a connected graph of nodes. It has become the default method of pathfinding in modern gaming.

Presented here is a simple variation of the A* algorithm, which demonstrates the core theme present in all the A* variations. This is a good starting point from which to tailor a solution optimized for your particular situation.

Getting ready

This recipe requires three, 20 x 20 pixel textures to represent a patch of ground, a segment of undecided path, and the final selection of path.

How to do it...

1. 1. Add a class to hold the map of the landscape to be navigated:

   class Map
   {
   Rectangle arena = new Rectangle(0, 0, 20, 20);
   public int Width
   {
   get
   {
   return arena.Width...