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

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

I noted today that there were conflicts with CVS, so the new patch
fixes that. Also I #define'd DIST_FACTOR, but #undef'ined
DIST_EXPONENT. This fixes it. 

The conflicts, incidentally, were changing of warmap.(sea)cost[][] to
WARMAP_(SEA)COST.

-- 
+-----------------------------------------------------------------
| PGP http://www.eng.uwaterloo.ca/student/cjmorlan/public-key.pgp
| Cameron Morland             ----             Cameron@xxxxxxxxxx
|
| Work is no disgrace, but idleness is.
|     --Hesiod
+-----------------------------------------------------------------

Index: ai/aiunit.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/ai/aiunit.c,v
retrieving revision 1.259
diff -u -3 -p -r1.259 aiunit.c
--- ai/aiunit.c 2003/02/02 13:21:50     1.259
+++ ai/aiunit.c 2003/02/02 21:04:58
@@ -320,38 +320,157 @@ 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 (is_ocean(map_get_terrain(x,y)) ? 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 (is_ocean(map_get_terrain(x, y)) ? 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 += (is_ocean(map_get_terrain(x1, y1)) ? 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;
+}
+
+/***************************************************************
+How likely is a tile to be coastline, given information that the 
+player actually has.
+***************************************************************/
+int likely_coastline(int x, int y, struct player *pplayer)
+{
+  int likely = 50;
+  int t;
 
+  adjc_iterate(x, y, x1, y1) {
+    if ((t = likely_ocean(x1, y1, pplayer)) == 0) {
+      return 100;
+    }
+    /* If all t values are 50, likely stays at 50. If all approach zero,
+     * ie are unlikely to be ocean, the tile is likely to be coastline, so
+     * likely will approach 100. If all approach 100, likely will 
+     * approach zero. */
+    likely += (50-t)/8;
+    
+  } adjc_iterate_end;
+
+  return likely;
+}
+
+/***************************************************************
+How likely is a trireme to be lost, given information that the
+player actually has.
+***************************************************************/
+int likely_trireme_loss_pct(struct player *pplayer, int x, int y) 
+{
+  int losspct = 50;
+
+  /*
+   * If we are in a city or next to land, we have no chance of losing
+   * the ship.  To make this really useful for ai planning purposes, we'd
+   * need to confirm that we can exist/move at the x,y location we are given.
+   */
+  if ((likely_ocean(x, y, pplayer) < 50) || 
+      (likely_coastline(x, y, pplayer) < 50) ||
+      (player_owns_active_wonder(pplayer, B_LIGHTHOUSE)))
+       losspct = 0;
+  else if (player_knows_techs_with_flag(pplayer,TF_REDUCE_TRIREME_LOSS2))
+       losspct /= 4;
+  else if (player_knows_techs_with_flag(pplayer,TF_REDUCE_TRIREME_LOSS1))
+       losspct /= 2;
+
+  return losspct;
+}
+
+/**************************************************************************
+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         18100
+#define HUT_SCORE              200000
+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)) {
@@ -360,126 +479,123 @@ bool ai_manage_explorer(struct unit *pun
     continent = 0;
   }
 
-  /*
-   * PART 1: Look for huts
-   * Non-Barbarian Ground units ONLY.
-   */
+  /* 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) && 
+       likely_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;
+  }
 
-  if (!is_barbarian(pplayer)
-      && is_ground_unit(punit)) {
-    /* Maximal acceptable _number_ of moves to the target */
-    int maxmoves = pplayer->ai.control ? 2 * THRESHOLD : 3;
-    /* Move _cost_ to the best target (=> lower is better) */
-    int bestcost = maxmoves * SINGLE_MOVE + 1;
-    /* Desired destination */
-    int best_x = -1, best_y = -1;
+  /* 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;
+  }
 
-    /* CPU-expensive but worth it -- Syela */
-    generate_warmap(map_get_city(x, y), punit);
-  
-    /* We're iterating outward so that with two tiles with the same movecost
-     * the nearest is used. */
-    iterate_outward(x, y, maxmoves, x1, y1) {
-      if (map_has_special(x1, y1, S_HUT)
-          && WARMAP_COST(x1, y1) < bestcost
-          && (!ai_handicap(pplayer, H_HUTS) || map_get_known(x1, y1, pplayer))
-          && tile_is_accessible(punit, x1, y1)
-          && ai_fuzzy(pplayer, TRUE)) {
-        best_x = x1;
-        best_y = y1;
-        bestcost = WARMAP_COST(best_x, best_y);
+  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;
       }
-    } iterate_outward_end;
-    
-    if (bestcost <= maxmoves * SINGLE_MOVE) {
-      /* Go there! */
-      if (!ai_unit_goto(punit, best_x, best_y)) {
-        /* We're dead. */
-        return FALSE;
+      desirable += (ocean*ocean_score + (100-ocean)*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*known_ocean_score + (100-ocean)*known_land_score);
       }
-
-      if (punit->moves_left > 0) {
-        /* We can still move on... */
+    }
+  } square_iterate_end;
 
-        if (same_pos(punit->x, punit->y, best_x, best_y)) {
-          /* ...and got into desired place. */
-          return ai_manage_explorer(punit);  
-        } else {
-          /* Something went wrong. This should almost never happen. */
-         if (!same_pos(punit->x, punit->y, x, y)) {
-           generate_warmap(map_get_city(punit->x, punit->y), punit);
-         }
-          
-          x = punit->x;
-          y = punit->y;
-          /* Fallthrough to next part. */
-        }
+  if (unknown <= 0) {
+    /* We make sure we'll uncover at least one unexplored tile. */
+    desirable = 0;
+  }
 
-      } else {
-        return TRUE;
-      }
-    }
+  if ((!pplayer->ai.control || !ai_handicap(pplayer, H_HUTS))
+      && 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;
+
   /* 
-   * PART 2: Move into unexplored territory
+   * PART 1: Move into unexplored territory
    * Move the unit as long as moving will unveil unknown territory
    */
   
   while (punit->moves_left > 0) {
-    /* Best (highest) number of unknown tiles adjacent (in vision range) */
-    int most_unknown = 0;
-    /* Desired destination */
+    /* How desirable the most desirable tile is, given nearby water, 
+     * cities, etc. */
+    int most_desirable = 0; 
+    /* coordinates of most desirable tile */
     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 (is_barbarian(pplayer) && map_has_special(x1, y1, S_HUT))
-          continue;
-          
-        most_unknown = unknown;
-        best_x = x1;
-        best_y = y1;
+      if (could_unit_move_to_tile(punit, x1, y1) == 0) {
+        /* we can't move there anyway, don't consider how good it might be. */
+       continue;
       }
-    } square_iterate_end;
+
+      desirable = explorer_desirable(x1, y1, pplayer, punit);
 
-    if (most_unknown > 0) {
+      if (desirable > most_desirable) {
+       most_desirable = desirable;
+       best_x = x1;
+       best_y = y1;
+      }
+    } adjc_iterate_end;
+
+    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))
           || (!pplayer->ai.control 
@@ -507,65 +623,53 @@ bool ai_manage_explorer(struct unit *pun
   }
 
   /* 
-   * PART 3: Go towards unexplored territory
+   * PART 2: Go towards unexplored territory
    * No adjacent squares help us to explore - really slow part follows.
    */
 
   {
-    /* Best (highest) number of unknown tiles adjectent (in vision range) */
-    int most_unknown = 0;
-    /* Desired destination */
+    /* most desirable tile, given nearby water, cities, etc. */
+    float most_desirable = 0;
+    /* coordinates of most desirable tile */
     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_FACTOR
+
+       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;
+       return FALSE;
       }
       
       if (punit->moves_left > 0) {
@@ -573,31 +677,43 @@ bool ai_manage_explorer(struct unit *pun
 
         if (same_pos(punit->x, punit->y, best_x, best_y)) {
           /* ...and got into desired place. */
-          return ai_manage_explorer(punit);          
+         return ai_manage_explorer(punit);          
         } else {
-          /* Something went wrong. What to do but return? */
+          /* 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) {
-            handle_unit_activity_request(punit, ACTIVITY_IDLE);
+           if(unit_flag(punit, F_TRIREME) &&
+              (punit->moves_left != unit_move_rate(punit))) {
+             /* we're a trireme with non-full complement of movement points,
+              * so wait until next turn. */
+             return TRUE;
+           }
+           handle_unit_activity_request(punit, ACTIVITY_IDLE);
           }
-          return FALSE;
+         return FALSE;
         }
-        
       } else {
         return TRUE;
       }
     }
-    
     /* No candidates; fall-through. */
   }
 
-  /* We have nothing to explore, so we can go idle. */
+  /* We have nothing to explore, so we can go idle. 
+   * Do we need this idle? It seems to me that we'll never get to part 3,
+   * so AI explorers will never go home. --CJM
+   */
   UNIT_LOG(LOG_DEBUG, punit, "failed to explore more");
   if (punit->activity == ACTIVITY_EXPLORE) {
     handle_unit_activity_request(punit, ACTIVITY_IDLE);
   }
   
   /* 
-   * PART 4: Go home
+   * PART 3: Go home
    * If we are AI controlled _military_ unit (so Explorers don't count, why?
    * --pasky), we will return to our homecity, maybe even to another continent.
    */
@@ -607,7 +723,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));
@@ -615,7 +734,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_ocean_near_tile(pcity->x, pcity->y))) {
         UNIT_LOG(LOG_DEBUG, punit, "sending explorer home by foot");
         if (punit->homecity != 0) {
           ai_military_gohome(pplayer, punit);

pgpPM62Kz0Gao.pgp
Description: PGP signature