git.pond.sub.org Git - empserver/blob - src/lib/common/path.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  *  path.c: Empire/A* Interface code.  Provides callbacks for A* code and
  29  *          a sector cache to speed things up.  Define BP_STATS for sector
  30  *          cache statistics, AS_STATS for A* statistics.
  31  *
  32  *  Known contributors to this file:
  33  *     Phil Lapsley, 1991
  34  *     Dave Pare, 1991
  35  *     Thomas Ruschak, 1993
  36  *     Steve McClure, 1997
  37  */
  38
  39 #include <stdio.h>
  40 #include <stdlib.h>
  41 #include "../as/as.h"
  42 #include "misc.h"
  43 #include "path.h"
  44 #include "xy.h"
  45 #include "sect.h"
  46 #include "file.h"
  47 #include "common.h"
  48 #include "gen.h"
  49 #include "optlist.h"
  50
  51 /* STM - The server is now reliant on the sector file being
  52  * memory mapped for other things.  So, this code has been
  53  * setup to have the sector hashing #ifdef'd instead so that
  54  * we don't have to do runtime checking.  If someone moves
  55  * the sector file to me non-memory mapped, they have larger
  56  * problems than this, and can just turn this back on.  Then
  57  * again, their performance will be so bad going to a file
  58  * all the time, it won't matter. */
  59
  60 /*#define DO_EFF_MEM_CHECKING*/
  61
  62
  63 /* XXX won't need sector hash when sect file is memory mapped */
  64
  65 #define BP_SCTHASHSIZE  128             /* sector cache hash table size */
  66 #define BP_ASHASHSIZE   128             /* A* queue hash table size */
  67 #define BP_NEIGHBORS    6               /* max number of neighbors */
  68
  69 struct  sctcache {
  70         coord   x, y;
  71         struct  sctstr *sp;
  72         struct  sctcache *next;
  73 };
  74
  75 struct bestp {
  76         struct  sctcache *sctcachetab[BP_SCTHASHSIZE];
  77         int     sctcache_hits;
  78         int     sctcache_misses;
  79         int     bp_mobtype;
  80         struct  as_data *adp;
  81 };
  82
  83 #ifdef DO_EFF_MEM_CHECKING
  84
  85 static  struct sctstr *bp_getsect(struct bestp *bp, coord x, coord y);
  86 static  struct sctstr *bp_sctcache_get(struct bestp *bp, coord x, coord y);
  87 static  void bp_sctcache_set(struct bestp *bp, coord x, coord y, struct sctstr *sp);
  88 static  void bp_sctcache_zap(struct bestp *bp);
  89
  90 #endif /* DO_EFF_MEM_CHECKING */
  91
  92 static  int bp_path(struct as_path *pp, s_char *buf);
  93 static  int bp_neighbors(struct as_coord c, struct as_coord *cp, s_char *pp);
  94 static  double bp_lbcost(struct as_coord from, struct as_coord to, s_char *pp);
  95 static  double bp_realcost(struct as_coord from, struct as_coord to, s_char *pp);
  96 static  double bp_seccost(struct as_coord from, struct as_coord to, s_char *pp);
  97 static  int bp_coord_hash(struct as_coord c);
  98
  99 struct empfile *ep;
 100
 101 /* We use this for caching neighbors.  It never changes except
 102  * at reboot time (maybe) so we never need to free it */
 103 struct sctstr **neighsects = (struct sctstr **)0;
 104
 105 s_char *
 106 bp_init(void)
 107 {
 108         struct  bestp *bp;
 109
 110         ep = &empfile[EF_SECTOR];
 111
 112         bp = (struct bestp *) malloc(sizeof(*bp));
 113         bzero((s_char *)bp, sizeof(*bp));
 114         bp->adp = as_init(BP_NEIGHBORS, BP_ASHASHSIZE, bp_coord_hash,
 115                 bp_neighbors, bp_lbcost, bp_realcost,
 116                 bp_seccost, (s_char *)bp);
 117
 118         if (bp->adp == NULL)
 119                 return NULL;
 120
 121         if (neighsects == (struct sctstr **)0)
 122           neighsects = (struct sctstr **)calloc(1, (sizeof(struct sctstr *) *
 123                                                 ((WORLD_X * WORLD_Y)/2)*6));
 124
 125         return (s_char *) bp;
 126 }
 127
 128 /*
 129  * Find the best path from sector to to sector, and put the Empire movement
 130  * string in path.  Return 0 on success, -1 on error.
 131  */
 132 int
 133 best_path(struct sctstr *from, struct sctstr *to, s_char *path, int mob_type)
 134 {
 135         static struct bestp *mybestpath;
 136         struct  as_data *adp;
 137         struct as_path *ap;
 138
 139         if (mybestpath == 0)
 140                 mybestpath = (struct bestp *)bp_init();
 141         adp = mybestpath->adp;
 142 #ifdef DO_EFF_MEM_CHECKING
 143         bp_sctcache_zap(mybestpath);
 144 #endif
 145         ap = as_find_cachepath(from->sct_x, from->sct_y, to->sct_x, to->sct_y);
 146         if (ap == NULL) {
 147             adp->from.x = from->sct_x;
 148             adp->from.y = from->sct_y;
 149             adp->to.x = to->sct_x;
 150             adp->to.y = to->sct_y;
 151             mybestpath->bp_mobtype = mob_type;
 152
 153             if (as_search(adp) < 0)
 154                 return -1;
 155             ap = adp->path;
 156         }
 157
 158         if (bp_path(ap, path) < 0)
 159                 return -1;
 160
 161 #ifdef AS_STATS
 162         as_stats(adp, stderr);
 163 #endif /* AS_STATS */
 164 #ifdef BP_STATS
 165         fprintf(stderr, "best path %s\n", path);
 166         fprintf(stderr, "cache hits/misses: %d/%d\n",
 167                 bp->sctcache_hits, bp->sctcache_misses);
 168 #endif /* BP_STATS */
 169         return 0;
 170 }
 171
 172 /*
 173  * Translate an A* path into an empire movement string.  Return 0 on
 174  * success, -1 on failure.
 175  */
 176 static int
 177 bp_path(struct as_path *pp, s_char *buf)
 178 {
 179         struct  as_path *np;
 180         s_char  *cp = buf;
 181         int     dx, dy;
 182         int     n;
 183
 184         np = pp->next;
 185         while (np) {
 186                 dx = np->c.x - pp->c.x;
 187                 /* deal with wraparound from non-neg coords */
 188                 if (dx < -2)
 189                         dx += WORLD_X;
 190                 else if (dx > 2)
 191                         dx -= WORLD_X;
 192                 dy = np->c.y - pp->c.y;
 193                 if (dy < -1)
 194                         dy += WORLD_Y;
 195                 else if (dy > 1)
 196                         dy -= WORLD_Y;
 197                 for (n=1;n<=6;n++)
 198                         if (dx == diroff[n][0] && dy == diroff[n][1])
 199                                 break;
 200                 if (n > 6)
 201                         return -1;
 202
 203                 *cp++ = dirch[n];
 204                 pp = np;
 205                 np = np->next;
 206         }
 207         *cp = '\0';
 208         return 0;
 209 }
 210
 211 /*
 212  * Find coords neighboring this sector; return number of such
 213  * coords, and coordinartes themselves in an array pointed
 214  * to by *cpp.
 215  * XXX need to check ownership, sector types, etc.
 216  */
 217 static int
 218 bp_neighbors(struct as_coord c, struct as_coord *cp, s_char *pp)
 219 {
 220 #ifdef DO_EFF_MEM_CHECKING
 221         struct  bestp *bp = (struct bestp *) pp;
 222 #endif /* DO_EFF_MEM_CHECKING */
 223         coord   x, y;
 224         coord   nx, ny;
 225         int     n = 0, q;
 226         struct  sctstr *sp, *from, **ssp;
 227         /* Six pointers, just in case our cache isn't there */
 228         struct  sctstr *tsp[] = { 0, 0, 0, 0, 0, 0 };
 229         int     sx, sy, offset;
 230
 231         x = c.x;
 232         y = c.y;
 233 #ifdef DO_EFF_MEM_CHECKING
 234         if ((ep->flags & EFF_MEM) == 0) {
 235                 from = bp_getsect(bp, x, y);
 236         } else {
 237 #endif /* DO_EFF_MEM_CHECKING */
 238             sx = XNORM(x);
 239             sy = YNORM(y);
 240             offset = (sy * WORLD_X + sx) / 2;
 241             from = (struct sctstr *) (ep->cache + ep->size * offset);
 242 #ifdef DO_EFF_MEM_CHECKING
 243         }
 244 #endif /* DO_EFF_MEM_CHECKING */
 245
 246         if (neighsects == (struct sctstr **)0)
 247             ssp = (struct sctstr **)&tsp[0];
 248         else
 249             ssp = (struct sctstr **)&neighsects[offset * 6];
 250         for (q = 1; q <= 6; q++, ssp++) {
 251             if (*ssp == (struct sctstr *)0) {
 252                 /* We haven't cached this neighbor yet */
 253                 nx = x + diroff[q][0];
 254                 ny = y + diroff[q][1];
 255                 sx = XNORM(nx);
 256                 sy = YNORM(ny);
 257 #ifdef DO_EFF_MEM_CHECKING
 258                 if ((ep->flags & EFF_MEM) == 0) {
 259                         sp = bp_getsect(bp, nx, ny);
 260                 } else {
 261 #endif /* DO_EFF_MEM_CHECKING */
 262                         offset = (sy * WORLD_X + sx) / 2;
 263                         sp = (struct sctstr *) (ep->cache + ep->size * offset);
 264                         /* We can only save in our neighbor cache if the
 265                            sector file is in memory */
 266                         *ssp = sp;
 267 #ifdef DO_EFF_MEM_CHECKING
 268                 }
 269 #endif /* DO_EFF_MEM_CHECKING */
 270             } else {
 271                 sp = *ssp;
 272                 sx = XNORM(sp->sct_x);
 273                 sy = YNORM(sp->sct_y);
 274             }
 275             /* No need to calculate cost each time, just make sure we can
 276                move through it.  We calculate it later. */
 277             if (dchr[sp->sct_type].d_mcst == 0)
 278                 continue;
 279             if (sp->sct_own != from->sct_own)
 280                 continue;
 281             cp[n].x = sx;
 282             cp[n].y = sy;
 283             n++;
 284         }
 285         return (n);
 286 }
 287
 288 /*
 289  * Compute a lower-bound on the cost from "from" to "to".
 290  */
 291 /*ARGSUSED*/
 292 static double
 293 bp_lbcost(struct as_coord from, struct as_coord to, s_char *pp)
 294 {
 295         struct  bestp *bp = (struct bestp *) pp;
 296         struct  sctstr *ts;
 297         float   cost;
 298         int x, y, sx, sy, offset;
 299
 300 #ifdef DO_EFF_MEM_CHECKING
 301         if ((ep->flags & EFF_MEM) == 0) {
 302                 ts = bp_getsect(bp, (coord)to.x, (coord)to.y);
 303         } else {
 304 #endif /* DO_EFF_MEM_CHECKING */
 305             x = to.x;
 306             y = to.y;
 307             sx = XNORM(x);
 308             sy = YNORM(y);
 309             offset = (sy * WORLD_X + sx) / 2;
 310             ts = (struct sctstr *)(ep->cache + ep->size * offset);
 311 #ifdef DO_EFF_MEM_CHECKING
 312         }
 313 #endif /* DO_EFF_MEM_CHECKING */
 314         cost = sector_mcost(ts, bp->bp_mobtype);
 315         return (cost);
 316 }
 317
 318 /*
 319  * Compute the real cost to move from "from" to "to".
 320  */
 321 static double
 322 bp_realcost(struct as_coord from, struct as_coord to, s_char *pp)
 323 {
 324         return (bp_lbcost(from, to, pp));
 325 }
 326
 327 /*
 328  * Tie breaker secondary metric (only used when lower bound costs
 329  * are equal).
 330  */
 331 /*ARGSUSED*/
 332 static double
 333 bp_seccost(struct as_coord from, struct as_coord to, s_char *pp)
 334 {
 335         return ((double) mapdist((coord)from.x, (coord)from.y,
 336                 (coord)to.x, (coord)to.y));
 337 }
 338
 339 #ifdef DO_EFF_MEM_CHECKING
 340
 341 /*
 342  * Get a sector from the cache.  If it's not in the cache,
 343  * get it from disk and add it to the cache.
 344  */
 345 static struct sctstr *
 346 bp_getsect(struct bestp *bp, coord x, coord y)
 347 {
 348         struct  sctstr *sp;
 349
 350         sp = bp_sctcache_get(bp, x, y);
 351         if (sp == NULL) {
 352                 sp = (struct sctstr *) malloc(sizeof(*sp));
 353                 getsect(x, y, sp);
 354                 bp_sctcache_set(bp, x, y, sp);
 355                 bp->sctcache_misses++;
 356         } else {
 357                 bp->sctcache_hits++;
 358         }
 359         return (sp);
 360 }
 361
 362 /*
 363  * Get a sector from the cache; return NULL if it's not there.
 364  */
 365 static struct sctstr *
 366 bp_sctcache_get(struct bestp *bp, coord x, coord y)
 367 {
 368         int     hashval;
 369         struct  as_coord c;
 370         struct  sctcache *hp;
 371
 372         c.x = x;
 373         c.y = y;
 374         hashval = bp_coord_hash(c) % BP_SCTHASHSIZE;
 375         for (hp = bp->sctcachetab[hashval]; hp; hp = hp->next) {
 376                 if (hp->x == x && hp->y == y)
 377                         return (hp->sp);
 378         }
 379         return (NULL);
 380 }
 381
 382 /*
 383  * Put a sector in the cache.
 384  */
 385 static void
 386 bp_sctcache_set(struct bestp *bp, coord x, coord y, struct sctstr *sp)
 387 {
 388         int     hashval;
 389         struct  as_coord c;
 390         struct  sctcache *hp;
 391
 392         hp = (struct sctcache *) calloc(1, sizeof(*hp));
 393         hp->x = x;
 394         hp->y = y;
 395         hp->sp = sp;
 396         c.x = x;
 397         c.y = y;
 398         hashval = bp_coord_hash(c) % BP_SCTHASHSIZE;
 399         hp->next = bp->sctcachetab[hashval];
 400         bp->sctcachetab[hashval] = hp;
 401 }
 402
 403 /*
 404  * Zap the cache and reset statistics.
 405  */
 406 static void
 407 bp_sctcache_zap(struct bestp *bp)
 408 {
 409         register struct sctcache *hp;
 410         register struct sctcache *np;
 411         register int i;
 412
 413         for (i = 0; i < BP_SCTHASHSIZE; i++) {
 414                 for (hp = bp->sctcachetab[i]; hp; hp = np) {
 415                         np = hp->next;
 416                         free(hp->sp);
 417                         free(hp);
 418                 }
 419                 bp->sctcachetab[i] = NULL;
 420         }
 421         bp->sctcache_hits = 0;
 422         bp->sctcache_misses = 0;
 423 }
 424
 425 #endif /* DO_EFF_MEM_CHECKING */
 426
 427 /*
 428  * Hash a coordinate into an integer.
 429  */
 430 static int
 431 bp_coord_hash(struct as_coord c)
 432 {
 433         return ((abs(c.x) + 1) << 3) ^ abs(c.y);
 434 }
 435
 436 void
 437 bp_enable_cachepath()
 438 {
 439     as_enable_cachepath();
 440 }
 441
 442 void
 443 bp_disable_cachepath()
 444 {
 445     as_disable_cachepath();
 446 }
 447
 448 void
 449 bp_clear_cachepath()
 450 {
 451     as_clear_cachepath();
 452 }
 453
 454 double
 455 pathcost(struct sctstr *start, s_char *path, int mob_type)
 456 {
 457         register int o;
 458         register int cx, cy;
 459         double  cost = 0.0;
 460         struct  sctstr *sp;
 461         int sx, sy, offset;
 462
 463         cx = start->sct_x;
 464         cy = start->sct_y;
 465
 466         while (*path) {
 467             if (*path == 'h') {
 468                 path++;
 469                 continue;
 470             }
 471             o = dirindex[(int)((*path) - 'a')];
 472             cx += diroff[o][0];
 473             cy += diroff[o][1];
 474             sx = XNORM(cx);
 475             sy = YNORM(cy);
 476             offset = (sy * WORLD_X + sx) / 2;
 477             sp = (struct sctstr *)(ep->cache + ep->size * offset);
 478             cost += sector_mcost(sp, mob_type);
 479             path++;
 480         }
 481
 482         return cost;
 483 }
 484
 485 s_char *
 486 BestDistPath(s_char *path,
 487              struct sctstr *from,
 488              struct sctstr *to,
 489              double *cost,
 490              int mob_type)
 491 {
 492     return BestLandPath(path, from, to, cost, mob_type);
 493 }
 494
 495 s_char *
 496 BestLandPath(s_char *path,
 497              struct sctstr *from,
 498              struct sctstr *to,
 499              double *cost,
 500              int mob_type)
 501 {
 502     int length;
 503
 504     *path = 0;
 505     *cost = 0.0;
 506     if (best_path(from, to, path, mob_type) < 0)
 507         return (s_char *)0;
 508     *cost = pathcost(from, path, mob_type);
 509     length = strlen(path);
 510     path[length] = 'h';
 511     path[length + 1] = '\0';
 512     return path;
 513 }
 514
 515 s_char *
 516 BestShipPath(s_char *path,
 517              int fx,
 518              int fy,
 519              int tx,
 520              int ty,
 521              int owner)
 522 {
 523     s_char *map;
 524
 525     /* need to make sector database available to bestpath */
 526     map = ef_ptr(EF_BMAP, owner);
 527
 528     return (bestownedpath(path, map, fx, fy, tx, ty, ".=h", owner));
 529 }
 530
 531 s_char *
 532 BestAirPath(s_char *path,
 533              int fx,
 534              int fy,
 535              int tx,
 536              int ty)
 537 {
 538     return (bestownedpath(path, 0, fx, fy, tx, ty, "", -1));
 539     /*    return (bestpath(path, fx, fy, tx, ty, ""));*/
 540 }
 541