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

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

Attached is a patch which provides the possibility of having multiple starting
points in the path-finding.  It is very useful for "advanced" path-finding like
units on transports finding a path to an inland city.

I haven't tested the new feature but for a single starting point it works as
normal, at least with no danger handling.

The implementation is a bit awkward, I would say.  Probably need to convert the
status into collection of flags: "initialized", "start", "processed", "waiting".
More thought should be given to it though.

I also discovered buglets in the PF-with-danger code.  Integration of PF into
client would provide a perfect testing interface, I really count on Raimar here.

Best wishes,
G.

Index: common/aicore/path_finding.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/aicore/path_finding.c,v
retrieving revision 1.3
diff -u -r1.3 path_finding.c
--- common/aicore/path_finding.c        2003/04/19 17:55:36     1.3
+++ common/aicore/path_finding.c        2003/04/20 13:00:50
@@ -83,13 +83,21 @@
                                 * need to remeber costs and stuff */
 };
 
+/* Note: If a tile is a start it doesn't mean that the shortest path to it
+ * is already found: a path from another start can be shorter. This 
+ * complicates things somewhat, making NS_PROCESSED_START necessary */
 enum pf_node_status {
   NS_UNINIT = 0,               /* memory is calloced, hence zero 
                                 * means uninitialised */
+  NS_START,                     /* a starting position of the path-finding
+                                 * (there could be more than one) */
   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 */
+  NS_WAITING_START,             /* WAITING at a START tile */
+  NS_PROCESSED,                        /* the optimal route is found */
+  NS_PROCESSED_START            /* same as PROCESSED, but it's START tile 
+                                 * as well */
 };
 
 
@@ -115,7 +123,47 @@
 static struct pf_path* pf_danger_construct_path(const struct pf_map *pf_map,
                                                 int x, int y);
 
+/*  ================== helper functions ========================== */
 
