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
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, 2011
42 #include "prototypes.h"
46 #ifdef PATH_FIND_DEBUG
47 #define DPRINTF(fmt, ...) ((void)printf(fmt , ## __VA_ARGS__))
49 #define DPRINTF(fmt, ...) ((void)0)
52 static char *bufrotate(char *buf, size_t bufsz, size_t i);
55 * A* algorithm. Refer to your graph algorithm textbook for how it
56 * works. Implementation is specialized to hex maps.
58 * Define PATH_FIND_STATS for performance statistics on stdout.
62 * Array of sector data, indexed by sector uid
64 * We need to store a few values per sector visited by the path
65 * search. An array is the stupidest data structure that could
68 * Extra benefit: it works really well for distribution in a
69 * continental game, where we visit most sectors. That's our most
70 * demanding use of path search, and its performance has noticable
71 * impact on the update.
73 * Island game distribution is much less demanding. The array may not
74 * be the best choice here, but it's plainly good enough. Same for
75 * path searches outside the update.
80 * visit < pf_visit : unvisited, remaining members invalid
81 * visit == pf_visit : open, dir & cost tentative, heapi used
82 * visit == pf_visit + 1 : closed, dir & cost final, heapi unused
85 signed char dir; /* cheapest direction to source */
86 int heapi; /* index in heap, valid if open */
87 double cost; /* cost from source */
90 static unsigned short pf_visit;
91 static struct pf_map *pf_map;
94 * Binary heap, cost priority queue of all open sectors
96 * Again, we use the stupidest data structure that could possibly
97 * work: an array. And we make it so large it can hold *all* sectors.
98 * In practice, we need much less space, but a tighter upper bound is
99 * not obvious to me right now.
103 int uid; /* sector uid and */
104 coord x, y; /* coordinates, uid == XYOFFSET(x, y) */
105 double f; /* estimated cost from source to dest */
108 static int pf_nheap; /* #entries in pf_nheap[] */
109 static struct pf_heap *pf_heap;
114 static coord pf_sx, pf_sy;
116 static natid pf_actor;
117 static double (*pf_sct_cost)(natid, int);
118 static double (*pf_h)(coord, coord, coord, coord, double);
121 * Performance statistics
123 #ifdef PATH_FIND_STATS
124 static unsigned pf_nsearch, pf_nsource, pf_nopen, pf_nreopen, pf_nclose;
125 static unsigned pf_nheap_max, pf_noway;
126 static double pf_sumcost;
127 #define STAT_INC(v) ((void)((v)++))
128 #define STAT_INCBY(v, i) ((void)((v) += i))
129 #define STAT_HIMARK(v, h) ((void)((v) < (h) ? (v) = (h) : (h)))
130 #else /* !PATH_FIND_STATS */
131 #define STAT_INC(v) ((void)0)
132 #define STAT_INCBY(v, i) ((void)0)
133 #define STAT_HIMARK(v, h) ((void)0)
134 #endif /* !PATH_FIND_STATS */
136 /* Is sector with uid UID open? */
140 return pf_map[uid].visit == pf_visit;
143 /* Is sector with uid UID closed? */
145 pf_is_closed(int uid)
148 * optimization: check > pf_visit instead of == pf_visit + 1
149 * works because pf_map[uid].visit <= pf_visit + 1
151 return pf_map[uid].visit > pf_visit;
154 /* Is sector with uid UID unvisited? */
156 pf_is_unvisited(int uid)
158 return pf_map[uid].visit < pf_visit;
161 #ifdef PATH_FIND_DEBUG
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].f);
174 assert(c >= pf_nheap || pf_heap[i].f <= pf_heap[c].f);
176 assert(c >= pf_nheap || pf_heap[i].f <= pf_heap[c].f);
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);
188 #define pf_check() ((void)0)
191 /* Swap pf_heap's I-th and J-th elements. */
193 pf_heap_swap(int i, int j)
197 assert(0 <= i && i < pf_nheap);
198 assert(0 <= j && j < pf_nheap);
200 pf_heap[i] = pf_heap[j];
202 pf_map[pf_heap[i].uid].heapi = i;
203 pf_map[pf_heap[j].uid].heapi = j;
206 /* Restore heap property after N-th element's cost increased. */
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].f > pf_heap[c + 1].f)
216 if (pf_heap[r].f < pf_heap[c].f)
222 /* Restore heap property after N-th element's cost decreased. */
228 assert(0 <= n && n < pf_nheap);
229 for (c = n; (p = (c - 1) / 2), c > 0; c = p) {
230 if (pf_heap[p].f < pf_heap[c].f)
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 * H is the estimated cost from X,Y to the destination.
243 pf_open(int uid, coord x, coord y, int dir, double cost, double h)
247 if (pf_is_open(uid)) {
248 STAT_INC(pf_nreopen);
249 i = pf_map[uid].heapi;
250 DPRINTF("pf: reopen %d,%d %g %c %d\n", x, y, cost, dirch[dir], i);
252 assert(pf_is_unvisited(uid));
255 STAT_HIMARK(pf_nheap_max, (unsigned)pf_nheap);
256 DPRINTF("pf: open %d,%d %g %c %d\n", x, y, cost, dirch[dir], i);
257 pf_map[uid].heapi = i;
258 pf_map[uid].visit = pf_visit;
259 pf_heap[i].uid = uid;
263 pf_map[uid].dir = dir;
264 pf_map[uid].cost = cost;
265 pf_heap[i].f = cost + h;
272 * Close the sector at the top of the heap.
277 int uid = pf_heap[0].uid;
280 DPRINTF("pf: close %d,%d %d\n", pf_heap[0].x, pf_heap[0].y, pf_nheap);
281 assert(pf_is_open(uid));
283 pf_heap[0] = pf_heap[pf_nheap];
284 pf_map[pf_heap[0].uid].heapi = 0;
287 pf_map[uid].visit = pf_visit + 1;
291 /* silence "not used" warning */
292 #ifdef PATH_FIND_DEBUG
294 * Return cost from source to sector with uid UID.
295 * It must be open (cost is an estimate) or closed (cost is exact).
300 assert(!pf_is_unvisited(uid));
301 return pf_map[uid].cost;
306 x_in_dir(coord x, int dir)
310 assert(0 <= x && x < WORLD_X);
311 assert(0 <= dir && dir <= DIR_LAST);
312 xx = x + diroff[dir][0];
321 y_in_dir(coord y, int dir)
325 assert(0 <= y && y < WORLD_Y);
326 assert(0 <= dir && dir <= DIR_LAST);
327 yy = y + diroff[dir][1];
338 assert(DIR_FIRST <= dir && dir <= DIR_LAST);
339 return dir >= DIR_FIRST + 3 ? dir - 3 : dir + 3;
343 * Set the current source and cost function.
344 * SX,SY is the source.
345 * The cost to enter the sector with uid u is COST(ACTOR, u).
346 * Negative value means the sector can't be entered.
347 * Optional H() is the heuristic: the cost from x,y to the destination
348 * dx,dy is at least H(x, y, dx, dy, c1d), where c1d is the cost to
349 * enter dx,dy. The closer H() is to the true cost, the more
350 * efficient this function works.
351 * With a null H(), A* degenerates into Dijkstra's algorithm. You can
352 * then call path_find_to() multiple times for the same source. This
353 * is faster when you need many destinations.
356 pf_set_source(coord sx, coord sy, natid actor, double (*cost) (natid, int),
357 double (*h) (coord, coord, coord, coord, double))
359 STAT_INC(pf_nsource);
360 DPRINTF("pf: source %d,%d\n", sx, sy);
363 pf_suid = XYOFFSET(sx, sy);
369 pf_map = calloc(WORLD_SZ(), sizeof(*pf_map));
370 pf_heap = malloc(WORLD_SZ() * sizeof(*pf_heap));
372 } else if ((unsigned short)(pf_visit + 3) < pf_visit) {
373 DPRINTF("pf: visit wrap-around\n");
374 memset(pf_map, 0, WORLD_SZ() * sizeof(*pf_map));
383 * Find cheapest path from current source to DX,DY, return its cost.
386 path_find_to(coord dx, coord dy)
390 double c1d, cost, c1;
393 STAT_INC(pf_nsearch);
394 DPRINTF("pf: dest %d,%d\n", dx, dy);
395 duid = XYOFFSET(dx, dy);
396 if (pf_is_closed(duid)) {
397 DPRINTF("pf: done old %g\n", pf_map[duid].cost);
398 STAT_INCBY(pf_sumcost, pf_map[duid].cost);
399 return pf_map[duid].cost;
402 c1d = pf_sct_cost(pf_actor, duid);
404 DPRINTF("pf: done new %g\n", -1.0);
409 if (pf_is_unvisited(pf_suid))
410 /* first search from this source */
411 pf_open(pf_suid, pf_sx, pf_sy, DIR_STOP, 0.0,
412 pf_h ? pf_h(pf_sx, pf_sy, dx, dy, c1d) : 0.0);
414 assert(!pf_h); /* multiple searches only w/o heuristic */
416 while (pf_nheap > 0 && (uid = pf_heap[0].uid) != duid) {
420 cost = pf_map[uid].cost;
422 for (i = 0; i < 6; i++) { /* for all neighbors */
423 nx = x_in_dir(x, DIR_FIRST + i);
424 ny = y_in_dir(y, DIR_FIRST + i);
425 nuid = XYOFFSET(nx, ny);
426 if (pf_h ? pf_is_closed(nuid) : !pf_is_unvisited(nuid))
428 c1 = pf_sct_cost(pf_actor, nuid);
431 if (pf_is_unvisited(nuid) || cost + c1 < pf_map[nuid].cost)
432 pf_open(nuid, nx, ny, DIR_FIRST + i, cost + c1,
433 pf_h ? pf_h(nx, ny, dx, dy, c1d) : 0);
437 DPRINTF("pf: done new %g\n", !pf_nheap ? -1.0 : pf_map[duid].cost);
442 STAT_INCBY(pf_sumcost, pf_map[duid].cost);
443 return pf_map[duid].cost;
447 * Write route from SX,SY to DX,DY to BUF[BUFSIZ], return its length.
448 * If the route is longer than BUFSIZ-1 characters, it's truncated.
449 * You must compute path cost first, with path_find_to().
450 * SX,SY must be on a shortest path from the current source to DX,DY.
453 path_find_route(char *buf, size_t bufsz,
454 coord sx, coord sy, coord dx, coord dy)
460 suid = XYOFFSET(sx, sy);
461 assert(bufsz > 0 && !pf_is_unvisited(suid));
470 DPRINTF("pf: %d,%d %.*s%.*s\n",
472 (int)(bufsz - i), buf + i,
473 len >= bufsz ? (int)i : 0, buf);
474 uid = XYOFFSET(x, y);
475 assert(!pf_is_unvisited(uid));
477 if (d == DIR_STOP || uid == suid)
483 x = x_in_dir(x, rev_dir(d));
484 y = y_in_dir(y, rev_dir(d));
487 assert(x == sx && y == sy);
489 bufrotate(buf, bufsz, i);
491 assert(i + len < bufsz);
492 memmove(buf, buf + i, len + 1);
498 * Rotate BUF[BUFSZ] to put BUF[I] into BUF[0], and zero-terminate.
501 bufrotate(char *buf, size_t bufsz, size_t i)
507 n = MIN(i, sizeof(tmp));
509 memcpy(buf, buf + n, bufsz - n);
510 memcpy(buf + bufsz - n, tmp, n);
517 #ifdef PATH_FIND_DEBUG
519 path_find_visualize(coord sx, coord sy, coord dx, coord dy)
522 int xmin, xmax, ymin, ymax, x, y, odd, ch;
526 assert(pf_cost(XYOFFSET(sx, sy)) == 0.0);
527 c = pf_cost(XYOFFSET(dx, dy));
530 /* find bounding box */
533 for (y = -WORLD_Y / 2; y < WORLD_Y / 2; y++) {
534 odd = ((sx + -WORLD_X / 2) ^ (sy + y)) & 1;
535 for (x = -WORLD_X / 2 + odd; x < WORLD_X / 2; x += 2) {
536 uid = XYOFFSET(XNORM(sx + x), YNORM(sy + y));
537 if (pf_is_unvisited(uid))
549 printf("bbox %d:%d,%d:%d origin %d,%d\n",
550 xmin, xmax, ymin, ymax, sx, sy);
552 for (y = ymin; y <= ymax; y++) {
553 odd = ((sx + xmin) ^ (sy + y)) & 1;
556 for (x = xmin + odd; x <= xmax; x += 2) {
557 uid = XYOFFSET(XNORM(sx + x), YNORM(sy + y));
558 if (pf_is_unvisited(uid))
560 else if (uid == XYOFFSET(dx, dy))
562 else if (uid == XYOFFSET(sx, sy))
566 ch = cost > c ? '+' : '0' + (int)(10 * (cost / c));
572 path_find_route(buf, sizeof(buf), sx, sy, dx, dy);
573 printf("%s %g\n", buf, pf_cost(XYOFFSET(dx, dy)));
577 #ifdef PATH_FIND_STATS
579 path_find_print_stats(void)
581 printf("pathfind %u searches, %u sources,"
582 " %u opened, %u reopened, %u closed,"
583 " %u heap max, %zu bytes, %u noway, %g avg cost\n",
584 pf_nsearch, pf_nsource, pf_nopen, pf_nreopen, pf_nclose,
586 (WORLD_SZ() * (sizeof(*pf_map) + sizeof(*pf_heap))),
587 pf_noway, pf_nsearch ? pf_sumcost / pf_nsearch : 0.0);
592 * Empire interface glue
596 cost_land(natid actor, int uid, int mobtype)
599 * Non-negative cost must not depend on ACTOR, see BestLandPath().
601 struct sctstr *sp = (void *)empfile[EF_SECTOR].cache;
603 if (sp[uid].sct_own != actor)
605 return sector_mcost(&sp[uid], mobtype);
609 cost_move(natid actor, int uid)
611 return cost_land(actor, uid, MOB_MOVE);
615 cost_march(natid actor, int uid)
617 return cost_land(actor, uid, MOB_MARCH);
621 cost_rail(natid actor, int uid)
623 return cost_land(actor, uid, MOB_RAIL);
627 h_move(coord x, coord y, coord dx, coord dy, double c1d)
629 int md = mapdist(x, y, dx, dy);
630 return md ? c1d + (md - 1) * 0.001 : 0.0;
634 h_march_rail(coord x, coord y, coord dx, coord dy, double c1d)
636 int md = mapdist(x, y, dx, dy);
637 return md ? c1d + (md - 1) * 0.02 : 0.0;
641 cost_sail(natid actor, int uid)
643 struct sctstr *sp = (void *)empfile[EF_SECTOR].cache;
644 natid sctown = sp[uid].sct_own;
647 if (sctown && relations_with(sctown, actor) == ALLIED) {
648 /* FIXME duplicates shp_check_nav() logic */
649 switch (dchr[sp[uid].sct_type].d_nav) {
653 /* FIXME return 1.0 when all ships have M_CANAL */
656 return sp[uid].sct_effic >= 2 ? 1.0 : -1.0;
658 return sp[uid].sct_effic >= 60 ? 1.0 : -1.0;
664 bmap = ef_ptr(EF_BMAP, actor);
665 return bmap[uid] == '.' || bmap[uid] == ' ' || bmap[uid] == 0
670 cost_fly(natid actor, int uid)
676 h_sail_fly(coord x, coord y, coord dx, coord dy, double c1d)
678 return mapdist(x, y, dx, dy);
681 static double (*cost_tab[])(natid, int) = {
682 cost_move, cost_march, cost_rail, cost_sail, cost_fly
685 static double (*h[])(coord, coord, coord, coord, double) = {
686 h_move, h_march_rail, h_march_rail, h_sail_fly, h_sail_fly
690 * Start finding paths from SX,SY.
691 * Use mobility costs for ACTOR and MOBTYPE.
694 path_find_from(coord sx, coord sy, natid actor, int mobtype)
696 pf_set_source(sx, sy, actor, cost_tab[mobtype], NULL);
700 * Find cheapest path from SX,SY to DX,DY, return its mobility cost.
701 * Use mobility costs for ACTOR and MOBTYPE.
704 path_find(coord sx, coord sy, coord dx, coord dy, natid actor, int mobtype)
706 pf_set_source(sx, sy, actor, cost_tab[mobtype], h[mobtype]);
707 return path_find_to(dx, dy);