2 * Empire - A multi-player, client/server Internet based war game.
3 * Copyright (C) 1986-2020, Dave Pare, Jeff Bailey, Thomas Ruschak,
4 * Ken Stevens, Steve McClure, Markus Armbruster
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.
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.
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/>.
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.
27 * pathfind.c: Find cheapest paths
29 * Known contributors to this file:
30 * Markus Armbruster, 2014
44 #ifdef PATH_FIND_DEBUG
45 #define DPRINTF(fmt, ...) ((void)printf(fmt , ## __VA_ARGS__))
47 #define DPRINTF(fmt, ...) ((void)0)
50 static char *bufrotate(char *buf, size_t bufsz, size_t i);
53 * Dijkstra's algorithm. Refer to your graph algorithm textbook for
54 * how it works. Implementation is specialized to hex maps.
56 * Define PATH_FIND_STATS for performance statistics on stdout.
60 * Array of sector data, indexed by sector UID
62 * We need to store a few values per sector visited by the path
63 * search. An array is the stupidest data structure that could
66 * Extra benefit: it works really well for distribution in a
67 * continental game, where we visit most sectors. That's our most
68 * demanding use of path search, and its performance has noticable
69 * impact on the update.
71 * Island game distribution is much less demanding. The array may not
72 * be the best choice here, but it's plainly good enough. Same for
73 * path searches outside the update.
78 * visit < pf_visit : unvisited, remaining members invalid
79 * visit == pf_visit : open, dir & cost tentative, heapi used
80 * visit == pf_visit + 1 : closed, dir & cost final, heapi unused
83 signed char dir; /* cheapest direction to source */
84 int heapi; /* index in heap, valid if open */
85 double cost; /* cost from source */
88 static unsigned short pf_visit;
89 static struct pf_map *pf_map;
92 * Binary heap, cost priority queue of all open sectors
94 * Again, we use the stupidest data structure that could possibly
95 * work: an array. And we make it so large it can hold *all* sectors.
96 * In practice, we need much less space, but a tighter upper bound is
97 * not obvious to me right now.
101 int uid; /* sector UID and ... */
102 coord x, y; /* coordinates, @uid == XYOFFSET(@x, @y) */
103 double cost; /* cost from source */
106 static int pf_nheap; /* #entries in pf_nheap[] */
107 static struct pf_heap *pf_heap;
112 static coord pf_sx, pf_sy;
114 static natid pf_actor;
115 static double (*pf_sct_cost)(natid, int);
118 * Performance statistics
120 #ifdef PATH_FIND_STATS
121 static unsigned pf_nsearch, pf_nsource, pf_nopen, pf_nclose;
122 static unsigned pf_nheap_max, pf_noway;
123 static double pf_sumcost;
124 #define STAT_INC(v) ((void)((v)++))
125 #define STAT_INCBY(v, i) ((void)((v) += i))
126 #define STAT_HIMARK(v, h) ((void)((v) < (h) ? (v) = (h) : (h)))
127 #else /* !PATH_FIND_STATS */
128 #define STAT_INC(v) ((void)0)
129 #define STAT_INCBY(v, i) ((void)0)
130 #define STAT_HIMARK(v, h) ((void)0)
131 #endif /* !PATH_FIND_STATS */
133 #ifndef NDEBUG /* silence "not used" warning */
134 /* Is sector with UID @uid open? */
138 return pf_map[uid].visit == pf_visit;
142 /* Is sector with UID @uid closed? */
144 pf_is_closed(int uid)
147 * optimization: check > pf_visit instead of == pf_visit + 1
148 * works because pf_map[uid].visit <= pf_visit + 1
150 return pf_map[uid].visit > pf_visit;
153 /* Is sector with UID @uid unvisited? */
155 pf_is_unvisited(int uid)
157 return pf_map[uid].visit < pf_visit;
160 #ifdef PATH_FIND_DEBUG
166 for (i = 0; i < pf_nheap; i++) {
167 uid = pf_heap[i].uid;
168 assert(0 <= uid && uid < WORLD_SZ());
169 assert(pf_map[uid].heapi == i);
170 assert(pf_map[uid].visit == pf_visit);
171 assert(pf_map[uid].cost <= pf_heap[i].cost);
173 assert(c >= pf_nheap || pf_heap[i].cost <= pf_heap[c].cost);
175 assert(c >= pf_nheap || pf_heap[i].cost <= pf_heap[c].cost);
178 for (uid = 0; uid < WORLD_SZ(); uid++) {
179 assert(pf_map[uid].visit <= pf_visit + 1);
180 if (pf_map[uid].visit == pf_visit) {
181 i = pf_map[uid].heapi;
182 assert(0 <= i && i < pf_nheap && pf_heap[i].uid == uid);
187 #define pf_check() ((void)0)
190 /* Swap pf_heap's @i-th and @j-th elements. */
192 pf_heap_swap(int i, int j)
196 assert(0 <= i && i < pf_nheap);
197 assert(0 <= j && j < pf_nheap);
199 pf_heap[i] = pf_heap[j];
201 pf_map[pf_heap[i].uid].heapi = i;
202 pf_map[pf_heap[j].uid].heapi = j;
205 /* Restore heap property after @n-th element's cost increased. */
211 assert(0 <= n && n < pf_nheap);
212 for (r = n; (c = 2 * r + 1) < pf_nheap; r = c) {
213 if (c + 1 < pf_nheap && pf_heap[c].cost > pf_heap[c + 1].cost)
215 if (pf_heap[r].cost < pf_heap[c].cost)
221 /* Restore heap property after @n-th element's cost decreased. */
227 assert(0 <= n && n < pf_nheap);
228 for (c = n; (p = (c - 1) / 2), c > 0; c = p) {
229 if (pf_heap[p].cost < pf_heap[c].cost)
236 * Open the unvisited sector @x,@y.
237 * @uid is sector UID, it equals XYOFFSET(@x,@y).
238 * Cheapest path from source comes from direction @dir and has cost @cost.
241 pf_open(int uid, coord x, coord y, int dir, double cost)
247 STAT_HIMARK(pf_nheap_max, (unsigned)pf_nheap);
248 DPRINTF("pf: open %d,%d %g %c %d\n", x, y, cost, dirch[dir], i);
249 assert(pf_is_unvisited(uid));
250 pf_map[uid].visit = pf_visit;
251 pf_map[uid].dir = dir;
252 pf_map[uid].heapi = i;
253 pf_map[uid].cost = cost;
254 pf_heap[i].uid = uid;
257 pf_heap[i].cost = cost;
264 * Close the sector at the top of the heap.
269 int uid = pf_heap[0].uid;
272 DPRINTF("pf: close %d,%d %d\n", pf_heap[0].x, pf_heap[0].y, pf_nheap);
273 assert(pf_is_open(uid));
275 pf_heap[0] = pf_heap[pf_nheap];
276 pf_map[pf_heap[0].uid].heapi = 0;
279 pf_map[uid].visit = pf_visit + 1;
283 /* silence "not used" warning */
284 #ifdef PATH_FIND_DEBUG
286 * Return cost from source to sector with UID @uid.
287 * It must be visited, i.e. open or closed.
292 assert(!pf_is_unvisited(uid));
293 return pf_map[uid].cost;
298 x_in_dir(coord x, int dir)
302 assert(0 <= x && x < WORLD_X);
303 assert(0 <= dir && dir <= DIR_LAST);
304 xx = x + diroff[dir][0];
313 y_in_dir(coord y, int dir)
317 assert(0 <= y && y < WORLD_Y);
318 assert(0 <= dir && dir <= DIR_LAST);
319 yy = y + diroff[dir][1];
328 * Set the current source and cost function.
329 * @sx,@sy is the source.
330 * The cost to enter the sector with UID ID is @cost(@actor, ID).
331 * Negative value means the sector can't be entered.
334 pf_set_source(coord sx, coord sy, natid actor, double (*cost)(natid, int))
336 STAT_INC(pf_nsource);
337 DPRINTF("pf: source %d,%d\n", sx, sy);
340 pf_suid = XYOFFSET(sx, sy);
345 pf_map = calloc(WORLD_SZ(), sizeof(*pf_map));
346 pf_heap = malloc(WORLD_SZ() * sizeof(*pf_heap));
348 } else if ((unsigned short)(pf_visit + 3) < pf_visit) {
349 DPRINTF("pf: visit wrap-around\n");
350 memset(pf_map, 0, WORLD_SZ() * sizeof(*pf_map));
357 pf_open(pf_suid, pf_sx, pf_sy, DIR_STOP, 0.0);
361 * Find cheapest path from current source to @dx,@dy, return its cost.
364 path_find_to(coord dx, coord dy)
370 STAT_INC(pf_nsearch);
371 DPRINTF("pf: dest %d,%d\n", dx, dy);
372 duid = XYOFFSET(dx, dy);
373 if (pf_is_closed(duid)) {
374 DPRINTF("pf: done old %g\n", pf_map[duid].cost);
375 STAT_INCBY(pf_sumcost, pf_map[duid].cost);
376 return pf_map[duid].cost;
379 while (pf_nheap > 0 && pf_heap[0].uid != duid) {
382 cost = pf_heap[0].cost;
385 for (i = 0; i < 6; i++) { /* for all neighbors */
386 nx = x_in_dir(x, DIR_FIRST + i);
387 ny = y_in_dir(y, DIR_FIRST + i);
388 nuid = XYOFFSET(nx, ny);
390 * Cost to enter @nx,@ny doesn't depend on direction of
391 * entry. This @x,@y is at least as expensive as any
392 * previous one. Therefore, cost to go to @nx,@ny via
393 * @x,@y is at least as high as any previously found
394 * route. Skip neighbors that have a route already.
396 if (!pf_is_unvisited(nuid))
398 c1 = pf_sct_cost(pf_actor, nuid);
401 pf_open(nuid, nx, ny, DIR_FIRST + i, cost + c1);
405 DPRINTF("pf: done new %g\n", !pf_nheap ? -1.0 : pf_map[duid].cost);
410 STAT_INCBY(pf_sumcost, pf_map[duid].cost);
411 return pf_map[duid].cost;
415 * Write route from @sx,@sy to @dx,@dy to array @buf[@bufsiz].
416 * If the route is longer than @bufsiz-1 characters, it's truncated.
417 * You must compute path cost first, with path_find_to().
418 * @sx,@sy must be on a shortest path from the current source to @dx,@dy.
419 * Return length of the (untruncated) route.
422 path_find_route(char *buf, size_t bufsz,
423 coord sx, coord sy, coord dx, coord dy)
429 suid = XYOFFSET(sx, sy);
430 assert(bufsz > 0 && !pf_is_unvisited(suid));
439 DPRINTF("pf: %d,%d %.*s%.*s\n",
441 (int)(bufsz - i), buf + i,
442 len >= bufsz ? (int)i : 0, buf);
443 uid = XYOFFSET(x, y);
444 assert(!pf_is_unvisited(uid));
446 if (d == DIR_STOP || uid == suid)
452 assert(DIR_FIRST <= d && d <= DIR_LAST);
453 x = x_in_dir(x, DIR_BACK(d));
454 y = y_in_dir(y, DIR_BACK(d));
457 assert(x == sx && y == sy);
459 bufrotate(buf, bufsz, i);
461 assert(i + len < bufsz);
462 memmove(buf, buf + i, len + 1);
468 * Rotate @buf[@bufsz] to put @buf[@i] into @buf[0], and zero-terminate.
471 bufrotate(char *buf, size_t bufsz, size_t i)
477 n = MIN(i, sizeof(tmp));
479 memcpy(buf, buf + n, bufsz - n);
480 memcpy(buf + bufsz - n, tmp, n);
487 #ifdef PATH_FIND_DEBUG
489 path_find_visualize(coord sx, coord sy, coord dx, coord dy)
492 int xmin, xmax, ymin, ymax, x, y, odd, ch;
496 assert(pf_cost(XYOFFSET(sx, sy)) == 0.0);
497 c = pf_cost(XYOFFSET(dx, dy));
500 /* find bounding box */
503 for (y = -WORLD_Y / 2; y < WORLD_Y / 2; y++) {
504 odd = ((sx + -WORLD_X / 2) ^ (sy + y)) & 1;
505 for (x = -WORLD_X / 2 + odd; x < WORLD_X / 2; x += 2) {
506 uid = XYOFFSET(XNORM(sx + x), YNORM(sy + y));
507 if (pf_is_unvisited(uid))
519 printf("bbox %d:%d,%d:%d origin %d,%d\n",
520 xmin, xmax, ymin, ymax, sx, sy);
522 for (y = ymin; y <= ymax; y++) {
523 odd = ((sx + xmin) ^ (sy + y)) & 1;
526 for (x = xmin + odd; x <= xmax; x += 2) {
527 uid = XYOFFSET(XNORM(sx + x), YNORM(sy + y));
528 if (pf_is_unvisited(uid))
530 else if (uid == XYOFFSET(dx, dy))
532 else if (uid == XYOFFSET(sx, sy))
536 ch = cost > c ? '+' : '0' + (int)(10 * (cost / c));
542 path_find_route(buf, sizeof(buf), sx, sy, dx, dy);
543 printf("%s %g\n", buf, pf_cost(XYOFFSET(dx, dy)));
547 #ifdef PATH_FIND_STATS
549 path_find_print_stats(void)
551 printf("pathfind %u searches, %u sources, %u opened, %u closed,"
552 " %u heap max, %zu bytes, %u noway, %g avg cost\n",
553 pf_nsearch, pf_nsource, pf_nopen, pf_nclose,
555 (WORLD_SZ() * (sizeof(*pf_map) + sizeof(*pf_heap))),
556 pf_noway, pf_nsearch ? pf_sumcost / pf_nsearch : 0.0);
561 * Empire interface glue
565 cost_land(natid actor, int uid, int mobtype)
568 * Non-negative cost must not depend on @actor, see unit_path().
570 struct sctstr *sp = (void *)empfile[EF_SECTOR].cache;
572 if (sp[uid].sct_own != actor)
574 return sector_mcost(&sp[uid], mobtype);
578 cost_move(natid actor, int uid)
580 return cost_land(actor, uid, MOB_MOVE);
584 cost_march(natid actor, int uid)
586 return cost_land(actor, uid, MOB_MARCH);
590 cost_rail(natid actor, int uid)
592 return cost_land(actor, uid, MOB_RAIL);
596 cost_sail(natid actor, int uid)
598 struct sctstr *sp = (void *)empfile[EF_SECTOR].cache;
599 natid sctown = sp[uid].sct_own;
602 if (sctown && relations_with(sctown, actor) == ALLIED) {
603 /* FIXME duplicates shp_check_nav() logic */
604 switch (dchr[sp[uid].sct_type].d_nav) {
608 /* FIXME return 1.0 when all ships have M_CANAL */
611 return sp[uid].sct_effic >= 2 ? 1.0 : -1.0;
613 return sp[uid].sct_effic >= 60 ? 1.0 : -1.0;
619 bmap = ef_ptr(EF_BMAP, actor);
620 return bmap[uid] == '.' || bmap[uid] == ' ' || bmap[uid] == 0
625 cost_fly(natid actor, int uid)
630 static double (*cost_tab[])(natid, int) = {
631 cost_move, cost_march, cost_rail, cost_sail, cost_fly
635 * Start finding paths from @sx,@sy.
636 * Use mobility costs for @actor and @mobtype.
639 path_find_from(coord sx, coord sy, natid actor, int mobtype)
641 pf_set_source(sx, sy, actor, cost_tab[mobtype]);
645 * Find cheapest path from @sx,@sy to @dx,@dy, return its mobility cost.
646 * Use mobility costs for @actor and @mobtype.
649 path_find(coord sx, coord sy, coord dx, coord dy, natid actor, int mobtype)
651 pf_set_source(sx, sy, actor, cost_tab[mobtype]);
652 return path_find_to(dx, dy);