Browse Source Download (without any required ccan dependencies)
a_star
A straightforward implementation of the a-star path finding algorithm
This code implements the A-star pathfinding algorithm without relying on any particular representation of the graph being searched other than that each node can be represented uniquely by a void pointer, which it treats as an opaque identifier. To use it, you need to provide, besides a start and a goal node, a function to estimate the distance (however you choose to define that) and cost (however you choose to define that) as a floating point value between two nodes, and a function to iterate over the neighbor nodes of any given node. Additionally you may provide a context pointer (cookie) which is simply passed back to your callback functions
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ccan/a_star/a_star.h>
static char maze[] =
"##########@################x#################\n"
"# # #\n"
"# # #\n"
"# ########### ################### #\n"
"# # # # # #\n"
"#### # # # #\n"
"# # # ######## # #\n"
"# # ######### # # # #\n"
"# # # # #\n"
"# # # # #\n"
"# # ##### ##################\n"
"# ########## # #\n"
"# # # # #\n"
"# ######################### #\n"
"# # # # #\n"
"############ # # # #\n"
"# # # #\n"
"#############################################\n";
static int maze_width(char *maze)
{
char *n;
n = strchr(maze, '\n');
return 1 + n - maze;
}
static int xoff[] = { 0, 1, 0, -1 };
static int yoff[] = { 1, 0, -1, 0 };
static char *maze_node(char *maze, int x, int y)
{
return maze + y * maze_width(maze) + x;
}
static void *nth_neighbor(void *context, void *p, int n)
{
char *maze = context;
char *c = p;
int i, x, y, offset = c - maze;
x = offset % maze_width(maze);
y = offset / maze_width(maze);
for (i = n; i < 4; i++) {
int tx = x + xoff[i];
int ty = y + yoff[i];
if (tx < 0 || ty < 0)
continue;
if (ty * maze_width(maze) + tx > strlen(maze))
continue;
c = maze_node(maze, x + xoff[i], y + yoff[i]);
if (*c != '#')
return c;
}
return NULL;
}
static float maze_cost(void *context, void *first, void *second)
{
char *maze = context;
char *f = first;
char *s = second;
int sx, sy, fx, fy;
float d, dx, dy;
int fp = f - maze;
int sp = s - maze;
sx = sp % maze_width(maze);
sy = sp / maze_width(maze);
fx = fp % maze_width(maze);
fy = fp / maze_width(maze);
dx = (float) sx - fx;
dy = (float) sy - fy;
d = (float) (abs(dx) + abs(dy));
return d;
}
int main(int argc, char *argv[])
{
static int maxnodes, i;
char *start, *goal;
struct a_star_path *path;
start = strchr(maze, '@');
goal = strchr(maze, 'x');
maxnodes = strlen(maze);
path = a_star((void *) maze, start, goal, maxnodes, maze_cost, maze_cost, nth_neighbor);
if (!path) {
printf("a_star() failed to return a path.\n");
return 0;
}
for (i = 0; i < path->node_count; i++) {
char *p = path->path[i];
*p = '.';
}
*goal = 'x';
*start = '@';
printf("%s\n", maze);
free(path);
return 0;
}
GPL (v2 or any later version)