[freeciv-ai] Re: (PR#2477) Improved Auto-Explore

["Gregory Berkolaiko via RT" <rt@xxxxxxxxxxxxxx>]

> > All others: I intend to commit this patch soon (when Cameron blesses my 
> > changes,
> > basically).  So comment now or...
> 
> ssh from a windows box over a modem. Ugh.
> 
> Your mods appear to be fine, and I assume that it compiles. It shouldn't 
> behave
> significantly differently.

I does compile but I am not 100% satisfied with the behaviour.  See 
attached savegame (login: aas02101).  After few turns it strays away from 
the shore.  Also it wasn't terribly eager to explore city tiles, I think 
you should increase the weight.

Also attached is the patch updated to the latest CVS.

G.

expl.sav.gz
Description: expl.sav.gz

? pitfight.sh
? pitfight_g.sh
Index: ai/aiunit.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/ai/aiunit.c,v
retrieving revision 1.244
diff -u -r1.244 aiunit.c
--- ai/aiunit.c 2002/12/24 19:40:36     1.244
+++ ai/aiunit.c 2002/12/24 20:01:24
@@ -257,44 +257,183 @@
 }
  
 /**************************************************************************
-Handle eXplore mode of a unit (explorers are always in eXplore mode for AI) -
-explores unknown territory, finds huts.
-
-Returns whether there is any more territory to be explored.
+  Determine if a tile is likely to be water, given information that
+  the player actually has. Return the % certainty that it's water
+  (100 = certain, 50 = no idea, 0 = certainly not).
 **************************************************************************/
