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

   1 #ifndef A_STAR_H__
   2 #define A_STAR_H__
   3 /*
   4         Copyright (C) 2016 Stephen M. Cameron
   5         Author: Stephen M. Cameron
   6
   7         This file is part of Spacenerds In Space.
   8
   9         Spacenerds in Space is free software; you can redistribute it and/or modify
  10         it under the terms of the GNU General Public License as published by
  11         the Free Software Foundation; either version 2 of the License, or
  12         (at your option) any later version.
  13
  14         Spacenerds in Space is distributed in the hope that it will be useful,
  15         but WITHOUT ANY WARRANTY; without even the implied warranty of
  16         MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17         GNU General Public License for more details.
  18
  19         You should have received a copy of the GNU General Public License
  20         along with Spacenerds in Space; if not, write to the Free Software
  21         Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  22 */
  23
  24 struct a_star_path {
  25         int node_count;
  26         __extension__ void *path[0];
  27 };
  28
  29 typedef float (*a_star_node_cost_fn)(void *context, void *first, void *second);
  30 typedef void *(*a_star_neighbor_iterator_fn)(void *context, void *node, int neighbor);
  31
  32 /**
  33  *
  34  * a_star - runs the 'A*' algorithm to find a path from the start to the goal.
  35  *
  36  * @context: an opaque pointer which the algorithm does not use, but passes
  37  *           along intact to the callback functions described below.
  38  * @start: an opaque pointer to the start node
  39  * @goal:  an opaque pointer to the goal node
  40  *
  41  * @maxnodes: the maximum number of nodes the algorithm will encounter (ie.
  42  *            the number of possible locations in a maze you are traversing.)
  43  *
  44  * @distance: a function which you provide which returns the distance (however you
  45  *            choose to define that) between two arbitrary nodes
  46  *
  47  * @cost_estimate: a function you provide which provides a heuristic cost estimate
  48  *                 for traversing between two nodes
  49  *
  50  * @nth_neighbor: a function you provide which returns the nth neighbor of a given
  51  *                node, or NULL if n is greater than the number of neighbors - 1.
  52  *
  53  * Returns:
  54  *   The return value is an allocated struct a_star_path.  the node_count is the
  55  *   number of nodes in the path, and the path array is a pointer to an array of
  56  *   node_count nodes in order from start to goal.
  57  *
  58  * See test/run.c example of how to use this.
  59  *
  60  */
  61
  62 struct a_star_path *a_star(void *context,
  63                 void *start,
  64                 void *goal,
  65                 int maxnodes,
  66                 a_star_node_cost_fn distance,
  67                 a_star_node_cost_fn cost_estimate,
  68                 a_star_neighbor_iterator_fn nth_neighbor);
  69 #endif