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.
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!
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.
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 AlchemyProxyHelp >.<
@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.
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;
Ok I got it so there is no error but the pathfinding isn’t working?
Ok so I eventually found something that within reason worked for me
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!
@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.
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.
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?
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
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.
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
@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.)
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?
@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).
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