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 "optlist.h"
  41 #include "path.h"
  42 #include "sect.h"
  43
  44 #ifdef PATH_FIND_DEBUG
  45 #define DPRINTF(fmt, ...) ((void)printf(fmt , ## __VA_ARGS__))
  46 #else
  47 #define DPRINTF(fmt, ...) ((void)0)
  48 #endif
  49
  50 static char *bufrotate(char *buf, size_t bufsz, size_t i);
  51
  52 /*
  53  * Dijkstra's algorithm.  Refer to your graph algorithm textbook for
  54  * how it works.  Implementation is specialized to hex maps.
  55  */
  56
  57 /*
  58  * Array of sector data, indexed by sector uid
  59  *
  60  * We need to store a few values per sector visited by the path
  61  * search.  An array is the stupidest data structure that could
  62  * possibly work.
  63  *
  64  * Extra benefit: it works really well for distribution in a
  65  * continental game, where we visit most sectors.  That's our most
  66  * demanding use of path search, and its performance has noticable
  67  * impact on the update.
  68  *
  69  * Island game distribution is much less demanding.  The array may not
  70  * be the best choice here, but it's plainly good enough.  Same for
  71  * path searches outside the update.
  72  */
  73
  74 struct pf_map {
  75     /*
  76      * visit < pf_visit      : unvisited, remaining members invalid
  77      * visit == pf_visit     : open, dir & cost tentative, heapi used
  78      * visit == pf_visit + 1 : closed, dir & cost final, heapi unused
  79      */
  80     unsigned short visit;
  81     signed char dir;            /* cheapest direction to source */
  82     int heapi;                  /* index in heap, valid if open */
  83     double cost;                /* cost from source */
  84 };
  85
  86 static unsigned short pf_visit;
  87 static struct pf_map *pf_map;
  88
  89 /*
  90  * Binary heap, cost priority queue of all open sectors
  91  *
  92  * Again, we use the stupidest data structure that could possibly
  93  * work: an array.  And we make it so large it can hold *all* sectors.
  94  * In practice, we need much less space, but a tighter upper bound is
  95  * not obvious to me right now.
  96  */
  97
  98 struct pf_heap {
  99     int uid;                    /* sector uid and */
 100     coord x, y;                 /* coordinates, uid == XYOFFSET(x, y) */
 101     double cost;                /* cost from source */
 102 };
 103
 104 static int pf_nheap;            /* #entries in pf_nheap[] */
 105 static struct pf_heap *pf_heap;
 106
 107 /*
 108  * Source and costs
 109  */
 110 static coord pf_sx, pf_sy;
 111 static int pf_suid;
 112 static natid pf_actor;
 113 static double (*pf_sct_cost)(natid, int);
 114
 115 #ifndef NDEBUG                  /* silence "not used" warning */
 116 /* Is sector with uid UID open?  */
 117 static int
 118 pf_is_open(int uid)
 119 {
 120     return pf_map[uid].visit == pf_visit;
 121 }
 122 #endif
 123
 124 /* Is sector with uid UID closed?  */
 125 static int
 126 pf_is_closed(int uid)
 127 {
 128     /*
 129      * optimization: check > pf_visit instead of == pf_visit + 1
 130      * works because pf_map[uid].visit <= pf_visit + 1
 131      */
 132     return pf_map[uid].visit > pf_visit;
 133 }
 134
 135 /* Is sector with uid UID unvisited?  */
 136 static int
 137 pf_is_unvisited(int uid)
 138 {
 139     return pf_map[uid].visit < pf_visit;
 140 }
 141
 142 #ifdef PATH_FIND_DEBUG
 143 static void
 144 pf_check(void)
 145 {
 146     int i, uid, c;
 147
 148     for (i = 0; i < pf_nheap; i++) {
 149         uid = pf_heap[i].uid;
 150         assert(0 <= uid && uid < WORLD_SZ());
 151         assert(pf_map[uid].heapi == i);
 152         assert(pf_map[uid].visit == pf_visit);
 153         assert(pf_map[uid].cost <= pf_heap[i].cost);
 154         c = 2 * i + 1;
 155         assert(c >= pf_nheap || pf_heap[i].cost <= pf_heap[c].cost);
 156         c++;
 157         assert(c >= pf_nheap || pf_heap[i].cost <= pf_heap[c].cost);
 158     }
 159
 160     for (uid = 0; uid < WORLD_SZ(); uid++) {
 161         assert(pf_map[uid].visit <= pf_visit + 1);
 162         if (pf_map[uid].visit == pf_visit) {
 163             i = pf_map[uid].heapi;
 164             assert(0 <= i && i < pf_nheap && pf_heap[i].uid == uid);
 165         }
 166     }
 167 }
 168 #else
 169 #define pf_check() ((void)0)
 170 #endif
 171
 172 /* Swap pf_heap's I-th and J-th elements.  */
 173 static void
 174 pf_heap_swap(int i, int j)
 175 {
 176     struct pf_heap tmp;
 177
 178     assert(0 <= i && i < pf_nheap);
 179     assert(0 <= j && j < pf_nheap);
 180     tmp = pf_heap[i];
 181     pf_heap[i] = pf_heap[j];
 182     pf_heap[j] = tmp;
 183     pf_map[pf_heap[i].uid].heapi = i;
 184     pf_map[pf_heap[j].uid].heapi = j;
 185 }
 186
 187 /* Restore heap property after N-th element's cost increased.  */
 188 static void
 189 pf_sift_down(int n)
 190 {
 191     int r, c;
 192
 193     assert(0 <= n && n < pf_nheap);
 194     for (r = n; (c = 2 * r + 1) < pf_nheap; r = c) {
 195         if (c + 1 < pf_nheap && pf_heap[c].cost > pf_heap[c + 1].cost)
 196             c++;
 197         if (pf_heap[r].cost < pf_heap[c].cost)
 198             break;
 199         pf_heap_swap(r, c);
 200     }
 201 }
 202
 203 /* Restore heap property after N-th element's cost decreased.  */
 204 static void
 205 pf_sift_up(int n)
 206 {
 207     int c, p;
 208
 209     assert(0 <= n && n < pf_nheap);
 210     for (c = n; (p = (c - 1) / 2), c > 0; c = p) {
 211         if (pf_heap[p].cost < pf_heap[c].cost)
 212             break;
 213         pf_heap_swap(p, c);
 214     }
 215 }
 216
 217 /*
 218  * Open the unvisited sector X,Y.
 219  * UID is sector uid, it equals XYOFFSET(X,Y).
 220  * Cheapest path from source comes from direction DIR and has cost COST.
 221  */
 222 static void
 223 pf_open(int uid, coord x, coord y, int dir, double cost)
 224 {
 225     int i;
 226
 227     i = pf_nheap++;
 228     DPRINTF("pf: open %d,%d %g %c %d\n", x, y, cost, dirch[dir], i);
 229     assert(pf_is_unvisited(uid));
 230     pf_map[uid].visit = pf_visit;
 231     pf_map[uid].dir = dir;
 232     pf_map[uid].heapi = i;
 233     pf_map[uid].cost = cost;
 234     pf_heap[i].uid = uid;
 235     pf_heap[i].x = x;
 236     pf_heap[i].y = y;
 237     pf_heap[i].cost = cost;
 238
 239     pf_sift_up(i);
 240     pf_check();
 241 }
 242
 243 /*
 244  * Close the sector at the top of the heap.
 245  */
 246 static void
 247 pf_close(void)
 248 {
 249     int uid = pf_heap[0].uid;
 250
 251     DPRINTF("pf: close %d,%d %d\n", pf_heap[0].x, pf_heap[0].y, pf_nheap);
 252     assert(pf_is_open(uid));
 253     if (--pf_nheap) {
 254         pf_heap[0] = pf_heap[pf_nheap];
 255         pf_map[pf_heap[0].uid].heapi = 0;
 256         pf_sift_down(0);
 257     }
 258     pf_map[uid].visit = pf_visit + 1;
 259     pf_check();
 260 }
 261
 262 static coord
 263 x_in_dir(coord x, int dir)
 264 {
 265     int xx;
 266
 267     assert(0 <= x && x < WORLD_X);
 268     assert(0 <= dir && dir <= DIR_LAST);
 269     xx = x + diroff[dir][0];
 270     if (xx < 0)
 271         return xx + WORLD_X;
 272     if (xx >= WORLD_X)
 273         return xx - WORLD_X;
 274     return xx;
 275 }
 276
 277 static coord
 278 y_in_dir(coord y, int dir)
 279 {
 280     int yy;
 281
 282     assert(0 <= y && y < WORLD_Y);
 283     assert(0 <= dir && dir <= DIR_LAST);
 284     yy = y + diroff[dir][1];
 285     if (yy < 0)
 286         return yy + WORLD_Y;
 287     if (yy >= WORLD_Y)
 288         return yy - WORLD_Y;
 289     return yy;
 290 }
 291
 292 static int
 293 rev_dir(int dir)
 294 {
 295     assert(DIR_FIRST <= dir && dir <= DIR_LAST);
 296     return dir >= DIR_FIRST + 3 ? dir - 3 : dir + 3;
 297 }
 298
 299 /*
 300  * Set the current source and cost function.
 301  * SX,SY is the source.
 302  * The cost to enter the sector with uid u is COST(ACTOR, u).
 303  * Negative value means the sector can't be entered.
 304  */
 305 static void
 306 pf_set_source(coord sx, coord sy, natid actor, double (*cost)(natid, int))
 307 {
 308     DPRINTF("pf: source %d,%d\n", sx, sy);
 309     pf_sx = sx;
 310     pf_sy = sy;
 311     pf_suid = XYOFFSET(sx, sy);
 312     pf_actor = actor;
 313     pf_sct_cost = cost;
 314
 315     if (!pf_map) {
 316         pf_map = calloc(WORLD_SZ(), sizeof(*pf_map));
 317         pf_heap = malloc(WORLD_SZ() * sizeof(*pf_heap));
 318         pf_visit = 1;
 319     } else if ((unsigned short)(pf_visit + 3) < pf_visit) {
 320         DPRINTF("pf: visit wrap-around\n");
 321         memset(pf_map, 0, WORLD_SZ() * sizeof(*pf_map));
 322         pf_visit = 1;
 323     } else
 324         pf_visit += 2;
 325
 326     pf_nheap = 0;
 327
 328     pf_open(pf_suid, pf_sx, pf_sy, DIR_STOP, 0.0);
 329 }
 330
 331 /*
 332  * Find cheapest path from current source to DX,DY, return its cost.
 333  */
 334 double
 335 path_find_to(coord dx, coord dy)
 336 {
 337     int duid;
 338     int uid, nuid, i;
 339     double cost, c1;
 340     coord x, y, nx, ny;
 341
 342     DPRINTF("pf: dest %d,%d\n", dx, dy);
 343     duid = XYOFFSET(dx, dy);
 344     if (pf_is_closed(duid)) {
 345         DPRINTF("pf: done old %g\n", pf_map[duid].cost);
 346         return pf_map[duid].cost;
 347     }
 348
 349     while (pf_nheap > 0 && (uid = pf_heap[0].uid) != duid) {
 350         x = pf_heap[0].x;
 351         y = pf_heap[0].y;
 352         cost = pf_heap[0].cost;
 353         pf_close();
 354
 355         for (i = 0; i < 6; i++) { /* for all neighbors */
 356             nx = x_in_dir(x, DIR_FIRST + i);
 357             ny = y_in_dir(y, DIR_FIRST + i);
 358             nuid = XYOFFSET(nx, ny);
 359             /*
 360              * Cost to enter NX,NY doesn't depend on direction of
 361              * entry.  This X,Y is at least as expensive as any
 362              * previous one.  Therefore, cost to go to NX,NY via X,Y
 363              * is at least as high as any previously found route.
 364              * Skip neighbors that have a route already.
 365              */
 366             if (!pf_is_unvisited(nuid))
 367                 continue;
 368             c1 = pf_sct_cost(pf_actor, nuid);
 369             if (c1 < 0)
 370                 continue;
 371             pf_open(nuid, nx, ny, DIR_FIRST + i, cost + c1);
 372         }
 373     }
 374
 375     DPRINTF("pf: done new %g\n", !pf_nheap ? -1.0 : pf_map[duid].cost);
 376     if (!pf_nheap)
 377         return -1.0;
 378     return pf_map[duid].cost;
 379 }
 380
 381 /*
 382  * Write route from SX,SY to DX,DY to BUF[BUFSIZ], return its length.
 383  * If the route is longer than BUFSIZ-1 characters, it's truncated.
 384  * You must compute path cost first, with path_find_to().
 385  * SX,SY must be on a shortest path from the current source to DX,DY.
 386  */
 387 size_t
 388 path_find_route(char *buf, size_t bufsz,
 389                 coord sx, coord sy, coord dx, coord dy)
 390 {
 391     coord x, y;
 392     size_t i, len;
 393     int suid, uid, d;
 394
 395     suid = XYOFFSET(sx, sy);
 396     assert(bufsz > 0 && !pf_is_unvisited(suid));
 397
 398     i = bufsz;
 399     buf[--i] = 0;
 400     len = 0;
 401
 402     x = dx;
 403     y = dy;
 404     for (;;) {
 405         DPRINTF("pf: %d,%d %.*s%.*s\n",
 406                 x, y,
 407                 (int)(bufsz - i), buf + i,
 408                 len >= bufsz ? (int)i : 0, buf);
 409         uid = XYOFFSET(x, y);
 410         assert(!pf_is_unvisited(uid));
 411         d = pf_map[uid].dir;
 412         if (d == DIR_STOP || uid == suid)
 413             break;
 414         if (!i)
 415             i = bufsz;
 416         buf[--i] = dirch[d];
 417         len++;
 418         x = x_in_dir(x, rev_dir(d));
 419         y = y_in_dir(y, rev_dir(d));
 420     }
 421
 422     assert(x == sx && y == sy);
 423     if (len >= bufsz)
 424         bufrotate(buf, bufsz, i);
 425     else {
 426         assert(i + len < bufsz);
 427         memmove(buf, buf + i, len + 1);
 428     }
 429     return len;
 430 }
 431
 432 /*
 433  * Rotate BUF[BUFSZ] to put BUF[I] into BUF[0], and zero-terminate.
 434  */
 435 static char *
 436 bufrotate(char *buf, size_t bufsz, size_t i)
 437 {
 438     char tmp[64];
 439     size_t n;
 440
 441     while (i) {
 442         n = MIN(i, sizeof(tmp));
 443         memcpy(tmp, buf, n);
 444         memcpy(buf, buf + n, bufsz - n);
 445         memcpy(buf + bufsz - n, tmp, n);
 446         i -= n;
 447     }
 448     buf[bufsz - 1] = 0;
 449     return buf;
 450 }
 451
 452
 453 /*
 454  * Empire interface glue
 455  */
 456
 457 static double
 458 cost_land(natid actor, int uid, int mobtype)
 459 {
 460     /*
 461      * Non-negative cost must not depend on ACTOR, see BestLandPath().
 462      */
 463     struct sctstr *sp = (void *)empfile[EF_SECTOR].cache;
 464
 465     if (sp[uid].sct_own != actor)
 466         return -1.0;
 467     return sector_mcost(&sp[uid], mobtype);
 468 }
 469
 470 static double
 471 cost_move(natid actor, int uid)
 472 {
 473     return cost_land(actor, uid, MOB_MOVE);
 474 }
 475
 476 static double
 477 cost_march(natid actor, int uid)
 478 {
 479     return cost_land(actor, uid, MOB_MARCH);
 480 }
 481
 482 static double
 483 cost_rail(natid actor, int uid)
 484 {
 485     return cost_land(actor, uid, MOB_RAIL);
 486 }
 487
 488 static double (*cost_tab[])(natid, int) = {
 489     cost_move, cost_march, cost_rail
 490 };
 491
 492 /*
 493  * Start finding paths from SX,SY.
 494  * Use mobility costs for ACTOR and MOBTYPE.
 495  */
 496 void
 497 path_find_from(coord sx, coord sy, natid actor, int mobtype)
 498 {
 499     pf_set_source(sx, sy, actor, cost_tab[mobtype]);
 500 }
 501
 502 /*
 503  * Find cheapest path from SX,SY to DX,DY, return its mobility cost.
 504  * Use mobility costs for ACTOR and MOBTYPE.
 505  */
 506 double
 507 path_find(coord sx, coord sy, coord dx, coord dy, natid actor, int mobtype)
 508 {
 509     pf_set_source(sx, sy, actor, cost_tab[mobtype]);
 510     return path_find_to(dx, dy);
 511 }