[freeciv-ai] Re: [Freeciv-Dev] Re: (PR#11995) Stupid AI Creates Tall Stacks

["Benedict Adamson" <badamson@xxxxxxxxxxx>]

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

I wrote:
...
> Unfortunately, the AI movement function, ai_unit_goto, uses a warmap 
> (via do_unit_goto) rather than PF
...
> so I suggest rewriting 
> ai_unit_goto and have that change reviewed and committed before 
> implementing a fix to prevent tall stacks.
...

Attached is an initial version of the patch that changes ai_unit_goto to 
use PF rather than a warmap. This change is incomplete because the 
beachhead code is far too slow, but I thought it best to show what I've 
done so far to get some feedback. For the next version, I will try 
implementing a proper amphibious PF (like the current overlap code, but 
able to handle multiple land moves) to replace the beachhead code.

diff -ru -Xvendor.freeciv.current/diff_ignore 
vendor.freeciv.current/ai/aiferry.c freeciv.PR11995/ai/aiferry.c
--- vendor.freeciv.current/ai/aiferry.c 2005-01-24 20:43:05.000000000 +0000
+++ freeciv.PR11995/ai/aiferry.c        2005-02-15 22:45:45.000000000 +0000
@@ -386,6 +386,23 @@
 
 /* ============================= go by boat ============================== */
 
+/**************************************************************************
+  Move a ferry to a specified destination. The destination may be a land tile.
+  in which case the ferry should stop on an adjacent tile.
+  Return FALSE iff we died.
+**************************************************************************/
+static bool aiferry_goto(struct unit *punit, struct tile *ptile)
+{
+  struct pf_parameter parameter;
+  pft_fill_unit_overlap_param(&parameter, punit);
+  parameter.turn_mode = TM_WORST_TIME;
+  /* Move as far along the path to the destination as we can;
+   * that is, ignore the presence of enemy units when computing the
+   * path */
+  parameter.get_zoc = NULL;
+  return ai_unit_goto_constrained(punit, ptile, &parameter);
+}
+
 /****************************************************************************
   This function is to be called if punit needs to use a boat to get to the 
   destination.
@@ -395,10 +412,6 @@
   TODO: A big one is rendezvous points between units and boats.  When this is 
   implemented, we won't have to be at the coast to ask for a boat to come 
   to us.
-
-  You MUST have warmap created before calling this function in order for 
-  find_beachhead to work here.  This requirement should be removed.  For 
-  example, we can require that (dest_x,dest_y) is on a coast.  
 ****************************************************************************/
 bool aiferry_gobyboat(struct player *pplayer, struct unit *punit,
                      struct tile *dest_tile)
@@ -493,7 +506,7 @@
           ||((is_non_allied_city_tile(dest_tile, pplayer) 
               || is_non_allied_unit_tile(dest_tile, pplayer))
              && !unit_flag(punit, F_MARINES))) {
-        if (!find_beachhead(punit, dest_tile, &beach_tile)) {
+        if (!find_beachhead(ferryboat, punit, dest_tile, &beach_tile)) {
           /* Nowhere to go */
           return FALSE;
         }
@@ -529,7 +542,7 @@
         assert(same_pos(punit->tile, bodyguard->tile));
        handle_unit_load(pplayer, bodyguard->id, ferryboat->id);
       }
-      if (!ai_unit_goto(ferryboat, beach_tile)) {
+      if (!aiferry_goto(ferryboat, beach_tile)) {
         /* died */
         return FALSE;
       }
@@ -841,7 +854,7 @@
   if (aiferry_findcargo(punit)) {
     UNIT_LOG(LOGLEVEL_FERRY, punit, "picking up cargo (moves left: %d)",
             punit->moves_left);
-    ai_unit_goto(punit, punit->goto_tile);
+    aiferry_goto(punit, punit->goto_tile);
     return;
   }
 
@@ -852,7 +865,7 @@
       return;
     } else {
       UNIT_LOG(LOGLEVEL_FERRY, punit, "going to city that needs us");
-      (void) ai_unit_goto(punit, punit->goto_tile);
+      (void) aiferry_goto(punit, punit->goto_tile);
       return;
     }
   }
@@ -865,7 +878,7 @@
     if (pcity) {
       punit->goto_tile = pcity->tile;
       UNIT_LOG(LOGLEVEL_FERRY, punit, "No work, going home");
-      (void) ai_unit_goto(punit, pcity->tile);
+      (void) aiferry_goto(punit, pcity->tile);
     }
   }
  
