6 * a_star - A straightforward implementation of the a-star path finding algorithm
8 * This code implements the A-star pathfinding algorithm without relying on any
9 * particular representation of the graph being searched other than that each node
10 * can be represented uniquely by a void pointer, which it treats as an opaque
11 * identifier. To use it, you need to provide, besides a start and a goal node,
12 * a function to estimate the distance (however you choose to define that) and
13 * cost (however you choose to define that) as a floating point value between
14 * two nodes, and a function to iterate over the neighbor nodes of any given
15 * node. Additionally you may provide a context pointer (cookie) which is simply
16 * passed back to your callback functions
24 * #include <ccan/a_star/a_star.h>
26 * static char maze[] =
27 * "##########@################x#################\n"
30 * "# ########### ################### #\n"
33 * "# # # ######## # #\n"
34 * "# # ######### # # # #\n"
37 * "# # ##### ##################\n"
38 * "# ########## # #\n"
40 * "# ######################### #\n"
42 * "############ # # # #\n"
44 * "#############################################\n";
46 * static int maze_width(char *maze)
50 * n = strchr(maze, '\n');
51 * return 1 + n - maze;
54 * static int xoff[] = { 0, 1, 0, -1 };
55 * static int yoff[] = { 1, 0, -1, 0 };
57 * static char *maze_node(char *maze, int x, int y)
59 * return maze + y * maze_width(maze) + x;
62 * static void *nth_neighbor(void *context, void *p, int n)
64 * char *maze = context;
66 * int i, x, y, offset = c - maze;
68 * x = offset % maze_width(maze);
69 * y = offset / maze_width(maze);
71 * for (i = n; i < 4; i++) {
72 * int tx = x + xoff[i];
73 * int ty = y + yoff[i];
74 * if (tx < 0 || ty < 0)
76 * if (ty * maze_width(maze) + tx > strlen(maze))
78 * c = maze_node(maze, x + xoff[i], y + yoff[i]);
85 * static float maze_cost(void *context, void *first, void *second)
87 * char *maze = context;
96 * sx = sp % maze_width(maze);
97 * sy = sp / maze_width(maze);
98 * fx = fp % maze_width(maze);
99 * fy = fp / maze_width(maze);
101 * dx = (float) sx - fx;
102 * dy = (float) sy - fy;
103 * d = (float) (abs(dx) + abs(dy));
107 * int main(int argc, char *argv[])
109 * static int maxnodes, i;
110 * char *start, *goal;
111 * struct a_star_path *path;
113 * start = strchr(maze, '@');
114 * goal = strchr(maze, 'x');
115 * maxnodes = strlen(maze);
117 * path = a_star((void *) maze, start, goal, maxnodes, maze_cost, maze_cost, nth_neighbor);
119 * printf("a_star() failed to return a path.\n");
122 * for (i = 0; i < path->node_count; i++) {
123 * char *p = path->path[i];
129 * printf("%s\n", maze);
134 * License: GPL (v2 or any later version)
136 int main(int argc, char *argv[])
138 /* Expect exactly one argument */
142 if (strcmp(argv[1], "depends") == 0) {