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

["Cameron Morland via RT" <rt@xxxxxxxxxxxxxx>]

Triremes would previously tend to wake up occasionally while
exploring. We fixed this by detecting when ai_unit_goto is returning
while the unit still has movement points left; moving the trireme
would leave it away from shore and hence unsafe. So now we return TRUE
if ai_unit_goto returns early, but only if we're a trireme and have
moved this turn (to prevent getting stuck by other bugs).

The goto code needs to more robustly deal with triremes, so the paths
it makes for them aren't unsafe, but that should be solved
independently of the explorer patch.

Also, AIs can cheat when judging where is a good place to leave
triremes, since trireme_loss_pct checks the map. This should be fixed,
but in a separate patch.

Do you know what this stuff near the end of the patch is about? I
can't recall writing it, did you? It seems to make sense.

@@ -546,7 +672,10 @@ bool ai_manage_explorer(struct unit *pun
     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));
@@ -554,7 +683,9 @@ bool ai_manage_explorer(struct unit *pun
     }
 
     if (pcity && !same_pos(punit->x, punit->y, pcity->x, pcity->y)) {
-      if (map_get_continent(pcity->x, pcity->y, NULL) == continent) {
+      if (map_get_continent(pcity->x, pcity->y, NULL) ==
map_get_continent(x, y, NULL)
+          || (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);

All in all, I think this patch may finally be done.

-- 
+-----------------------------------------------------------------
| PGP http://www.eng.uwaterloo.ca/student/cjmorlan/public-key.pgp
| Cameron Morland             ----             Cameron@xxxxxxxxxx
|
| I don't worry about anything. Worry never solved any problem. If 
| the problem is there, you'll find the answer. You just have to 
| keep working on it.    
|     ---Milton Garland
+-----------------------------------------------------------------

? type
? ai/aiunit.c.trireme
? data/mono
? data/mono.tilespec
? data/oldciv
? data/oldciv.tilespec
? data/oldciv_shields.tilespec
? data/tinydent
? data/tinydent.tilespec
Index: ai/aiunit.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/ai/aiunit.c,v
retrieving revision 1.251
diff -u -3 -p -r1.251 aiunit.c
--- ai/aiunit.c 2003/01/09 02:36:36     1.251
+++ ai/aiunit.c 2003/01/09 03:42:12
@@ -259,46 +259,196 @@ static bool tile_is_accessible(struct un
 }
  
 /**************************************************************************
-Handle eXplore mode of a unit (explorers are always in eXplore mode for AI) -
-explores unknown territory, finds huts.
+  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).
+**************************************************************************/
+static int likely_ocean(int x, int y, struct player *pplayer)
+{
+  int sum;
 
-Returns whether there is any more territory to be explored.
+  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.
 **************************************************************************/
-bool ai_manage_explorer(struct unit *punit)
+static int get_range_at(int x, int y, 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;
-  /* Continent the unit is on */
-  int continent;
-  /* Unit's speed */
-  int move_rate = unit_move_rate(punit);
-  /* Range of unit's vision */
   int range;
 
   CHECK_UNIT(punit);
 
-  /* 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 */
-
+  /* 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   51
+#define OWN_CITY_SCORE         181
+#define HUT_SCORE              2000
+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, NULL);
   } 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, NULL) != 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++;
+      if (is_within_own_city_radius(pplayer, x1, y1)) {
+       desirable += OWN_CITY_SCORE;
+      }
+      desirable += (ocean >= 50 ? ocean_score : land_score);
+    } else {
+      if(is_tiles_adjacent(x, y, x1, y1)) {
+       /* we don't value staying offshore from land,
+        * only adjacent. Otherwise destroyers do the wrong thing. */
+       desirable += (ocean >= 50 ? known_ocean_score : known_land_score);
+      }
+    }
+  } square_iterate_end;
+
+  if (unknown <= 0) {
+    /* We make sure we'll uncover at least one unexplored tile. */
+    desirable = 0;
+  }
+
+  if (map_get_known(x, y, pplayer) && map_has_special(x, y, S_HUT)) {
+    /* we want to explore huts whenever we can,
+     * even if doing so will not uncover any tiles. */
+    desirable += HUT_SCORE;
+  }
+
+  return desirable;
+}
+#undef SAME_TER_SCORE
+#undef DIFF_TER_SCORE
+#undef KNOWN_SAME_TER_SCORE
+#undef KNOWN_DIFF_TER_SCORE
+#undef OWN_CITY_SCORE
+#undef HUT_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.
@@ -366,58 +516,36 @@ bool ai_manage_explorer(struct unit *pun
    */
   
   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, NULL) != 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))
@@ -451,57 +579,45 @@ bool ai_manage_explorer(struct unit *pun
    */
 
   {
-    /* Best (highest) number of unknown tiles adjectent (in vision range) */
-    int most_unknown = 0;
+    /* most desirable tile, given nearby water, cities, etc. */
+    float 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;
+      float 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 += myrand(100) * 0.001;
+
+       /* now we want to reduce the desirability of far-away
+        * tiles, without reducing it to zero, regardless how
+        * far away it is. */
+#define DIST_FACTOR   0.8
+       desirable = pow(DIST_FACTOR, is_sailing_unit(punit) ?
+                       warmap.seacost[x1][y1] : 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;
@@ -514,11 +630,21 @@ bool ai_manage_explorer(struct unit *pun
           /* ...and got into desired place. */
           return ai_manage_explorer(punit);          
         } else {
-          /* Something went wrong. What to do but return? */
-          if (punit->activity == ACTIVITY_EXPLORE) {
-            handle_unit_activity_request(punit, ACTIVITY_IDLE);
+          /* Something went wrong. What to do but return? 
+          * Answer: if we're a trireme we could get to this point,
+          * but only with a non-full complement of movement points, 
+          * in which case the goto code is simply requesting a
+          * one turn delay (the next tile we would occupy is not safe). 
+          * In that case, we should just wait. */
+          if ((punit->activity == ACTIVITY_EXPLORE) &&
+             (!unit_flag(punit, F_TRIREME) ||
+              punit->moves_left == unit_move_rate(punit))) {
+           handle_unit_activity_request(punit, ACTIVITY_IDLE);
+           return FALSE;
           }
-          return FALSE;
+         /* we're a trireme with non-full complement of movement points,
+          * so wait until next turn. */
+         return TRUE;
         }
         
       } else {
@@ -546,7 +672,10 @@ bool ai_manage_explorer(struct unit *pun
     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));
@@ -554,7 +683,9 @@ bool ai_manage_explorer(struct unit *pun
     }
 
     if (pcity && !same_pos(punit->x, punit->y, pcity->x, pcity->y)) {
-      if (map_get_continent(pcity->x, pcity->y, NULL) == continent) {
+      if (map_get_continent(pcity->x, pcity->y, NULL) == map_get_continent(x, 
y, NULL)
+          || (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);

pgpzhK3NYA5gm.pgp
Description: PGP signature