[freeciv-ai] (PR#8992) Patch: Centralised ferry building

["Benedict Adamson" <badamson@xxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=8992 >

[Resending because the original did not register in RT]
Attached is an altered version of Gregory Berkolaiko's patch for
centralised ferry building. This is applicable to the 2004-10-08 CVS
development snapshot.

This incorporates a fix of PR#10216 (AI Builds Too Many Transports).
I've added some comments and assertions and improved the logging. I
extracted the determination
of the type of new ferries from the loop. I separated the examination of
the facts about an ocean from the decision about how many boats to
build, placing the decision code in a new function, new_boats_to_build.
I did that because I assume that the decision logic is likely to need
the most tweaking to get optimal ferry building. I've indicated
suggestions for future work as 'TODO' comments.

What do you think, Gregory?



diff -Nur -Xfreeciv.PR8992/diff_ignore vendor.freeciv.current/ai/advdomestic.c 
freeciv.PR8992/ai/advdomestic.c
--- vendor.freeciv.current/ai/advdomestic.c     2004-10-03 11:40:07.000000000 
+0100
+++ freeciv.PR8992/ai/advdomestic.c     2004-10-09 22:14:58.000000000 +0100
@@ -200,7 +200,6 @@
       choice->type = CT_NONMIL;
       choice->choice = unit_type; /* default */
       choice->need_boat = TRUE;
-      ai_choose_role_unit(pplayer, pcity, choice, L_FERRYBOAT, -want);
     }
   }
 
diff -Nur -Xfreeciv.PR8992/diff_ignore vendor.freeciv.current/ai/advmilitary.c 
freeciv.PR8992/ai/advmilitary.c
--- vendor.freeciv.current/ai/advmilitary.c     2004-10-03 11:40:07.000000000 
+0100
+++ freeciv.PR8992/ai/advmilitary.c     2004-10-09 22:14:58.000000000 +0100
@@ -768,7 +768,7 @@
   kill_something_with send it some more variables for it to meddle with. 
   -- Syela
 
-  (x,y) is location of the target.
+  ptile is location of the target (?)
   best_choice is pre-filled with our current choice, we only 
   consider units of the same move_type as best_choice
 **************************************************************************/
