/*
* Empire - A multi-player, client/server Internet based war game.
- * Copyright (C) 1986-2011, Dave Pare, Jeff Bailey, Thomas Ruschak,
+ * Copyright (C) 1986-2021, Dave Pare, Jeff Bailey, Thomas Ruschak,
* Ken Stevens, Steve McClure, Markus Armbruster
*
* Empire is free software: you can redistribute it and/or modify
* pathfind.c: Find cheapest paths
*
* Known contributors to this file:
- * Markus Armbruster, 2011
+ * Markus Armbruster, 2014-2020
*/
#include <config.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
-#include "file.h"
+#include "nat.h"
#include "optlist.h"
#include "path.h"
#include "sect.h"
#ifdef PATH_FIND_DEBUG
-#define DPRINTF(fmt, ...) ((void)printf(fmt , ## __VA_ARGS__))
+#define DPRINTF(...) ((void)fprintf(stdout, ## __VA_ARGS__))
#else
-#define DPRINTF(fmt, ...) ((void)0)
+#define DPRINTF(...) ((void)0)
#endif
static char *bufrotate(char *buf, size_t bufsz, size_t i);
*/
/*
- * Array of sector data, indexed by sector uid
+ * Array of sector data, indexed by sector UID
*
* We need to store a few values per sector visited by the path
* search. An array is the stupidest data structure that could
*/
struct pf_heap {
- int uid; /* sector uid and */
- coord x, y; /* coordinates, uid == XYOFFSET(x, y) */
+ int uid; /* sector UID and ... */
+ coord x, y; /* coordinates, @uid == XYOFFSET(@x, @y) */
double cost; /* cost from source */
};
#endif /* !PATH_FIND_STATS */
#ifndef NDEBUG /* silence "not used" warning */
-/* Is sector with uid UID open? */
+/* Is sector with UID @uid open? */
static int
pf_is_open(int uid)
{
}
#endif
-/* Is sector with uid UID closed? */
+/* Is sector with UID @uid closed? */
static int
pf_is_closed(int uid)
{
return pf_map[uid].visit > pf_visit;
}
-/* Is sector with uid UID unvisited? */
+/* Is sector with UID @uid unvisited? */
static int
pf_is_unvisited(int uid)
{
#define pf_check() ((void)0)
#endif
-/* Swap pf_heap's I-th and J-th elements. */
+/* Swap pf_heap's @i-th and @j-th elements. */
static void
pf_heap_swap(int i, int j)
{
pf_map[pf_heap[j].uid].heapi = j;
}
-/* Restore heap property after N-th element's cost increased. */
+/* Restore heap property after @n-th element's cost increased. */
static void
pf_sift_down(int n)
{
}
}
-/* Restore heap property after N-th element's cost decreased. */
+/* Restore heap property after @n-th element's cost decreased. */
static void
pf_sift_up(int n)
{
}
/*
- * Open the unvisited sector X,Y.
- * UID is sector uid, it equals XYOFFSET(X,Y).
- * Cheapest path from source comes from direction DIR and has cost COST.
+ * Open the unvisited sector @x,@y.
+ * @uid is sector UID, it equals XYOFFSET(@x,@y).
+ * Cheapest path from source comes from direction @dir and has cost @cost.
*/
static void
pf_open(int uid, coord x, coord y, int dir, double cost)
pf_check();
}
+/* silence "not used" warning */
+#ifdef PATH_FIND_DEBUG
+/*
+ * Return cost from source to sector with UID @uid.
+ * It must be visited, i.e. open or closed.
+ */
+static double
+pf_cost(int uid)
+{
+ assert(!pf_is_unvisited(uid));
+ return pf_map[uid].cost;
+}
+#endif
+
static coord
x_in_dir(coord x, int dir)
{
return yy;
}
-static int
-rev_dir(int dir)
-{
- assert(DIR_FIRST <= dir && dir <= DIR_LAST);
- return dir >= DIR_FIRST + 3 ? dir - 3 : dir + 3;
-}
-
/*
* Set the current source and cost function.
- * SX,SY is the source.
- * The cost to enter the sector with uid u is COST(ACTOR, u).
+ * @sx,@sy is the source.
+ * The cost to enter the sector with UID ID is @cost(@actor, ID).
* Negative value means the sector can't be entered.
*/
static void
}
/*
- * Find cheapest path from current source to DX,DY, return its cost.
+ * Find cheapest path from current source to @dx,@dy, return its cost.
*/
double
path_find_to(coord dx, coord dy)
{
- int duid;
- int uid, nuid, i;
+ int duid, nuid, i;
double cost, c1;
coord x, y, nx, ny;
return pf_map[duid].cost;
}
- while (pf_nheap > 0 && (uid = pf_heap[0].uid) != duid) {
+ while (pf_nheap > 0 && pf_heap[0].uid != duid) {
x = pf_heap[0].x;
y = pf_heap[0].y;
cost = pf_heap[0].cost;
ny = y_in_dir(y, DIR_FIRST + i);
nuid = XYOFFSET(nx, ny);
/*
- * Cost to enter NX,NY doesn't depend on direction of
- * entry. This X,Y is at least as expensive as any
- * previous one. Therefore, cost to go to NX,NY via X,Y
- * is at least as high as any previously found route.
- * Skip neighbors that have a route already.
+ * Cost to enter @nx,@ny doesn't depend on direction of
+ * entry. This @x,@y is at least as expensive as any
+ * previous one. Therefore, cost to go to @nx,@ny via
+ * @x,@y is at least as high as any previously found
+ * route. Skip neighbors that have a route already.
*/
if (!pf_is_unvisited(nuid))
continue;
}
/*
- * Write route from SX,SY to DX,DY to BUF[BUFSIZ], return its length.
- * If the route is longer than BUFSIZ-1 characters, it's truncated.
+ * Write route from @sx,@sy to @dx,@dy to array @buf[@bufsiz].
+ * If the route is longer than @bufsiz-1 characters, it's truncated.
* You must compute path cost first, with path_find_to().
- * SX,SY must be on a shortest path from the current source to DX,DY.
+ * @sx,@sy must be on a shortest path from the current source to @dx,@dy.
+ * Return length of the (untruncated) route.
*/
size_t
path_find_route(char *buf, size_t bufsz,
i = bufsz;
buf[--i] = dirch[d];
len++;
- x = x_in_dir(x, rev_dir(d));
- y = y_in_dir(y, rev_dir(d));
+ assert(DIR_FIRST <= d && d <= DIR_LAST);
+ x = x_in_dir(x, DIR_BACK(d));
+ y = y_in_dir(y, DIR_BACK(d));
}
assert(x == sx && y == sy);
}
/*
- * Rotate BUF[BUFSZ] to put BUF[I] into BUF[0], and zero-terminate.
+ * Rotate @buf[@bufsz] to put @buf[@i] into @buf[0], and zero-terminate.
*/
static char *
bufrotate(char *buf, size_t bufsz, size_t i)
return buf;
}
+#ifdef PATH_FIND_DEBUG
+void
+path_find_visualize(coord sx, coord sy, coord dx, coord dy)
+{
+ int uid;
+ int xmin, xmax, ymin, ymax, x, y, odd, ch;
+ double c, u, cost;
+ char buf[1024];
+
+ assert(pf_cost(XYOFFSET(sx, sy)) == 0.0);
+ c = pf_cost(XYOFFSET(dx, dy));
+ u = c / 10.0;
+
+ /* find bounding box */
+ xmin = xmax = 0;
+ ymin = ymax = 0;
+ for (y = -WORLD_Y / 2; y < WORLD_Y / 2; y++) {
+ odd = ((sx + -WORLD_X / 2) ^ (sy + y)) & 1;
+ for (x = -WORLD_X / 2 + odd; x < WORLD_X / 2; x += 2) {
+ uid = XYOFFSET(XNORM(sx + x), YNORM(sy + y));
+ if (pf_is_unvisited(uid))
+ continue;
+ if (xmin > x)
+ xmin = x;
+ if (xmax < x)
+ xmax = x;
+ if (ymin > y)
+ ymin = y;
+ if (ymax < y)
+ ymax = y;
+ }
+ }
+ printf("bbox %d:%d,%d:%d origin %d,%d\n",
+ xmin, xmax, ymin, ymax, sx, sy);
+
+ for (y = ymin; y <= ymax; y++) {
+ odd = ((sx + xmin) ^ (sy + y)) & 1;
+ if (odd)
+ printf(" ");
+ for (x = xmin + odd; x <= xmax; x += 2) {
+ uid = XYOFFSET(XNORM(sx + x), YNORM(sy + y));
+ if (pf_is_unvisited(uid))
+ ch = ' ';
+ else if (uid == XYOFFSET(dx, dy))
+ ch = 'D';
+ else if (uid == XYOFFSET(sx, sy))
+ ch = 'S';
+ else {
+ cost = pf_cost(uid);
+ ch = cost > c ? '+' : '0' + (int)(10 * (cost / c));
+ }
+ printf(" %c", ch);
+ }
+ printf("\n");
+ }
+ path_find_route(buf, sizeof(buf), sx, sy, dx, dy);
+ printf("%s %g\n", buf, pf_cost(XYOFFSET(dx, dy)));
+}
+#endif
+
#ifdef PATH_FIND_STATS
void
path_find_print_stats(void)
cost_land(natid actor, int uid, int mobtype)
{
/*
- * Non-negative cost must not depend on ACTOR, see BestLandPath().
+ * Non-negative cost must not depend on @actor, see unit_path().
*/
struct sctstr *sp = (void *)empfile[EF_SECTOR].cache;
return cost_land(actor, uid, MOB_RAIL);
}
+static double
+cost_sail(natid actor, int uid)
+{
+ struct sctstr *sp = (void *)empfile[EF_SECTOR].cache;
+ natid sctown = sp[uid].sct_own;
+ char *bmap;
+
+ if (sctown && relations_with(sctown, actor) == ALLIED) {
+ /* FIXME duplicates shp_check_nav() logic */
+ switch (dchr[sp[uid].sct_type].d_nav) {
+ case NAVOK:
+ return 1.0;
+ case NAV_CANAL:
+ /* FIXME return 1.0 when all ships have M_CANAL */
+ return -1.0;
+ case NAV_02:
+ return sp[uid].sct_effic >= 2 ? 1.0 : -1.0;
+ case NAV_60:
+ return sp[uid].sct_effic >= 60 ? 1.0 : -1.0;
+ default:
+ return -1.0;
+ }
+ }
+
+ bmap = ef_ptr(EF_BMAP, actor);
+ return bmap[uid] == '.' || bmap[uid] == ' ' || bmap[uid] == 0
+ ? 1.0 : -1.0;
+}
+
+static double
+cost_fly(natid actor, int uid)
+{
+ return 1.0;
+}
+
static double (*cost_tab[])(natid, int) = {
- cost_move, cost_march, cost_rail
+ cost_move, cost_march, cost_rail, cost_sail, cost_fly
};
/*
- * Start finding paths from SX,SY.
- * Use mobility costs for ACTOR and MOBTYPE.
+ * Start finding paths from @sx,@sy.
+ * Use mobility costs for @actor and @mobtype.
*/
void
path_find_from(coord sx, coord sy, natid actor, int mobtype)
}
/*
- * Find cheapest path from SX,SY to DX,DY, return its mobility cost.
- * Use mobility costs for ACTOR and MOBTYPE.
+ * Find cheapest path from @sx,@sy to @dx,@dy, return its mobility cost.
+ * Use mobility costs for @actor and @mobtype.
*/
double
path_find(coord sx, coord sy, coord dx, coord dy, natid actor, int mobtype)
projects / empserver / blobdiff