2 * A* Search - A search library used in Empire to determine paths between
4 * Copyright (C) 1990-1998 Phil Lapsley
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
23 * @(#)as.h 1.9 11/13/90
26 * 11/09/98 - Steve McClure
27 * Added path list caching structures
30 #include <stdio.h> /* for FILE */
31 #include "misc.h" /* for s_char */
41 * Path, made up of a linked list of coordinates.
49 * Basic node, used internally by A* algorithm.
52 struct as_coord c; /* our coordinate */
53 double knowncost; /* cost so far */
54 double lbcost; /* lower bound on cost to dest */
55 double inclbcost; /* incremental lower bound cost */
56 double seccost; /* used to break ties */
61 #define AS_TRIED 1 /* we've tried this node before */
64 * Linked list of nodes, used internally by A* algorithm.
68 struct as_queue *next;
69 struct as_queue *prev;
73 * Hash table entry, used to determine if we've seen a particular
83 * User's handle on A*, returned by as_init(). Some of the data here is
84 * used by A* internals.
87 int maxneighbors; /* max # of neighbors a cell can have */
88 int hashsize; /* size of internal hash table */
90 int (*hash) (struct as_coord); /* hash function (coord -> int) */
91 int (*neighbor) (struct as_coord, struct as_coord *, s_char *); /* function to find neighbors */
92 double (*lbcost) (struct as_coord, struct as_coord, s_char *); /* function to give lower bound cost */
93 double (*realcost) (struct as_coord, struct as_coord, s_char *); /* function to give real cost */
94 double (*seccost) (struct as_coord, struct as_coord, s_char *); /* function to secondary cost */
95 char *userdata; /* user's data, passed to callbacks */
96 struct as_coord from; /* from coordinate */
97 struct as_coord to; /* to coordinate */
98 struct as_path *path; /* solution */
100 /* below are "private" to as_ routines */
101 struct as_queue *head;
102 struct as_queue *tried;
103 struct as_hash **hashtab;
104 struct as_queue *subsumed;
105 struct as_coord *neighbor_coords;
106 struct as_node **neighbor_nodes;
110 * Added these for caching of paths as we stumble across them
115 struct as_path *path; /* Path from holder of this list to here */
116 struct as_topath *next;
121 struct as_topath **tolist; /* List of nodes we have a path to */
122 struct as_frompath *next;
126 * Some cheezy allocation macros.
128 #define AS_NEW_ARRAY(p, type, n, err) \
129 (p) = (type *)calloc((n), sizeof (*(p))); \
133 #define AS_NEW(p, type, err) \
134 AS_NEW_ARRAY((p), type, 1, err);
136 #define AS_NEW_MALLOC(p, type, err) \
137 (p) = (type *)malloc(sizeof(type)); \
141 /* Functions that the user can call. */
143 extern struct as_data *as_init(int maxneighbors, int hashsize,
144 int (*hashfunc) (struct as_coord),
145 int (*neighborfunc) (struct as_coord,
148 double (*lbcostfunc) (struct as_coord,
151 double (*realcostfunc) (struct as_coord,
154 double (*seccostfunc) (struct as_coord,
158 extern int as_search(struct as_data *adp);
159 extern void as_delete(struct as_data *adp);
160 extern void as_reset(struct as_data *adp);
161 extern void as_stats(struct as_data *adp, FILE * fp);
162 extern struct as_path *as_find_cachepath(coord fx,
163 coord fy, coord tx, coord ty);
165 /* Functions that are "private" to algorithm */
167 extern void as_add_cachepath(struct as_data *adp);
168 extern void as_clear_cachepath();
169 extern void as_enable_cachepath();
170 extern void as_disable_cachepath();
172 extern void as_makepath(struct as_data *adp);
173 extern void as_free_path(struct as_path *pp);
175 extern int as_costcomp(struct as_node **n1, struct as_node **n2);
176 extern struct as_queue *as_extend(struct as_data *adp);
177 extern struct as_queue *as_merge(struct as_data *adp,
178 struct as_queue *head,
179 struct as_node **neighbors);
180 extern struct as_queue *as_iscinq(struct as_data *adp, struct as_coord c);
181 extern void as_setcinq(struct as_data *adp,
182 struct as_coord c, struct as_queue *qp);
183 extern void as_free_hashtab(struct as_data *adp);
184 extern int as_winnow(struct as_data *adp,
185 struct as_coord *coords, int ncoords);