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
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.
58 * Array of sector data, indexed by sector uid
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
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.
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.
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
81 signed char dir; /* cheapest direction to source */
82 int heapi; /* index in heap, valid if open */
83 double cost; /* cost from source */
86 static unsigned short pf_visit;
87 static struct pf_map *pf_map;
90 * Binary heap, cost priority queue of all open sectors
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.
99 int uid; /* sector uid and */
100 coord x, y; /* coordinates, uid == XYOFFSET(x, y) */
101 double cost; /* cost from source */
104 static int pf_nheap; /* #entries in pf_nheap[] */
105 static struct pf_heap *pf_heap;
110 static coord pf_sx, pf_sy;
112 static natid pf_actor;
113 static double (*pf_sct_cost)(natid, int);
115 /* Is sector with uid UID open? */
119 return pf_map[uid].visit == pf_visit;
122 /* Is sector with uid UID closed? */
124 pf_is_closed(int uid)
127 * optimization: check > pf_visit instead of == pf_visit + 1
128 * works because pf_map[uid].visit <= pf_visit + 1
130 return pf_map[uid].visit > pf_visit;
133 /* Is sector with uid UID unvisited? */
135 pf_is_unvisited(int uid)
137 return pf_map[uid].visit < pf_visit;
140 #ifdef PATH_FIND_DEBUG
146 for (i = 0; i < pf_nheap; i++) {
147 uid = pf_heap[i].uid;
148 assert(0 <= uid && uid < WORLD_SZ());
149 assert(pf_map[uid].heapi == i);
150 assert(pf_map[uid].visit == pf_visit);
151 assert(pf_map[uid].cost <= pf_heap[i].cost);
153 assert(c >= pf_nheap || pf_heap[i].cost <= pf_heap[c].cost);
155 assert(c >= pf_nheap || pf_heap[i].cost <= pf_heap[c].cost);
158 for (uid = 0; uid < WORLD_SZ(); uid++) {
159 assert(pf_map[uid].visit <= pf_visit + 1);
160 if (pf_map[uid].visit == pf_visit) {
161 i = pf_map[uid].heapi;
162 assert(0 <= i && i < pf_nheap && pf_heap[i].uid == uid);
167 #define pf_check() ((void)0)
170 /* Swap pf_heap's I-th and J-th elements. */
172 pf_heap_swap(int i, int j)
176 assert(0 <= i && i < pf_nheap);
177 assert(0 <= j && j < pf_nheap);
179 pf_heap[i] = pf_heap[j];
181 pf_map[pf_heap[i].uid].heapi = i;
182 pf_map[pf_heap[j].uid].heapi = j;
185 /* Restore heap property after N-th element's cost increased. */
191 assert(0 <= n && n < pf_nheap);
192 for (r = n; (c = 2 * r + 1) < pf_nheap; r = c) {
193 if (c + 1 < pf_nheap && pf_heap[c].cost > pf_heap[c + 1].cost)
195 if (pf_heap[r].cost < pf_heap[c].cost)
201 /* Restore heap property after N-th element's cost decreased. */
207 assert(0 <= n && n < pf_nheap);
208 for (c = n; (p = (c - 1) / 2), c > 0; c = p) {
209 if (pf_heap[p].cost < pf_heap[c].cost)
216 * Open the unvisited sector X,Y.
217 * UID is sector uid, it equals XYOFFSET(X,Y).
218 * Cheapest path from source comes from direction DIR and has cost COST.
221 pf_open(int uid, coord x, coord y, int dir, double cost)
225 if (pf_is_open(uid)) {
226 i = pf_map[uid].heapi;
227 DPRINTF("pf: reopen %d,%d %g %c %d\n", x, y, cost, dirch[dir], i);
228 assert(cost < pf_map[uid].cost);
231 DPRINTF("pf: open %d,%d %g %c %d\n", x, y, cost, dirch[dir], i);
232 pf_map[uid].heapi = i;
233 pf_map[uid].visit = pf_visit;
234 pf_heap[i].uid = uid;
238 pf_map[uid].dir = dir;
239 pf_map[uid].cost = cost;
240 pf_heap[i].cost = cost;
247 * Close the sector at the top of the heap.
252 int uid = pf_heap[0].uid;
254 DPRINTF("pf: close %d,%d %d\n", pf_heap[0].x, pf_heap[0].y, pf_nheap);
255 assert(pf_is_open(uid));
257 pf_heap[0] = pf_heap[pf_nheap];
258 pf_map[pf_heap[0].uid].heapi = 0;
261 pf_map[uid].visit = pf_visit + 1;
266 x_in_dir(coord x, int dir)
270 assert(0 <= x && x < WORLD_X);
271 assert(0 <= dir && dir <= DIR_LAST);
272 xx = x + diroff[dir][0];
281 y_in_dir(coord y, int dir)
285 assert(0 <= y && y < WORLD_Y);
286 assert(0 <= dir && dir <= DIR_LAST);
287 yy = y + diroff[dir][1];
298 assert(DIR_FIRST <= dir && dir <= DIR_LAST);
299 return dir >= DIR_FIRST + 3 ? dir - 3 : dir + 3;
303 * Set the current source and cost function.
304 * SX,SY is the source.
305 * The cost to enter the sector with uid u is COST(ACTOR, u).
306 * Negative value means the sector can't be entered.
309 pf_set_source(coord sx, coord sy, natid actor, double (*cost)(natid, int))
311 DPRINTF("pf: source %d,%d\n", sx, sy);
314 pf_suid = XYOFFSET(sx, sy);
319 pf_map = calloc(WORLD_SZ(), sizeof(*pf_map));
320 pf_heap = malloc(WORLD_SZ() * sizeof(*pf_heap));
322 } else if ((unsigned short)(pf_visit + 3) < pf_visit) {
323 DPRINTF("pf: visit wrap-around\n");
324 memset(pf_map, 0, WORLD_SZ() * sizeof(*pf_map));
331 pf_open(pf_suid, pf_sx, pf_sy, DIR_STOP, 0.0);
335 * Find cheapest path from current source to DX,DY, return its cost.
338 path_find_to(coord dx, coord dy)
345 DPRINTF("pf: dest %d,%d\n", dx, dy);
346 duid = XYOFFSET(dx, dy);
347 if (pf_is_closed(duid)) {
348 DPRINTF("pf: done old %g\n", pf_map[duid].cost);
349 return pf_map[duid].cost;
352 while (pf_nheap > 0 && (uid = pf_heap[0].uid) != duid) {
355 cost = pf_heap[0].cost;
358 for (i = 0; i < 6; i++) { /* for all neighbors */
359 nx = x_in_dir(x, DIR_FIRST + i);
360 ny = y_in_dir(y, DIR_FIRST + i);
361 nuid = XYOFFSET(nx, ny);
362 c1 = pf_sct_cost(pf_actor, nuid);
365 if (pf_is_unvisited(nuid) || cost + c1 < pf_map[nuid].cost)
366 pf_open(nuid, nx, ny, DIR_FIRST + i, cost + c1);
370 DPRINTF("pf: done new %g\n", !pf_nheap ? -1.0 : pf_map[duid].cost);
373 return pf_map[duid].cost;
377 * Write route from SX,SY to DX,DY to BUF[BUFSIZ], return its length.
378 * If the route is longer than BUFSIZ-1 characters, it's truncated.
379 * You must compute path cost first, with path_find_to().
380 * SX,SY must be on a shortest path from the current source to DX,DY.
383 path_find_route(char *buf, size_t bufsz,
384 coord sx, coord sy, coord dx, coord dy)
390 suid = XYOFFSET(sx, sy);
391 assert(bufsz > 0 && !pf_is_unvisited(suid));
400 DPRINTF("pf: %d,%d %.*s%.*s\n",
402 (int)(bufsz - i), buf + i,
403 len >= bufsz ? (int)i : 0, buf);
404 uid = XYOFFSET(x, y);
405 assert(!pf_is_unvisited(uid));
407 if (d == DIR_STOP || uid == suid)
413 x = x_in_dir(x, rev_dir(d));
414 y = y_in_dir(y, rev_dir(d));
417 assert(x == sx && y == sy);
419 bufrotate(buf, bufsz, i);
421 assert(i + len < bufsz);
422 memmove(buf, buf + i, len + 1);
428 * Rotate BUF[BUFSZ] to put BUF[I] into BUF[0], and zero-terminate.
431 bufrotate(char *buf, size_t bufsz, size_t i)
437 n = MIN(i, sizeof(tmp));
439 memcpy(buf, buf + n, bufsz - n);
440 memcpy(buf + bufsz - n, tmp, n);
449 * Empire interface glue
453 cost_land(natid actor, int uid, int mobtype)
455 struct sctstr *sp = (void *)empfile[EF_SECTOR].cache;
457 if (sp[uid].sct_own != actor)
459 return sector_mcost(&sp[uid], mobtype);
463 cost_move(natid actor, int uid)
465 return cost_land(actor, uid, MOB_MOVE);
469 cost_march(natid actor, int uid)
471 return cost_land(actor, uid, MOB_MARCH);
475 cost_rail(natid actor, int uid)
477 return cost_land(actor, uid, MOB_RAIL);
480 static double (*cost_tab[])(natid, int) = {
481 cost_move, cost_march, cost_rail
485 * Start finding paths from SX,SY.
486 * Use mobility costs for ACTOR and MOBTYPE.
489 path_find_from(coord sx, coord sy, natid actor, int mobtype)
491 pf_set_source(sx, sy, actor, cost_tab[mobtype]);
495 * Find cheapest path from SX,SY to DX,DY, return its mobility cost.
496 * Use mobility costs for ACTOR and MOBTYPE.
499 path_find(coord sx, coord sy, coord dx, coord dy, natid actor, int mobtype)
501 pf_set_source(sx, sy, actor, cost_tab[mobtype]);
502 return path_find_to(dx, dy);