[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 the patch.
* ai_unit_goto uses PF instead of Warmap
* the ferry code uses an amphibious PF
* the PF code uses an extra-cost callback to discourage creation of tall 
stacks.

I tried to completely prevent tall stacks by creating an 
is_pos_dangerous callback function that marked all tiles with tall 
stacks as dangerous. I couldn't get it to work for amphibious movement 
with fast ferries (>3 tiles/turn). I suspect an overflow bug, or perhaps 
a bug in PF itself, but despite considerable effort I couldn't track it 
down. Perhaps someone else will have more luck.

The settler code could use the amphibious PF to consider settling cities 
overease that are not on the coast.

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-22 23:17:36.000000000 +0000
@@ -270,7 +270,7 @@
   Runs a few checks to determine if "boat" is a free boat that can carry
   "cap" units of the same type as "punit" (the last one isn't implemented).
 ****************************************************************************/
-static bool is_boat_free(struct unit *boat, struct unit *punit, int cap)
+bool is_boat_free(struct unit *boat, struct unit *punit, int cap)
 {
   /* - Only ground-unit transporters are consider.
    * - Units with orders are skipped (the AI doesn't control units with
@@ -386,6 +386,61 @@
 
 /* ============================= 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;
+  struct pft_stack_cost stack_cost;
+
+  pft_fill_unit_overlap_param(&parameter, punit);
+  pft_no_tall_stacks(&parameter, &stack_cost, punit,
+                    FERRY_STACKING_STRICTNESS);
+
+  /* Must use TM_WORST_TIME, so triremes move safely */
+  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;
+  /* Ferries are not warships: */
+  parameter.get_TB = no_fights;
+
+  punit->goto_tile = ptile;
+  return ai_unit_goto_constrained(punit, ptile, &parameter);
+}
+
+/**************************************************************************
+  Move a passenger on a ferry to a specified destination.
+  Return FALSE iff we died.
+**************************************************************************/
+static bool aiferry_goto_amphibious(struct unit *ferry,
+                                   struct unit *passenger, struct tile *ptile)
+{
+  struct pft_amphibious parameter;
+  struct pft_stack_cost land_stack_cost;
+  struct pft_stack_cost sea_stack_cost;
+
+  pft_fill_amphibious_parameter(&parameter, ferry, passenger);
+  pft_no_tall_stacks(&parameter.sea, &sea_stack_cost, ferry,
+                    FERRY_STACKING_STRICTNESS);
+  pft_no_tall_stacks(&parameter.land, &land_stack_cost, passenger,
+                    LAND_STACKING_STRICTNESS);
+
+  /* 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.combined.get_zoc = NULL;
+  parameter.land.get_zoc = NULL;
+  parameter.sea.get_zoc = NULL;
+
+  ferry->goto_tile = ptile;
+  return ai_amphibious_goto_constrained(ferry, passenger, ptile, &parameter);
+}
+
 /****************************************************************************
   This function is to be called if punit needs to use a boat to get to the 
   destination.
@@ -395,10 +450,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)
@@ -478,7 +529,6 @@
 
     /* Check if we are the passenger-in-charge */
     if (is_boat_free(ferryboat, punit, 0)) {
-      struct tile *beach_tile;     /* Destination for the boat */
       struct unit *bodyguard = find_unit_by_id(punit->ai.bodyguard);
 
       UNIT_LOG(LOGLEVEL_GOBYBOAT, punit, 
@@ -486,24 +536,6 @@
                ferryboat->id, ferryboat->moves_left, TILE_XY(dest_tile));
       aiferry_psngr_meet_boat(punit, ferryboat);
 
-      /* If the location is not accessible directly from sea
-       * or is defended and we are not marines, we will need a 
-       * landing beach */
-      if (!is_ocean_near_tile(dest_tile)
-          ||((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)) {
-          /* Nowhere to go */
-          return FALSE;
-        }
-        UNIT_LOG(LOGLEVEL_GOBYBOAT, punit, 
-                 "Found beachhead (%d,%d)", TILE_XY(beach_tile));
-      } else {
-       beach_tile = dest_tile;
-      }
-
-      ferryboat->goto_tile = beach_tile;
       punit->goto_tile = dest_tile;
       /* Grab bodyguard */
       if (bodyguard
@@ -529,14 +561,12 @@
         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_amphibious(ferryboat, punit, dest_tile)) {
         /* died */
         return FALSE;
       }
-      if (!is_tiles_adjacent(ferryboat->tile, beach_tile)
-          && !same_pos(ferryboat->tile, beach_tile)) {
-        /* We are in still transit */
-        return FALSE;
+      if (same_pos(punit->tile, dest_tile)) {
+       handle_unit_activity_request(punit, ACTIVITY_IDLE);
       }
     } else {
       /* Waiting for the boss to load and move us */
@@ -545,10 +575,6 @@
                ferryboat->id, ferryboat->ai.passenger);
       return FALSE;
     }
-
-    UNIT_LOG(LOGLEVEL_GOBYBOAT, punit, "Our boat has arrived "
-            "[%d](moves left: %d)", ferryboat->id, ferryboat->moves_left);
-    handle_unit_activity_request(punit, ACTIVITY_IDLE);
   }
 
   return TRUE;
@@ -841,7 +867,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 +878,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 +891,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/aiferry.h freeciv.PR11995/ai/aiferry.h
--- vendor.freeciv.current/ai/aiferry.h 2005-01-24 20:43:05.000000000 +0000
+++ freeciv.PR11995/ai/aiferry.h        2005-02-22 23:17:36.000000000 +0000
@@ -41,6 +41,8 @@
 bool aiferry_gobyboat(struct player *pplayer, struct unit *punit,
                      struct tile *dst_tile);
 
+bool is_boat_free(struct unit *boat, struct unit *punit, int cap);
+
 /*
  * Main boat managing function.  Gets units on board to where they want to
  * go and then looks for new passengers or (if it fails) for a city which
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-22 23:17:36.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-22 23:17:36.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,189 @@
 }
 
 /**************************************************************************
-  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.
+  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;
+}
 
-  FIXME: add some logging functionality to replace GOTO_LOG()
+/**************************************************************************
+  Move a unit along a path without disturbing its activity, role
+  or assigned destination
+  Return FALSE iff we died.
 **************************************************************************/
-bool ai_unit_goto(struct unit *punit, struct tile *ptile)
+static bool follow_path(struct unit *punit, struct pf_path *path,
+                       struct tile *ptile)
 {
-  enum goto_result result;
-  struct tile *old_tile;
+  struct tile *old_tile = punit->goto_tile;
   enum unit_activity activity = punit->activity;
-
-  old_tile = punit->goto_tile; /* May be NULL. */
-
-  CHECK_UNIT(punit);
-  /* TODO: log error on same_pos with punit->x|y */
+  bool alive;
   punit->goto_tile = ptile;
   handle_unit_activity_request(punit, ACTIVITY_GOTO);
-  result = do_unit_goto(punit, GOTO_MOVE_ANY, FALSE);
-  if (result != GR_DIED) {
+  alive = ai_unit_execute_path(punit, path);
+  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. */
+    send_unit_info(NULL, punit);
+  }
+  return alive;
+}
+
+/**************************************************************************
+  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.
+
+  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_constrained(struct unit *punit, struct tile *ptile,
+                             struct pf_parameter *parameter)
+{
+  bool alive = TRUE;
+  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;
   }
-  return FALSE;
+
+  map = pf_create_map(parameter);
+  path = pf_get_path(map, ptile);
+
+  if (path) {
+    alive = follow_path(punit, path, ptile);
+  } else {
+    UNIT_LOG(LOG_DEBUG, punit, "no path to destination");
+  }
+
+  pf_destroy_path(path);
+  pf_destroy_map(map);
+
+  return alive;
+}
+
+/*
+ * WAG: how hard to avoid tall stacks of units.
+ */
+#define STACKING_STRICTNESS (PF_TURN_FACTOR / 360)
+/**************************************************************************
+  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;
+  struct pft_stack_cost stack_cost;
+
+  pft_fill_unit_parameter(&parameter, punit);
+  pft_no_tall_stacks(&parameter, &stack_cost, punit, STACKING_STRICTNESS);
+  /* Be optimisitic; allows attacks across dangerous terrain,
+   * and polar settlements. */
+  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);
+}
+
+/**************************************************************************
+  Move a passenger on a ferry to a specified destination.
+  The destination may be in land, in which case the passenger will ride
+  the ferry to a beach head, disembark, then continue on land.
+  Return FALSE iff we died.
+**************************************************************************/
+bool ai_amphibious_goto_constrained(struct unit *ferry,
+                                   struct unit *passenger,
+                                   struct tile *ptile,
+                                   struct pft_amphibious *parameter)
+{
+  bool alive = TRUE;
+  struct player *pplayer = unit_owner(passenger);
+  struct pf_map *map = NULL;
+  struct pf_path *path = NULL;
+
+  assert(pplayer->ai.control);
+  assert(!unit_has_orders(passenger));
+
+  ptile = immediate_destination(passenger, ptile);
+
+  if (same_pos(passenger->tile, ptile)) {
+    /* Not an error; sometimes immediate_destination instructs the unit
+     * to stay here. For example, to refuel.*/
+    send_unit_info(NULL, passenger);
+    return TRUE;
+  } else if (passenger->moves_left == 0 && ferry->moves_left == 0) {
+    send_unit_info(NULL, passenger);
+    return TRUE;
+  }
+
+  map = pf_create_map(&parameter->combined);
+  path = pf_get_path(map, ptile);
+
+  if (path) {
+    /* Sea leg */
+    alive = follow_path(ferry, path, ptile);
+    if (alive && passenger->tile != ptile) {
+      pft_advance_path(path, passenger->tile);
+      if (!is_ocean(path->positions[1].tile->terrain)) {
+       UNIT_LOG(LOG_DEBUG, passenger, "Our boat has arrived "
+                "[%d](moves left: %d)", ferry->id, ferry->moves_left);
+       UNIT_LOG(LOG_DEBUG, passenger, "Disembarking to (%d,%d)",
+                TILE_XY(path->positions[1].tile));
+       /* Land leg */
+       alive = follow_path(passenger, path, ptile);
+      }
+      /* else at se */
+    }
+  } else {
+    /* Not always an error; enemy units might block all paths. */
+    UNIT_LOG(LOG_DEBUG, passenger, "no path to destination");
+  }
+
+  pf_destroy_path(path);
+  pf_destroy_map(map);
+
+  return alive;
 }
 
 /**************************************************************************
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-22 23:17:36.000000000 +0000
@@ -21,6 +21,8 @@
 
 struct ai_choice;
 struct pf_path;
+struct pf_parameter;
+struct pft_amphibious;
 
 #ifdef DEBUG
 #define CHECK_UNIT(punit)                                        \
@@ -44,6 +46,12 @@
 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_amphibious_goto_constrained(struct unit *ferry,
+                                   struct unit *passenger,
+                                   struct tile *ptile,
+                                   struct pft_amphibious *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-22 23:17:36.000000000 +0000
@@ -658,6 +658,7 @@
   return 0;
 }
 
+
 /*************************************************************************
   Look for worthy targets within a one-turn horizon.
 *************************************************************************/