+/********************************************************************
+  Is the status of the tile "processed"?
+********************************************************************/
+static bool is_processed(enum pf_node_status status)
+{
+  return (status == NS_PROCESSED || status == NS_PROCESSED_START);
+}
+
+/********************************************************************
+  The external version of the above function
+********************************************************************/
+bool pf_is_path_found(const struct pf_map *pf_map, int x, int y)
+{
+  if (!is_normal_map_pos(x, y)) {
+    freelog(LOG_ERROR, "Non-normal map position in pf_is_path_found");
+    return FALSE;
+  }
+  
+  return is_processed(pf_map->status[map_pos_to_index(x, y)]);
+}
+
+/********************************************************************
+  Is the status of the tile "waiting"?
+********************************************************************/
+static bool is_waiting(enum pf_node_status status)
+{
+  return (status == NS_WAITING || status == NS_WAITING_START);
+}
+
+/********************************************************************
+  Is the status of the tile "start"?
+********************************************************************/
+static bool is_start(enum pf_node_status status)
+{
+  return (status == NS_START || status == NS_WAITING_START 
+          || status == NS_PROCESSED_START);
+}
+
+
 /* =================== manipulating the cost ===================== */
 
 /********************************************************************
@@ -234,114 +282,120 @@
 
 /*****************************************************************
   Primary method for iterative path-finding.
-  Plan: 1. Process previous position
-        2. Get new nearest position and return it
+  1. Get new nearest position (return FALSE if none available).
+  2. Process it.
 *****************************************************************/
 bool pf_next(struct pf_map *pf_map)
 {
   index_t index;
-  struct pf_node *node = &pf_map->lattice[pf_map->index];
+  struct pf_node *node;
 
   if (pf_map->params->is_pos_dangerous) {
     /* It's a lot different if is_pos_dangerous is defined */
     return pf_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) {
-
-    /* Processing Stage */
-    /* The previous position is contained in {x,y} fields of map */
-
-    adjc_dir_iterate(pf_map->x, pf_map->y, x1, y1, dir) {
-      index_t index1 = map_pos_to_index(x1, y1);
-      struct pf_node *node1 = &pf_map->lattice[index1];
-      utiny_t *status = &pf_map->status[index1];
-      int cost;
-      int extra = 0;
-
-      if (*status == NS_PROCESSED) {
-       /* This gives 15% speedup */
-       continue;
-      }
-
-      if (*status == NS_UNINIT) {
-       pf_init_node(pf_map, node1, x1, y1);
-      }
-
-      /* Can we enter this tile at all? */
-      if (node1->behavior == TB_IGNORE) {
-       continue;
-      }
-
-      /* Is the move ZOC-ok? */
-      if (pf_map->params->zoc_used
-         && !(node->zoc_number > 1 || node1->zoc_number > 0)) {
-       continue;
-      }
-
-      /* Evaluate the cost of the move */
-      if (node1->node_known_type == TILE_UNKNOWN) {
-       cost = MOVE_COST_UNKNOWN;
-      } else {
-       cost = pf_map->params->get_MC(pf_map->x, pf_map->y, dir, x1, y1,
-                                     pf_map->params);
-       if (cost == PF_IMPOSSIBLE_MC) {
-         continue;
-       }
-       cost = adjust_cost(pf_map, cost);
-      }
-
-      /* Total cost at xy1 */
-      cost += node->cost;
-
-      /* check for overflow */
-      assert(cost >= 0);
-
-      /* Evaluate the extra cost of the destination,
-       * if it's relevant */
-      if (pf_map->params->get_EC) {
-       extra = node1->extra_tile;
-       extra += node->extra_cost;
-      }
-
-      /* Update costs and add to queue, if we found a better route to xy1. */
-      {
-       int cost_of_path = get_total_CC(pf_map, cost, extra);
-
-       if (*status == NS_UNINIT
-           || cost_of_path < get_total_CC(pf_map, node1->cost,
-                                          node1->extra_cost)) {
-         *status = NS_NEW;
-         node1->extra_cost = extra;
-         node1->cost = cost;
-         node1->dir_to_here = dir;
-         pq_insert(pf_map->queue, index1, -cost_of_path);
-       }
-      }
-
-    }
-    adjc_dir_iterate_end;
-  }
-
   /* Get the next nearest node */
   for (;;) {
     bool removed = pq_remove(pf_map->queue, &index);
 
     if (!removed) {
+      /* No more tiles in the queue.  Iteration is finished. */
       return FALSE;
     }
-    if (pf_map->status[index] == NS_NEW) {
+    if (!is_processed(pf_map->status[index])) {
       /* Discard if this node has already been processed */
       break;
     }
   }
-
   pf_map->index = index;
   index_to_map_pos(&(pf_map->x), &(pf_map->y), index);
+  node = &pf_map->lattice[pf_map->index];
 
+  /* Mark the tile processed (hopefully we will be able to process it). */
+  if (is_start(pf_map->status[pf_map->index])) {
+    pf_map->status[pf_map->index] = NS_PROCESSED_START;
+  } else {
+    pf_map->status[pf_map->index] = NS_PROCESSED;
+  }
+
+  if (node->behavior == TB_DONT_LEAVE) {
+    /* There is no exit from DONT_LEAVE tiles! Return prematurely. */
+    return TRUE;
+  }
+
+  /* Processing Stage */
+  /* The current position is contained in {x,y} fields of map */
+  adjc_dir_iterate(pf_map->x, pf_map->y, x1, y1, dir) {
+    index_t index1 = map_pos_to_index(x1, y1);
+    struct pf_node *node1 = &pf_map->lattice[index1];
+    utiny_t *status = &pf_map->status[index1];
+    int cost;
+    int extra = 0;
+    
+    if (is_processed(*status)) {
+      /* This gives 15% speedup */
+      continue;
+    }
+    
+    if (*status == NS_UNINIT) {
+      pf_init_node(pf_map, node1, x1, y1);
+    }
+    
+    /* Can we enter this tile at all? */
+    if (node1->behavior == TB_IGNORE) {
+      continue;
+    }
+    
+    /* Is the move ZOC-ok? */
+    if (pf_map->params->zoc_used
+        && !(node->zoc_number > 1 || node1->zoc_number > 0)) {
+      continue;
+    }
+    
+    /* Evaluate the cost of the move */
+    if (node1->node_known_type == TILE_UNKNOWN) {
+      cost = MOVE_COST_UNKNOWN;
+    } else {
+      cost = pf_map->params->get_MC(pf_map->x, pf_map->y, dir, x1, y1,
+                                    pf_map->params);
+      if (cost == PF_IMPOSSIBLE_MC) {
+        continue;
+      }
+      cost = adjust_cost(pf_map, cost);
+    }
+    
+    /* Total cost at xy1 */
+    cost += node->cost;
+    
+    /* check for overflow */
+    assert(cost >= 0);
+
+    /* Evaluate the extra cost of the destination,
+     * if it's relevant */
+    if (pf_map->params->get_EC) {
+      extra = node1->extra_tile;
+      extra += node->extra_cost;
+    }
+    
+    /* Update costs and add to queue, if we found a better route to xy1. */
+    {
+      int cost_of_path = get_total_CC(pf_map, cost, extra);
+      
+      if (*status == NS_UNINIT
+          || cost_of_path < get_total_CC(pf_map, node1->cost,
+                                         node1->extra_cost)) {
+        *status = NS_NEW;
+        node1->extra_cost = extra;
+        node1->cost = cost;
+        node1->dir_to_here = dir;
+        pq_insert(pf_map->queue, index1, -cost_of_path);
+      }
+    }
+    
+  }
+  adjc_dir_iterate_end;
+
   return TRUE;
 }
 
@@ -366,6 +420,30 @@
   return pf_map;
 }
 
