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

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.

18 Responses to A* Path Finding Library

  1. Alessandro Morais says:

    With this lib, i could implement pathfinding in my game in like 2 minutes. A thing i couldn’t do by my own, because of my still poor programming experience.

    Thanks alot!

  2. Ashiq Alibhai says:

    That’s precisely the point! I myself needed it and saved hours by simply finding and enhancing (slightly) an existing library. We always talk about code reuse, but we rarely practice it.

  3. Alan says:

    Error  12  Argument 1: cannot convert from 'AlchemyProxy.Point' to 'DeenGames.Utils.Point'  C:\Users\AlanKnight\Desktop\AlchemyProxy(2)\AlchemyProxy\Handlers\Bot.cs  50  75  AlchemyProxy

    Help >.<

  4. Ashiq Alibhai, PMP says:

    @Alan: what line of code did you write that caused this? Did you import the DeenGames.Utils.Point class? It looks like the compiler can’t distinguish that from an AlchamyProxy.Point class.

  5. Alan says:

    List path = new PathFinderFast(grid).FindPath(new Point(0, 0), new Point(4, 2))

    I get the error with that :( Yes I imported.

    using DeenGames.Utils.AStarPathFinder;

  6. Alan says:

    Ok I got it so there is no error but the pathfinding isn’t working?

  7. Alan says:

    Ok so I eventually found something that within reason worked for me :)

  8. I was wanting to look at the source code for how exactly you optimized CastorTiu’s code and got it working for Silverlight, but the link to your source code above is for Persistent Storage instead of A* Path-Finder. If you could add the source code for the pathfinding, that would be awesome!

  9. Ashiq Alibhai, PMP says:

    @Chris thanks for pointing it out, I fixed the link. I didn’t optimize the code; the original author did. I make no claim on it :) except to make it slightly easier to use by not forcing you to pass a power-of-two grid size.

  10. I really like this library, good job!

    Only thing i noticed is, when i use a grid of 128×64, 64×32, or pretty much whenever the width and height is different (the grid is rather complex — think of a maze), sometimes it gives me an OutOfMemoryException. And “Sometimes” becomes “All the time” when it’s called a few times per second. :S

    So for now, i’m using a square grid of 128×128, works fine, but i’m puzzled.

  11. Rick says:

    Hi, this is a great post :) I used the sample code above and it works fine for that example but if I change the ‘new PathFinderFast(grid).FindPath(new Point(0, 0), new Point(4, 2))’ to a different point so (4,2) to (4,1) ‘new PathFinderFast(grid).FindPath(new Point(0, 0), new Point(4, 1))’ it throws a System.OutOfMemoryException even though there is a path that exists.

    Is this a problem with the library?

  12. Ashiq Alibhai, PMP says:

    Rick: It might be related to the grid not being a power-of-two on one of the dimensions (that’s a requirement). Try using a power-of-two grid (like 4×2 or 4×4).

    Thanks! It’s not my library, so I can’t take any credit for it :)

  13. Lyle says:

    Thanks for putting this up.

    PathFinder works great. PathFinderFast on the other hand only finds a path if it is really short(not sure exactly but likely <4 nodes.) When no path is found the built in debug output only returns ~4 times all saying Fx and Fy = 0.

    Any ideas? If not, at least this comment is here for anyone else in the future.

  14. Lyle says:

    Figured it out, both width and height of the grid need to be the same value.
    I had them as powers of two, but not the same value. Works great nowl

  15. Ashiq Alibhai, PMP says:

    @Lyle great, thanks for posting the solution here. I’m not really supporting these any more, but I will make a note somewhere to come back and fix this. (Internally, we just create a power-of-two size grid anyway, so there’s no problem making it rectangular instead of square.)

  16. Quick question about the grid loop. You have:

    for (int i = 0; i < 8; i++) {
    for (int j= 0; j < 4; j++) {

    Shouldn't that be looping like this:

    for (int i = 0; i < width; i++) {
    for (int j= 0; j < height; j++) {

    Or does the nature of the grid make it function differently and you have to use 8 and 4?

  17. Ashiq Alibhai, PMP says:

    @Jeremy you can use width and height properties. I use 8 and 4 to point out that it rounds to a power of two (the actual dimensions I wanted were 5×3).

  18. Marco says:

    This is a good library, but keep in mind that the sample is very very simple and it looks like it´s only intended for demostration, since it´s not at all optimal, and when you try to change the path you want to find it crashes, so you will need a little bit of exploration and knowledge to make this work right.

    If anyone intrested I came up with this, which I think it´s a better example. Hope it helps

    http://pastebin.com/Ex2UvjPv

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>