diff -ru -Xvendor.freeciv.current/diff_ignore 
vendor.freeciv.current/ai/aihunt.c freeciv.PR11995/ai/aihunt.c
--- vendor.freeciv.current/ai/aihunt.c  2005-01-24 20:43:05.000000000 +0000
+++ freeciv.PR11995/ai/aihunt.c 2005-02-15 22:45:45.000000000 +0000
@@ -471,8 +471,15 @@
   }
 
   /* Go towards it. */
-  if (!ai_unit_goto(punit, target->tile)) {
-    return TRUE;
+  if (unit_type(punit)->move_type == LAND_MOVING) {
+    /* If necessary, use a ferry */
+    if (!ai_gothere(pplayer, punit, target->tile)) {
+      return TRUE;
+    }
+  } else {
+    if (!ai_unit_goto(punit, target->tile)) {
+      return TRUE;
+    }
   }
 
   /* Check if we can nuke it now */
diff -ru -Xvendor.freeciv.current/diff_ignore 
vendor.freeciv.current/ai/aitools.c freeciv.PR11995/ai/aitools.c
--- vendor.freeciv.current/ai/aitools.c 2005-02-13 15:07:21.000000000 +0000
+++ freeciv.PR11995/ai/aitools.c        2005-02-15 22:45:45.000000000 +0000
@@ -214,9 +214,6 @@
 
   TODO: A big one is rendezvous points.  When this is implemented, we won't
   have to be at the coast to ask for a boat to come to us.
-
-  You MUST have warmap created before calling this function in order for 
-  find_beachhead to work here. This requirement should be removed.
 ****************************************************************************/
 bool ai_gothere(struct player *pplayer, struct unit *punit,
                 struct tile *dest_tile)
@@ -269,30 +266,113 @@
 }
 
 /**************************************************************************
-  Go to specified destination but do not disturb existing role or activity
+  Returns the destination for a unit moving towards a given final destination.
+  That is, it gives a suitable waypoint, if necessary.
+  For example, aircraft need these waypoints to refuel.
+**************************************************************************/
+static struct tile *immediate_destination(struct unit *punit,
+                                         struct tile *dest_tile)
+{
+  if (!same_pos(punit->tile, dest_tile) && is_air_unit(punit)) {
+    struct tile *waypoint_tile = punit->goto_tile;
+    if (find_air_first_destination(punit, &waypoint_tile)) {
+      return waypoint_tile;
+    } else {
+      struct player *pplayer = unit_owner(punit);
+      freelog(LOG_VERBOSE, "Did not find an airroute for "
+             "%s's %s at (%d, %d) -> (%d, %d)",
+             pplayer->name, unit_type(punit)->name,
+             TILE_XY(punit->tile), TILE_XY(dest_tile));
+      /* Prevent take off */
+      return punit->tile;
+    }
+  }
+  /* else does not need waypoints */
+  return dest_tile;
+}
+
+/**************************************************************************
+  Go to specified destination, subject to given PF constraints,
+  but do not disturb existing role or activity
   and do not clear the role's destination. Return FALSE iff we died.
 
-  FIXME: add some logging functionality to replace GOTO_LOG()
+  parameter: the PF constraints on the computed path. The unit will move
+  as far along the computed path is it can; the movement code will impose
+  all the real constraints (ZOC, etc).
 **************************************************************************/
