/*
* Dijkstra's algorithm. Refer to your graph algorithm textbook for
* how it works. Implementation is specialized to hex maps.
+ *
+ * Define PATH_FIND_STATS for performance statistics on stdout.
*/
/*
static natid pf_actor;
static double (*pf_sct_cost)(natid, int);
+/*
+ * Performance statistics
+ */
+#ifdef PATH_FIND_STATS
+static unsigned pf_nsearch, pf_nsource, pf_nopen, pf_nclose;
+static unsigned pf_nheap_max, pf_noway;
+static double pf_sumcost;
+#define STAT_INC(v) ((void)((v)++))
+#define STAT_INCBY(v, i) ((void)((v) += i))
+#define STAT_HIMARK(v, h) ((void)((v) < (h) ? (v) = (h) : (h)))
+#else /* !PATH_FIND_STATS */
+#define STAT_INC(v) ((void)0)
+#define STAT_INCBY(v, i) ((void)0)
+#define STAT_HIMARK(v, h) ((void)0)
+#endif /* !PATH_FIND_STATS */
+
+#ifndef NDEBUG /* silence "not used" warning */
/* Is sector with uid UID open? */
static int
pf_is_open(int uid)
{
return pf_map[uid].visit == pf_visit;
}
+#endif
/* Is sector with uid UID closed? */
static int
{
int i;
- if (pf_is_open(uid)) {
- i = pf_map[uid].heapi;
- DPRINTF("pf: reopen %d,%d %g %c %d\n", x, y, cost, dirch[dir], i);
- assert(cost < pf_map[uid].cost);
- } else {
- i = pf_nheap++;
- DPRINTF("pf: open %d,%d %g %c %d\n", x, y, cost, dirch[dir], i);
- pf_map[uid].heapi = i;
- pf_map[uid].visit = pf_visit;
- pf_heap[i].uid = uid;
- pf_heap[i].x = x;
- pf_heap[i].y = y;
- }
+ STAT_INC(pf_nopen);
+ i = pf_nheap++;
+ STAT_HIMARK(pf_nheap_max, (unsigned)pf_nheap);
+ DPRINTF("pf: open %d,%d %g %c %d\n", x, y, cost, dirch[dir], i);
+ assert(pf_is_unvisited(uid));
+ pf_map[uid].visit = pf_visit;
pf_map[uid].dir = dir;
+ pf_map[uid].heapi = i;
pf_map[uid].cost = cost;
+ pf_heap[i].uid = uid;
+ pf_heap[i].x = x;
+ pf_heap[i].y = y;
pf_heap[i].cost = cost;
pf_sift_up(i);
{
int uid = pf_heap[0].uid;
+ STAT_INC(pf_nclose);
DPRINTF("pf: close %d,%d %d\n", pf_heap[0].x, pf_heap[0].y, pf_nheap);
assert(pf_is_open(uid));
if (--pf_nheap) {
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)
{
static void
pf_set_source(coord sx, coord sy, natid actor, double (*cost)(natid, int))
{
+ STAT_INC(pf_nsource);
DPRINTF("pf: source %d,%d\n", sx, sy);
pf_sx = sx;
pf_sy = sy;
double cost, c1;
coord x, y, nx, ny;
+ STAT_INC(pf_nsearch);
DPRINTF("pf: dest %d,%d\n", dx, dy);
duid = XYOFFSET(dx, dy);
if (pf_is_closed(duid)) {
DPRINTF("pf: done old %g\n", pf_map[duid].cost);
+ STAT_INCBY(pf_sumcost, pf_map[duid].cost);
return pf_map[duid].cost;
}
nx = x_in_dir(x, DIR_FIRST + i);
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.
+ */
+ if (!pf_is_unvisited(nuid))
+ continue;
c1 = pf_sct_cost(pf_actor, nuid);
if (c1 < 0)
continue;
- if (pf_is_unvisited(nuid) || cost + c1 < pf_map[nuid].cost)
- pf_open(nuid, nx, ny, DIR_FIRST + i, cost + c1);
+ pf_open(nuid, nx, ny, DIR_FIRST + i, cost + c1);
}
}
DPRINTF("pf: done new %g\n", !pf_nheap ? -1.0 : pf_map[duid].cost);
- if (!pf_nheap)
+ if (!pf_nheap) {
+ STAT_INC(pf_noway);
return -1.0;
+ }
+ STAT_INCBY(pf_sumcost, pf_map[duid].cost);
return pf_map[duid].cost;
}
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)
+{
+ printf("pathfind %u searches, %u sources, %u opened, %u closed,"
+ " %u heap max, %zu bytes, %u noway, %g avg cost\n",
+ pf_nsearch, pf_nsource, pf_nopen, pf_nclose,
+ pf_nheap_max,
+ (WORLD_SZ() * (sizeof(*pf_map) + sizeof(*pf_heap))),
+ pf_noway, pf_nsearch ? pf_sumcost / pf_nsearch : 0.0);
+}
+#endif
/*
* Empire interface glue
projects / empserver / blobdiff