[Freeciv-Dev] Re: (PR#4038) Multiple starting points for PF

["Gregory Berkolaiko" <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Tue, 22 Apr 2003, Raimar Falke wrote:

> On Sun, Apr 20, 2003 at 06:35:43AM -0700, Gregory Berkolaiko wrote:
> > +/* Adds (possibly another) starting position to the map.  The path-finding
> > + * will try to find a path to each position from its _nearest_ starting 
> > + * position. */
> > +void pf_add_start_pos(struct pf_map *map, int x, int y, int cost, int 
> > extra);
> 
> Hmmmm We should either add all starting positions to the parameter
> struct as an array or remove the starting position from the
> parameter. The solution of your patch is an special casting which I
> think is unclean.

But I want to have a possibility of adding more starting positions while 
pf-iteration is running.  The idea behind it is this:
suppose you are on a boat near continent 1 and want to find a way to the 
city inland.  To do it you first find the way to all the beaches by boat, 
then put these beaches into a next map as starting positions and then 
iterate the second map to find the second segment of your path.

But if you are quite close to your destination already, you don't want to 
find the paths to _all_ the beaches first.  You want to start the second 
iteration as soon as possible, so you can break it early!  So the second 
iteration should already be running while the first is finding paths to 
beaches further and further away...

Anyway, nonwithstanding this, here is a patch which changes the status of 
a tile from enum to a bit-vector.  It also introduces new flag S_START to 
denote a start position but there is no possibility of multiple starts 
yet.

I want to commit it fairly soon so I can move on to multiple positions 
proper.

G.

Index: common/aicore/path_finding.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/aicore/path_finding.c,v
retrieving revision 1.9
diff -u -r1.9 path_finding.c
--- common/aicore/path_finding.c        2003/05/03 13:28:48     1.9
+++ common/aicore/path_finding.c        2003/05/03 13:30:39
@@ -83,15 +83,15 @@
                                 * need to remeber costs and stuff */
 };
 
-enum pf_node_status {
-  NS_UNINIT = 0,               /* memory is calloced, hence zero 
-                                * means uninitialised */
-  NS_NEW,                      /* the optimal route isn't found yet */
-  NS_WAITING,                  /* the optimal route is found,
-                                * considering waiting */
-  NS_PROCESSED                 /* the optimal route is found */
+enum status_bits {
+  S_INIT = 0,                  /* is tile initialised */
+  S_START,                      /* is it a starting position */ 
+  S_PROCESSED,                 /* is the optimal route found */
+  S_WAITING,                   /* are we waiting here */
+  S_LAST
 };
 
+BV_DEFINE(node_status_t, S_LAST);
 
 /*
  * The map structure itself.  (x, y) is the current position of the iteration
@@ -102,11 +102,9 @@
   mapindex_t index;            /* Current offset into lattice */
   struct pf_parameter *params;  /* Initial parameters */
   struct pqueue *queue;         /* Queue of nodes we have reached but not 
-                                 * processed yet (NS_NEW), sorted by their 
-                                 * total_CC*/
+                                 * processed yet, sorted by their total_CC*/
   struct pf_node *lattice;      /* Lattice of nodes */
-  utiny_t *status;             /* Array of node statuses 
-                                * (enum pf_node_status really) */
+  node_status_t *status;       /* Array of node statuses */
   struct pqueue *danger_queue; /* Dangerous positions go there */
   struct danger_node *d_lattice;       /* Lattice with danger stuff */
 };
@@ -249,8 +247,6 @@
     return danger_iterate_map(pf_map);
   }
 