-bool ai_unit_goto(struct unit *punit, struct tile *ptile)
+bool ai_unit_goto_constrained(struct unit *punit, struct tile *ptile,
+                             struct pf_parameter *parameter)
 {
-  enum goto_result result;
+  bool alive = TRUE;
   struct tile *old_tile;
   enum unit_activity activity = punit->activity;
+  struct player *pplayer = unit_owner(punit);
+  struct pf_map *map = NULL;
+  struct pf_path *path = NULL;
+
+  assert(pplayer->ai.control);
+  assert(!unit_has_orders(punit));
+
+  ptile = immediate_destination(punit, ptile);
+
+  if (same_pos(punit->tile, ptile)) {
+    /* Not an error; sometimes immediate_destination instructs the unit
+     * to stay here. For example, to refuel.*/
+    send_unit_info(NULL, punit);
+    return TRUE;
+  } else if (!goto_is_sane(punit, ptile, FALSE)) {
+    punit->activity = ACTIVITY_IDLE;
+    send_unit_info(NULL, punit);
+    return TRUE;
+  } else if(punit->moves_left == 0) {
+    send_unit_info(NULL, punit);
+    return TRUE;
+  }
 
   old_tile = punit->goto_tile; /* May be NULL. */
 
   CHECK_UNIT(punit);
-  /* TODO: log error on same_pos with punit->x|y */
   punit->goto_tile = ptile;
   handle_unit_activity_request(punit, ACTIVITY_GOTO);
-  result = do_unit_goto(punit, GOTO_MOVE_ANY, FALSE);
-  if (result != GR_DIED) {
+
+  map = pf_create_map(parameter);
+  path = pf_get_path(map, ptile);
+
+  if (path) {
+    alive = ai_unit_execute_path(punit, path);
+  } else {
+    UNIT_LOG(LOG_DEBUG, punit, "no path to destination");
+  }
+
+  pf_destroy_path(path);
+  pf_destroy_map(map);
+
+  if (alive) {
+    handle_unit_activity_request(punit, ACTIVITY_IDLE);
+    send_unit_info(NULL, punit);
     handle_unit_activity_request(punit, activity);
     punit->goto_tile = old_tile; /* May be NULL. */
-    return TRUE;
+    send_unit_info(NULL, punit);
   }
-  return FALSE;
+
+  return alive;
+}
+
+/**************************************************************************
+  Go to specified destination but do not disturb existing role or activity
+  and do not clear the role's destination. Return FALSE iff we died.
+**************************************************************************/
+bool ai_unit_goto(struct unit *punit, struct tile *ptile)
+{
+  struct pf_parameter parameter;
+  pft_fill_unit_parameter(&parameter, punit);
+  /* Be optimisitic; allows attacks across dangerous terrain */
+  parameter.is_pos_dangerous = NULL;
+  /* Move as far along the path to the destination as we can;
+   * that is, ignore the presence of enemy units when computing the
+   * path */
+  parameter.get_zoc = NULL;
+  return ai_unit_goto_constrained(punit, ptile, &parameter);
 }
 
 /**************************************************************************
diff -ru -Xvendor.freeciv.current/diff_ignore 
vendor.freeciv.current/ai/aitools.h freeciv.PR11995/ai/aitools.h
--- vendor.freeciv.current/ai/aitools.h 2005-02-13 15:07:21.000000000 +0000
+++ freeciv.PR11995/ai/aitools.h        2005-02-15 22:45:45.000000000 +0000
@@ -21,6 +21,7 @@
 
 struct ai_choice;
 struct pf_path;
+struct pf_parameter;
 
 #ifdef DEBUG
 #define CHECK_UNIT(punit)                                        \
@@ -44,6 +45,8 @@
 bool ai_unit_execute_path(struct unit *punit, struct pf_path *path);
 bool ai_gothere(struct player *pplayer, struct unit *punit, 
                 struct tile *dst_tile);
+bool ai_unit_goto_constrained(struct unit *punit, struct tile *ptile,
+                             struct pf_parameter *parameter);
 bool ai_unit_goto(struct unit *punit, struct tile *ptile);
 
 void ai_unit_new_role(struct unit *punit, enum ai_unit_task task, 
diff -ru -Xvendor.freeciv.current/diff_ignore 
vendor.freeciv.current/ai/aiunit.c freeciv.PR11995/ai/aiunit.c
--- vendor.freeciv.current/ai/aiunit.c  2005-02-13 15:07:21.000000000 +0000
+++ freeciv.PR11995/ai/aiunit.c 2005-02-15 22:45:45.000000000 +0000
@@ -804,7 +804,7 @@
 
   if (!same_pos(punit->tile, ptile)) {
     if (goto_is_sane(punit, ptile, TRUE)) {
-      if (!ai_unit_goto(punit, ptile)) {
+      if (!ai_gothere(pplayer, punit, ptile)) {
         /* We died */
         return;
       }
@@ -821,23 +821,58 @@
 }
 
 /*************************************************************************
+  If the given ferry were to travel to the given beach head,
+  how long would it take?
+**************************************************************************/
+static unsigned int beachhead_time(struct unit *ferryboat, 
+                                  struct pf_map *pf_map,
+                                  struct tile *beachhead_tile)
+{
+  struct pf_path *path;
+  unsigned int time = FC_INFINITY;
+  path = pf_get_path(pf_map, beachhead_tile);
+  if (path) {
+    time = SINGLE_MOVE * path->length / unit_move_rate(ferryboat);
+  }
+  pf_destroy_path(path);
+  return time;
+}
+
+/*************************************************************************
   Tries to find a land tile adjacent to water and to our target 
-  (dest_x, dest_y).  Prefers tiles which are more defensible and/or
+  (dest_tile).  Prefers tiles which are more defensible and/or
   where we will have moves left.
   FIXME: It checks if the ocean tile is in our Zone of Control?!
 **************************************************************************/