@@ -955,12 +955,86 @@
 }
 
 /************************************************************************** 
+Guess information about the kind of ferry we can expect to transport an
+attacker to its target.
+
+Although we do not force a boat to the city (that is done by the centralised
+boat dispatcher), we still need to know some information about the kind of boat
+we can expect to have, so we can select suitable targets.
+We want to estimate how long it will take for the boat to get there
+(if we will use an existing boat) and the sailing speed after we board it.
+
+*go_by_boat: expect to need a ferry
+*ferryboat: expect to get this ferry. NULL indicates to expect
+            to get a new boat instead, in which case use *boattype to
+            determine the characterisitics of the new ferry.
+*boattype: expect to get this type of ferry
+
+TODO: Perhaps should use the ai->stats about passengers, boats and
+available_boats to help decide what kind of ferry to expect.
+TODO: Perhaps should examine the current mix of boat types in our current
+fleet to help decide what kind of ferry to expect.
+TODO: If we will soon have improved ferry technology, perhaps should
+assume that new ferries will have that type.
+*************************************************************************/
+static void guess_attacker_ferry(struct player *pplayer, struct unit *myunit,
+                                 int move_rate, struct tile *destination,
+                                 bool *go_by_boat,
+                                 struct unit **ferryboat,
+                                 Unit_Type_id *boattype)
+{
+  if (is_ground_unit(myunit)) {
+
+    /* Are there free boats nearby?*/
+    struct tile *boat_tile = NULL;
+    int boatid = find_boat(pplayer, &boat_tile, 2); /*quick but unreliable*/
+    *ferryboat = player_find_unit_by_id(pplayer, boatid);
+
+    if (*ferryboat) { /*there is a free boat nearby*/
+      /* Assume we will get a boat like this existing free nearby boat.*/
+      /* This is a good assumption if we have many free boats*/
+      *boattype = (*ferryboat)->type;
+    } else {
+      /* Assume we will get a shiny new boat.*/
+      /* Because find_boat() is unreliable, we will make this assumption
+       * unrealisitically often. When the unit is finally built, it might
+       * have to make do with a low tech boat from our old fleet,
+       * but this optimism is probably not too bad for most games.
+       */
+      *boattype = best_role_unit_for_player(pplayer, L_FERRYBOAT);
+      if (*boattype == U_LAST) {
+        /* We pretend that we can have the simplest boat --
+           to stimulate tech */
+        *boattype = get_role_unit(L_FERRYBOAT, 0);
+      }
+    }
+
+    *go_by_boat = !(WARMAP_COST(destination) <= (MIN(6, move_rate) * THRESHOLD)
+                    && goto_is_sane(myunit, destination, TRUE));
+  } else {/*never needs a boat*/
+    *go_by_boat = FALSE;
+    *ferryboat = NULL;
+    *boattype = U_LAST;
+  }
+
+  /*Only ground units ever need boats:*/
+  assert(!(!is_ground_unit(myunit) && *go_by_boat));
+  /*If we will go by boat, it will be on a ferry of some kind:*/
+  assert(!(*go_by_boat) || *boattype != U_LAST);
+  assert(!(*go_by_boat) || SEA_MOVING == unit_types[*boattype].move_type);
+  /*Provide consistent output data:*/
+  assert(0 == *ferryboat || (*ferryboat)->type == *boattype);
+}
+
+/************************************************************************** 
 This function 
 1. receives (in myunit) a first estimate of what we would like to build.
 2. finds a potential victim for it.
 3. calculates the relevant stats of the victim.
 4. finds the best attacker for this type of victim (in process_attacker_want)
 5. if we still want to attack, records the best attacker in choice.
+If the target is overseas, the function might suggest using a ferry
+to carry a land attack unit.
 **************************************************************************/
 static void kill_something_with(struct player *pplayer, struct city *pcity, 
                                struct unit *myunit, struct ai_choice *choice)
@@ -974,17 +1048,15 @@
   Unit_Type_id def_type;
   /* Target coordinates */
   struct tile *ptile;
-  /* Our transport */
+  /* The ferry we expect to use, if using an existing ferry*/
   struct unit *ferryboat = NULL;
   /* Out target */
   struct city *acity;
   /* Defender of the target city/tile */
   struct unit *pdef; 
-  /* Coordinates of the boat */
-  struct tile *boat_tile = NULL;
-  /* Type of the boat (real or a future one) */
+  /* Type of the ferry we expect to use(real or a future one) */
   Unit_Type_id boattype = U_LAST;
-  bool go_by_boat;
+  bool go_by_boat = FALSE;
   /* Is the defender veteran? */
   int def_vet;
   struct ai_choice best_choice;
@@ -1007,21 +1079,6 @@
     return;
   }
 
-  if (is_ground_unit(myunit)) {
-    int boatid = find_boat(pplayer, &boat_tile, 2);
-    ferryboat = player_find_unit_by_id(pplayer, boatid);
-  }
-
-  if (ferryboat) {
-    boattype = ferryboat->type;
-  } else {
-    boattype = best_role_unit_for_player(pplayer, L_FERRYBOAT);
-    if (boattype == U_LAST) {
-      /* We pretend that we can have the simplest boat -- to stimulate tech */
-      boattype = get_role_unit(L_FERRYBOAT, 0);
-    }
-  }
-
   best_choice.want = find_something_to_kill(pplayer, myunit, &ptile);
 
   acity = map_get_city(ptile);
@@ -1055,8 +1112,8 @@
       return;
     }
 
-    go_by_boat = !(goto_is_sane(myunit, acity->tile, TRUE) 
-                  && WARMAP_COST(ptile) <= (MIN(6, move_rate) * THRESHOLD));
+    guess_attacker_ferry(pplayer, myunit, move_rate, ptile,
+                         &go_by_boat, &ferryboat, &boattype);
     move_time = turns_to_enemy_city(myunit->type, acity, move_rate, 
                                     go_by_boat, ferryboat, boattype);
 
