server/advisors/autoexplorer.c

   1 /**********************************************************************
   2  Freeciv - Copyright (C) 2004 - The Freeciv Project
   3    This program is free software; you can redistribute it and/or modify
   4    it under the terms of the GNU General Public License as published by
   5    the Free Software Foundation; either version 2, or (at your option)
   6    any later version.
   7
   8    This program is distributed in the hope that it will be useful,
   9    but WITHOUT ANY WARRANTY; without even the implied warranty of
  10    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11    GNU General Public License for more details.
  12 ***********************************************************************/
  13
  14 #ifdef HAVE_CONFIG_H
  15 #include <fc_config.h>
  16 #endif
  17
  18 #include <math.h> /* log */
  19
  20 /* utility */
  21 #include "bitvector.h"
  22 #include "log.h"
  23
  24 /* common */
  25 #include "ai.h"
  26 #include "movement.h"
  27 #include "player.h"
  28 #include "unit.h"
  29
  30 /* common/aicore */
  31 #include "path_finding.h"
  32 #include "pf_tools.h"
  33
  34 /* server */
  35 #include "maphand.h"
  36 #include "srv_log.h"
  37
  38 /* server/advisors */
  39 #include "advgoto.h"
  40
  41 /* ai */
  42 #include "handicaps.h"
  43
  44 #include "autoexplorer.h"
  45
  46
  47 /**************************************************************************
  48   Determine if a tile is likely to be native, given information that
  49   the player actually has. Return the % certainty that it's native
  50   (100 = certain, 50 = no idea, 0 = certainly not).
  51 **************************************************************************/
  52 static int likely_native(struct tile *ptile,
  53                          struct player *pplayer,
  54                          struct unit_class *pclass)
  55 {
  56   int native = 0;
  57   int foreign = 0;
  58
  59   /* We do not check H_MAP here, it should be done by map_is_known() */
  60   if (map_is_known(ptile, pplayer)) {
  61     /* we've seen the tile already. */
  62     return (is_native_tile_to_class(pclass, ptile) ? 100 : 0);
  63   }
  64
  65   /* The central tile is likely to be the same as the
  66    * nearby tiles. */
  67   adjc_dir_iterate(ptile, ptile1, dir) {
  68     if (map_is_known(ptile1, pplayer)) {
  69       if (is_native_tile_to_class(pclass, ptile)) {
  70         native++;
  71       } else {
  72         foreign++;
  73       }
  74     }
  75   } adjc_dir_iterate_end;
  76
  77   return 50 + (50 / game.map.num_valid_dirs * (native - foreign));
  78 }
  79
  80 /**************************************************************************
  81   Returns TRUE if a unit owned by the given player can safely "explore" the
  82   given tile. This mainly takes care that military units do not try to
  83   move into another player's territory in violation of a treaty.
  84 **************************************************************************/
  85 static bool player_may_explore(const struct tile *ptile,
  86                                const struct player *pplayer,
  87                                const struct unit_type *punittype)
  88 {
  89   /* Don't allow military units to cross borders. */
  90   if (!utype_has_flag(punittype, UTYF_CIVILIAN)
  91       && !player_can_invade_tile(pplayer, ptile)) {
  92     return FALSE;
  93   }
  94
  95   /* Can't visit tiles with non-allied units. */
  96   if (is_non_allied_unit_tile(ptile, pplayer)) {
  97     return FALSE;
  98   }
  99
 100   /* Non-allied cities are taboo even if no units are inside. */
 101   if (tile_city(ptile)
 102       && !pplayers_allied(city_owner(tile_city(ptile)), pplayer)) {
 103     return FALSE;
 104   }
 105
 106   return TRUE;
 107 }
 108
 109 /***************************************************************************
 110   TB function used by explorer_goto().
 111 ***************************************************************************/
 112 static enum tile_behavior explorer_tb(const struct tile *ptile,
 113                                       enum known_type k,
 114                                       const struct pf_parameter *param)
 115 {
 116   if (!player_may_explore(ptile, param->owner, param->utype)) {
 117     return TB_IGNORE;
 118   }
 119   return TB_NORMAL;
 120 }
 121
 122 /***************************************************************************
 123   Constrained goto using player_may_explore().
 124 ***************************************************************************/
 125 static bool explorer_goto(struct unit *punit, struct tile *ptile)
 126 {
 127   struct pf_parameter parameter;
 128   struct adv_risk_cost risk_cost;
 129   bool alive = TRUE;
 130   struct pf_map *pfm;
 131   struct pf_path *path;
 132   struct player *pplayer = unit_owner(punit);
 133
 134   pft_fill_unit_parameter(&parameter, punit);
 135   parameter.omniscience = !has_handicap(pplayer, H_MAP);
 136   parameter.get_TB = explorer_tb;
 137   adv_avoid_risks(&parameter, &risk_cost, punit, NORMAL_STACKING_FEARFULNESS);
 138
 139   /* Show the destination in the client */
 140   punit->goto_tile = ptile;
 141
 142   UNIT_LOG(LOG_DEBUG, punit, "explorer_goto to %d,%d", TILE_XY(ptile));
 143
 144   pfm = pf_map_new(&parameter);
 145   path = pf_map_path(pfm, ptile);
 146
 147   if (path != NULL) {
 148     alive = adv_follow_path(punit, path, ptile);
 149     pf_path_destroy(path);
 150   }
 151
 152   pf_map_destroy(pfm);
 153
 154   return alive;
 155 }
 156
 157 /**************************************************************************
 158 Return a value indicating how desirable it is to explore the given tile.
 159 In general, we want to discover unknown terrain of the opposite kind to
 160 our natural terrain, i.e. pedestrians like ocean and boats like land.
 161 Even if terrain is known, but of opposite kind, we still want it
 162 -- so that we follow the shoreline.
 163 We also would like discovering tiles which can be harvested by our cities --
 164 because that improves citizen placement. We do not currently do this, see
 165 comment below.
 166 **************************************************************************/
 167 #define SAME_TER_SCORE         21
 168 #define DIFF_TER_SCORE         81
 169 #define KNOWN_SAME_TER_SCORE   0
 170 #define KNOWN_DIFF_TER_SCORE   51
 171
 172 /* The maximum number of tiles that the unit might uncover in a move.
 173  * #define MAX_NEW_TILES          (1 + 4 * (unit_type_get(punit)->vision_range))
 174  * The previous line would be ideal, but we'd like these to be constants
 175  * for efficiency, so pretend vision_range == 1 */
 176 #define MAX_NEW_TILES          5
 177
 178 /* The number of tiles that the unit can see. =(1 + 2r)^2
 179  * #define VISION_TILES           (1 + 2 * unit_type_get(punit)->vision_range)*\
 180  *                                (1 + 2 * unit_type_get(punit)->vision_range)
 181  * As above, set vision_range == 1 */
 182 #define VISION_TILES           9
 183
 184 /* The desirability of the best tile possible without cities or huts.
 185  * TER_SCORE is given per 1% of certainty about the terrain, so
 186  * muliply by 100 to compensate. */
 187 #define BEST_NORMAL_TILE       \
 188   (100 * MAX_NEW_TILES * DIFF_TER_SCORE +\
 189    100 * (VISION_TILES - MAX_NEW_TILES) * KNOWN_DIFF_TER_SCORE)
 190
 191 /* We value exploring around our cities just slightly more than exploring
 192  * tiles fully surrounded by different terrain. */
 193 #define OWN_CITY_SCORE         (BEST_NORMAL_TILE + 1)
 194
 195 /* And we value exploring huts even more than our own cities. */
 196 #define HUT_SCORE              (OWN_CITY_SCORE + 1)
 197
 198 #define BEST_POSSIBLE_SCORE    (HUT_SCORE + BEST_NORMAL_TILE)
 199
 200 static int explorer_desirable(struct tile *ptile, struct player *pplayer,
 201                               struct unit *punit)
 202 {
 203   int radius_sq = unit_type_get(punit)->vision_radius_sq;
 204   int desirable = 0;
 205   int unknown = 0;
 206
 207   /* First do some checks that would make a tile completely non-desirable.
 208    * If we're a barbarian and the tile has a hut, don't go there. */
 209   if (is_barbarian(pplayer) && tile_has_cause_extra(ptile, EC_HUT)) {
 210     return 0;
 211   }
 212
 213   /* Do no try to cross borders and break a treaty, etc. */
 214   if (!player_may_explore(ptile, punit->owner, unit_type_get(punit))) {
 215     return 0;
 216   }
 217
 218   circle_iterate(ptile, radius_sq, ptile1) {
 219     int native = likely_native(ptile1, pplayer, unit_class_get(punit));
 220
 221     if (!map_is_known(ptile1, pplayer)) {
 222       unknown++;
 223
 224       /* FIXME: we should add OWN_CITY_SCORE to desirable if the tile
 225        * can be harvested by a city of ours. Just calculating this each
 226        * time becomes rather expensive. Jason Short suggests:
 227        * It should be easy to generate this information once, for
 228        * the entire world.  It can be used by everyone and only
 229        * sometimes needs to be recalculated (actually all changes
 230        * only require local recalculation, but that could be unstable). */
 231
 232       desirable += (native * SAME_TER_SCORE + (100 - native) * DIFF_TER_SCORE);
 233     } else {
 234       if(is_tiles_adjacent(ptile, ptile1)) {
 235         /* we don't value staying offshore from land,
 236          * only adjacent. Otherwise destroyers do the wrong thing. */
 237         desirable += (native * KNOWN_SAME_TER_SCORE
 238                       + (100 - native) * KNOWN_DIFF_TER_SCORE);
 239       }
 240     }
 241   } circle_iterate_end;
 242
 243   if (unknown <= 0) {
 244     /* We make sure we'll uncover at least one unexplored tile. */
 245     desirable = 0;
 246   }
 247
 248   if ((!pplayer->ai_controlled || !has_handicap(pplayer, H_HUTS))
 249       && map_is_known(ptile, pplayer)
 250       && tile_has_cause_extra(ptile, EC_HUT)) {
 251     /* we want to explore huts whenever we can,
 252      * even if doing so will not uncover any tiles. */
 253     desirable += HUT_SCORE;
 254   }
 255
 256   return desirable;
 257 }
 258
 259 /**************************************************************************
 260   Handle eXplore mode of a unit (explorers are always in eXplore mode
 261   for AI) - explores unknown territory, finds huts.
 262
 263   MR_OK: there is more territory to be explored.
 264   MR_DEATH: unit died.
 265   MR_PAUSE: unit cannot explore further now.
 266   Other results: unit cannot explore further.
 267 **************************************************************************/
 268 enum unit_move_result manage_auto_explorer(struct unit *punit)
 269 {
 270   struct player *pplayer = unit_owner(punit);
 271   /* Loop prevention */
 272   const struct tile *init_tile = unit_tile(punit);
 273
 274   /* The log of the want of the most desirable tile,
 275    * given nearby water, cities, etc. */
 276   double log_most_desirable = -FC_INFINITY;
 277
 278   /* The maximum distance we are willing to search. It decreases depending
 279    * on the want of already discovered tagets.  It is defined as the distance
 280    * at which a tile with BEST_POSSIBLE_SCORE would have to be found in
 281    * order to be better than the current most_desirable tile. */
 282   int max_dist = FC_INFINITY;
 283
 284   /* Coordinates of most desirable tile. Initialized to make
 285    * compiler happy. Also MC to the best tile. */
 286   struct tile *best_tile = NULL;
 287   int best_MC = FC_INFINITY;
 288
 289   /* Path-finding stuff */
 290   struct pf_map *pfm;
 291   struct pf_parameter parameter;
 292
 293 #define DIST_FACTOR   0.6
 294
 295   double logDF = log(DIST_FACTOR);
 296   double logBPS = log(BEST_POSSIBLE_SCORE);
 297
 298   UNIT_LOG(LOG_DEBUG, punit, "auto-exploring.");
 299
 300   if (pplayer->ai_controlled && unit_has_type_flag(punit, UTYF_GAMELOSS)) {
 301     UNIT_LOG(LOG_DEBUG, punit, "exploration too dangerous!");
 302     return MR_BAD_ACTIVITY; /* too dangerous */
 303   }
 304
 305   TIMING_LOG(AIT_EXPLORER, TIMER_START);
 306
 307   pft_fill_unit_parameter(&parameter, punit);
 308   parameter.get_TB = no_fights_or_unknown;
 309   /* When exploring, even AI should pretend to not cheat. */
 310   parameter.omniscience = FALSE;
 311
 312   pfm = pf_map_new(&parameter);
 313   pf_map_move_costs_iterate(pfm, ptile, move_cost, FALSE) {
 314     int desirable;
 315     double log_desirable;
 316
 317     /* Our callback should insure this. */
 318     fc_assert_action(map_is_known(ptile, pplayer), continue);
 319
 320     desirable = explorer_desirable(ptile, pplayer, punit);
 321
 322     if (desirable <= 0) {
 323       /* Totally non-desirable tile. No need to continue. */
 324       continue;
 325     }
 326
 327     /* take the natural log */
 328     log_desirable = log(desirable);
 329
 330     /* Ok, the way we calculate goodness is taking the base tile
 331      * desirability amortized by the time it takes to get there:
 332      *
 333      *     goodness = desirability * DIST_FACTOR^total_MC
 334      *
 335      * TODO: JDS notes that we should really make our exponential
 336      *       term dimensionless by dividing by move_rate.
 337      *
 338      * We want to truncate our search, so we calculate a maximum distance
 339      * that we would move to find the tile with the most possible desirability
 340      * (BEST_POSSIBLE_SCORE) that gives us the same goodness as the current
 341      * tile position we're looking at. Therefore we have:
 342      *
 343      *   desirability * DIST_FACTOR^total_MC =
 344      *               BEST_POSSIBLE_SCORE * DIST_FACTOR^(max distance)      (1)
 345      *
 346      * and then solve for max_dist. We only want to change max_dist when
 347      * we find a tile that has better goodness than we've found so far; hence
 348      * the conditional below. It looks cryptic, but all it is is testing which
 349      * of two goodnesses is bigger after taking the natural log of both sides.
 350      */
 351     if (log_desirable + move_cost * logDF
 352         > log_most_desirable + best_MC * logDF) {
 353
 354       log_most_desirable = log_desirable;
 355       best_tile = ptile;
 356       best_MC = move_cost;
 357
 358       /* take the natural log and solve equation (1) above.  We round
 359        * max_dist down (is this correct?). */
 360       max_dist = best_MC + (log_most_desirable - logBPS)/logDF;
 361     }
 362
 363     /* let's not go further than this */
 364     if (move_cost > max_dist) {
 365       break;
 366     }
 367   } pf_map_move_costs_iterate_end;
 368   pf_map_destroy(pfm);
 369
 370   TIMING_LOG(AIT_EXPLORER, TIMER_STOP);
 371
 372   /* Go to the best tile found. */
 373   if (best_tile != NULL) {
 374     /* TODO: read the path off the map we made.  Then we can make a path
 375      * which goes beside the unknown, with a good EC callback... */
 376     enum override_bool allow = NO_OVERRIDE;
 377
 378     if (pplayer->ai_controlled) {
 379       CALL_PLR_AI_FUNC(want_to_explore, pplayer, punit, best_tile, &allow);
 380     }
 381     if (allow == OVERRIDE_FALSE) {
 382       UNIT_LOG(LOG_DEBUG, punit, "not allowed to explore");
 383       return MR_NOT_ALLOWED;
 384     }
 385     if (!explorer_goto(punit, best_tile)) {
 386       /* Died?  Strange... */
 387       return MR_DEATH;
 388     }
 389     UNIT_LOG(LOG_DEBUG, punit, "exploration GOTO succeeded");
 390     if (punit->moves_left > 0) {
 391       /* We can still move on... */
 392       if (!same_pos(init_tile, unit_tile(punit))) {
 393         /* At least we moved (and maybe even got to where we wanted).
 394          * Let's do more exploring.
 395          * (Checking only whether our position changed is unsafe: can allow
 396          * yoyoing on a RR) */
 397         UNIT_LOG(LOG_DEBUG, punit, "recursively exploring...");
 398         return manage_auto_explorer(punit);
 399       } else {
 400         UNIT_LOG(LOG_DEBUG, punit, "done exploring (all finished)...");
 401         return MR_PAUSE;
 402       }
 403     }
 404     UNIT_LOG(LOG_DEBUG, punit, "done exploring (but more go go)...");
 405     return MR_OK;
 406   } else {
 407     /* Didn't find anything. */
 408     UNIT_LOG(LOG_DEBUG, punit, "failed to explore more");
 409     return MR_BAD_MAP_POSITION;
 410   }
 411 #undef DIST_FACTOR
 412 }
 413
 414 #undef SAME_TER_SCORE
 415 #undef DIFF_TER_SCORE
 416 #undef KNOWN_SAME_TER_SCORE
 417 #undef KNOWN_DIFF_TER_SCORE
 418 #undef OWN_CITY_SCORE
 419 #undef HUT_SCORE