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 #include <stdio.h> /* for FILE */
  31 #include "misc.h" /* for s_char */
  32
  33 /*
  34  * Coordinate.
  35  */
  36 struct as_coord {
  37         int     x, y;
  38 };
  39
  40 /*
  41  * Path, made up of a linked list of coordinates.
  42  */
  43 struct as_path {
  44         struct as_coord c;
  45         struct as_path  *next;
  46 };
  47
  48 /*
  49  * Basic node, used internally by A* algorithm.
  50  */
  51 struct as_node {
  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 */
  57         int             step;
  58         int             flags;
  59         struct as_node  *back;
  60 };
  61 #define AS_TRIED        1               /* we've tried this node before */
  62
  63 /*
  64  * Linked list of nodes, used internally by A* algorithm.
  65  */
  66 struct as_queue {
  67         struct as_node  *np;
  68         struct as_queue *next;
  69         struct as_queue *prev;
  70 };
  71
  72 /*
  73  * Hash table entry, used to determine if we've seen a particular
  74  * coordinate before.
  75  */
  76 struct as_hash {
  77         struct as_coord c;
  78         struct as_queue *qp;
  79         struct as_hash  *next;
  80 };
  81
  82 /*
  83  * User's handle on A*, returned by as_init().  Some of the data here is
  84  * used by A* internals.
  85  */
  86 struct as_data {
  87         int             maxneighbors;   /* max # of neighbors a cell can have */
  88         int             hashsize;       /* size of internal hash table */
  89
  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 */
  99
 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;
 107 };
 108
 109 /*
 110  * Added these for caching of paths as we stumble across them
 111  */
 112
 113 struct as_topath {
 114     coord x;
 115     struct as_path *path; /* Path from holder of this list to here */
 116     struct as_topath *next;
 117 };
 118
 119 struct as_frompath {
 120     coord x;
 121     struct as_topath **tolist; /* List of nodes we have a path to */
 122     struct as_frompath *next;
 123 };
 124
 125 /*
 126  * Some cheezy allocation macros.
 127  */
 128 #define AS_NEW_ARRAY(p, type, n, err) \
 129         (p) = (type *)calloc((n), sizeof (*(p))); \
 130         if ((p) == NULL) \
 131                 return err; \
 132
 133 #define AS_NEW(p, type, err) \
 134         AS_NEW_ARRAY((p), type, 1, err);
 135
 136 #define AS_NEW_MALLOC(p, type, err) \
 137         (p) = (type *)malloc(sizeof(type)); \
 138         if ((p) == NULL) \
 139                return err; \
 140
 141 /* Functions that the user can call.  */
 142
 143 extern  struct as_data  *
 144 as_init(int maxneighbors, int hashsize,
 145         int (*hashfunc) (struct as_coord),
 146         int (*neighborfunc) (struct as_coord, struct as_coord *, s_char *),
 147         double (*lbcostfunc) (struct as_coord, struct as_coord, s_char *),
 148         double (*realcostfunc) (struct as_coord, struct as_coord, s_char *),
 149         double (*seccostfunc) (struct as_coord, struct as_coord, s_char *),
 150         s_char *userdata);
 151 extern  int             as_search(struct as_data *adp);
 152 extern  void            as_delete(struct as_data *adp);
 153 extern  void            as_reset(struct as_data *adp);
 154 extern  void            as_stats(struct as_data *adp, FILE *fp);
 155 extern struct as_path *as_find_cachepath(coord fx,
 156                                          coord fy,
 157                                          coord tx,
 158                                          coord ty);
 159
 160 /* Functions that are "private" to algorithm */
 161
 162 extern void as_add_cachepath(struct as_data *adp);
 163 extern void as_clear_cachepath();
 164 extern void as_enable_cachepath();
 165 extern void as_disable_cachepath();
 166
 167 extern void     as_makepath(struct as_data *adp);
 168 extern void     as_free_path(struct as_path *pp);
 169
 170 extern  int             as_costcomp(struct as_node **n1, struct as_node **n2);
 171 extern  struct as_queue *as_extend(struct as_data *adp);
 172 extern  struct as_queue *as_merge(struct as_data *adp,
 173                                   struct as_queue *head,
 174                                   struct as_node **neighbors);
 175 extern  struct as_queue *as_iscinq(struct as_data *adp, struct as_coord c);
 176 extern  void            as_setcinq(struct as_data *adp,
 177                                    struct as_coord c, struct as_queue *qp);
 178 extern  void            as_free_hashtab(struct as_data *adp);
 179 extern  int             as_winnow(struct as_data *adp,
 180                                   struct as_coord *coords, int ncoords);