@@ -667,6 +668,7 @@
   struct pf_map *tgt_map;
   struct pf_path *path = NULL;
   struct pf_parameter parameter;
+  struct pft_stack_cost stack_cost;
   /* Coordinates of the best target (initialize to silence compiler) */
   struct tile *ptile = punit->tile;
   /* Want of the best target */
@@ -674,6 +676,7 @@
   struct player *pplayer = unit_owner(punit);
  
   pft_fill_unit_attack_param(&parameter, punit);
+  pft_no_tall_stacks(&parameter, &stack_cost, punit, LAND_STACKING_STRICTNESS);
   
   tgt_map = pf_create_map(&parameter);
   while (pf_next(tgt_map)) {
@@ -804,7 +807,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;
       }
@@ -822,12 +825,12 @@
 
 /*************************************************************************
   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,
-                   struct tile **beachhead_tile)
+static bool find_beachhead(struct unit *punit, struct tile *dest_tile,
+                          struct tile **beachhead_tile)
 {
   int ok, best = 0;
   Terrain_type_id t;
@@ -872,32 +875,6 @@
   return (best > 0);
 }
 
-/**************************************************************************
-find_beachhead() works only when city is not further that 1 tile from
-the sea. But Sea Raiders might want to attack cities inland.
-So this finds the nearest land tile on the same continent as the city.
-**************************************************************************/
-static void find_city_beach(struct city *pc, struct unit *punit,
-                           struct tile **dest_tile)
-{
-  struct tile *best_tile = punit->tile;
-  int dist = 100;
-  int search_dist = real_map_distance(pc->tile, punit->tile) - 1;
-
-  CHECK_UNIT(punit);
-  
-  square_iterate(punit->tile, search_dist, tile1) {
-    if (map_get_continent(tile1) == map_get_continent(pc->tile)
-        && real_map_distance(punit->tile, tile1) < dist) {
-
-      dist = real_map_distance(punit->tile, tile1);
-      best_tile = tile1;
-    }
-  } square_iterate_end;
-
-  *dest_tile = best_tile;
-}
-
 /*************************************************************************
   Does the unit with the id given have the flag L_DEFEND_GOOD?
 **************************************************************************/
