X-Git-Url: https://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Fa_star%2F_info;fp=ccan%2Fa_star%2F_info;h=2cfd941a19fb1dde72a76d590341f8b7e0f60d45;hb=d045cbf77cbaaa784c5627e5cb8eee9155214229;hp=0000000000000000000000000000000000000000;hpb=64b9c66673ed48b09c9be72668acdfb9230df488;p=ccan

diff --git a/ccan/a_star/_info b/ccan/a_star/_info
new file mode 100644
index 00000000..2cfd941a
--- /dev/null
+++ b/ccan/a_star/_info
@@ -0,0 +1,147 @@
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+
+/**
+ * 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
+ *
+ * Example:
+ * #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;
+ * }
+ * License: GPL (v2 or any later version)
+ */
+int main(int argc, char *argv[])
+{
+	/* Expect exactly one argument */
+	if (argc != 2)
+		return 1;
+
+	if (strcmp(argv[1], "depends") == 0) {
+		return 0;
+	}
+
+	return 1;
+}