A* Path Finding Library


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!


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.


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

28 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


  19. Regina says:

    Hello Sir. We’re having a project about A* Pathfinder. I’m glad to have crossed-path on your link. May I ask, if you don’t mind. What’s the difference between the two libraries, A*Pathfinder for Silverlight and A*Pathfinder for Non-silverlight in their functions? I would be glad and feel honored for your reply. Thank you.

  20. Ashiq Alibhai, PMP says:

    @Regina it’s not my code, I just repackaged it to make it easy to use. There is no difference; you just can’t link non-Silverlight code from Silverlight projects, which is why there’s a separate DLL for that.

  21. Regina says:

    Thank you for your time sir. But, I have a follow-up question. If I’m not going to use Silverlight, what other options can I have in connection to this project?

  22. Regina says:

    What I mean sir is that, can you please suggest me a non-silverlight application? I believe sir that you have these great ideas in hand. :) Thank you very much sir.

  23. Hey i found your article and it seems to be working properly as i wanted!.

    I hope you don’t mind but i uploaded it to github:

    I hope you don’t mind. If you feel uncomfortable with it uploaded, let me know and i can take it down

  24. Ashiq Alibhai, PMP says:

    @Ezequiel thanks for the nudge. I would prefer to upload (and maintain) it myself, but you’re welcome to mirror/fork/etc. I’ll post it in a day or two if I can.

  25. T0by says:

    I think it’s stuck. i keep getting a return that a path was found even when there should be no paths. Also, is there a method to print a list of the nodes in the path?

  26. T0by says:

    Apologies! it’s not stuck, just an oversight on my part.
    I’d still really appreciate a more direct way to print out the nodes in the path, mine is a lil sloppy. And a way to set the parameters especially the no diagonals.

    foreach (PathFinderNode node in path)
    Console.Write(“X = ” + node.PX); Console.WriteLine( ” , Y = ” + node.PY);

  27. JamilaX says:

    I must say you have very interesting articles here.
    Your content should go viral. You need initial boost only.
    How to get massive traffic? Search for: Murgrabia’s tools go viral

  28. nonlagma ea says:

    Excellent website. A lot of helpful information here. I am sending it to some pals ans also sharing in delicious. And of course, thank you to your sweat!

Leave a Reply

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