Update copyright notice

[empserver] / src / lib / common / pathfind.c

diff --git a/src/lib/common/pathfind.c b/src/lib/common/pathfind.c
index a7f9636182f8779a39e7e3aeaa17a66e4ae7ac7a..2856952c928081c9d1e07ada2ec0216197b881d2 100644 (file)
--- a/src/lib/common/pathfind.c
+++ b/src/lib/common/pathfind.c
@@ -1,6 +1,6 @@
 /*
  *  Empire - A multi-player, client/server Internet based war game.
- *  Copyright (C) 1986-2011, Dave Pare, Jeff Bailey, Thomas Ruschak,
+ *  Copyright (C) 1986-2015, Dave Pare, Jeff Bailey, Thomas Ruschak,
  *                Ken Stevens, Steve McClure, Markus Armbruster
  *
  *  Empire is free software: you can redistribute it and/or modify
@@ -27,7 +27,7 @@
  *  pathfind.c: Find cheapest paths
  *
  *  Known contributors to this file:
- *     Markus Armbruster, 2011
+ *     Markus Armbruster, 2014
  */
 
 #include <config.h>
@@ -37,6 +37,7 @@
 #include <stdlib.h>
 #include <string.h>
 #include "file.h"
+#include "nat.h"
 #include "optlist.h"
 #include "path.h"
 #include "sect.h"
@@ -280,6 +281,20 @@ pf_close(void)
     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)
 {
@@ -310,13 +325,6 @@ y_in_dir(coord y, 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.
@@ -356,8 +364,7 @@ pf_set_source(coord sx, coord sy, natid actor, double (*cost)(natid, int))
 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;
 
@@ -370,7 +377,7 @@ path_find_to(coord dx, coord dy)
        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;
@@ -442,8 +449,9 @@ 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);
@@ -476,6 +484,66 @@ 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)
@@ -497,7 +565,7 @@ static double
 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;
 
@@ -524,8 +592,43 @@ cost_rail(natid actor, int uid)
     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
 };
 
 /*