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