git.pond.sub.org Git - empserver/blob - src/lib/as/as.h

   1 /*
   2  *  A* Search - A search library used in Empire to determine paths between
   3  *              objects.
   4  *  Copyright (C) 1990-1998 Phil Lapsley
   5  *
   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.
  10  *
  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.
  15  *
  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
  19  */
  20 /*
  21  * A* definitions.
  22  *
  23  * @(#)as.h     1.9     11/13/90
  24  */
  25 /*
  26  * 11/09/98 - Steve McClure
  27  *  Added path list caching structures
  28  */
  29
  30 #ifndef AS_H
  31 #define AS_H
  32
  33 #include <stdio.h>
  34 #include "types.h"
  35
  36 /*
  37  * Coordinate.
  38  */
  39 struct as_coord {
  40     int x, y;
  41 };
  42
  43 /*
  44  * Path, made up of a linked list of coordinates.
  45  */
  46 struct as_path {
  47     struct as_coord c;
  48     struct as_path *next;
  49 };
  50
  51 /*
  52  * Basic node, used internally by A* algorithm.
  53  */
  54 struct as_node {
  55     struct as_coord c;          /* our coordinate */
  56     double knowncost;           /* cost so far  */
  57     double lbcost;              /* lower bound on cost to dest */
  58     double inclbcost;           /* incremental lower bound cost */
  59     double seccost;             /* used to break ties */
  60     int step;
  61     int flags;
  62     struct as_node *back;
  63 };
  64 #define AS_TRIED        1       /* we've tried this node before */
  65
  66 /*
  67  * Linked list of nodes, used internally by A* algorithm.
  68  */
  69 struct as_queue {
  70     struct as_node *np;
  71     struct as_queue *next;
  72     struct as_queue *prev;
  73 };
  74
  75 /*
  76  * Hash table entry, used to determine if we've seen a particular
  77  * coordinate before.
  78  */
  79 struct as_hash {
  80     struct as_coord c;
  81     struct as_queue *qp;
  82     struct as_hash *next;
  83 };
  84
  85 /*
  86  * User's handle on A*, returned by as_init().  Some of the data here is
  87  * used by A* internals.
  88  */
  89 struct as_data {
  90     int maxneighbors;           /* max # of neighbors a cell can have */
  91     int hashsize;               /* size of internal hash table */
  92
  93     /* hash function (coord -> int) */
  94     int (*hash)(struct as_coord);
  95     /* function to find neighbors */
  96     int (*neighbor)(struct as_coord, struct as_coord *, void *);
  97     /* function to give lower bound cost */
  98     double (*lbcost)(struct as_coord, struct as_coord, void *);
  99     /* function to give real cost */
 100     double (*realcost)(struct as_coord, struct as_coord, void *);
 101     /* function to secondary cost */
 102     double (*seccost)(struct as_coord, struct as_coord, void *);
 103     void *userdata;             /* user's data, passed to callbacks */
 104     struct as_coord from;       /* from coordinate */
 105     struct as_coord to;         /* to coordinate */
 106     struct as_path *path;       /* solution */
 107
 108     /* below are "private" to as_ routines */
 109     struct as_queue *head;
 110     struct as_queue *tried;
 111     struct as_hash **hashtab;
 112     struct as_queue *subsumed;
 113     struct as_coord *neighbor_coords;
 114     struct as_node **neighbor_nodes;
 115 };
 116
 117 /*
 118  * Added these for caching of paths as we stumble across them
 119  */
 120
 121 struct as_topath {
 122     coord x;
 123     struct as_path *path;       /* Path from holder of this list to here */
 124     struct as_topath *next;
 125 };
 126
 127 struct as_frompath {
 128     coord x;
 129     struct as_topath **tolist;  /* List of nodes we have a path to */
 130     struct as_frompath *next;
 131 };
 132
 133 /*
 134  * Some cheezy allocation macros.
 135  */
 136 #define AS_NEW_ARRAY(p, type, n, err) \
 137         (p) = (type *)calloc((n), sizeof(*(p))); \
 138         if ((p) == NULL) \
 139                 return err; \
 140
 141 #define AS_NEW(p, type, err) \
 142         AS_NEW_ARRAY((p), type, 1, err);
 143
 144 #define AS_NEW_MALLOC(p, type, err) \
 145         (p) = (type *)malloc(sizeof(type)); \
 146         if ((p) == NULL) \
 147                return err; \
 148
 149 /* Functions that the user can call.  */
 150
 151 extern struct as_data *as_init(int maxneighbors, int hashsize,
 152                                int (*hashfunc)(struct as_coord),
 153                                int (*neighborfunc)(struct as_coord,
 154                                                    struct as_coord *,
 155                                                    void *),
 156                                double (*lbcostfunc)(struct as_coord,
 157                                                     struct as_coord,
 158                                                     void *),
 159                                double (*realcostfunc)(struct as_coord,
 160                                                       struct as_coord,
 161                                                       void *),
 162                                double (*seccostfunc)(struct as_coord,
 163                                                      struct as_coord,
 164                                                      void *),
 165                                void *userdata);
 166 extern int as_search(struct as_data *adp);
 167 extern void as_delete(struct as_data *adp);
 168 extern void as_reset(struct as_data *adp);
 169 extern void as_stats(struct as_data *adp, FILE * fp);
 170 extern struct as_path *as_find_cachepath(coord fx, coord fy,
 171                                          coord tx, coord ty);
 172
 173 /* Functions that are "private" to algorithm */
 174
 175 extern void as_add_cachepath(struct as_data *adp);
 176 extern void as_clear_cachepath(void);
 177 extern void as_enable_cachepath(void);
 178 extern void as_disable_cachepath(void);
 179
 180 extern void as_makepath(struct as_data *adp);
 181 extern void as_free_path(struct as_path *pp);
 182
 183 extern int as_costcomp(const void *, const void *);
 184 extern struct as_queue *as_extend(struct as_data *adp);
 185 extern struct as_queue *as_merge(struct as_data *adp,
 186                                  struct as_queue *head,
 187                                  struct as_node **neighbors);
 188 extern struct as_queue *as_iscinq(struct as_data *adp, struct as_coord c);
 189 extern void as_setcinq(struct as_data *adp,
 190                        struct as_coord c, struct as_queue *qp);
 191 extern void as_free_hashtab(struct as_data *adp);
 192 extern int as_winnow(struct as_data *adp,
 193                      struct as_coord *coords, int ncoords);
 194
 195 #endif