[Freeciv-Dev] (PR#13277) air units, fuel, and pathfinding (PF) / goto

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

<URL: http://bugs.freeciv.org/Ticket/Display.html?id=13277 >

And here is a better, hopefully final, patch.

Fuel support is moved entirely into path_finding.c.  Two new fields are
added to the pf_parameter: fuel and fuel_left_initially.  Internally,
the PF code leaves the parameter as it is but uses accessors -
get_moves_left_initially and get_move_rate - to access certain fields of
the parameter rather than reading them directly.  Thus to most of the PF
code it will appear that a bomber (8 MP, 2 fuel) has a move rate of 16
while the parameter contains the "true" values.  The majority of the PF
code thus knows nothing about fuel.

When it comes time to assemble a pf_position we have to reverse this
process.  Positions are created in several places (it's done separately
for danger paths versus normal paths) so a new function
finalize_position(0 is created.  After the position is filled out this
function is called and it "finalizes" the turns, moves_left, and
fuel_left of the position.

I've tested this with client goto (orders) and can't find any flaws. 
However that's not to say there aren't any.

Note that fuel does not apply to helicoptor units, which are handled
separately.

One assumption this code makes is that units with fuel have all moves
equal.  Thus taking two turns at once gives the same amount of movement
as taking two turns separately.  This would not hold for land or sea
units but it does hold for air units.

-jason

Index: client/goto.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/client/goto.c,v
retrieving revision 1.86
diff -u -r1.86 goto.c
--- client/goto.c       28 May 2005 21:24:00 -0000      1.86
+++ client/goto.c       18 Jun 2005 23:26:47 -0000
@@ -41,9 +41,9 @@
  * therefore requires it's own map.
  */
 struct part {
-  int start_moves_left;
+  int start_moves_left, start_fuel_left;
   struct tile *start_tile, *end_tile;
-  int end_moves_left;
+  int end_moves_left, end_fuel_left;
   int time;
   struct pf_path *path;
   struct pf_map *map;
@@ -192,6 +192,7 @@
   p->path = new_path;
   p->end_tile = ptile;
   p->end_moves_left = pf_last_position(p->path)->moves_left;
+  p->end_fuel_left = pf_last_position(p->path)->fuel_left;
 
   if (hover_state == HOVER_CONNECT) {
     int move_rate = goto_map.template.move_rate;
@@ -248,19 +249,21 @@
     struct unit *punit = find_unit_by_id(goto_map.unit_id);
 
     p->start_tile = punit->tile;
-    p->start_moves_left = punit->moves_left;
+    p->start_moves_left = parameter.moves_left_initially;
+    p->start_fuel_left = parameter.fuel_left_initially;
   } else {
     struct part *prev = &goto_map.parts[goto_map.num_parts - 2];
 
     p->start_tile = prev->end_tile;
     p->start_moves_left = prev->end_moves_left;
+    p->start_fuel_left = prev->end_fuel_left;
     parameter.moves_left_initially = p->start_moves_left;
+    parameter.fuel_left_initially = p->start_fuel_left;
   }
   p->path = NULL;
   p->end_tile = p->start_tile;
   p->time = 0;
   parameter.start_tile = p->start_tile;
-  parameter.moves_left_initially = p->start_moves_left;
   p->map = pf_create_map(&parameter);
 }
 
@@ -905,6 +908,8 @@
   parameter.start_tile = goto_map.parts[goto_map.num_parts - 1].end_tile;
   parameter.moves_left_initially
     = goto_map.parts[goto_map.num_parts - 1].end_moves_left;
+  parameter.fuel_left_initially
+    = goto_map.parts[goto_map.num_parts - 1].end_fuel_left;
   map = pf_create_map(&parameter);
   return_path = pf_get_path(map, goto_map.parts[0].start_tile);
   if (!return_path) {
Index: common/aicore/path_finding.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/aicore/path_finding.c,v
retrieving revision 1.31
diff -u -r1.31 path_finding.c
--- common/aicore/path_finding.c        2 May 2005 15:42:53 -0000       1.31
+++ common/aicore/path_finding.c        18 Jun 2005 23:26:47 -0000
@@ -118,6 +118,33 @@
 
 /* =================== manipulating the cost ===================== */
 
+/****************************************************************************
+  Return the number of "moves" started with.
+
+  This is different from the moves_left_initially because of fuel.  For units
+  with fuel > 1 all moves on the same tank of fuel are considered to be one
+  turn.  Thus the rest of the PF code doesn't actually know that the unit
+  has fuel, it just thinks it has that many more MP.
+****************************************************************************/
+static int get_moves_left_initially(const struct pf_parameter *param)
+{
+  return (param->moves_left_initially
+         + (param->fuel_left_initially - 1) * param->move_rate);
+}
+
+/****************************************************************************
+  Return the "move rate".
+
+  This is different from the parameter's move_rate because of fuel.  For units
+  with fuel > 1 all moves on the same tank of fuel are considered to be one
+  turn.  Thus the rest of the PF code doesn't actually know that the unit
+  has fuel, it just thinks it has that many more MP.
+****************************************************************************/
+static int get_move_rate(const struct pf_parameter *param)
+{
+  return param->move_rate * param->fuel;
+}
+
 /********************************************************************
   Number of turns required to reach node
 ********************************************************************/
@@ -128,7 +155,7 @@
    * we'd better be ready.
    *
    * Note that cost==0 corresponds to the current turn with full MP. */
-  return (cost < 0 ? 0 : cost / pf_map->params->move_rate);
+  return (cost < 0 ? 0 : cost / get_move_rate(pf_map->params));
 }
 
 /********************************************************************
@@ -137,8 +164,9 @@
 static int get_moves_left(const struct pf_map *pf_map, int cost)
 {
   /* Cost may be negative; see get_turn(). */
-  return (cost < 0 ? pf_map->params->move_rate - cost
-          : pf_map->params->move_rate - (cost % pf_map->params->move_rate));
+  return (cost < 0 ? get_move_rate(pf_map->params) - cost
+          : (get_move_rate(pf_map->params)
+            - (cost % get_move_rate(pf_map->params))));
 }
 
 /********************************************************************
@@ -152,10 +180,10 @@
   case TM_NONE:
     break;
   case TM_CAPPED:
-    cost = MIN(cost, pf_map->params->move_rate);
+    cost = MIN(cost, get_move_rate(pf_map->params));
     break;
   case TM_WORST_TIME:
-    cost = MIN(cost, pf_map->params->move_rate);
+    cost = MIN(cost, get_move_rate(pf_map->params));
     {
       int moves_left
          = get_moves_left(pf_map, pf_map->lattice[pf_map->tile->index].cost);
@@ -239,7 +267,7 @@
 *****************************************************************/
 static int get_total_CC(struct pf_map *pf_map, int cost, int extra)
 {
-  return PF_TURN_FACTOR * cost + extra * pf_map->params->move_rate;
+  return PF_TURN_FACTOR * cost + extra * get_move_rate(pf_map->params);
 }
 
 /**************************************************************************
@@ -465,8 +493,8 @@
    * need to subtract this value before we return cost to the user.  Note
    * that cost may be negative if moves_left_initially > move_rate
    * (see get_turn()). */
-  pf_map->lattice[pf_map->tile->index].cost = pf_map->params->move_rate
-      - pf_map->params->moves_left_initially;
+  pf_map->lattice[pf_map->tile->index].cost = get_move_rate(pf_map->params)
+    - get_moves_left_initially(pf_map->params);
   pf_map->lattice[pf_map->tile->index].extra_cost = 0;
   pf_map->lattice[pf_map->tile->index].dir_to_here = -1;
   if (pf_map->params->is_pos_dangerous) {
@@ -512,10 +540,33 @@
 
 /* =================== Lifting info from the map ================ */
 
-/*******************************************************************
+/****************************************************************************
+  Take a position previously filled out (as by fill_position) and
+  "finalize" it by reversing all fuel multipliers.
+
+  See get_moves_left_initially and get_move_rate.
+****************************************************************************/
+static void finalize_position(const struct pf_map *pf_map,
+                             struct pf_position *pos)
+{
+  if (pf_map->params->turn_mode == TM_BEST_TIME ||
+      pf_map->params->turn_mode == TM_WORST_TIME) {
+    pos->turn *= pf_map->params->fuel;
+    pos->turn += ((get_move_rate(pf_map->params) - pos->moves_left)
+                 / pf_map->params->move_rate);
+
+    /* We add 1 because a fuel of 1 means "no" fuel left; e.g. fuel
+     * ranges from [1,ut->fuel] not from [0,ut->fuel) as you may think. */
+    pos->fuel_left = pos->moves_left / pf_map->params->move_rate + 1;
+
+    pos->moves_left %= pf_map->params->move_rate;
+  }
+}
+
+/****************************************************************************
   Fill in the position which must be discovered already. A helper 
-  for *_get_position functions.
-*******************************************************************/
+  for *_get_position functions.  This also "finalizes" the position.
+****************************************************************************/
 static void fill_position(const struct pf_map *pf_map, struct tile *ptile,
                             struct pf_position *pos)
 {
@@ -531,8 +582,8 @@
 
   pos->tile = ptile;
   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 - get_move_rate(pf_map->params)
+    + get_moves_left_initially(pf_map->params);
   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);
@@ -541,6 +592,7 @@
             pf_map->params->turn_mode == TM_CAPPED) {
     pos->turn = -1;
     pos->moves_left = -1;
+    pos->fuel_left = -1;
   } else {
     die("unknown TC");
   }
@@ -548,6 +600,8 @@
   pos->dir_to_here = node->dir_to_here;
   /* This field does not apply */
   pos->dir_to_next_pos = -1;
+
+  finalize_position(pf_map, pos);
 }
 
 /*******************************************************************
@@ -810,7 +864,7 @@
     return PF_IMPOSSIBLE_MC;
   }
 
-  cost = MIN(cost, pf_map->params->move_rate);
+  cost = MIN(cost, get_move_rate(pf_map->params));
 
   if (pf_map->params->turn_mode == TM_BEST_TIME) {
     if (to_danger && cost >= moves_left) {
@@ -1001,7 +1055,7 @@
   if (!d_node->is_dangerous
       && pf_map->status[pf_map->tile->index] != NS_WAITING
       && (get_moves_left(pf_map, node->cost)
-         < pf_map->params->move_rate)) {
+         < get_move_rate(pf_map->params))) {
     /* Consider waiting at this node. 
      * To do it, put it back into queue. */
     pf_map->status[pf_map->tile->index] = NS_WAITING;
