A lot of people out there are looking for implementations of the A* (a-star) algorithm for game writing, myself included. Eventually, I gave up trying to find one that fit the bill, and wrote one myself. My needs were complex (and I didn't want a C++ version), so I wrote this as generic as possible, and I'm releasing it for public consumption. Bon appetit!
What Is It?
A* is an algorithm to find the shortest path in a graph. Along with Dijkstra's algorithm, it's commonly used in game programming when a moving unit needs to navigate a map with obstacles, travelling from one location to another. The algorithm will look for a good, short path between the two locations, avoiding obstacles (and perhaps difficult terrain too).
Please be aware that this A* implementation lacks the fully generic nature of the A* graphalgorithm. The domain here is 2D grids, with travel in four or eight directions. If you need to know more about this, Patrick Lester has a good tutorial on this algorithm.
If you absolutely must have more information, many publications on graph theory and algorithms will shed light. Wikipedia has a good article on it, for instance.
Features
Written in pure ANSI C99. It may be integrated with projects written in any language that can interface with C APIs. Namely, every language except INTERCAL1.
The algorithm implements its open list using a fast, custom-designed binary heap.
A* can find complete paths, but it can also yield partial paths when a full path can't be found.
It may be used on small parts of a game map for higher efficiency.
A timeout feature is included for CPU cycle misers.
Routes are found using either the four cardinal directions (North, South, East West), or the full eight directions.
Custom heuristics are supported. In the interest of keeping the algorithm ‘batteries included’, a default Manhattan distance heuristic function is provided. Heuristics can be fine-tuned: different directions can incur different costs2; changing the direction of travel can incur additional cost (this can keep the route more straight). The cost of ‘walking’ on each map square is a continuous value, allowing for different types of terrain (e.g. mountains can be more expensive to cross than plains).
Screenshots
Everyone wants them. Libastar doesn't actually produce any output, so here's the output of the example bundled with the source.
The libastar example has found a route from the green ‘S’ to the magenta ‘E’, avoiding the white ‘X’ blocks.
Here, libastar failed to find a good route and has offered the best compromise.
Example
Using libastar is pretty trivial. Assuming you have a function map_get to retrieve map costs at given co-ordinates, you can find a route like this:
#include <stdio.h>
#include <libastar/astar.h>
#define MAP_WIDTH 100
#define MAP_HEIGHT 100
extern uint8_t map_get (uint32_t x, uint32_t y);
int main (int argc, char ** argv)
{
astar_t * as = astar_new (MAP_WIDTH, MAP_HEIGHT, map_get, NULL);
astar_set_origin (as, 0, 0);
/* Try to find a route from (10,10) to (20,20) */
int result = astar_run (as, 10, 10, 20, 20);
if (astar_have_route (as)) {
directions_t * directions;
uint32_t num_steps = astar_get_directions (as, &directions);
printf ("Found a route with %d steps.\n", num_steps);
/* Do something with the route ... */
astar_free_directions (directions);
} else {
printf ("Route not found, result=%d (%s)\n",
result, as->str_result);
}
return 0;
}
License
This library is provided under the terms of the GNU Public License. The use of the GPL (and not the LGPL, which is more customary for libraries) is deliberate. This is my gift to the free game writing community, and especially to the one-man-project roguelike game writers among us. I've reaped the fruits of your labour long enough!
If you need a version of A* for a commercial piece of software, you may use another version with less restrictive terms. Or get one of your employees to write one. It really isn't that difficult.
Download
You can get this here! Like most of my non-work-related projects, this is maintained in my Copious Free Time, so it's essentially unmaintained — still, I'd love to know if you find it useful or if I can do something to improve it!
If you use a Debian-like Linux distribution, you could download from the BedroomLAN Debian Repository, or view all contents of the project's directory (more versions etc.) in the repository.