@@ -1848,22 +1825,34 @@
       UNIT_LOG(LOG_DEBUG, punit, "nothing to do - no more exploring either");
     }
   } else {
+    /* Barbarian */
     /* You can still have some moves left here, but barbarians should
        not sit helplessly, but advance towards nearest known enemy city */
     struct city *pc;
-    struct tile *ftile;
 
     if ((pc = dist_nearest_city(pplayer, punit->tile, FALSE, TRUE))) {
       if (!is_ocean(map_get_terrain(punit->tile))) {
         UNIT_LOG(LOG_DEBUG, punit, "Barbarian marching to conquer %s", 
pc->name);
         (void) ai_gothere(pplayer, punit, pc->tile);
       } else {
-        /* sometimes find_beachhead is not enough */
-        if (!find_beachhead(punit, pc->tile, &ftile)) {
-          find_city_beach(pc, punit, &ftile);
-        }
-        UNIT_LOG(LOG_DEBUG, punit, "Barbarian sailing to %s", pc->name);
-        (void) ai_gothere(pplayer, punit, ftile);
+       struct unit *ferry = NULL;
+       unit_list_iterate(punit->tile->units, aunit) {
+         if (is_boat_free(aunit, punit, 2)) {
+           ferry = aunit;
+           break;
+         }
+       } unit_list_iterate_end;
+       if (ferry) {
+         struct pft_amphibious parameter;
+         UNIT_LOG(LOG_DEBUG, punit, "Barbarian sailing to conquer %s",
+                  pc->name);
+         pft_fill_amphibious_parameter(&parameter, ferry, punit);
+         /* Barbarians bravely/stupidly do not avoid creating tall stacks */
+         (void)ai_amphibious_goto_constrained(punit, punit,
+                                              pc->tile, &parameter);
+       } else {
+         UNIT_LOG(LOG_ERROR, punit, "unable to find barbarian ferry");
+       }
       }
     }
   }
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-22 23:17:36.000000000 +0000
@@ -62,8 +62,6 @@
                         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,