@@ -1081,11 +1135,12 @@
         path->positions[i].tile = ptile;
         path->positions[i].total_EC = node->extra_cost;
         path->positions[i].turn = get_turn(pf_map, node->cost) + 1;
-        path->positions[i].moves_left = pf_map->params->move_rate;
+        path->positions[i].moves_left = get_move_rate(pf_map->params);
         path->positions[i].total_MC 
           = ((path->positions[i].turn - 1) * pf_map->params->move_rate
              + pf_map->params->moves_left_initially);
         path->positions[i].dir_to_next_pos = dir_next;
+       finalize_position(pf_map, &path->positions[i]);
         /* Set old_waited so that we record -1 as a direction at the step 
          * we were going to wait */
         old_waited = TRUE;
@@ -1109,9 +1164,10 @@
     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);
-    path->positions[i].total_MC -= pf_map->params->move_rate
-      - pf_map->params->moves_left_initially;
+    path->positions[i].total_MC -= get_move_rate(pf_map->params)
+      - get_moves_left_initially(pf_map->params);
     path->positions[i].dir_to_next_pos = (old_waited ? -1 : dir_next);
+    finalize_position(pf_map, &path->positions[i]);
 
     /* 3: Check if we finished */
     if (i == 0) {
Index: common/aicore/path_finding.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/aicore/path_finding.h,v
retrieving revision 1.11
diff -u -r1.11 path_finding.h
--- common/aicore/path_finding.h        10 Jan 2005 03:24:16 -0000      1.11
+++ common/aicore/path_finding.h        18 Jun 2005 23:26:47 -0000
@@ -270,7 +270,7 @@
 /* Full specification of a position and time to reach it. */
 struct pf_position {
   struct tile *tile;
-  int turn, moves_left;                /* See definitions above */
+  int turn, moves_left, fuel_left;     /* See definitions above */
 
   int total_MC;                        /* Total MC to reach this point */
   int total_EC;                        /* Total EC to reach this point */
@@ -294,8 +294,12 @@
  * Examples of callbacks can be found in pf_tools.c*/
 struct pf_parameter {
   struct tile *start_tile;     /* Initial position */
+
   int moves_left_initially;
+  int fuel_left_initially;      /* Ignored for non-air units. */
+
   int move_rate;               /* Move rate of the virtual unit */
+  int fuel;                     /* Should be 1 for units without fuel. */
 
   struct player *owner;
 
Index: common/aicore/pf_tools.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/aicore/pf_tools.c,v
retrieving revision 1.32
diff -u -r1.32 pf_tools.c
--- common/aicore/pf_tools.c    23 Apr 2005 17:40:28 -0000      1.32
+++ common/aicore/pf_tools.c    18 Jun 2005 23:26:47 -0000
@@ -782,6 +782,13 @@
   parameter->start_tile = punit->tile;
   parameter->moves_left_initially = punit->moves_left;
   parameter->move_rate = unit_move_rate(punit);
+  if (is_air_unit(punit)) {
+    parameter->fuel_left_initially = punit->fuel;
+    parameter->fuel = unit_type(punit)->fuel;
+  } else {
+    parameter->fuel = 1;
+    parameter->fuel_left_initially = 1;
+  }
   parameter->owner = unit_owner(punit);
   parameter->unit_flags = unit_type(punit)->flags;