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

   1 /*
   2  *  Empire - A multi-player, client/server Internet based war game.
   3  *  Copyright (C) 1986-2000, Dave Pare, Jeff Bailey, Thomas Ruschak,
   4  *                           Ken Stevens, Steve McClure
   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  *
  22  *  See the "LEGAL", "LICENSE", "CREDITS" and "README" files for all the
  23  *  related information and legal notices. It is expected that any future
  24  *  projects/authors will amend these files as needed.
  25  *
  26  *  ---
  27  *
  28  *  as_cache.c: Routines used to create/delete caches of A* paths.
  29  *
  30  *  Known contributors to this file:
  31  *     Steve McClure, 1998
  32  */
  33
  34 #include "as.h"
  35 #include "optlist.h"
  36
  37 /* The way this works is interesting. :) */
  38 /* We keep a pointer to a list of pointers.  The index into this list
  39  * is the y coordinate of the from sector.  This member points to a list
  40  * of from sectors on that y coordinate.  So, we march that list checking
  41  * the x value to find the from x,y we want. */
  42 /* Once we find the from x,y, that node has the same type of pointer to
  43  * a list of pointers.  The index into this list is the y coordinate of
  44  * the to sector.  This member points to a list of to sectors on that y
  45  * coordinate.  So, we march that list checking the x value to find the
  46  * to x,y we want. */
  47 /* These lists are dynamically created since the world is dynamically sized. */
  48 /* See, I told you it was interesting. :) */
  49
  50 static struct as_frompath **fromhead = (struct as_frompath **)0;
  51
  52 /* Note that we only want to cache during updates.  Other times, it
  53  * probably doesn't make much sense, but can be done. */
  54
  55 static int as_cachepath_on = 0; /* Default to off */
  56
  57 void
  58 as_enable_cachepath()
  59 {
  60     as_cachepath_on = 1;
  61 }
  62
  63 void
  64 as_disable_cachepath()
  65 {
  66     as_cachepath_on = 0;
  67 }
  68
  69 /* Note we want these to be as fast as possible */
  70
  71 void
  72 as_add_cachepath(struct as_data *adp)
  73 {
  74     struct as_frompath *from;
  75     struct as_topath *to = (struct as_topath *)0;
  76     struct as_node *np;
  77
  78     /* Don't do anything if we aren't cacheing these */
  79     if (as_cachepath_on == 0)
  80         return;
  81
  82     /* Note we will only allocate this once.  Afterwards, we just keep
  83      * zeroing it since it's rather small and we don't need to re-allocate
  84      * each time. */
  85     if (fromhead == (struct as_frompath **)0) {
  86         fromhead = calloc(1, sizeof(struct as_frompath *) * WORLD_Y);
  87         if (fromhead == (struct as_frompath **)0)
  88             return;
  89     }
  90
  91     np = adp->head->np;
  92     for (from = fromhead[adp->from.y]; from; from = from->next)
  93         if (from->x == adp->from.x)
  94             break;
  95     if (from) {
  96         for (to = from->tolist[np->c.y]; to; to = to->next) {
  97             if (to->x == np->c.x) {
  98                 /* It is already here!  Don't bother adding it again */
  99                 return;
 100             }
 101         }
 102     } else {
 103         /* We must make a new one of these */
 104         from = (struct as_frompath *)malloc(sizeof(struct as_frompath));
 105         if (from == NULL)
 106             return;
 107         /* And set some stuff */
 108         from->x = adp->from.x;
 109         /* Here we malloc a whole bunch of tolist pointers. */
 110         from->tolist = (struct as_topath **)calloc(1,
 111                                                    sizeof(struct as_topath
 112                                                           *) * WORLD_Y);
 113         /* Now, add from to the global list */
 114         from->next = fromhead[adp->from.y];
 115         fromhead[adp->from.y] = from;
 116     }
 117     if (!to) {
 118         /* We must make a new one */
 119         to = (struct as_topath *)malloc(sizeof(struct as_topath));
 120         /* We can't, sorry */
 121         if (to == NULL)
 122             return;
 123         /* Now set some stuff */
 124         to->x = np->c.x;
 125         /* Now add it to the list we are in */
 126         to->next = from->tolist[np->c.y];
 127         from->tolist[np->c.y] = to;
 128     }
 129     /* Now, make the path */
 130     as_makepath(adp);
 131     /* Now, take the path */
 132     to->path = adp->path;
 133     /* And clear the path in the adp */
 134     adp->path = NULL;
 135 }
 136
 137 void
 138 as_clear_cachepath()
 139 {
 140     struct as_frompath *from, *from2;
 141     struct as_topath *to, *to2;
 142     int i, j;
 143
 144     /* Cache not used yet :) */
 145     if (fromhead == (struct as_frompath **)0)
 146         return;
 147
 148     for (j = 0; j < WORLD_Y; j++) {
 149         for (from = fromhead[j]; from; from = from2) {
 150             for (i = 0; i < WORLD_Y; i++) {
 151                 for (to = from->tolist[i]; to; to = to2) {
 152                     to2 = to->next;
 153                     /* Free this path */
 154                     as_free_path(to->path);
 155                     /* Free this node */
 156                     free((s_char *)to);
 157                 }
 158             }
 159             /* Now, free the list of lists */
 160             free((s_char *)from->tolist);
 161             /* Save the next pointer */
 162             from2 = from->next;
 163             /* now, free this from node */
 164             free((s_char *)from);
 165         }
 166     }
 167     /* Note we don't free the fromhead here, we just zero it.  That way,
 168        we can use it next time without mallocing int */
 169     bzero((s_char *)fromhead, (sizeof(struct as_frompath *) * WORLD_Y));
 170 }
 171
 172 struct as_path *
 173 as_find_cachepath(coord fx, coord fy, coord tx, coord ty)
 174 {
 175     struct as_frompath *from;
 176     struct as_topath *to;
 177
 178     /* Is the cache on?  if not, return NULL */
 179     if (as_cachepath_on == 0)
 180         return (NULL);
 181
 182     /* Do we have any cached? */
 183     if (fromhead == (struct as_frompath **)0)
 184         return (NULL);
 185
 186     /* Yes! */
 187     for (from = fromhead[fy]; from; from = from->next) {
 188         if (from->x == fx) {
 189             for (to = from->tolist[ty]; to; to = to->next) {
 190                 if (to->x == tx)
 191                     return (to->path);
 192             }
 193         }
 194     }
 195     return (NULL);
 196 }