git.ozlabs.org Git - ccan/blob - ccan/a_star/_info

   1 #include "config.h"
   2 #include <stdio.h>
   3 #include <string.h>
   4
   5 /**
   6  * a_star - A straightforward implementation of the a-star path finding algorithm
   7  *
   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
  17  *
  18  * Example:
  19  * #include <stdio.h>
  20  * #include <string.h>
  21  * #include <stdlib.h>
  22  * #include <math.h>
  23  *
  24  * #include <ccan/a_star/a_star.h>
  25  *
  26  * static char maze[] =
  27  *      "##########@################x#################\n"
  28  *      "#                  #                        #\n"
  29  *      "#                  #                        #\n"
  30  *      "#  ###########     ###################      #\n"
  31  *      "#  #        #      #                 #      #\n"
  32  *      "####        #      #                 #      #\n"
  33  *      "#     #            #   ########      #      #\n"
  34  *      "#     #    #########   #      #      #      #\n"
  35  *      "#     #            #          #             #\n"
  36  *      "#     #            #          #             #\n"
  37  *      "#     #            #####   ##################\n"
  38  *      "#     ##########   #                        #\n"
  39  *      "#     #        #   #                        #\n"
  40  *      "#              #########################    #\n"
  41  *      "#          #           #           #        #\n"
  42  *      "############           #     #     #        #\n"
  43  *      "#                  #         #              #\n"
  44  *      "#############################################\n";
  45  *
  46  * static int maze_width(char *maze)
  47  * {
  48  *      char *n;
  49  *
  50  *      n = strchr(maze, '\n');
  51  *      return 1 + n - maze;
  52  * }
  53  *
  54  * static int xoff[] = { 0, 1, 0, -1 };
  55  * static int yoff[] = { 1, 0, -1, 0 };
  56  *
  57  * static char *maze_node(char *maze, int x, int y)
  58  * {
  59  *      return maze + y * maze_width(maze) + x;
  60  * }
  61  *
  62  * static void *nth_neighbor(void *context, void *p, int n)
  63  * {
  64  *      char *maze = context;
  65  *      char *c = p;
  66  *      int i, x, y, offset = c - maze;
  67  *
  68  *      x = offset % maze_width(maze);
  69  *      y = offset / maze_width(maze);
  70  *
  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)
  75  *                      continue;
  76  *              if (ty * maze_width(maze) + tx > strlen(maze))
  77  *                      continue;
  78  *              c = maze_node(maze, x + xoff[i], y + yoff[i]);
  79  *              if (*c != '#')
  80  *                      return c;
  81  *      }
  82  *      return NULL;
  83  * }
  84  *
  85  * static float maze_cost(void *context, void *first, void *second)
  86  * {
  87  *      char *maze = context;
  88  *      char *f = first;
  89  *      char *s = second;
  90  *      int sx, sy, fx, fy;
  91  *      float d, dx, dy;
  92  *
  93  *      int fp = f - maze;
  94  *      int sp = s - maze;
  95  *
  96  *      sx = sp % maze_width(maze);
  97  *      sy = sp / maze_width(maze);
  98  *      fx = fp % maze_width(maze);
  99  *      fy = fp / maze_width(maze);
 100  *
 101  *      dx = (float) sx - fx;
 102  *      dy = (float) sy - fy;
 103  *      d = (float) (abs(dx) + abs(dy));
 104  *      return d;
 105  * }
 106  *
 107  * int main(int argc, char *argv[])
 108  * {
 109  *      static int maxnodes, i;
 110  *      char *start, *goal;
 111  *      struct a_star_path *path;
 112  *
 113  *      start = strchr(maze, '@');
 114  *      goal = strchr(maze, 'x');
 115  *      maxnodes = strlen(maze);
 116  *
 117  *      path = a_star((void *) maze, start, goal, maxnodes, maze_cost, maze_cost, nth_neighbor);
 118  *      if (!path) {
 119  *              printf("a_star() failed to return a path.\n");
 120  *              return 0;
 121  *      }
 122  *      for (i = 0; i < path->node_count; i++) {
 123  *              char *p = path->path[i];
 124  *              *p = '.';
 125  *      }
 126  *      *goal = 'x';
 127  *      *start = '@';
 128  *
 129  *      printf("%s\n", maze);
 130  *
 131  *      free(path);
 132  *      return 0;
 133  * }
 134  * License: GPL (v2 or any later version)
 135  */
 136 int main(int argc, char *argv[])
 137 {
 138         /* Expect exactly one argument */
 139         if (argc != 2)
 140                 return 1;
 141
 142         if (strcmp(argv[1], "depends") == 0) {
 143                 return 0;
 144         }
 145
 146         return 1;
 147 }