-                   struct tile **ptile);
 
 int build_cost_balanced(Unit_Type_id type);
 int unittype_att_rating(Unit_Type_id type, int veteran,
diff -ru -Xvendor.freeciv.current/diff_ignore 
vendor.freeciv.current/common/aicore/path_finding.c 
freeciv.PR11995/common/aicore/path_finding.c
--- vendor.freeciv.current/common/aicore/path_finding.c 2005-01-24 
20:45:28.000000000 +0000
+++ freeciv.PR11995/common/aicore/path_finding.c        2005-02-22 
23:17:35.000000000 +0000
@@ -222,11 +222,15 @@
     /* 2 means can move unrestricted from/into it, 
      * 1 means can move unrestricted into it, but not necessarily from it */
     node->zoc_number = (my_zoc ? 2 : (occupied ? 1 : 0));
+  } else {
+    node->zoc_number = 0;
   }
 
   /* Evaluate the extra cost of the destination */
   if (params->get_EC) {
     node->extra_tile = params->get_EC(ptile, node->node_known_type, params);
+  } else {
+    node->extra_tile = 0;
   }
 }
 
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-22 23:17:35.000000000 
+0000
@@ -18,6 +18,7 @@
 #include <assert.h>
 #include <string.h>
 
+#include "combat.h"
 #include "mem.h"
 
 #include "pf_tools.h"