@@ -1105,24 +1162,18 @@
     /* end dealing with units */
   }
   
-  if (!go_by_boat) {
-    process_attacker_want(pcity, benefit, def_type, def_vet, ptile, 
-                          &best_choice, NULL, U_LAST);
-  } else { 
-    /* Attract a boat to our city or retain the one that's already here */
-    best_choice.need_boat = TRUE;
-    process_attacker_want(pcity, benefit, def_type, def_vet, ptile, 
-                          &best_choice, ferryboat, boattype);
-  }
+  best_choice.need_boat = go_by_boat;
+  process_attacker_want(pcity, benefit, def_type, def_vet, ptile, 
+                       &best_choice, ferryboat, boattype);
+  /*Only ground units ever need boats:*/
+  assert(!(!is_ground_unit(myunit) && best_choice.need_boat));
 
   if (best_choice.want > choice->want) {
     /* We want attacker more that what we have selected before */
     copy_if_better_choice(&best_choice, choice);
-    if (go_by_boat && !ferryboat) {
-      ai_choose_role_unit(pplayer, pcity, choice, L_FERRYBOAT, choice->want);
-    }
-    freelog(LOG_DEBUG, "%s has chosen attacker, %s, want=%d",
-            pcity->name, unit_types[choice->choice].name, choice->want);
+    CITY_LOG(LOG_DEBUG, pcity, "has chosen attacker, %s, want=%d%s",
+            unit_types[choice->choice].name, choice->want, 
+            (best_choice.need_boat ? "(need boat)" : ""));
   } 
 }
 
diff -Nur -Xfreeciv.PR8992/diff_ignore vendor.freeciv.current/ai/aicity.c 
freeciv.PR8992/ai/aicity.c
--- vendor.freeciv.current/ai/aicity.c  2004-10-03 11:40:07.000000000 +0100
+++ freeciv.PR8992/ai/aicity.c  2004-10-09 22:14:58.000000000 +0100
@@ -46,6 +46,7 @@
 #include "advdomestic.h"
 #include "advmilitary.h"
 #include "aidata.h"
+#include "aiferry.h"
 #include "aihand.h"
 #include "ailog.h"
 #include "aitools.h"
@@ -980,6 +981,8 @@
     ai_city_choose_build(pplayer, pcity);
   } city_list_iterate_end;
 
+  aiferry_choose_build_global(pplayer);
+
   ai_spend_gold(pplayer);
 }
 
diff -Nur -Xfreeciv.PR8992/diff_ignore vendor.freeciv.current/ai/aiferry.c 
freeciv.PR8992/ai/aiferry.c
--- vendor.freeciv.current/ai/aiferry.c 2004-10-03 11:40:07.000000000 +0100
+++ freeciv.PR8992/ai/aiferry.c 2004-10-09 22:14:58.000000000 +0100
@@ -16,6 +16,7 @@
 #endif
 
 #include "log.h"
+#include "mem.h"
 #include "unit.h"
 
 #include "path_finding.h"
@@ -27,6 +28,7 @@
 
 #include "aidata.h"
 #include "aiexplorer.h"
+#include "aihand.h"
 #include "ailog.h"
 #include "aitools.h"
 #include "aiunit.h"
@@ -44,13 +46,14 @@
  * The below is used only by passengers in ai.ferryboat field 
  */ 
 #define FERRY_WANTED      -1      /* Needs a boat */
-#define FERRY_NONE         0      /* Has no boa and doesn't need one */
+#define FERRY_NONE         0      /* Has no boat and doesn't need one */
 
 
 /* =================== group log levels, debug options ================= */
 
 /* Logging in ferry management functions */
 #define LOGLEVEL_FERRY LOG_DEBUG
+#define LOGLEVEL_BUILDFERRY LOG_NORMAL
 /* Logging in go_by_boat functions */
 #define LOGLEVEL_GOBYBOAT LOG_DEBUG
 /* Logging in find_ferry functions */
@@ -58,7 +61,6 @@
 /* Extra consistency checks */
 #define DEBUG_FERRY_STATS 0
 