-bool ai_manage_explorer(struct unit *punit)
+static int likely_ocean(int x, int y, struct player *pplayer)
 {
-  struct player *pplayer = unit_owner(punit);
-  /* The position of the unit; updated inside the function */
-  int x = punit->x, y = punit->y;
-  /* Continent the unit is on */
-  int continent;
-  /* Unit's speed */
-  int move_rate = unit_move_rate(punit);
-  /* Range of unit's vision */
-  int range;
+  int sum;
 
-  /* Get the range */
-  /* FIXME: The vision range should NOT take into account watchtower benefit.
-   * Now it is done in a wrong way: the watchtower bonus is computed locally,
-   * at the point where the unit is, and then it is applied at a faraway
-   * location, as if there is a watchtower there too. --gb */
+  if (map_get_known(x, y, pplayer)) {
+    /* we've seen the tile already. */
+    return (map_get_terrain(x,y) == T_OCEAN ? 100 : 0);
+  }
+  
+  /* Now we're going to do two things at once. We're going to see if
+   * we know any cardinally adjacent tiles, since knowing one will
+   * give a guaranteed value for the centre tile. Also, we're going
+   * to count the non-cardinal (diagonal) tiles, and see how many
+   * of them are ocean, which gives a guess for the ocean-ness of 
+   * the centre tile. */
+  sum = 50;
+  adjc_dir_iterate(x, y, x1, y1, dir) {
+    if (map_get_known(x1, y1, pplayer)) {
+      if (DIR_IS_CARDINAL(dir)) {
+       /* If a tile is cardinally adjacent, we can tell if the 
+        * central tile is ocean or not by the appearance of
+        * the adjacent tile. So, given that we can tell, 
+        * it's fair to look at the actual tile. */
+        return (map_get_terrain(x, y) == T_OCEAN ? 100 : 0);
+      } else {
+       /* We're diagonal to the tile in question. So we can't
+        * be sure what the central tile is, but the central
+        * tile is likely to be the same as the nearby tiles. 
+        * If all 4 are water, return 90; if all 4 are land, 
+        * return 10. */
+        sum += (map_get_terrain(x1, y1) == T_OCEAN ? 10 : -10);
+      }
+    }
+  } adjc_dir_iterate_end;
 
+  return sum;
+}
+
+/**************************************************************************
+Return the vision range that a unit would experience at the given location.
+**************************************************************************/
+static int get_range_at(int x, int y, struct unit *punit)
+{
+  int range;
+  /* Check if there is a watchtower at the given tile, and return the 
+   * vision range that the unit would have as a result. */
   if (unit_profits_of_watchtower(punit)
-      && map_has_special(punit->x, punit->y, S_FORTRESS)) {
+      && map_has_special(x, y, S_FORTRESS)) {
     range = get_watchtower_vision(punit);
   } else {
     range = unit_type(punit)->vision_range;
   }
+  
+  return range;
+}
+
+/**************************************************************************
+Tell whether the tile (x, y) is within radius of one of our cities.
+NB: Move this function to common/city.c should it cease to be static.
+**************************************************************************/
+static bool is_within_own_city_radius(struct player *owner, int x, int y)
+{
+  map_city_radius_iterate (x, y, x1, y1) {
+    struct city * pcity = map_get_city (x1, y1);
+    if (pcity && owner == city_owner(pcity))
+      return TRUE;
+  } map_city_radius_iterate_end;
+
+  return FALSE;
+}
+
+/**************************************************************************
+Return a value indicating how desirable it is to explore the given tile.
+In general, we want to discover unknown terrain of the opposite kind to
+our natural terrain, i.e. pedestrians like ocean and boats like land.
+Even if terrain is known, but of opposite kind, we still want it
+-- so that we follow the shoreline.
+We also like discovering tiles which can be harvested by our cities --
+because that improves citizen placement.
+**************************************************************************/
+#define SAME_TER_SCORE         21
+#define DIFF_TER_SCORE         81
+#define KNOWN_SAME_TER_SCORE   0
+#define KNOWN_DIFF_TER_SCORE   16
+#define OWN_CITY_SCORE    181
+static int explorer_desirable(int x, int y, struct player *pplayer, 
+                              struct unit *punit)
+{
+  int land_score, ocean_score, known_land_score, known_ocean_score;
+  int range = get_range_at(x, y, punit);
+  int desirable = 0;
+  int unknown = 0;
+  int continent;
 
   /* Localize the unit */
-  
   if (is_ground_unit(punit)) {
-    continent = map_get_continent(x, y);
+    continent = map_get_continent(punit->x, punit->y);
   } else {
     continent = 0;
   }
 
+  /* First do some checks that would make a tile completely non-desirable.
+   * If we're a trireme and we could die at the given tile, or if there
+   * is a city on the tile, or if the 
+   * tile is on a different continent, or if we're a barbarian and
+   * the tile has a hut, don't go there. */
+  if ((unit_flag(punit, F_TRIREME) && trireme_loss_pct(pplayer, x, y) != 0)
+     || map_get_city(x, y)
+     || map_get_continent(x, y) != continent
+     || (is_barbarian(pplayer) && map_has_special(x, y, S_HUT))) {
+    return 0;
+  }
+
+  /* What value we assign to the number of land and water tiles
+   * depends on if we're a land or water unit. */
+  if (is_ground_unit(punit)) {
+    land_score = SAME_TER_SCORE;
+    ocean_score = DIFF_TER_SCORE;
+    known_land_score = KNOWN_SAME_TER_SCORE;
+    known_ocean_score = KNOWN_DIFF_TER_SCORE;
+  } else {
+    land_score = DIFF_TER_SCORE;
+    ocean_score = SAME_TER_SCORE;
+    known_land_score = KNOWN_DIFF_TER_SCORE;
+    known_ocean_score = KNOWN_SAME_TER_SCORE;
+  }
+
+  square_iterate(x, y, range, x1, y1) {
+    int ocean = likely_ocean(x1,y1, pplayer);
+
+    if (!map_get_known(x1, y1, pplayer)) {
+      unknown++;
+      desirable += (ocean >= 50 ? ocean_score : land_score);
+    } else {
+      desirable += (ocean >= 50 ? known_ocean_score : known_land_score);
+    }
+  } square_iterate_end;
+
+  if (is_within_own_city_radius(pplayer, x, y)) {
+    /* Friendly city is not quite the same as own city, but... */
+    desirable += OWN_CITY_SCORE;
+  }
+
+  if (unknown <= 0) {
+    /* We make sure we'll uncover at least one unexplored tile. */
+    desirable = 0;
+  }
+
+  return desirable;
+}
+#undef SAME_TER_SCORE
+#undef DIFF_TER_SCORE
+#undef KNOWN_SAME_TER_SCORE
+#undef KNOWN_DIFF_TER_SCORE
+#undef OWN_CITY_SCORE
+
+/**************************************************************************
+Handle eXplore mode of a unit (explorers are always in eXplore mode for AI) -
+explores unknown territory, finds huts.
+
+Returns whether there is any more territory to be explored.
+**************************************************************************/
+bool ai_manage_explorer(struct unit *punit)
+{
+  struct player *pplayer = unit_owner(punit);
+  /* The position of the unit; updated inside the function */
+  int x = punit->x, y = punit->y;
+
+  /* Idle unit */
+  if (punit->activity != ACTIVITY_IDLE) {
+    handle_unit_activity_request(punit, ACTIVITY_IDLE);
+  }
+
   /*
    * PART 1: Look for huts
    * Non-Barbarian Ground units ONLY.
@@ -362,58 +501,36 @@
    */
   
   while (punit->moves_left > 0) {
-    /* Best (highest) number of unknown tiles adjacent (in vision range) */
-    int most_unknown = 0;
+    /* most desirable tile, given nearby water, cities, etc. */
+    int most_desirable = 0; 
     /* Desired destination */
     int best_x = -1, best_y = -1;
 
     /* Evaluate all adjacent tiles. */
-    
-    square_iterate(x, y, 1, x1, y1) {
-      /* Number of unknown tiles in vision range around this tile */
-      int unknown = 0;
-      
-      square_iterate(x1, y1, range, x2, y2) {
-        if (!map_get_known(x2, y2, pplayer))
-          unknown++;
-      } square_iterate_end;
-
-      if (unknown > most_unknown) {
-        if (unit_flag(punit, F_TRIREME)
-            && trireme_loss_pct(pplayer, x1, y1) != 0)
-          continue;
-        
-        if (map_get_continent(x1, y1) != continent)
-          continue;
-        
-        if (could_unit_move_to_tile(punit, x1, y1) == 0) {
-          continue;
-        }
+    adjc_iterate(x, y, x1, y1) {
+      int desirable;
 
-        /* We won't travel into cities, unless we are able to do so - diplomats
-         * and caravans can. */
-        /* FIXME/TODO: special flag for this? --pasky */
-        /* FIXME: either comment or code is wrong here :-) --pasky */
-        if (map_get_city(x1, y1) && (unit_flag(punit, F_DIPLOMAT) 
-                                     || unit_flag(punit, F_TRADE_ROUTE)))
-          continue;
+      if (!could_unit_move_to_tile(punit, x1, y1)) {
+        /* we can't move there anyway, don't consider how good it might be. */
+       continue;
+      }
 
-        if (is_barbarian(pplayer) && map_has_special(x1, y1, S_HUT))
-          continue;
-          
-        most_unknown = unknown;
-        best_x = x1;
-        best_y = y1;
+      desirable = explorer_desirable(x1, y1, pplayer, punit);
+
+      if (desirable > most_desirable) {
+       most_desirable = desirable;
+       best_x = x1;
+       best_y = y1;
       }
-    } square_iterate_end;
+    } adjc_iterate_end;
 
-    if (most_unknown > 0) {
+    if (most_desirable > 0) {
       /* We can die because easy AI may stumble on huts and so disappear in the
        * wilderness - unit_id is used to check this */
       int unit_id = punit->id;
       bool broken = TRUE; /* failed movement */
       
-      /* Some tile have unexplored territory adjacent, let's move there. */
+      /* Some tile has unexplored territory adjacent, let's move there. */
 
       /* ai_unit_move for AI players, handle_unit_move_request for humans */
       if ((pplayer->ai.control && ai_unit_move(punit, best_x, best_y))
@@ -447,57 +564,51 @@
    */
 
   {
-    /* Best (highest) number of unknown tiles adjectent (in vision range) */
-    int most_unknown = 0;
+    /* most desirable tile, given nearby water, cities, etc. */
+    int most_desirable = 0;
     /* Desired destination */
     int best_x = -1, best_y = -1;
   
     generate_warmap(map_get_city(x, y), punit);
 
-    /* XXX: There's some duplicate code here, but it's several tiny pieces,
-     * impossible to group together and not worth their own function
-     * separately. --pasky */
-    
     whole_map_iterate(x1, y1) {
-      /* The actual map tile */
-      struct tile *ptile = map_get_tile(x1, y1);
-      
-      if (ptile->continent == continent
-          && !is_non_allied_unit_tile(ptile, pplayer)
-          && !is_non_allied_city_tile(ptile, pplayer)
-          && tile_is_accessible(punit, x1, y1)) {
-        /* Number of unknown tiles in vision range around this tile */
-        int unknown = 0;
-        
-        square_iterate(x1, y1, range, x2, y2) {
-          if (!map_get_known(x2, y2, pplayer))
-            unknown++;
-        } square_iterate_end;
-        
-        if (unknown > 0) {
-#define COSTWEIGHT 9
-          /* How far it's worth moving away */
-          int threshold = THRESHOLD * move_rate;
-          
-          if (is_sailing_unit(punit))
-            unknown += COSTWEIGHT * (threshold - warmap.seacost[x1][y1]);
-          else
-            unknown += COSTWEIGHT * (threshold - warmap.cost[x1][y1]);
-          
-          /* FIXME? Why we don't do same tests like in part 2? --pasky */
-          if (((unknown > most_unknown) ||
-               (unknown == most_unknown && myrand(2) == 1))
-              && !(is_barbarian(pplayer) && tile_has_special(ptile, S_HUT))) {
-            best_x = x1;
-            best_y = y1;
-            most_unknown = unknown;
+      int desirable;
+
+      desirable = explorer_desirable(x1, y1, pplayer, punit);
+
+      if (desirable > 0) {
+       /* add some "noise" to the signal so equally desirable tiles
+        * will be selected randomly. The noise has an amplitude
+        * of 0.1, so a far-away tile with a higher score will still
+        * usually be selected over a nearby tile with a high noise 
+        * value. */
+       desirable = 1000*desirable + myrand(100);
+
+       /* now we want to reduce the desirability of far-away
+        * tiles, without reducing it to zero, regardless how
+        * far away it is. */
+#define DIST_EXPONENT   5
+       if (is_sailing_unit(punit)) {
+          /* Hijack amortize for our needs */
+         desirable = amortize(desirable, 
+                               DIST_EXPONENT*warmap.seacost[x1][y1]);
+       } else {
+         desirable = amortize(desirable, 
+                               DIST_EXPONENT*warmap.cost[x1][y1]);
+       }
+#undef DIST_EXPONENT
+
+       if (desirable > most_desirable) {
+         best_x = x1;
+         best_y = y1;
+         if (desirable > most_desirable) {
+           most_desirable = desirable;
           }
-#undef COSTWEIGHT
         }
       }
     } whole_map_iterate_end;
 
-    if (most_unknown > 0) {
+    if (most_desirable > 0) {
       /* Go there! */
       if (!ai_unit_goto(punit, best_x, best_y)) {
         return FALSE;
@@ -542,7 +653,10 @@
     struct city *pcity = find_city_by_id(punit->homecity);
     /* No homecity? Find one! */
     if (!pcity) {
-      pcity = find_closest_owned_city(pplayer, punit->x, punit->y, FALSE, 
NULL);
+      bool sea_required = is_sailing_unit(punit);
+
+      pcity = find_closest_owned_city(pplayer, punit->x, punit->y, 
+                                      sea_required, NULL);
       if (pcity && ai_unit_make_homecity(punit, pcity)) {
         CITY_LOG(LOG_DEBUG, pcity, "we became home to an exploring %s",
                  unit_name(punit->type));
@@ -550,7 +664,9 @@
     }
 
     if (pcity && !same_pos(punit->x, punit->y, pcity->x, pcity->y)) {
-      if (map_get_continent(pcity->x, pcity->y) == continent) {
+      if (map_get_continent(pcity->x, pcity->y) == map_get_continent(x, y)
+          || (is_sailing_unit(punit) 
+              && is_terrain_near_tile(pcity->x, pcity->y, T_OCEAN))) {
         UNIT_LOG(LOG_DEBUG, punit, "sending explorer home by foot");
         if (punit->homecity != 0) {
           ai_military_gohome(pplayer, punit);