-  pf_map->status[pf_map->index] = NS_PROCESSED;
-
   /* There is no exit from DONT_LEAVE tiles! */
   if (node->behavior != TB_DONT_LEAVE) {
 
@@ -260,16 +256,18 @@
     adjc_dir_iterate(pf_map->x, pf_map->y, x1, y1, dir) {
       mapindex_t index1 = map_pos_to_index(x1, y1);
       struct pf_node *node1 = &pf_map->lattice[index1];
-      utiny_t *status = &pf_map->status[index1];
+      node_status_t *status = &pf_map->status[index1];
       int cost;
       int extra = 0;
 
-      if (*status == NS_PROCESSED) {
+      if (BV_ISSET(*status, S_PROCESSED)) {
        /* This gives 15% speedup */
        continue;
       }
 
-      if (*status == NS_UNINIT) {
+      if (!BV_ISSET(*status, S_INIT)) {
+        /* NB: We don't set S_INIT in init_node so we can set it later
+         * when updating costs */
        init_node(pf_map, node1, x1, y1);
       }
 
@@ -313,10 +311,10 @@
       {
        int cost_of_path = get_total_CC(pf_map, cost, extra);
 
-       if (*status == NS_UNINIT
+       if (!BV_ISSET(*status, S_INIT)
            || cost_of_path < get_total_CC(pf_map, node1->cost,
                                           node1->extra_cost)) {
-         *status = NS_NEW;
+         BV_SET(*status, S_INIT);
          node1->extra_cost = extra;
          node1->cost = cost;
          node1->dir_to_here = dir;
@@ -335,14 +333,15 @@
     if (!removed) {
       return FALSE;
     }
-    if (pf_map->status[index] == NS_NEW) {
-      /* Discard if this node has already been processed */
+    if (!BV_ISSET(pf_map->status[index], S_PROCESSED)) {
       break;
     }
+    /* Discard if this node has already been processed */
   }
 
   pf_map->index = index;
   index_to_map_pos(&(pf_map->x), &(pf_map->y), index);
+  BV_SET(pf_map->status[pf_map->index], S_PROCESSED);
 
   return TRUE;
 }
@@ -391,6 +390,13 @@
   /* Initialise starting node */
   init_node(pf_map, &pf_map->lattice[pf_map->index], pf_map->x,
             pf_map->y);
+  /* The path to the starting node we know! */
+  BV_SET(pf_map->status[pf_map->index], S_PROCESSED);
+  /* And it is the starting node alright */
+  BV_SET(pf_map->status[pf_map->index], S_START);
+  /* And we just initialised it */
+  BV_SET(pf_map->status[pf_map->index], S_INIT);
+
   /* This makes calculations of turn/moves_left more convenient, but we 
    * need to subtract this value before we return cost to the user */
   pf_map->lattice[pf_map->index].cost = pf_map->params->move_rate
@@ -451,8 +457,7 @@
   struct pf_node *node = &pf_map->lattice[index];
 
   /* Debug period only!  Please remove after PF is settled */
-  if (pf_map->status[index] != NS_PROCESSED
-      && !same_pos(x, y, pf_map->x, pf_map->y)) {
+  if (!BV_ISSET(pf_map->status[index], S_PROCESSED)) {
     die("pf_construct_path to an unreached destination");
     return;
   }
@@ -498,9 +503,9 @@
                     struct pf_position *pos)
 {
   mapindex_t index = map_pos_to_index(x, y);
-  utiny_t status = pf_map->status[index];
+  node_status_t status = pf_map->status[index];
 
-  if (status == NS_PROCESSED || same_pos(x, y, pf_map->x, pf_map->y)) {
+  if (BV_ISSET(status, S_PROCESSED)) {
     /* We already reached (x,y) */
     fill_position(pf_map, x, y, pos);
     return TRUE;
@@ -526,14 +531,13 @@
 {
   int i;
   int x, y;
-  int index = map_pos_to_index(dest_x, dest_y);
+  mapindex_t index = map_pos_to_index(dest_x, dest_y);
   enum direction8 dir_next;
   struct pf_path *path;
 
   /* Debug period only!  Please remove after PF is settled */
   assert(!pf_map->params->is_pos_dangerous);
-  if (pf_map->status[index] != NS_PROCESSED
-      && !same_pos(dest_x, dest_y, pf_map->x, pf_map->y)) {
+  if (!BV_ISSET(pf_map->status[index], S_PROCESSED)) {
     die("construct_path to an unreached destination");
     return NULL;
   }
@@ -545,9 +549,10 @@
   /* 1: Count the number of steps to get here.
    * To do it, backtrack until we hit the starting point */
   for (i = 0; ; i++) {
+    node_status_t status = pf_map->status[map_pos_to_index(x, y)];
     struct pf_node *node = &pf_map->lattice[map_pos_to_index(x, y)];
 
-    if (same_pos(x, y, pf_map->params->start_x, pf_map->params->start_y)) {
+    if (BV_ISSET(status, S_START)) {
       /* Ah-ha, reached the starting point! */
       break;
     }
@@ -607,14 +612,14 @@
 struct pf_path *pf_get_path(struct pf_map *pf_map, int x, int y)
 {
   mapindex_t index = map_pos_to_index(x, y);
-  utiny_t status = pf_map->status[index];
+  node_status_t status = pf_map->status[index];
 
   if (pf_map->params->is_pos_dangerous) {
     /* It's very different in the presence of danger */
     return danger_get_path(pf_map, x, y);
   }
 
-  if (status == NS_PROCESSED || same_pos(x, y, pf_map->x, pf_map->y)) {
+  if (BV_ISSET(status, S_PROCESSED)) {
     /* We already reached (x,y) */
     return construct_path(pf_map, x, y);
   }
@@ -776,11 +781,11 @@
   sooner than P, because there might be several copies of it in 
   the queue already.  But that does not seem to present any 
   problems.
-  3. For some purposes, NS_WAITING is just another flavour of NS_PROCESSED,
-  since the path to a NS_WAITING tile has already been found.
+  3. S_WAITING still have S_PROCESSED set, since the path to a S_WAITING 
+  tile has already been found.
   4. The code is arranged so that if the turn-mode is TM_WORST_TIME, a 
   cavalry with non-full MP will get to a safe mountain tile only after 
-  waiting.  This waiting, although realised through NS_WAITING, is 
+  waiting.  This waiting, although realised through S_WAITING, is 
   different from waiting before going into the danger area, so it will not 
   be marked as "waiting" on the resulting paths.
   5. This algorithm cannot guarantee the best safe segments across 
@@ -797,15 +802,14 @@
 
   /* There is no exit from DONT_LEAVE tiles! */
   if (node->behavior != TB_DONT_LEAVE) {
+    /* Did we wait at this node? */
+    bool waited = BV_ISSET(pf_map->status[pf_map->index], S_WAITING);
     /* Cost at xy but taking into account waiting */
-    int loc_cost
-       = (pf_map->status[pf_map->index] != NS_WAITING ? node->cost
-          : node->cost + get_moves_left(pf_map, node->cost));
+    int loc_cost = (waited ? node->cost + get_moves_left(pf_map, node->cost)
+                    : node->cost);
     /* Step number at xy taking into account waiting 
      * (waiting counts as one step) */
-    int loc_step
-        = (pf_map->status[pf_map->index] != NS_WAITING ? d_node->step
-           : d_node->step + 1);
+    int loc_step = (waited ? d_node->step + 1 : d_node->step);
 
     /* The previous position is contained in {x,y} fields of map */
     adjc_dir_iterate(pf_map->x, pf_map->y, x1, y1, dir) {
@@ -816,14 +820,13 @@
       int extra = 0;
 
       /* Dangerous tiles can be updated even after being processed */
-      if ((pf_map->status[index1] == NS_PROCESSED 
-           || pf_map->status[index1] == NS_WAITING) 
+      if (BV_ISSET(pf_map->status[index1], S_PROCESSED)
           && !d_node1->is_dangerous) {
        continue;
       }
 
       /* Initialise target tile if necessary */
-      if (pf_map->status[index1] == NS_UNINIT) {
+      if (!BV_ISSET(pf_map->status[index1], S_INIT)) {
        init_node(pf_map, node1, x1, y1);
        init_danger_node(pf_map, d_node1, node1, x1, y1);
       }
@@ -866,7 +869,7 @@
       if (!d_node1->is_dangerous) {
        int cost_of_path = get_total_CC(pf_map, cost, extra);
 
-       if (pf_map->status[index1] == NS_UNINIT
+       if (!BV_ISSET(pf_map->status[index1], S_INIT)
            || (cost_of_path
                < get_total_CC(pf_map, node1->cost, node1->extra_cost))) {
          node1->extra_cost = extra;
@@ -887,7 +890,7 @@
              * "real" waiting */
            d_node1->waited = FALSE;
          }
-         pf_map->status[index1] = NS_NEW;
+         BV_SET(pf_map->status[index1], S_INIT);
          pq_insert(pf_map->queue, index1, -cost_of_path);
        }
       } else {
@@ -897,12 +900,12 @@
         * 2: we can possibly go further across dangerous area or
         * 3: we can have lower extra and will not 
         *    overwrite anything useful */
-       if (pf_map->status[index1] == NS_UNINIT
+       if (!BV_ISSET(pf_map->status[index1], S_INIT)
            || (get_moves_left(pf_map, cost)
                > get_moves_left(pf_map, node1->cost))
            || (get_total_CC(pf_map, cost, extra)
                < get_total_CC(pf_map, node1->cost, node1->extra_cost)
-               && pf_map->status[index1] == NS_PROCESSED)) {
+               && BV_ISSET(pf_map->status[index1], S_PROCESSED))) {
          node1->extra_cost = extra;
          node1->cost = cost;
          node1->dir_to_here = dir;
@@ -914,8 +917,10 @@
             /* We just moved into the danger area */
             d_node1->segment_length = 1;
           }
-         pf_map->status[index1] = NS_NEW;
-         d_node1->waited = (pf_map->status[pf_map->index] == NS_WAITING);
+          /* If PROCESSED was set it needs to be cleared */
+          BV_CLR(pf_map->status[index1], S_PROCESSED);
+         BV_SET(pf_map->status[index1], S_INIT);
+         d_node1->waited = waited;
          /* Extra costs of all nodes in danger_queue are equal! */
          pq_insert(pf_map->danger_queue, index1, -cost);
        }
@@ -924,17 +929,16 @@
     adjc_dir_iterate_end;
   }
 
-  if (!d_node->is_dangerous && pf_map->status[pf_map->index] != NS_WAITING
-      && (get_moves_left(pf_map, node->cost)
-         < pf_map->params->move_rate)) {
-    /* Consider waiting at this node. 
-     * To do it, put it back into queue. */
-    pf_map->status[pf_map->index] = NS_WAITING;
+  if (!d_node->is_dangerous 
+      && !BV_ISSET(pf_map->status[pf_map->index], S_WAITING)
+      && get_moves_left(pf_map, node->cost) < pf_map->params->move_rate) {
+    /* Consider waiting at this node.  To do it, put it back into queue. */
+    BV_SET(pf_map->status[pf_map->index], S_WAITING);
     pq_insert(pf_map->queue, pf_map->index,
              -get_total_CC(pf_map, get_moves_left(pf_map, node->cost)
                            + node->cost, node->extra_cost));
   } else {
-    pf_map->status[pf_map->index] = NS_PROCESSED;
+    BV_CLR(pf_map->status[pf_map->index], S_WAITING);
   }
 
   /* Get the next nearest node */
@@ -944,17 +948,20 @@
     /* No dangerous nodes to process, go for a safe one */
     do {
       if (!pq_remove(pf_map->queue, &index)) {
+        /* All queues are empty, the map is finished */
        return FALSE;
       }
-    } while (pf_map->status[index] == NS_PROCESSED);
+    } while (BV_ISSET(pf_map->status[index], S_PROCESSED) &&
+             !BV_ISSET(pf_map->status[index], S_WAITING));
   }
 
-  assert(pf_map->status[pf_map->index] != NS_UNINIT);
+  assert(BV_ISSET(pf_map->status[pf_map->index], S_INIT));
+  BV_SET(pf_map->status[pf_map->index], S_PROCESSED);
 
   pf_map->index = index;
   index_to_map_pos(&(pf_map->x), &(pf_map->y), index);
 
-  if (pf_map->status[pf_map->index] == NS_WAITING) {
+  if (BV_ISSET(pf_map->status[pf_map->index], S_WAITING)) {
     /* We've already returned this node once, skip it */
     freelog(LOG_DEBUG, "Considering waiting at (%d, %d)", pf_map->x,
            pf_map->y);
@@ -1033,7 +1040,7 @@
       assert(danger_seg);
       path->positions[i].total_MC = danger_seg[segment_index].cost;
       path->positions[i].total_EC = danger_seg[segment_index].extra_cost;
-    } 
+    }
     path->positions[i].turn = get_turn(pf_map, path->positions[i].total_MC);
     path->positions[i].moves_left 
       = get_moves_left(pf_map, path->positions[i].total_MC);
@@ -1044,7 +1051,7 @@
     /* 3: Check if we finished */
     if (i == 0) {
       /* We should be back at the start now! */
-      assert(same_pos(x, y, pf_map->params->start_x, pf_map->params->start_y));
+      assert(BV_ISSET(pf_map->status[map_pos_to_index(x, y)], S_START));
       return path;
     }
 
@@ -1083,7 +1090,7 @@
 static struct pf_path *danger_get_path(struct pf_map *pf_map, int x, int y)
 {
   mapindex_t index = map_pos_to_index(x, y);
-  utiny_t status = pf_map->status[index];
+  node_status_t status = pf_map->status[index];
   struct danger_node *d_node = &pf_map->d_lattice[index];
 
   if (d_node->is_dangerous) {
@@ -1092,8 +1099,7 @@
     return NULL;
   }
 
-  if (status == NS_PROCESSED || status == NS_WAITING 
-      || same_pos(x, y, pf_map->x, pf_map->y)) {
+  if (BV_ISSET(status, S_PROCESSED)) {
     /* We already reached (x,y) */
     return danger_construct_path(pf_map, x, y);
   }