git.pond.sub.org Git - empserver/blob - src/lib/common/pathfind.c

   1 /*
   2  *  Empire - A multi-player, client/server Internet based war game.
   3  *  Copyright (C) 1986-2011, Dave Pare, Jeff Bailey, Thomas Ruschak,
   4  *                Ken Stevens, Steve McClure, Markus Armbruster
   5  *
   6  *  Empire 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 3 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, see <http://www.gnu.org/licenses/>.
  18  *
  19  *  ---
  20  *
  21  *  See files README, COPYING and CREDITS in the root of the source
  22  *  tree for related information and legal notices.  It is expected
  23  *  that future projects/authors will amend these files as needed.
  24  *
  25  *  ---
  26  *
  27  *  pathfind.c: Find cheapest paths
  28  *
  29  *  Known contributors to this file:
  30  *     Markus Armbruster, 2011
  31  */
  32
  33 #include <config.h>
  34
  35 #include <assert.h>
  36 #include <stdio.h>
  37 #include <stdlib.h>
  38 #include <string.h>
  39 #include "file.h"
  40 #include "nat.h"
  41 #include "optlist.h"
  42 #include "path.h"
  43 #include "sect.h"
  44
  45 #ifdef PATH_FIND_DEBUG
  46 #define DPRINTF(fmt, ...) ((void)printf(fmt , ## __VA_ARGS__))
  47 #else
  48 #define DPRINTF(fmt, ...) ((void)0)
  49 #endif
  50
  51 static char *bufrotate(char *buf, size_t bufsz, size_t i);
  52
  53 /*
  54  * Dijkstra's algorithm.  Refer to your graph algorithm textbook for
  55  * how it works.  Implementation is specialized to hex maps.
  56  *
  57  * Define PATH_FIND_STATS for performance statistics on stdout.
  58  */
  59
  60 /*
  61  * Array of sector data, indexed by sector uid
  62  *
  63  * We need to store a few values per sector visited by the path
  64  * search.  An array is the stupidest data structure that could
  65  * possibly work.
  66  *
  67  * Extra benefit: it works really well for distribution in a
  68  * continental game, where we visit most sectors.  That's our most
  69  * demanding use of path search, and its performance has noticable
  70  * impact on the update.
  71  *
  72  * Island game distribution is much less demanding.  The array may not
  73  * be the best choice here, but it's plainly good enough.  Same for
  74  * path searches outside the update.
  75  */
  76
  77 struct pf_map {
  78     /*
  79      * visit < pf_visit      : unvisited, remaining members invalid
  80      * visit == pf_visit     : open, dir & cost tentative, heapi used
  81      * visit == pf_visit + 1 : closed, dir & cost final, heapi unused
  82      */
  83     unsigned short visit;
  84     signed char dir;            /* cheapest direction to source */
  85     int heapi;                  /* index in heap, valid if open */
  86     double cost;                /* cost from source */
  87 };
  88
  89 static unsigned short pf_visit;
  90 static struct pf_map *pf_map;
  91
  92 /*
  93  * Binary heap, cost priority queue of all open sectors
  94  *
  95  * Again, we use the stupidest data structure that could possibly
  96  * work: an array.  And we make it so large it can hold *all* sectors.
  97  * In practice, we need much less space, but a tighter upper bound is
  98  * not obvious to me right now.
  99  */
 100
 101 struct pf_heap {
 102     int uid;                    /* sector uid and */
 103     coord x, y;                 /* coordinates, uid == XYOFFSET(x, y) */
 104     double cost;                /* cost from source */
 105 };
 106
 107 static int pf_nheap;            /* #entries in pf_nheap[] */
 108 static struct pf_heap *pf_heap;
 109
 110 /*
 111  * Source and costs
 112  */
 113 static coord pf_sx, pf_sy;
 114 static int pf_suid;
 115 static natid pf_actor;
 116 static double (*pf_sct_cost)(natid, int);
 117
 118 /*
 119  * Performance statistics
 120  */
 121 #ifdef PATH_FIND_STATS
 122 static unsigned pf_nsearch, pf_nsource, pf_nopen, pf_nclose;
 123 static unsigned pf_nheap_max, pf_noway;
 124 static double pf_sumcost;
 125 #define STAT_INC(v) ((void)((v)++))
 126 #define STAT_INCBY(v, i) ((void)((v) += i))
 127 #define STAT_HIMARK(v, h) ((void)((v) < (h) ? (v) = (h) : (h)))
 128 #else   /* !PATH_FIND_STATS */
 129 #define STAT_INC(v) ((void)0)
 130 #define STAT_INCBY(v, i) ((void)0)
 131 #define STAT_HIMARK(v, h) ((void)0)
 132 #endif  /* !PATH_FIND_STATS */
 133
 134 #ifndef NDEBUG                  /* silence "not used" warning */
 135 /* Is sector with uid UID open?  */
 136 static int
 137 pf_is_open(int uid)
 138 {
 139     return pf_map[uid].visit == pf_visit;
 140 }
 141 #endif
 142
 143 /* Is sector with uid UID closed?  */
 144 static int
 145 pf_is_closed(int uid)
 146 {
 147     /*
 148      * optimization: check > pf_visit instead of == pf_visit + 1
 149      * works because pf_map[uid].visit <= pf_visit + 1
 150      */
 151     return pf_map[uid].visit > pf_visit;
 152 }
 153
 154 /* Is sector with uid UID unvisited?  */
 155 static int
 156 pf_is_unvisited(int uid)
 157 {
 158     return pf_map[uid].visit < pf_visit;
 159 }
 160
 161 #ifdef PATH_FIND_DEBUG
 162 static void
 163 pf_check(void)
 164 {
 165     int i, uid, c;
 166
 167     for (i = 0; i < pf_nheap; i++) {
 168         uid = pf_heap[i].uid;
 169         assert(0 <= uid && uid < WORLD_SZ());
 170         assert(pf_map[uid].heapi == i);
 171         assert(pf_map[uid].visit == pf_visit);
 172         assert(pf_map[uid].cost <= pf_heap[i].cost);
 173         c = 2 * i + 1;
 174         assert(c >= pf_nheap || pf_heap[i].cost <= pf_heap[c].cost);
 175         c++;
 176         assert(c >= pf_nheap || pf_heap[i].cost <= pf_heap[c].cost);
 177     }
 178
 179     for (uid = 0; uid < WORLD_SZ(); uid++) {
 180         assert(pf_map[uid].visit <= pf_visit + 1);
 181         if (pf_map[uid].visit == pf_visit) {
 182             i = pf_map[uid].heapi;
 183             assert(0 <= i && i < pf_nheap && pf_heap[i].uid == uid);
 184         }
 185     }
 186 }
 187 #else
 188 #define pf_check() ((void)0)
 189 #endif
 190
 191 /* Swap pf_heap's I-th and J-th elements.  */
 192 static void
 193 pf_heap_swap(int i, int j)
 194 {
 195     struct pf_heap tmp;
 196
 197     assert(0 <= i && i < pf_nheap);
 198     assert(0 <= j && j < pf_nheap);
 199     tmp = pf_heap[i];
 200     pf_heap[i] = pf_heap[j];
 201     pf_heap[j] = tmp;
 202     pf_map[pf_heap[i].uid].heapi = i;
 203     pf_map[pf_heap[j].uid].heapi = j;
 204 }
 205
 206 /* Restore heap property after N-th element's cost increased.  */
 207 static void
 208 pf_sift_down(int n)
 209 {
 210     int r, c;
 211
 212     assert(0 <= n && n < pf_nheap);
 213     for (r = n; (c = 2 * r + 1) < pf_nheap; r = c) {
 214         if (c + 1 < pf_nheap && pf_heap[c].cost > pf_heap[c + 1].cost)
 215             c++;
 216         if (pf_heap[r].cost < pf_heap[c].cost)
 217             break;
 218         pf_heap_swap(r, c);
 219     }
 220 }
 221
 222 /* Restore heap property after N-th element's cost decreased.  */
 223 static void
 224 pf_sift_up(int n)
 225 {
 226     int c, p;
 227
 228     assert(0 <= n && n < pf_nheap);
 229     for (c = n; (p = (c - 1) / 2), c > 0; c = p) {
 230         if (pf_heap[p].cost < pf_heap[c].cost)
 231             break;
 232         pf_heap_swap(p, c);
 233     }
 234 }
 235
 236 /*
 237  * Open the unvisited sector X,Y.
 238  * UID is sector uid, it equals XYOFFSET(X,Y).
 239  * Cheapest path from source comes from direction DIR and has cost COST.
 240  */
 241 static void
 242 pf_open(int uid, coord x, coord y, int dir, double cost)
 243 {
 244     int i;
 245
 246     STAT_INC(pf_nopen);
 247     i = pf_nheap++;
 248     STAT_HIMARK(pf_nheap_max, (unsigned)pf_nheap);
 249     DPRINTF("pf: open %d,%d %g %c %d\n", x, y, cost, dirch[dir], i);
 250     assert(pf_is_unvisited(uid));
 251     pf_map[uid].visit = pf_visit;
 252     pf_map[uid].dir = dir;
 253     pf_map[uid].heapi = i;
 254     pf_map[uid].cost = cost;
 255     pf_heap[i].uid = uid;
 256     pf_heap[i].x = x;
 257     pf_heap[i].y = y;
 258     pf_heap[i].cost = cost;
 259
 260     pf_sift_up(i);
 261     pf_check();
 262 }
 263
 264 /*
 265  * Close the sector at the top of the heap.
 266  */
 267 static void
 268 pf_close(void)
 269 {
 270     int uid = pf_heap[0].uid;
 271
 272     STAT_INC(pf_nclose);
 273     DPRINTF("pf: close %d,%d %d\n", pf_heap[0].x, pf_heap[0].y, pf_nheap);
 274     assert(pf_is_open(uid));
 275     if (--pf_nheap) {
 276         pf_heap[0] = pf_heap[pf_nheap];
 277         pf_map[pf_heap[0].uid].heapi = 0;
 278         pf_sift_down(0);
 279     }
 280     pf_map[uid].visit = pf_visit + 1;
 281     pf_check();
 282 }
 283
 284 /* silence "not used" warning */
 285 #ifdef PATH_FIND_DEBUG
 286 /*
 287  * Return cost from source to sector with uid UID.
 288  * It must be visited, i.e. open or closed.
 289  */
 290 static double
 291 pf_cost(int uid)
 292 {
 293     assert(!pf_is_unvisited(uid));
 294     return pf_map[uid].cost;
 295 }
 296 #endif
 297
 298 static coord
 299 x_in_dir(coord x, int dir)
 300 {
 301     int xx;
 302
 303     assert(0 <= x && x < WORLD_X);
 304     assert(0 <= dir && dir <= DIR_LAST);
 305     xx = x + diroff[dir][0];
 306     if (xx < 0)
 307         return xx + WORLD_X;
 308     if (xx >= WORLD_X)
 309         return xx - WORLD_X;
 310     return xx;
 311 }
 312
 313 static coord
 314 y_in_dir(coord y, int dir)
 315 {
 316     int yy;
 317
 318     assert(0 <= y && y < WORLD_Y);
 319     assert(0 <= dir && dir <= DIR_LAST);
 320     yy = y + diroff[dir][1];
 321     if (yy < 0)
 322         return yy + WORLD_Y;
 323     if (yy >= WORLD_Y)
 324         return yy - WORLD_Y;
 325     return yy;
 326 }
 327
 328 static int
 329 rev_dir(int dir)
 330 {
 331     assert(DIR_FIRST <= dir && dir <= DIR_LAST);
 332     return dir >= DIR_FIRST + 3 ? dir - 3 : dir + 3;
 333 }
 334
 335 /*
 336  * Set the current source and cost function.
 337  * SX,SY is the source.
 338  * The cost to enter the sector with uid u is COST(ACTOR, u).
 339  * Negative value means the sector can't be entered.
 340  */
 341 static void
 342 pf_set_source(coord sx, coord sy, natid actor, double (*cost)(natid, int))
 343 {
 344     STAT_INC(pf_nsource);
 345     DPRINTF("pf: source %d,%d\n", sx, sy);
 346     pf_sx = sx;
 347     pf_sy = sy;
 348     pf_suid = XYOFFSET(sx, sy);
 349     pf_actor = actor;
 350     pf_sct_cost = cost;
 351
 352     if (!pf_map) {
 353         pf_map = calloc(WORLD_SZ(), sizeof(*pf_map));
 354         pf_heap = malloc(WORLD_SZ() * sizeof(*pf_heap));
 355         pf_visit = 1;
 356     } else if ((unsigned short)(pf_visit + 3) < pf_visit) {
 357         DPRINTF("pf: visit wrap-around\n");
 358         memset(pf_map, 0, WORLD_SZ() * sizeof(*pf_map));
 359         pf_visit = 1;
 360     } else
 361         pf_visit += 2;
 362
 363     pf_nheap = 0;
 364
 365     pf_open(pf_suid, pf_sx, pf_sy, DIR_STOP, 0.0);
 366 }
 367
 368 /*
 369  * Find cheapest path from current source to DX,DY, return its cost.
 370  */
 371 double
 372 path_find_to(coord dx, coord dy)
 373 {
 374     int duid;
 375     int uid, nuid, i;
 376     double cost, c1;
 377     coord x, y, nx, ny;
 378
 379     STAT_INC(pf_nsearch);
 380     DPRINTF("pf: dest %d,%d\n", dx, dy);
 381     duid = XYOFFSET(dx, dy);
 382     if (pf_is_closed(duid)) {
 383         DPRINTF("pf: done old %g\n", pf_map[duid].cost);
 384         STAT_INCBY(pf_sumcost, pf_map[duid].cost);
 385         return pf_map[duid].cost;
 386     }
 387
 388     while (pf_nheap > 0 && (uid = pf_heap[0].uid) != duid) {
 389         x = pf_heap[0].x;
 390         y = pf_heap[0].y;
 391         cost = pf_heap[0].cost;
 392         pf_close();
 393
 394         for (i = 0; i < 6; i++) { /* for all neighbors */
 395             nx = x_in_dir(x, DIR_FIRST + i);
 396             ny = y_in_dir(y, DIR_FIRST + i);
 397             nuid = XYOFFSET(nx, ny);
 398             /*
 399              * Cost to enter NX,NY doesn't depend on direction of
 400              * entry.  This X,Y is at least as expensive as any
 401              * previous one.  Therefore, cost to go to NX,NY via X,Y
 402              * is at least as high as any previously found route.
 403              * Skip neighbors that have a route already.
 404              */
 405             if (!pf_is_unvisited(nuid))
 406                 continue;
 407             c1 = pf_sct_cost(pf_actor, nuid);
 408             if (c1 < 0)
 409                 continue;
 410             pf_open(nuid, nx, ny, DIR_FIRST + i, cost + c1);
 411         }
 412     }
 413
 414     DPRINTF("pf: done new %g\n", !pf_nheap ? -1.0 : pf_map[duid].cost);
 415     if (!pf_nheap) {
 416         STAT_INC(pf_noway);
 417         return -1.0;
 418     }
 419     STAT_INCBY(pf_sumcost, pf_map[duid].cost);
 420     return pf_map[duid].cost;
 421 }
 422
 423 /*
 424  * Write route from SX,SY to DX,DY to BUF[BUFSIZ], return its length.
 425  * If the route is longer than BUFSIZ-1 characters, it's truncated.
 426  * You must compute path cost first, with path_find_to().
 427  * SX,SY must be on a shortest path from the current source to DX,DY.
 428  */
 429 size_t
 430 path_find_route(char *buf, size_t bufsz,
 431                 coord sx, coord sy, coord dx, coord dy)
 432 {
 433     coord x, y;
 434     size_t i, len;
 435     int suid, uid, d;
 436
 437     suid = XYOFFSET(sx, sy);
 438     assert(bufsz > 0 && !pf_is_unvisited(suid));
 439
 440     i = bufsz;
 441     buf[--i] = 0;
 442     len = 0;
 443
 444     x = dx;
 445     y = dy;
 446     for (;;) {
 447         DPRINTF("pf: %d,%d %.*s%.*s\n",
 448                 x, y,
 449                 (int)(bufsz - i), buf + i,
 450                 len >= bufsz ? (int)i : 0, buf);
 451         uid = XYOFFSET(x, y);
 452         assert(!pf_is_unvisited(uid));
 453         d = pf_map[uid].dir;
 454         if (d == DIR_STOP || uid == suid)
 455             break;
 456         if (!i)
 457             i = bufsz;
 458         buf[--i] = dirch[d];
 459         len++;
 460         x = x_in_dir(x, rev_dir(d));
 461         y = y_in_dir(y, rev_dir(d));
 462     }
 463
 464     assert(x == sx && y == sy);
 465     if (len >= bufsz)
 466         bufrotate(buf, bufsz, i);
 467     else {
 468         assert(i + len < bufsz);
 469         memmove(buf, buf + i, len + 1);
 470     }
 471     return len;
 472 }
 473
 474 /*
 475  * Rotate BUF[BUFSZ] to put BUF[I] into BUF[0], and zero-terminate.
 476  */
 477 static char *
 478 bufrotate(char *buf, size_t bufsz, size_t i)
 479 {
 480     char tmp[64];
 481     size_t n;
 482
 483     while (i) {
 484         n = MIN(i, sizeof(tmp));
 485         memcpy(tmp, buf, n);
 486         memcpy(buf, buf + n, bufsz - n);
 487         memcpy(buf + bufsz - n, tmp, n);
 488         i -= n;
 489     }
 490     buf[bufsz - 1] = 0;
 491     return buf;
 492 }
 493
 494 #ifdef PATH_FIND_DEBUG
 495 void
 496 path_find_visualize(coord sx, coord sy, coord dx, coord dy)
 497 {
 498     int uid;
 499     int xmin, xmax, ymin, ymax, x, y, odd, ch;
 500     double c, u, cost;
 501     char buf[1024];
 502
 503     assert(pf_cost(XYOFFSET(sx, sy)) == 0.0);
 504     c = pf_cost(XYOFFSET(dx, dy));
 505     u = c / 10.0;
 506
 507     /* find bounding box */
 508     xmin = xmax = 0;
 509     ymin = ymax = 0;
 510     for (y = -WORLD_Y / 2; y < WORLD_Y / 2; y++) {
 511         odd = ((sx + -WORLD_X / 2) ^ (sy + y)) & 1;
 512         for (x = -WORLD_X / 2 + odd; x < WORLD_X / 2; x += 2) {
 513             uid = XYOFFSET(XNORM(sx + x), YNORM(sy + y));
 514             if (pf_is_unvisited(uid))
 515                 continue;
 516             if (xmin > x)
 517                 xmin = x;
 518             if (xmax < x)
 519                 xmax = x;
 520             if (ymin > y)
 521                 ymin = y;
 522             if (ymax < y)
 523                 ymax = y;
 524         }
 525     }
 526     printf("bbox %d:%d,%d:%d origin %d,%d\n",
 527            xmin, xmax, ymin, ymax, sx, sy);
 528
 529     for (y = ymin; y <= ymax; y++) {
 530         odd = ((sx + xmin) ^ (sy + y)) & 1;
 531         if (odd)
 532             printf(" ");
 533         for (x = xmin + odd; x <= xmax; x += 2) {
 534             uid = XYOFFSET(XNORM(sx + x), YNORM(sy + y));
 535             if (pf_is_unvisited(uid))
 536                 ch = ' ';
 537             else if (uid == XYOFFSET(dx, dy))
 538                 ch = 'D';
 539             else if (uid == XYOFFSET(sx, sy))
 540                 ch = 'S';
 541             else {
 542                 cost = pf_cost(uid);
 543                 ch = cost > c ? '+' : '0' + (int)(10 * (cost / c));
 544             }
 545             printf(" %c", ch);
 546         }
 547         printf("\n");
 548     }
 549     path_find_route(buf, sizeof(buf), sx, sy, dx, dy);
 550     printf("%s %g\n", buf, pf_cost(XYOFFSET(dx, dy)));
 551 }
 552 #endif
 553
 554 #ifdef PATH_FIND_STATS
 555 void
 556 path_find_print_stats(void)
 557 {
 558     printf("pathfind %u searches, %u sources, %u opened, %u closed,"
 559            " %u heap max, %zu bytes, %u noway, %g avg cost\n",
 560            pf_nsearch, pf_nsource, pf_nopen, pf_nclose,
 561            pf_nheap_max,
 562            (WORLD_SZ() * (sizeof(*pf_map) + sizeof(*pf_heap))),
 563            pf_noway, pf_nsearch ? pf_sumcost / pf_nsearch : 0.0);
 564 }
 565 #endif
 566
 567 /*
 568  * Empire interface glue
 569  */
 570
 571 static double
 572 cost_land(natid actor, int uid, int mobtype)
 573 {
 574     /*
 575      * Non-negative cost must not depend on ACTOR, see BestLandPath().
 576      */
 577     struct sctstr *sp = (void *)empfile[EF_SECTOR].cache;
 578
 579     if (sp[uid].sct_own != actor)
 580         return -1.0;
 581     return sector_mcost(&sp[uid], mobtype);
 582 }
 583
 584 static double
 585 cost_move(natid actor, int uid)
 586 {
 587     return cost_land(actor, uid, MOB_MOVE);
 588 }
 589
 590 static double
 591 cost_march(natid actor, int uid)
 592 {
 593     return cost_land(actor, uid, MOB_MARCH);
 594 }
 595
 596 static double
 597 cost_rail(natid actor, int uid)
 598 {
 599     return cost_land(actor, uid, MOB_RAIL);
 600 }
 601
 602 static double
 603 cost_sail(natid actor, int uid)
 604 {
 605     struct sctstr *sp = (void *)empfile[EF_SECTOR].cache;
 606     natid sctown = sp[uid].sct_own;
 607     char *bmap;
 608
 609     if (sctown && relations_with(sctown, actor) == ALLIED) {
 610         /* FIXME duplicates shp_check_nav() logic */
 611         switch (dchr[sp[uid].sct_type].d_nav) {
 612         case NAVOK:
 613             return 1.0;
 614         case NAV_CANAL:
 615             /* FIXME return 1.0 when all ships have M_CANAL */
 616             return -1.0;
 617         case NAV_02:
 618             return sp[uid].sct_effic >= 2 ? 1.0 : -1.0;
 619         case NAV_60:
 620             return sp[uid].sct_effic >= 60 ? 1.0 : -1.0;
 621         default:
 622             return -1.0;
 623         }
 624     }
 625
 626     bmap = ef_ptr(EF_BMAP, actor);
 627     return bmap[uid] == '.' || bmap[uid] == ' ' || bmap[uid] == 0
 628         ? 1.0 : -1.0;
 629 }
 630
 631 static double
 632 cost_fly(natid actor, int uid)
 633 {
 634     return 1.0;
 635 }
 636
 637 static double (*cost_tab[])(natid, int) = {
 638     cost_move, cost_march, cost_rail, cost_sail, cost_fly
 639 };
 640
 641 /*
 642  * Start finding paths from SX,SY.
 643  * Use mobility costs for ACTOR and MOBTYPE.
 644  */
 645 void
 646 path_find_from(coord sx, coord sy, natid actor, int mobtype)
 647 {
 648     pf_set_source(sx, sy, actor, cost_tab[mobtype]);
 649 }
 650
 651 /*
 652  * Find cheapest path from SX,SY to DX,DY, return its mobility cost.
 653  * Use mobility costs for ACTOR and MOBTYPE.
 654  */
 655 double
 656 path_find(coord sx, coord sy, coord dx, coord dy, natid actor, int mobtype)
 657 {
 658     pf_set_source(sx, sy, actor, cost_tab[mobtype]);
 659     return path_find_to(dx, dy);
 660 }