4 Copyright (C) 2016 Stephen M. Cameron
5 Author: Stephen M. Cameron
7 This file is part of Spacenerds In Space.
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.
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.
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
26 __extension__ void *path[0];
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);
34 * a_star - runs the 'A*' algorithm to find a path from the start to the goal.
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
41 * @maxnodes: the maximum number of nodes the algorithm will encounter (ie.
42 * the number of possible locations in a maze you are traversing.)
44 * @distance: a function which you provide which returns the distance (however you
45 * choose to define that) between two arbitrary nodes
47 * @cost_estimate: a function you provide which provides a heuristic cost estimate
48 * for traversing between two nodes
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.
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.
58 * See test/run.c example of how to use this.
62 struct a_star_path *a_star(void *context,
66 a_star_node_cost_fn distance,
67 a_star_node_cost_fn cost_estimate,
68 a_star_neighbor_iterator_fn nth_neighbor);