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

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

On Tue, Dec 24, 2002 at 12:05:23PM -0800, Gregory Berkolaiko via RT wrote:
> 
> 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.

I adjusted the weight to stay closer to shore, as I described before,
and also made huts more desirable (unless we're a barbarian, in which
case the desirability is automatically zero).

The reason it doesn't try very hard to explore around cities is that
it will always move locally to unexplored tiles, unless it can't, and
only then will it consider distant tiles. So a crummy adjacent tile is
prefererred over a really good tile 2 moves away. Simply increasing
the weight of city desirability doesn't help (I changed it to 18100 in
a test with no effect). I'm not sure what to do about this, if
anything. 

-- 
+-----------------------------------------------------------------
| PGP http://www.eng.uwaterloo.ca/student/cjmorlan/public-key.pgp
| Cameron Morland             ----             Cameron@xxxxxxxxxx
|
| I know engineers; they love to change things.
|     --Dr. McCoy
+-----------------------------------------------------------------

? data/mono
? data/mono.tilespec
Index: ai/aiunit.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/ai/aiunit.c,v
retrieving revision 1.248
diff -u -3 -p -r1.248 aiunit.c
--- ai/aiunit.c 2003/01/02 11:59:29     1.248
+++ ai/aiunit.c 2003/01/02 15:44:20
@@ -257,44 +257,190 @@ 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.
-
-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   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);
+    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 (map_has_special(x, y, S_HUT)) {
+    /* we want to explore huts whenever we can. */
+    desirable += HUT_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
+#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.
@@ -362,58 +508,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) != 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 +571,51 @@ 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. */
+    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 +660,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));
@@ -550,7 +671,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) == 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);

pgpoRrf2B_eSj.pgp
Description: PGP signature