+/*****************************************************************
+  Add (possibly another) starting position to the map
+*****************************************************************/
+void pf_add_start_pos(struct pf_map *pf_map, int x, int y, int cost, int extra)
+{
+  index_t index = map_pos_to_index(x, y);
+
+  assert(pf_map);
+
+  /* Initialize the position */
+  pf_map->status[index] = NS_START;
+  pf_init_node(pf_map, &pf_map->lattice[index], x, y);
+  pf_map->lattice[index].cost = cost;
+  pf_map->lattice[index].extra_cost = extra;
+  if (pf_map->params->is_pos_dangerous) {
+    /* The starting point is always safe */
+    pf_map->d_lattice[index].is_dangerous = FALSE;
+    /* Initialize the step counter */
+    pf_map->d_lattice[index].step = 0;
+  }  
+  /* Now shove the starting position into the queue */
+  pq_insert(pf_map->queue, index, get_total_CC(pf_map, cost, extra));
+}
+
 /***************************************************************
   Sets up the map according to the parameters
   Does not do any iterations
@@ -381,30 +459,29 @@
   pf_map->params = fc_malloc(sizeof(struct pf_parameter));
   *pf_map->params = *parameter;
 
-  /* Initialise starting coordinates */
-  pf_map->x = pf_map->params->start_x;
-  pf_map->y = pf_map->params->start_y;
-  pf_map->index = map_pos_to_index(pf_map->x, pf_map->y);
-
-  /* Initialise starting node */
-  pf_init_node(pf_map, &pf_map->lattice[pf_map->index], pf_map->x,
-              pf_map->y);
-  /* 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
-      - pf_map->params->moves_left_initially;
-  pf_map->lattice[pf_map->index].extra_cost = 0;
-  if (pf_map->params->is_pos_dangerous) {
-    /* The starting point is safe */
-    pf_map->d_lattice[pf_map->index].is_dangerous = FALSE;
-    /* Initialize step counter */
-    pf_map->d_lattice[pf_map->index].step = 0;
+  /* Initialise starting coordinates to nothing */
+  pf_map->x = -1;
+  pf_map->y = -1;
+  pf_map->index = -1;
+
+  /* If no_start == TRUE, the user want to set up the starting positions
+   * directly */
+  if (!parameter->no_start) {
+    int x = parameter->start_x, y = parameter->start_y;
+    int init_cost;
+
+    /* Setting such cost makes calculations of turn/moves_left more 
+     * convenient, but we will need to subtract this value before we return 
+     * cost to the user */
+    init_cost = parameter->move_rate - parameter->moves_left_initially;
+    
+    /* Add the default starting position */
+    pf_add_start_pos(pf_map, x, y, init_cost, 0);
   }
-
+  
   return pf_map;
 }
 
-
 /*********************************************************************
   After usage the map must be destroyed.
 *********************************************************************/