@@ -26,6 +27,28 @@
 static void pft_fill_unit_default_parameter(struct pf_parameter *parameter,
                                            struct unit *punit);
 
+
+/*********************************************************************
+  Stack danger cost. How undesirable is being on a tile
+  because of danger of attack?
+  Assume all tiles are equally likely to be attacked,
+  and weight by the cost of destruction.
+*********************************************************************/
+static int stack_danger(const struct tile *ptile,
+                       struct pft_stack_cost *stack_cost,
+                       struct pf_parameter *param)
+{
+  int cost = stack_cost->base_cost;
+  if (is_stack_vulnerable(ptile)) {
+    unit_list_iterate(ptile->units, punit) {
+      if (unit_owner(punit) == param->owner) {
+       cost += unit_build_shield_cost(punit->type);
+      }
+    } unit_list_iterate_end;
+  }
+  return cost * stack_cost->strictness;
+}
+
 /* ===================== Move Cost Callbacks ========================= */
 
 /*************************************************************
@@ -36,10 +59,8 @@
 static int seamove(const struct tile *ptile, enum direction8 dir,
                    const struct tile *ptile1, struct pf_parameter *param)
 {
-  /* MOVE_COST_FOR_VALID_SEA_STEP means ships can move between */
-  if (ptile->move_cost[dir] == MOVE_COST_FOR_VALID_SEA_STEP
-      || is_non_allied_unit_tile(ptile1, param->owner)
-      || is_non_allied_city_tile(ptile1, param->owner)) {
+  if (is_ocean(ptile1->terrain) || ptile1->city
+      || is_non_allied_unit_tile(ptile1, param->owner)) {
     return SINGLE_MOVE;
   } else {
     return PF_IMPOSSIBLE_MC;
@@ -323,6 +344,49 @@
 #endif
 
 
+/*************************************************************
+  A cost function for amphibious movement.
+*************************************************************/
+static int amphibious_move(const struct tile *ptile, enum direction8 dir,
+                          const struct tile *ptile1,
+                          struct pf_parameter *param)
+{
+  const bool ocean = is_ocean(ptile->terrain);
+  const bool ocean1 = is_ocean(ptile1->terrain);
+  struct pft_amphibious *amphibious = (struct pft_amphibious *)param->data;
+  int cost, scale;
+
+  if (ocean && ocean1) {
+    /* Sea move */
+    cost = amphibious->sea.get_MC(ptile, dir, ptile1, &amphibious->sea);
+    scale = amphibious->sea_scale;
+  } else if (ocean && is_allied_city_tile(ptile1, param->owner)) {
+    /* Entering port */
+    cost = amphibious->sea.get_MC(ptile, dir, ptile1, &amphibious->sea);
+    scale = amphibious->sea_scale;
+  } else if (ocean) {
+    /* Disembark; use land movement function to handle F_MARINES */
+    cost = amphibious->land.get_MC(ptile, dir, ptile1, &amphibious->land);
+    scale = amphibious->land_scale;
+  } else if (is_allied_city_tile(ptile, param->owner) && ocean1) {
+    /* Leaving port */
+    cost = amphibious->sea.get_MC(ptile, dir, ptile1, &amphibious->sea);
+    scale = amphibious->sea_scale;
+  } else if (ocean1) {
+    /* Now we have disembarked, our ferry can not help us */
+    cost = PF_IMPOSSIBLE_MC;
+    scale = amphibious->land_scale;
+  } else {
+    /* land move */
+    cost = amphibious->land.get_MC(ptile, dir, ptile1, &amphibious->land);
+    scale = amphibious->land_scale;
+  }
+  if (cost != PF_IMPOSSIBLE_MC) {
+    cost *= scale;
+  }
+  return cost;
+}
+
 /* ===================== Extra Cost Callbacks ======================== */
 
 /*********************************************************************
@@ -342,6 +406,50 @@
 }
 #endif
 
+/*********************************************************************
+  Extra cost call back to avoid creating tall stacks.
+  By setting this as an extra-cost call-back, paths will avoid tall stacks.
+  Avoiding tall stacks *all* along a path is useful because a unit following a
+  path might have to stop early because of ZoC or random movement.
+*********************************************************************/
+static int prefer_short_stacks(const struct tile *ptile,
+                              enum known_type known,
+                              struct pf_parameter *param)
+{
+  return stack_danger(ptile, (struct pft_stack_cost *)param->data, param);
+}
+
+/*********************************************************************
+  Extra cost call back for amphibious movement
+*********************************************************************/
+static int amphibious_extra_cost(const struct tile *ptile,
+                                enum known_type known,
+                                struct pf_parameter *param)
+{
+  struct pft_amphibious *amphibious = (struct pft_amphibious *)param->data;
+  const bool ocean = is_ocean(ptile->terrain);
+  int cost, scale;
+  if (known == TILE_UNKNOWN) {
+    /* We can travel almost anywhere */
+    cost = SINGLE_MOVE;
+    scale = MAX(amphibious->sea_scale, amphibious->land_scale);
+  } else if (ocean && amphibious->sea.get_EC) {
+    cost = amphibious->sea.get_EC(ptile, known, &amphibious->sea);
+    scale = amphibious->sea_scale;
+  } else if (!ocean && amphibious->land.get_EC) {
+    cost = amphibious->land.get_EC(ptile, known, &amphibious->land);
+    scale = amphibious->land_scale;
+  } else {
+    cost = 0;
+    scale = 1;
+  }
+
+  if (cost != PF_IMPOSSIBLE_MC) {
+    cost *= scale;
+  }
+  return cost;
+}
+
 
 /* ===================== Tile Behaviour Callbacks ==================== */
 
@@ -390,12 +498,44 @@
   return TB_NORMAL;
 }
 
+/********************************************************************** 
+  PF callback to prohibit attacking anyone, except at the destination.
+***********************************************************************/
+enum tile_behavior no_intermediate_fights(const struct tile *ptile,
+                                         enum known_type known,
+                                         struct pf_parameter *param)
+{
+  if (is_non_allied_unit_tile(ptile, param->owner)
+      || is_non_allied_city_tile(ptile, param->owner)) {
+    return TB_DONT_LEAVE;
+  }
+  return TB_NORMAL;
+}
+
+/*********************************************************************
+  A callback for amphibious movement
+*********************************************************************/
+static enum tile_behavior amphibious_behaviour(const struct tile *ptile,
+                                              enum known_type known,
+                                              struct pf_parameter *param)
+{
+  struct pft_amphibious *amphibious = (struct pft_amphibious *)param->data;
+  const bool ocean = is_ocean(ptile->terrain);
+  if (ocean && amphibious->sea.get_TB) {
+    return amphibious->sea.get_TB(ptile, known, &amphibious->sea);
+  } else if (!ocean && amphibious->land.get_TB) {
+    return amphibious->land.get_TB(ptile, known, &amphibious->land);
+  }
+  return TB_NORMAL;
+}
 
 /* =====================  Postion Dangerous Callbacks ================ */
 
 /**********************************************************************
   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 +544,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 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 all units other than triremes.
+  Position-dangerous callback for typical units.
 ***********************************************************************/
 static bool is_pos_dangerous(const struct tile *ptile, enum known_type known,
                             struct pf_parameter *param)
@@ -420,6 +578,23 @@
          && ptile->city == NULL);
 }
 