-bool find_beachhead(struct unit *punit, struct tile *dest_tile,
+bool find_beachhead(struct unit *ferryboat, struct unit *punit,
+                   struct tile *dest_tile,
                    struct tile **beachhead_tile)
 {
   int ok, best = 0;
   Terrain_type_id t;
+  struct pf_parameter parameter;
+  struct pf_map *pf_map;
 
+  pft_fill_unit_overlap_param(&parameter, ferryboat);
+  parameter.turn_mode = TM_WORST_TIME;
+  /* Move as far along the path to the destination as we can;
+   * that is, ignore the presence of enemy units when computing the
+   * path */
+  parameter.get_zoc = NULL;
+
+  pf_map = pf_create_map(&parameter);
+
+  assert(ferryboat);
   CHECK_UNIT(punit);
 
   adjc_iterate(dest_tile, tile1) {
+    int time = FC_INFINITY;
     ok = 0;
     t = map_get_terrain(tile1);
-    if (WARMAP_SEACOST(tile1) <= 6 * THRESHOLD && !is_ocean(t)) {
+    if (!is_ocean(t)) {
+      time = beachhead_time(ferryboat, pf_map, tile1);
+    }
+    if (time < FC_INFINITY) {
       /* accessible beachhead */
       adjc_iterate(tile1, tile2) {
        if (is_ocean(map_get_terrain(tile2))
@@ -860,7 +895,7 @@
         if (get_tile_type(t)->movement_cost * SINGLE_MOVE <
             unit_move_rate(punit))
          ok *= 8;
-        ok += (6 * THRESHOLD - WARMAP_SEACOST(tile1));
+        ok = ok - 6 * time;
         if (ok > best) {
          best = ok;
          *beachhead_tile = tile1;
@@ -869,6 +904,8 @@
     }
   } adjc_iterate_end;
 
+  pf_destroy_map(pf_map);
+
   return (best > 0);
 }
 
@@ -1613,7 +1650,7 @@
            * to the city and an available ocean tile */
          struct tile *btile;
 
-          if (find_beachhead(punit, acity->tile, &btile)) { 
+          if (find_beachhead(ferryboat, punit, acity->tile, &btile)) { 
             best = want;
            *dest_tile = acity->tile;
             /* the ferryboat needs to target the beachhead, but the unit 
@@ -1859,7 +1896,7 @@
         (void) ai_gothere(pplayer, punit, pc->tile);
       } else {
         /* sometimes find_beachhead is not enough */
-        if (!find_beachhead(punit, pc->tile, &ftile)) {
+        if (!find_beachhead(punit, punit, pc->tile, &ftile)) {
           find_city_beach(pc, punit, &ftile);
         }
         UNIT_LOG(LOG_DEBUG, punit, "Barbarian sailing to %s", pc->name);
diff -ru -Xvendor.freeciv.current/diff_ignore 
vendor.freeciv.current/ai/aiunit.h freeciv.PR11995/ai/aiunit.h
--- vendor.freeciv.current/ai/aiunit.h  2005-02-13 15:07:21.000000000 +0000
+++ freeciv.PR11995/ai/aiunit.h 2005-02-15 22:45:45.000000000 +0000
@@ -62,7 +62,8 @@
                         Unit_Type_id enemy_type);
 int find_something_to_kill(struct player *pplayer, struct unit *punit, 
                           struct tile **ptile);
-bool find_beachhead(struct unit *punit, struct tile *dst_tile,
+bool find_beachhead(struct unit *ferryboat, struct unit *punit,
+                   struct tile *dst_tile,
                    struct tile **ptile);
 
 int build_cost_balanced(Unit_Type_id type);
diff -ru -Xvendor.freeciv.current/diff_ignore 
vendor.freeciv.current/common/aicore/pf_tools.c 
freeciv.PR11995/common/aicore/pf_tools.c
--- vendor.freeciv.current/common/aicore/pf_tools.c     2005-01-24 
20:43:03.000000000 +0000
+++ freeciv.PR11995/common/aicore/pf_tools.c    2005-02-15 22:45:44.000000000 
+0000
@@ -396,6 +396,8 @@
 /**********************************************************************
   An example of position-dangerous callback.  For triremes.
   FIXME: it cheats.
+  Allow one move onto land (for use for ferries and land
+  bombardment)
 ***********************************************************************/
 static bool trireme_is_pos_dangerous(const struct tile *ptile,
                                     enum known_type known,
@@ -404,13 +406,31 @@
   /* We test TER_UNSAFE even though under the current ruleset there is no
    * way for a trireme to be on a TER_UNSAFE tile. */
   /* Unsafe or unsafe-ocean tiles without cities are dangerous. */
-  return ((terrain_has_flag(ptile->terrain, TER_UNSAFE) 
-         || (is_ocean(ptile->terrain) && !is_safe_ocean(ptile)))
+  /* Pretend all land tiles are safe. */
+  return (is_ocean(ptile->terrain)
+         && (terrain_has_flag(ptile->terrain, TER_UNSAFE) 
+             || (is_ocean(ptile->terrain) && !is_safe_ocean(ptile)))
          && ptile->city == NULL);
 }
 
 /**********************************************************************
-  Position-dangerous callback for all units other than triremes.
+  Position-dangerous callback for sea units other than triremes.
+  Allow one move onto land (for use for ferries and land
+  bombardment)
+***********************************************************************/
+static bool is_overlap_pos_dangerous(const struct tile *ptile,
+                                    enum known_type known,
+                                    struct pf_parameter *param)
+{
+  /* Unsafe tiles without cities are dangerous. */
+  /* Pretend all land tiles are safe. */
+  return (is_ocean(ptile->terrain)
+         && terrain_has_flag(ptile->terrain, TER_UNSAFE)
+         && ptile->city == NULL);
+}
+
+/**********************************************************************
+  Position-dangerous callback for typical units.
 ***********************************************************************/
 static bool is_pos_dangerous(const struct tile *ptile, enum known_type known,
                             struct pf_parameter *param)
@@ -476,28 +496,37 @@
 void pft_fill_unit_overlap_param(struct pf_parameter *parameter,
                                 struct unit *punit)
 {
+  const bool trireme_danger = unit_flag(punit, F_TRIREME)
+                     && base_trireme_loss_pct(unit_owner(punit), punit) > 0;
+  const bool danger = base_unsafe_terrain_loss_pct(unit_owner(punit), punit)
+                      > 0;
+
   pft_fill_unit_default_parameter(parameter, punit);
 
   switch (unit_type(punit)->move_type) {
   case LAND_MOVING:
     parameter->get_MC = land_overlap_move;
     parameter->get_TB = dont_cross_ocean;
+
+    assert(!trireme_danger);
+    if (danger) {
+      parameter->is_pos_dangerous = is_pos_dangerous;
+    }
     break;
   case SEA_MOVING:
     parameter->get_MC = sea_overlap_move;
+
+    if (trireme_danger) {
+      parameter->is_pos_dangerous = trireme_is_pos_dangerous;
+    } else if (danger) {
+      parameter->is_pos_dangerous = is_overlap_pos_dangerous;
+    }
     break;
   default:
     die("Unsupported move_type");
   }
 
   parameter->get_zoc = NULL;
-
-  if (unit_flag(punit, F_TRIREME)
-      && base_trireme_loss_pct(unit_owner(punit), punit) > 0) {
-    parameter->is_pos_dangerous = trireme_is_pos_dangerous;
-  } else if (base_unsafe_terrain_loss_pct(unit_owner(punit), punit) > 0) {
-    parameter->is_pos_dangerous = is_pos_dangerous;
-  }
 }
 
 /**********************************************************************
diff -ru -Xvendor.freeciv.current/diff_ignore 
vendor.freeciv.current/server/unittools.c freeciv.PR11995/server/unittools.c
--- vendor.freeciv.current/server/unittools.c   2005-02-15 21:55:28.000000000 
+0000
+++ freeciv.PR11995/server/unittools.c  2005-02-15 22:45:18.000000000 +0000
@@ -1917,8 +1917,8 @@
 
 /**************************************************************************
   Send the unit into to those connections in dest which can see the units
-  at it's position, or the specified (x,y) (if different).
-  Eg, use x and y as where the unit came from, so that the info can be
+  at it's position, or the specified ptile (if different).
+  Eg, use ptile as where the unit came from, so that the info can be
   sent if the other players can see either the target or destination tile.
   dest = NULL means all connections (game.game_connections)
 **************************************************************************/