@@ -448,18 +525,20 @@
   index_t index = map_pos_to_index(x, y);
   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)) {
-    die("pf_construct_path to an unreached destination");
+  if (!is_processed(pf_map->status[index])) {
+    die("pf_*_get_position called on unreached destination");
     return;
   }
 
   pos->x = x;
   pos->y = y;
   pos->total_EC = node->extra_cost;
-  pos->total_MC = node->cost - pf_map->params->move_rate
-    + pf_map->params->moves_left_initially;
+  pos->total_MC = node->cost;
+  if (!pf_map->params->no_start) {
+    pos->total_MC -= (pf_map->params->move_rate 
+                      - pf_map->params->moves_left_initially);
+  }
+
   if (pf_map->params->turn_mode == TM_BEST_TIME ||
       pf_map->params->turn_mode == TM_WORST_TIME) {
     pos->turn = get_turn(pf_map, node->cost);
@@ -480,9 +559,14 @@
 /*******************************************************************
   Read all info about the current position into pos
 *******************************************************************/
-void pf_next_get_position(const struct pf_map *pf_map,
+void pf_next_get_position(struct pf_map *pf_map,
                          struct pf_position *pos)
 {
+  if (!is_normal_map_pos(pf_map->x, pf_map->y)) {
+    freelog(LOG_ERROR, "Non-normal position in pf_next_get_position."
+            "Trying to resolve peacefully.");
+    pf_next(pf_map);
+  }
   pf_fill_position(pf_map, pf_map->x, pf_map->y, pos);
 }
 
@@ -496,21 +580,15 @@
                     struct pf_position *pos)
 {
   index_t index = map_pos_to_index(x, y);
-  utiny_t status = pf_map->status[index];
 
-  if (status == NS_PROCESSED || same_pos(x, y, pf_map->x, pf_map->y)) {
-    /* We already reached (x,y) */
-    pf_fill_position(pf_map, x, y, pos);
-    return TRUE;
-  }
-
-  while (pf_next(pf_map)) {
-    if (same_pos(x, y, pf_map->x, pf_map->y)) {
-      /* That's the one */
+  do {
+    if (is_processed(pf_map->status[index])) {
+      /* Shortest path is found and confirmed */
       pf_fill_position(pf_map, x, y, pos);
       return TRUE;
     }
-  }
+    /* Shortest path might not be found yet, continue PF iteration */
+  } while (pf_next(pf_map));
 
   return FALSE;
 }
@@ -519,19 +597,18 @@
   Read off the path to the node (x,y), which must already be 
   discovered.  A helper for *get_path functions.
 *******************************************************************/
-static struct pf_path* pf_construct_path(const struct pf_map *pf_map, 
+static struct pf_path* pf_construct_path(struct pf_map *pf_map, 
                                          int dest_x, int dest_y)
 {
   int i;
   int x, y;
-  int index = map_pos_to_index(dest_x, dest_y);
+  index_t dest_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 */
-  if (pf_map->status[index] != NS_PROCESSED
-      && !same_pos(dest_x, dest_y, pf_map->x, pf_map->y)) {
-    die("pf_construct_path to an unreached destination");
+  if (!is_processed(pf_map->status[dest_index])) {
+    die("pf_*_get_path to an unreached destination");
     return NULL;
   }
 
@@ -547,9 +624,10 @@
   /* 1: Count the number of steps to get here.
    * To do it, backtrack until we hit the starting point */
   for (i = 0; ; i++) {
-    struct pf_node *node = &pf_map->lattice[map_pos_to_index(x, y)];
+    index_t index = map_pos_to_index(x, y);
+    struct pf_node *node = &pf_map->lattice[index];
 
-    if (same_pos(x, y, pf_map->params->start_x, pf_map->params->start_y)) {
+    if (is_start(pf_map->status[index])) {
       /* Ah-ha, reached the starting point! */
       break;
     }
@@ -592,8 +670,13 @@
 /************************************************************************
   Get the path to our current position
 ************************************************************************/
-struct pf_path *pf_next_get_path(const struct pf_map *pf_map)
+struct pf_path *pf_next_get_path(struct pf_map *pf_map)
 {
+  if (!is_normal_map_pos(pf_map->x, pf_map->y)) {
+    freelog(LOG_ERROR, "Non-normal position in pf_next_get_path."
+            "Trying to resolve peacefully.");
+    pf_next(pf_map);
+  }
   return pf_construct_path(pf_map, pf_map->x, pf_map->y);
 }
 
@@ -604,19 +687,14 @@
 struct pf_path *pf_get_path(struct pf_map *pf_map, int x, int y)
 {
   index_t index = map_pos_to_index(x, y);
-  utiny_t status = pf_map->status[index];
 
-  if (status == NS_PROCESSED || same_pos(x, y, pf_map->x, pf_map->y)) {
-    /* We already reached (x,y) */
-    return pf_construct_path(pf_map, x, y);
-  }
-
-  while (pf_next(pf_map)) {
-    if (same_pos(x, y, pf_map->x, pf_map->y)) {
-      /* That's the one */
+  do {
+    if (is_processed(pf_map->status[index])) {
+      /* Shortest path found and confirmed */
       return pf_construct_path(pf_map, x, y);
     }
-  }
+    /* Shortest path might not be found yet, continue PF iteration */
+  } while (pf_next(pf_map));
 
   return NULL;
 }
@@ -747,14 +825,32 @@
   index_t index;
   struct pf_node *node = &pf_map->lattice[pf_map->index];
   struct danger_node *d_node = &pf_map->d_lattice[pf_map->index];
+  utiny_t old_status;
 
+  /* Get the next nearest node */
+
+  /* First try to get it from danger_queue */
+  if (!pq_remove(pf_map->danger_queue, &index)) {
+    /* No dangerous nodes to process, go for a safe one */
+    do {
+      if (!pq_remove(pf_map->queue, &index)) {
+       return FALSE;
+      }
+    } while (is_processed(pf_map->status[index]));
+  }
+  assert(pf_map->status[index] != NS_UNINIT);
+  
+  pf_map->index = index;
+  index_to_map_pos(&(pf_map->x), &(pf_map->y), index);
+
+  /* Now process what we got */
+  
   /* There is no exit from DONT_LEAVE tiles! */
   if (node->behavior != TB_DONT_LEAVE) {
     /* 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 = (is_waiting(pf_map->status[pf_map->index]) ? node->cost
+                    : node->cost + get_moves_left(pf_map, node->cost));
+    
     /* The previous position is contained in {x,y} fields of map */
     adjc_dir_iterate(pf_map->x, pf_map->y, x1, y1, dir) {
       index_t index1 = map_pos_to_index(x1, y1);
@@ -762,12 +858,12 @@
       struct danger_node *d_node1 = &pf_map->d_lattice[index1];
       int cost;
       int extra = 0;
-
-      /* Dangerous tiles can be uptaded even after being processed */
-      if (pf_map->status[index1] == NS_PROCESSED && !d_node1->is_dangerous) {
-       continue;
+      
+      /* NB: Dangerous tiles can be uptaded even after being processed! */
+      if (is_processed(pf_map->status[index1]) && !d_node1->is_dangerous) {
+        continue;
       }
-
+      
       /* Initialise target tile if necessary */
       if (pf_map->status[index1] == NS_UNINIT) {
        pf_init_node(pf_map, node1, x1, y1);
@@ -843,7 +939,7 @@
              free(d_node1->danger_segment);
              d_node1->danger_segment = NULL;
            }
-           d_node1->waited = (pf_map->status[pf_map->index] == NS_WAITING);
+           d_node1->waited = (is_waiting(pf_map->status[pf_map->index]));
          }
          pf_map->status[index1] = NS_NEW;
          pq_insert(pf_map->queue, index1, -cost_of_path);
@@ -860,7 +956,7 @@
                > 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)) {
+               && is_processed(pf_map->status[index1]))) {
          node1->extra_cost = extra;
          node1->cost = cost;
          node1->dir_to_here = dir;
@@ -873,51 +969,47 @@
             d_node1->segment_length = 1;
           }
          pf_map->status[index1] = NS_NEW;
-         d_node1->waited = (pf_map->status[pf_map->index] == NS_WAITING);
+         d_node1->waited = (is_waiting(pf_map->status[pf_map->index]));
          /* Extra costs of all nodes in danger_queue are equal! */
          pq_insert(pf_map->danger_queue, index1, -cost);
        }
       }
     }
     adjc_dir_iterate_end;
-  }
+  } /* if (!DONT_LEAVE) */
+
+  /* We need the old status to decide whether we want to retrun the tile */
+  old_status = pf_map->status[pf_map->index];
+
+  /* Update the status of the tile */
+  if (!d_node->is_dangerous && !is_waiting(pf_map->status[pf_map->index])
+      && (get_moves_left(pf_map, node->cost) < pf_map->params->move_rate)) {
 
-  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;
+    freelog(LOG_NORMAL, "Considering waiting at (%d, %d)", pf_map->x,
+           pf_map->y);
+    /* Adjust the status */
+    if (is_start(pf_map->status[pf_map->index])) {
+      pf_map->status[pf_map->index] = NS_WAITING_START;
+    } else {
+      pf_map->status[pf_map->index] = NS_WAITING;
+    }
     /* Waiting counts as a step */
     d_node->step++;
+    /* Put it back into queue. */
     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;
-  }
-
-  /* Get the next nearest node */
-
-  /* First try to get it from danger_queue */
-  if (!pq_remove(pf_map->danger_queue, &index)) {
-    /* No dangerous nodes to process, go for a safe one */
-    do {
-      if (!pq_remove(pf_map->queue, &index)) {
-       return FALSE;
-      }
-    } while (pf_map->status[index] == NS_PROCESSED);
+    /* Mark as processed */
+    if (is_start(pf_map->status[pf_map->index])) {
+      pf_map->status[pf_map->index] = NS_PROCESSED_START;
+    } else {
+      pf_map->status[pf_map->index] = NS_PROCESSED;
+    }
   }
-
-  assert(pf_map->status[pf_map->index] != NS_UNINIT);
-
-  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 (is_waiting(old_status)) {
     /* We've already returned this node once, skip it */
-    freelog(LOG_NORMAL, "Considering waiting at (%d, %d)", pf_map->x,
-           pf_map->y);
     return pf_danger_iterate_map(pf_map);
   } else if (pf_map->d_lattice[index].is_dangerous) {
     /* We don't return dangerous tiles */
@@ -958,7 +1050,6 @@
     return NULL;
   }
 
-
   path->positions 
     = fc_malloc((d_node->step + 1) * sizeof(struct pf_position));
   path->length = d_node->step + 1;
@@ -1007,7 +1098,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(is_start(pf_map->status[map_pos_to_index(x, y)]));
       return path;
     }
 
Index: common/aicore/path_finding.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/aicore/path_finding.h,v
retrieving revision 1.2
diff -u -r1.2 path_finding.h
--- common/aicore/path_finding.h        2003/04/04 15:47:49     1.2
+++ common/aicore/path_finding.h        2003/04/20 13:00:51
@@ -292,6 +292,8 @@
  *
  * Examples of callbacks can be found in pf_tools.c*/
 struct pf_parameter {
+  bool no_start;                /* If TRUE, the initial position info is 
+                                 * not supplied */
   int start_x, start_y;                /* Initial position */
   int moves_left_initially;
   int move_rate;               /* Move rate of the virtual unit */
@@ -344,6 +346,15 @@
  * everything up. */
 struct pf_map *pf_create_map(const struct pf_parameter *const parameter);
 
+/* 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);
+
+/* Check if we have already found the shortest path to (x, y).  Does not 
+ * alter the state of the map iteration */
+bool pf_is_path_found(const struct pf_map *map, int x, int y);
+
 /* Tries to find the best path in the given map to the position (x, y). 
  * If NULL is returned no path could be found.  The pf_last_position of such 
  * path would be the same (almost) as the result of the call to 
@@ -366,11 +377,11 @@
 
 /* Return the full info on the position reached in the last call to 
  * pf_next. */
-void pf_next_get_position(const struct pf_map *pf_map,
+void pf_next_get_position(struct pf_map *pf_map,
                          struct pf_position *pos);
 
 /* Return the path to the position reached in the last call to pf_next. */
-struct pf_path * pf_next_get_path(const struct pf_map *pf_map);
+struct pf_path * pf_next_get_path(struct pf_map *pf_map);
 
 /* Print the path via freelog and the given log-level. For debugging
  * purposes.  Make sure the path is valid (if you got it from pf_get_path). */
Index: common/aicore/pf_tools.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/aicore/pf_tools.c,v
retrieving revision 1.1
diff -u -r1.1 pf_tools.c
--- common/aicore/pf_tools.c    2003/03/11 17:59:26     1.1
+++ common/aicore/pf_tools.c    2003/04/20 13:00:51
@@ -337,4 +444,5 @@
   parameter->turn_mode = TM_CAPPED;
   parameter->get_TB = NULL;
   parameter->get_EC = NULL;
+  parameter->no_start = FALSE;
 }