+/**********************************************************************
+  Position-dangerous callback for amphibious movement.
+***********************************************************************/
+static bool amphibious_is_pos_dangerous(const struct tile *ptile,
+                                       enum known_type known,
+                                       struct pf_parameter *param)
+{
+  struct pft_amphibious *amphibious = (struct pft_amphibious *)param->data;
+  const bool ocean = is_ocean(ptile->terrain);
+  if (ocean && amphibious->sea.is_pos_dangerous) {
+    return amphibious->sea.is_pos_dangerous(ptile, known, param);
+  } else if (!ocean && amphibious->land.is_pos_dangerous) {
+    return amphibious->land.is_pos_dangerous(ptile, known, param);
+  }
+  return FALSE;
+}
+
 /* =====================  Tools for filling parameters =============== */
 
 /**********************************************************************
@@ -476,28 +651,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;
-  }
 }
 
 /**********************************************************************
@@ -531,6 +715,51 @@
 }
 
 /**********************************************************************
+  Fill parameters for combined sea-land movement.
+  One complexity of amphibious movement is that the movemnet rate on land
+  might be different from that at sea. We therefore scale up the movement rates
+  (and the corresponding movement consts) to the product of the two rates.
+***********************************************************************/
+void pft_fill_amphibious_parameter(struct pft_amphibious *parameter,
+                                  struct unit *ferry,
+                                  struct unit *passenger)
+{
+  int move_rate;
+
+  pft_fill_unit_parameter(&parameter->land, passenger);
+  /* Allow attacks over dangerous terrain and polar settlements */
+  parameter->land.is_pos_dangerous = NULL;
+  /* Use the ferry to go around danger areas: */
+  parameter->land.get_TB = no_intermediate_fights;
+
+  pft_fill_unit_parameter(&parameter->sea, ferry);
+  /* Ferries are not warships: */
+  parameter->sea.get_TB = no_fights;
+
+  move_rate = parameter->land.move_rate * parameter->sea.move_rate;
+  parameter->land_scale = move_rate / parameter->land.move_rate;
+  parameter->sea_scale = move_rate / parameter->sea.move_rate;
+
+  parameter->land.moves_left_initially *= parameter->land_scale;
+  parameter->land.move_rate *= parameter->land_scale;
+  parameter->sea.moves_left_initially *= parameter->sea_scale;
+  parameter->sea.move_rate *= parameter->sea_scale;
+
+  pft_fill_unit_default_parameter(&parameter->combined, ferry);
+  parameter->combined.moves_left_initially *= parameter->sea_scale;
+  parameter->combined.move_rate = move_rate;
+  /* To ensure triremes behave correctly: */
+  parameter->combined.turn_mode = TM_WORST_TIME;
+  parameter->combined.get_MC = amphibious_move;
+  parameter->combined.get_TB = amphibious_behaviour;
+  parameter->combined.get_EC = amphibious_extra_cost;
+  parameter->combined.is_pos_dangerous = amphibious_is_pos_dangerous;
+  BV_CLR_ALL(parameter->combined.unit_flags);
+
+  parameter->combined.data = parameter;
+}
+
+/**********************************************************************
   Fill general use parameters to defaults
 ***********************************************************************/
 static void pft_fill_unit_default_parameter(struct pf_parameter *parameter,
@@ -587,3 +816,42 @@
   }
   return dest_path;
 }