-
 /* ========= managing statistics and boat/passanger assignments ======== */
 
 /**************************************************************************
@@ -73,7 +75,7 @@
   ai->stats.available_boats = 0;
  
   unit_list_iterate(pplayer->units, punit) {
-    if (is_sailing_unit(punit) && is_ground_units_transport(punit)) {
+    if (unit_has_role(punit->type, L_FERRYBOAT)) {
       ai->stats.boats++;
       if (punit->ai.passenger == FERRY_AVAILABLE) {
        ai->stats.available_boats++;
@@ -95,8 +97,8 @@
   struct ai_data *ai = ai_data_get(pplayer);
   int n = 1;
 
-  freelog(LOG_NORMAL, "Boat stats for %s[%d]", 
-         pplayer->name, pplayer->player_no);
+  freelog(LOG_NORMAL, "Boat stats for %s[%d] in turn %d", 
+         pplayer->name, pplayer->player_no, game.turn);
   freelog(LOG_NORMAL, "Registered: %d free out of total %d",
          ai->stats.available_boats, ai->stats.boats);
   unit_list_iterate(pplayer->units, punit) {
@@ -855,3 +857,256 @@
  
   return;
 }
+
+/**************************************************************************
+  A cost function for a sea unit which allows going one step into the land.
+  
+  Things to remember: we should prevent going from land to anywhere, unless 
+  we are leaving a city, in which case we can move into the ocean but not 
+  into the land.
+**************************************************************************/
+static int overlap_move(const struct tile *ptile, enum direction8 dir,
+                        const struct tile *ptile1, struct pf_parameter *param)
+{
+  if (is_ocean(map_get_terrain(ptile))) {
+    return SINGLE_MOVE;
+  } else if (is_allied_city_tile(ptile, param->owner)
+            && is_ocean(map_get_terrain(ptile1))) {
+    return SINGLE_MOVE;
+  }
+
+  return PF_IMPOSSIBLE_MC;
+}
+
+/* Least Common Multiple of 2,3,..,8 (a very divisible number) */
+#define DENOM 840
+
+/****************************************************************************
+ Convert facts about a sea into an opinion about how many boats to build
+ for that sea.
+****************************************************************************/
+static unsigned int new_boats_to_build(int psngrs, int boats,
+                                       int avail_boats,
+                                       unsigned int turns_horizon,
+                                       unsigned int extra_passengers[])
+{
+  unsigned int boats_to_be_built;
+  unsigned int t;
+  int future_psngrs = 0;
+  for(t = 1; t < turns_horizon; t++) {
+    future_psngrs += (DENOM * extra_passengers[t])/ t;
+  }
+
+  /* WAG rules: idle boats count twice, future passangers 
+   * count as half */ 
+  psngrs = psngrs * DENOM + MAX(0, future_psngrs - boats * DENOM);
+  boats = (boats + avail_boats) * DENOM;
+  /*TODO: Allow building more than one boat at a time*/
+  boats_to_be_built = (psngrs > boats ? 1 : 0);
+
+  freelog(LOGLEVEL_BUILDFERRY,
+          "future passenger score %d, boat-want %d, should build %d boats", 
+          future_psngrs, psngrs - boats, boats_to_be_built);
+  return boats_to_be_built;
+}
+#undef DENOM
+
+/****************************************************************************
+  A global ferry build selector.  Estimates our want for the boats and finds
+  cities who will build them.
+
+  FIXME: Gross hack, uses pcity->ai.founder_want field for its local 
+  calculations.
+  0: unprocessed or non-coastal
+  1: on the coast of the current ocean and
+     future need for boats has been counted
+  2: processed
+****************************************************************************/
+void aiferry_choose_build_global(struct player *pplayer)
+{
+  struct city *pcity;
+  /* The worst case is that each of our coastal cities
+   * is on a different ocean:*/
+  int inf_loop_guard = city_list_size(&pplayer->cities);
+
+  unsigned int turns_horizon = 30U;
+  /*extra_passengers[t] = increment in passengers in turn t from now*/
+  unsigned int *extra_passengers =
+    fc_calloc(turns_horizon, sizeof(unsigned int));
+  /* Path-finding stuff */
+  struct pf_map *pfmap;
+  struct pf_parameter parameter;
+
+  /*Choose type of boats to build*/
+  Unit_Type_id boattype = best_role_unit_for_player(pplayer, L_FERRYBOAT);
+
+  /* Initialize */
+  city_list_iterate(pplayer->cities, acity) {
+    acity->ai.founder_want = 0;
+  } city_list_iterate_end;
+
+  parameter.turn_mode = TM_NONE;
+  parameter.get_MC = overlap_move; /*an ocean and its shore*/
+  parameter.get_TB = NULL;
+  parameter.get_EC = NULL;
+  parameter.get_costs = NULL;
+  parameter.get_zoc = NULL;
+  parameter.is_pos_dangerous = NULL;
+  BV_CLR_ALL(parameter.unit_flags);
+  parameter.owner = pplayer;
+  parameter.omniscience = !ai_handicap(pplayer, H_MAP);
+  /* These don't matter */
+  parameter.moves_left_initially = 0;
+  parameter.move_rate = 3;
+
+  do {/*each ocean for which we have coastal cities*/
+    unsigned int future_psngrs = 0, psngrs = 0;
+    unsigned int boats = 0, avail_boats = 0;
+    unsigned int boats_to_be_built, t;
+
+    /* Find an unprocessed coastal city;
+     * such a city is on the shore of an unprocessed ocean. */
+    pcity = NULL;
+    city_list_iterate(pplayer->cities, acity) {
+      if (acity->ai.founder_want == 0 
+         && is_ocean_near_tile(acity->tile)) {
+       pcity = acity;
+       break;
+      }
+    } city_list_iterate_end;
+
+    if (!pcity) {/*no more oceans*/
+      break;
+    }
+
+    /* Get a map of the sea plus shore accessible from pcity*/
+    /* If the city is adjacent to more than one ocean,
+     * or oceans are accessible from the city through channels in allied
+     * cities, this processes all those oceans as one sea.*/
+    parameter.start_tile = pcity->tile;
+    pfmap = pf_create_map(&parameter);
+
+    /* Part 1: measure the demand for boats for this ocean*/
+
+    for(t = 0; t < turns_horizon; t++) {
+      extra_passengers[t] = 0;
+    }
+
+    /* We want to consider the place we are currently in too, hence the 
+     * do-while loop */
+    do {/*all tiles in the sea or on its shore*/
+      struct pf_position pos;
+      struct city *acity;
+
+      pf_next_get_position(pfmap, &pos);
+      acity = map_get_city(pos.tile);
+
+      /* Cities on the shore of this sea that are building units
+       * that will require ferrries increase the demand for ferries
+       * for this sea.*/
+      if (acity && acity->owner == pplayer->player_no) {
+       assert(acity->ai.founder_want == 0);
+       acity->ai.founder_want = 1;
+
+       if (acity->ai.choice.need_boat) {
+         int turns_to_build = 
+           city_turns_to_build(acity, acity->ai.choice.choice, 
+                               is_unit_choice_type(acity->ai.choice.type),
+                               TRUE);
+         assert(0 < turns_to_build);
+         future_psngrs++;
+         extra_passengers[MIN(turns_to_build, turns_horizon-1)]++;
+        }
+      }
+
+      /* Update information about ferries and passengers in this sea
+       * for the units on this tile*/
+      unit_list_iterate(pos.tile->units, aunit) {
+       if (aunit->owner != pplayer->player_no) {
+         continue;
+       }
+       if (unit_has_role(aunit->type, L_FERRYBOAT)) {
+         boats++;
+         if (aunit->ai.passenger == FERRY_AVAILABLE) {
+           avail_boats++;
+         }
+         if (aunit->ai.passenger == 0) {
+           freelog(LOG_ERROR, "Passenger field set to 0");
+           avail_boats++;
+         }
+       } else if (aunit->ai.ferryboat == FERRY_WANTED) {
+         psngrs++;
+       }
+      } unit_list_iterate_end;      
+    } while (pf_next(pfmap));
+
+    pf_destroy_map(pfmap);
+
+    freelog(LOGLEVEL_BUILDFERRY, "Sea near %s's %s: %d boats (%d free), "
+            "%d waiting units (%d future)", pplayer->name, pcity->name,
+            boats, avail_boats, psngrs, future_psngrs);
+    assert(avail_boats <= boats);
+
+    /* Part 2: Decide on how many boats we want built */
+    boats_to_be_built = new_boats_to_build(psngrs, boats, avail_boats,
+                                           turns_horizon, extra_passengers);
+    freelog(LOGLEVEL_BUILDFERRY,
+            "Sea near %s's %s: should build %d boats", 
+           pplayer->name, pcity->name, boats_to_be_built);
+
+    if (boattype == U_LAST) {
+      /* Stimulate tech A LOT!!! */
+      /* TODO: do it*/
+      freelog(LOGLEVEL_BUILDFERRY,
+              "%s lacks the technology to build needed boats", pplayer->name);
+      boats_to_be_built = 0;
+    }
+
+    /* Part 3: Decide where to build the boats */
+    while (boats_to_be_built > 0) {
+      int best = FC_INFINITY;
+      struct city *bestcity = NULL;
+
+      /* Choose the city on the shore of this ocean
+       * that can complete a boat soonest*/
+      city_list_iterate(pplayer->cities, acity) {
+       if (acity->ai.founder_want == 1 
+           && acity->ai.choice.need_boat
+           && city_turns_to_build(acity, boattype, TRUE, TRUE) < best) {
+         assert(is_ocean_near_tile(pcity->tile));
+         best = city_turns_to_build(acity, boattype, TRUE, TRUE);
+         bestcity = acity;
+       }
+      } city_list_iterate_end;
+
+      if (!bestcity) {
+       break;
+      }
+
+      /* FIXME: separate a function ai_set_build from 
+       * aicity.c:ai_city_choose_build and use it here */
+      CITY_LOG(LOGLEVEL_BUILDFERRY, bestcity, "will build a boat");
+      bestcity->currently_building = boattype;
+      pcity->is_building_unit = TRUE;
+      boats_to_be_built--;
+    }
+
+    if (0 < boats_to_be_built) {
+      /*TODO: hasten production on the shores of this sea?*/
+      freelog(LOGLEVEL_BUILDFERRY,
+             "Sea near %s's %s: unable to build %d boats",
+             pplayer->name, pcity->name, boats_to_be_built);
+    }
+
+    /* Part 4: Cleanup */
+    city_list_iterate(pplayer->cities, acity) {
+      if (acity->ai.founder_want == 1) { 
+         acity->ai.founder_want = 2;
+      }
+    } city_list_iterate_end;
+
+    inf_loop_guard--;
+  } while(inf_loop_guard > 0);
+
+  free(extra_passengers);
+}
diff -Nur -Xfreeciv.PR8992/diff_ignore vendor.freeciv.current/ai/aiferry.h 
freeciv.PR8992/ai/aiferry.h
--- vendor.freeciv.current/ai/aiferry.h 2004-10-03 11:40:07.000000000 +0100
+++ freeciv.PR8992/ai/aiferry.h 2004-10-09 22:14:58.000000000 +0100
@@ -48,4 +48,10 @@
  */
 void ai_manage_ferryboat(struct player *pplayer, struct unit *punit);
 
+/* 
+ * A function for a centralized (i.e. per-civilization rather than per-city
+ * estimation of need to build more ferries and where to build them
+ */
+void aiferry_choose_build_global(struct player *pplayer);
+
 #endif /* FC__AIFERRY_H */
diff -Nur -Xfreeciv.PR8992/diff_ignore vendor.freeciv.current/diff_ignore 
freeciv.PR8992/diff_ignore
--- vendor.freeciv.current/diff_ignore  2004-09-05 21:01:58.000000000 +0100
+++ freeciv.PR8992/diff_ignore  2004-10-09 22:14:58.000000000 +0100
@@ -17,6 +17,7 @@
 *~
 .#*
 .deps
+.svn
 CVS
 Freeciv.h
 Makefile