A* Path Finding Library

Summary

A* Path-Finder is a library that performs fast and efficient A* path-finding. You can read more about the A* algorithm on Wikipedia.

This code is adapted from CastorTiu’s original A* algorithm; it was slightly cleaned up, and the unsafe code was reused, so that it could work with Silverlight applications. You can read the original article by CastorTiu here. It’s a good read!

Download

• Source code: A* Path-Finder (Source) v1.0 (66.28 kB)
• Silverlight binary: A* Path-Finder (Silverlight) v1.0 (8.43 KB)
• Non-Silverlight binary: A* Path-Finder (Non-Silverlight) v1.0 (8.39 KB)

Benefits of Using A* Path-Finder

If you ever needed to solve a path-finding problem, this is the library for you. It uses a well-established, efficient algorithm to quickly find the best path connecting two points–or tells you if none is available.

Drawbacks

A* path-finding is a best-first algorithm; in certain cases where the path is not optimal, the performance degrades. However, this library implementation was optimized to be extremely fast; the performance is quite good, even on large grids with reasonably complicated paths.

The only other real drawback is that your grid must have a width and height that is a power of two. So if you want a 5×3 grid, you have to use a 8×4 grid. We will try to rectify this at some point.

Sample Code

Below is some sample code to set up a simple grid, and detect if there’s a path between the elements of that grid.

using DeenGames.Utils.AStarPathFinder;

// Sample initialization code
int width = 5;
int height = 3;
width = PathFinderHelper.RoundToNearestPowerOfTwo(width);
height = PathFinderHelper.RoundToNearestPowerOfTwo(height); 

byte[,] grid = new byte[width,height];
for (int i = 0; i < 8; i++) {
  for (int j= 0; j < 4; j++) {
    grid[i, j] = PathFinderHelper.EMPTY_TILE;
  }
}

// Create a grid like this (X = wall, . = free):
// .X...
// .X.X.
// ...X.

grid[1, 0] = PathFinderHelper.BLOCKED_TILE;
grid[1, 1] = PathFinderHelper.BLOCKED_TILE;
grid[3, 1] = PathFinderHelper.BLOCKED_TILE;
grid[3, 2] = PathFinderHelper.BLOCKED_TILE;

List<PathFinderNode> path = new PathFinderFast(grid).FindPath(new Point(0, 0), new Point(4, 2));
if (path != null) {
  // found the path!
}

Initializing and setting-up the grid is the only real difficulty–making sure it’s a power of two, especially, though that’s alleviated by our helper method; everything else is pretty simple. The return value is either null (indicating no path found) or a list of all the nodes in the path.

Technical Design

I cannot comment much on this–you need to read the original article by CastorTiu to find out about this. Suffice to say that it’s efficient and has a decent memory footprint, and an easy-to-use API.

Future Development

There are no plans for future development of this library.