+
+/**********************************************************************
+  Remove the part of a path leading up to a given tile.
+  The given tile must be on the path.
+***********************************************************************/
+void pft_advance_path(struct pf_path *path,
+                     struct tile *ptile)
+{
+  int i;
+  struct pf_position *new_positions;
+  for(i = 0; i < path->length; i++) {
+    if (path->positions[i].tile == ptile) {
+      break;
+    }
+  }
+  assert(i < path->length);
+  path->length -= i;
+  new_positions = 
+    fc_malloc(sizeof(*path->positions) * path->length);
+  memcpy(new_positions, path->positions + i,
+        path->length * sizeof(*path->positions));
+  free(path->positions);
+  path->positions = new_positions;
+}
+
+/**********************************************************************
+  Set callbacks to favour paths that do not create tall stacks.
+***********************************************************************/
+void pft_no_tall_stacks(struct pf_parameter *parameter,
+                       struct pft_stack_cost *stack_cost,
+                       struct unit *punit,
+                       const int strictness)
+{
+  parameter->data = stack_cost;
+  parameter->get_EC = prefer_short_stacks;
+  parameter->turn_mode = TM_WORST_TIME;
+  stack_cost->base_cost = 0;
+  stack_cost->strictness = strictness;
+}
diff -ru -Xvendor.freeciv.current/diff_ignore 
vendor.freeciv.current/common/aicore/pf_tools.h 
freeciv.PR11995/common/aicore/pf_tools.h
--- vendor.freeciv.current/common/aicore/pf_tools.h     2005-01-24 
20:43:03.000000000 +0000
+++ freeciv.PR11995/common/aicore/pf_tools.h    2005-02-22 23:17:35.000000000 
+0000
@@ -15,19 +15,59 @@
 
 #include "path_finding.h"
 
+
+
+/*
+ * WAG: how hard to avoid tall stacks of units.
+ */
+#define FERRY_STACKING_STRICTNESS (PF_TURN_FACTOR / 240)
+#define LAND_STACKING_STRICTNESS (PF_TURN_FACTOR / 360)
+
+struct pft_amphibious
+{
+  /* Initialise using pft_fill_amphibious_parameter().
+   * Give the 'combined' field to pf_create_map to create a map
+   * for finding amphibious paths */
+  struct pf_parameter combined;
+  struct pf_parameter land;
+  struct pf_parameter sea;
+  int land_scale;
+  int sea_scale;
+};
+
+struct pft_stack_cost
+{
+  int base_cost;
+  int strictness;
+};
+
+
+
 struct pf_path *pft_concat(struct pf_path *dest_path,
                           const struct pf_path *src_path);
+void pft_advance_path(struct pf_path *path,
+                     struct tile *ptile);
 void pft_fill_unit_parameter(struct pf_parameter *parameter,
                             struct unit *punit);
 void pft_fill_unit_overlap_param(struct pf_parameter *parameter,
                                 struct unit *punit);
 void pft_fill_unit_attack_param(struct pf_parameter *parameter,
                                 struct unit *punit);
+void pft_no_tall_stacks(struct pf_parameter *parameter,
+                       struct pft_stack_cost *stack_cost,
+                       struct unit *punit,
+                       const int strictness);
+void pft_fill_amphibious_parameter(struct pft_amphibious *parameter,
+                                  struct unit *ferry,
+                                  struct unit *passenger);
 enum tile_behavior no_fights_or_unknown(const struct tile *ptile,
                                         enum known_type known,
                                         struct pf_parameter *param);
 enum tile_behavior no_fights(const struct tile *ptile, enum known_type known,
                             struct pf_parameter *param);
+enum tile_behavior no_intermediate_fights(const struct tile *ptile,
+                                         enum known_type known,
+                                         struct pf_parameter *param);
 
 #define pf_iterator(map, position) {                       \
   struct pf_position position;                             \
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-22 23:17:15.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)
 **************************************************************************/