server/generator/startpos.c

   1 /***********************************************************************
   2  Freeciv - Copyright (C) 1996 - 2004 The Freeciv Project Team
   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> /* sqrt, HUGE_VAL */
  19
  20 /* utility */
  21 #include "log.h"
  22 #include "fcintl.h"
  23
  24 /* common */
  25 #include "game.h"
  26 #include "map.h"
  27 #include "movement.h"
  28
  29 /* server */
  30 #include "maphand.h"
  31
  32 /* server/generator */
  33 #include "mapgen_topology.h"
  34 #include "mapgen_utils.h"
  35 #include "startpos.h"
  36 #include "temperature_map.h"
  37
  38 struct islands_data_type {
  39   Continent_id id;
  40   int size;
  41   int goodies;
  42   int starters;
  43   int total;
  44 };
  45 static struct islands_data_type *islands;
  46 static int *islands_index;
  47
  48 /****************************************************************************
  49   Return an approximation of the goodness of a tile to a civilization.
  50 ****************************************************************************/
  51 static int get_tile_value(struct tile *ptile)
  52 {
  53   int value;
  54   int irrig_bonus = 0;
  55   int mine_bonus = 0;
  56   struct tile *roaded;
  57   struct extra_type *nextra;
  58
  59   /* Give one point for each food / shield / trade produced. */
  60   value = 0;
  61   output_type_iterate(o) {
  62     value += city_tile_output(NULL, ptile, FALSE, o);
  63   } output_type_iterate_end;
  64
  65   roaded = tile_virtual_new(ptile);
  66
  67   if (num_role_units(L_SETTLERS) > 0) {
  68     struct unit_type *start_worker = get_role_unit(L_SETTLERS, 0);
  69
  70     extra_type_by_cause_iterate(EC_ROAD, pextra) {
  71       struct road_type *proad = extra_road_get(pextra);
  72
  73       if (road_can_be_built(proad, roaded)
  74           && are_reqs_active(NULL, NULL, NULL, NULL, roaded,
  75                              NULL, start_worker, NULL, NULL, NULL,
  76                              &pextra->reqs, RPT_CERTAIN)) {
  77         tile_add_extra(roaded, pextra);
  78       }
  79     } extra_type_by_cause_iterate_end;
  80   }
  81
  82   nextra = next_extra_for_tile(roaded, EC_IRRIGATION, NULL, NULL);
  83
  84   if (nextra != NULL) {
  85     struct tile *vtile;
  86
  87     vtile = tile_virtual_new(roaded);
  88     tile_apply_activity(vtile, ACTIVITY_IRRIGATE, nextra);
  89     irrig_bonus = -value;
  90     output_type_iterate(o) {
  91       irrig_bonus += city_tile_output(NULL, vtile, FALSE, o);
  92     } output_type_iterate_end;
  93     tile_virtual_destroy(vtile);
  94   }
  95
  96   nextra = next_extra_for_tile(roaded, EC_MINE, NULL, NULL);
  97
  98   /* Same set of roads used with mine as with irrigation. */
  99   if (nextra != NULL) {
 100     struct tile *vtile;
 101
 102     vtile = tile_virtual_new(roaded);
 103     tile_apply_activity(vtile, ACTIVITY_MINE, nextra);
 104     mine_bonus = -value;
 105     output_type_iterate(o) {
 106       mine_bonus += city_tile_output(NULL, vtile, FALSE, o);
 107     } output_type_iterate_end;
 108     tile_virtual_destroy(vtile);
 109   }
 110
 111   tile_virtual_destroy(roaded);
 112
 113   value += MAX(0, MAX(mine_bonus, irrig_bonus)) / 2;
 114
 115   return value;
 116 }
 117
 118 struct start_filter_data {
 119   int min_value;
 120   struct unit_type *initial_unit;
 121   int *value;
 122 };
 123
 124 /****************************************************************************
 125   Check if number of reachable native tiles is sufficient.
 126   Initially given tile is assumed to be native (not checked by this function)
 127 ****************************************************************************/
 128 static bool check_native_area(const struct unit_type *utype,
 129                               const struct tile *ptile,
 130                               int min_area)
 131 {
 132   int tiles = 1; /* There's the central tile already. */
 133   struct tile_list *tlist = tile_list_new();
 134   struct tile *central = tile_virtual_new(ptile); /* Non-const virtual tile */
 135   struct dbv handled;
 136
 137   dbv_init(&handled, MAP_INDEX_SIZE);
 138
 139   tile_list_append(tlist, central);
 140
 141   while (tile_list_size(tlist) > 0 && tiles < min_area) {
 142     tile_list_iterate(tlist, ptile2) {
 143       adjc_iterate(&(wld.map), ptile2, ptile3) {
 144         int idx = tile_index(ptile3);
 145
 146         if (!dbv_isset(&handled, idx) && is_native_tile(utype, ptile3)) {
 147           tiles++;
 148           tile_list_append(tlist, ptile3);
 149           dbv_set(&handled, idx);
 150           if (tiles >= min_area) {
 151             /* Break out when we already know that area is sufficient. */
 152             break;
 153           }
 154         }
 155       } adjc_iterate_end;
 156
 157       tile_list_remove(tlist, ptile2);
 158
 159       if (tiles >= min_area) {
 160         /* Break out when we already know that area is sufficient. */
 161         break;
 162       }
 163     } tile_list_iterate_end;
 164   }
 165
 166   tile_list_destroy(tlist);
 167
 168   dbv_free(&handled);
 169
 170   tile_virtual_destroy(central);
 171
 172   return tiles >= min_area;
 173 }
 174
 175 /****************************************************************************
 176   Return TRUE if (x,y) is a good starting position.
 177
 178   Bad places:
 179   - Islands with no room.
 180   - Non-suitable terrain;
 181   - On a hut;
 182   - Too close to another starter on the same continent:
 183     'dist' is too close (real_map_distance)
 184     'nr' is the number of other start positions to check for too closeness.
 185 ****************************************************************************/
 186 static bool is_valid_start_pos(const struct tile *ptile, const void *dataptr)
 187 {
 188   const struct start_filter_data *pdata = dataptr;
 189   struct islands_data_type *island;
 190   int cont_size, cont = tile_continent(ptile);
 191
 192   /* Only start on certain terrain types. */
 193   if (pdata->value[tile_index(ptile)] < pdata->min_value) {
 194       return FALSE;
 195   }
 196
 197   fc_assert_ret_val(cont > 0, FALSE);
 198   if (islands[islands_index[cont]].starters == 0) {
 199     return FALSE;
 200   }
 201
 202   /* Don't start on a hut. */
 203   if (tile_has_cause_extra(ptile, EC_HUT)) {
 204     return FALSE;
 205   }
 206
 207   /* Has to be native tile for initial unit */
 208   if (!is_native_tile(pdata->initial_unit, ptile)) {
 209     return FALSE;
 210   }
 211
 212   /* Check native area size. */
 213   if (!check_native_area(pdata->initial_unit, ptile,
 214                          terrain_control.min_start_native_area)) {
 215     return FALSE;
 216   }
 217
 218   if (game.server.start_city && terrain_has_flag(tile_terrain(ptile), TER_NO_CITIES)) {
 219     return FALSE;
 220   }
 221
 222   /* A longstanding bug allowed starting positions to exist on poles,
 223    * sometimes.  This hack prevents it by setting a fixed distance from
 224    * the pole (dependent on map temperature) that a start pos must be.
 225    * Cold and frozen tiles are not allowed for start pos placement. */
 226   if (tmap_is(ptile, TT_NHOT)) {
 227     return FALSE;
 228   }
 229
 230   /* Don't start too close to someone else. */
 231   cont_size = get_continent_size(cont);
 232   island = islands + islands_index[cont];
 233   map_startpos_iterate(psp) {
 234     struct tile *tile1 = startpos_tile(psp);
 235
 236     if ((tile_continent(ptile) == tile_continent(tile1)
 237          && (real_map_distance(ptile, tile1) * 1000 / pdata->min_value
 238              <= (sqrt(cont_size / island->total))))
 239         || (real_map_distance(ptile, tile1) * 1000 / pdata->min_value < 5)) {
 240       return FALSE;
 241     }
 242   } map_startpos_iterate_end;
 243   return TRUE;
 244 }
 245
 246 /*************************************************************************
 247  help function for qsort
 248  *************************************************************************/
 249 static int compare_islands(const void *A_, const void *B_)
 250 {
 251   const struct islands_data_type *A = A_, *B = B_;
 252
 253   return B->goodies - A->goodies;
 254 }
 255
 256 /****************************************************************************
 257   Initialize islands data.
 258 ****************************************************************************/
 259 static void initialize_isle_data(void)
 260 {
 261   int nr;
 262
 263   islands = fc_malloc((wld.map.num_continents + 1) * sizeof(*islands));
 264   islands_index = fc_malloc((wld.map.num_continents + 1)
 265                             * sizeof(*islands_index));
 266
 267   /* islands[0] is unused. */
 268   for (nr = 1; nr <= wld.map.num_continents; nr++) {
 269     islands[nr].id = nr;
 270     islands[nr].size = get_continent_size(nr);
 271     islands[nr].goodies = 0;
 272     islands[nr].starters = 0;
 273     islands[nr].total = 0;
 274   }
 275 }
 276
 277 /****************************************************************************
 278   A function that filters for TER_STARTER tiles.
 279 ****************************************************************************/
 280 static bool filter_starters(const struct tile *ptile, const void *data)
 281 {
 282   return terrain_has_flag(tile_terrain(ptile), TER_STARTER);
 283 }
 284
 285 /****************************************************************************
 286   where do the different nations start on the map? well this function tries
 287   to spread them out on the different islands.
 288
 289   MAPSTARTPOS_SINGLE: one player per isle.
 290   MAPSTARTPOS_2or3: 2 players per isle (maybe one isle with 3).
 291   MAPSTARTPOS_ALL: all players in asingle isle.
 292   MAPSTARTPOS_VARIABLE: at least 2 player per isle.
 293
 294   Assumes assign_continent_numbers() has already been done!
 295   Returns true on success
 296 ****************************************************************************/
 297 bool create_start_positions(enum map_startpos mode,
 298                             struct unit_type *initial_unit)
 299 {
 300   struct tile *ptile;
 301   int k, sum;
 302   struct start_filter_data data;
 303   int *tile_value_aux = NULL;
 304   int *tile_value = NULL;
 305   int min_goodies_per_player = 1500;
 306   int total_goodies = 0;
 307   /* this is factor is used to maximize land used in extreme little maps */
 308   float efactor =  player_count() / map_size_checked() / 4;
 309   bool failure = FALSE;
 310   bool is_tmap = temperature_is_initialized();
 311
 312   if (wld.map.num_continents < 1) {
 313     /* Currently we can only place starters on land terrain, so fail
 314      * immediately if there isn't any on the map. */
 315     log_verbose("Map has no land, so cannot assign start positions!");
 316     return FALSE;
 317   }
 318
 319   if (!is_tmap) {
 320     /* The temperature map has already been destroyed by the time start
 321      * positions have been placed.  We check for this and then create a
 322      * false temperature map. This is used in the tmap_is() call above.
 323      * We don't create a "real" map here because that requires the height
 324      * map and other information which has already been destroyed. */
 325     create_tmap(FALSE);
 326   }
 327
 328   /* If the default is given, just use MAPSTARTPOS_VARIABLE. */
 329   if (MAPSTARTPOS_DEFAULT == mode) {
 330     log_verbose("Using startpos=VARIABLE");
 331     mode = MAPSTARTPOS_VARIABLE;
 332   }
 333
 334   tile_value_aux = fc_calloc(MAP_INDEX_SIZE, sizeof(*tile_value_aux));
 335   tile_value = fc_calloc(MAP_INDEX_SIZE, sizeof(*tile_value));
 336
 337   /* get the tile value */
 338   whole_map_iterate(&(wld.map), value_tile) {
 339     tile_value_aux[tile_index(value_tile)] = get_tile_value(value_tile);
 340   } whole_map_iterate_end;
 341
 342   /* select the best tiles */
 343   whole_map_iterate(&(wld.map), value_tile) {
 344     int this_tile_value = tile_value_aux[tile_index(value_tile)];
 345     int lcount = 0, bcount = 0;
 346
 347     /* check all tiles within the default city radius */
 348     city_tile_iterate(CITY_MAP_DEFAULT_RADIUS_SQ, value_tile, ptile1) {
 349       if (this_tile_value > tile_value_aux[tile_index(ptile1)]) {
 350         lcount++;
 351       } else if (this_tile_value < tile_value_aux[tile_index(ptile1)]) {
 352         bcount++;
 353       }
 354     } city_tile_iterate_end;
 355
 356     if (lcount <= bcount) {
 357       this_tile_value = 0;
 358     }
 359     tile_value[tile_index(value_tile)] = 100 * this_tile_value;
 360   } whole_map_iterate_end;
 361   /* get an average value */
 362   smooth_int_map(tile_value, TRUE);
 363
 364   initialize_isle_data();
 365
 366   /* Only consider tiles marked as 'starter terrains' by ruleset */
 367   whole_map_iterate(&(wld.map), starter_tile) {
 368     if (!filter_starters(starter_tile, NULL)) {
 369       tile_value[tile_index(starter_tile)] = 0;
 370     } else {
 371       /* Oceanic terrain cannot be starter terrain currently */
 372       fc_assert_action(tile_continent(starter_tile) > 0, continue);
 373       islands[tile_continent(starter_tile)].goodies += tile_value[tile_index(starter_tile)];
 374       total_goodies += tile_value[tile_index(starter_tile)];
 375     }
 376   } whole_map_iterate_end;
 377
 378   /* evaluate the best places on the map */
 379   adjust_int_map_filtered(tile_value, 1000, NULL, filter_starters);
 380
 381   /* Sort the islands so the best ones come first.  Note that islands[0] is
 382    * unused so we just skip it. */
 383   qsort(islands + 1, wld.map.num_continents,
 384         sizeof(*islands), compare_islands);
 385
 386   /* If we can't place starters according to the first choice, change the
 387    * choice. */
 388   if (MAPSTARTPOS_SINGLE == mode
 389       && wld.map.num_continents < player_count() + 3) {
 390     log_verbose("Not enough continents; falling back to startpos=2or3");
 391     mode = MAPSTARTPOS_2or3;
 392   }
 393
 394   if (MAPSTARTPOS_2or3 == mode
 395       && wld.map.num_continents < player_count() / 2 + 4) {
 396     log_verbose("Not enough continents; falling back to startpos=VARIABLE");
 397     mode = MAPSTARTPOS_VARIABLE;
 398   }
 399
 400   if (MAPSTARTPOS_ALL == mode
 401       && (islands[1].goodies < player_count() * min_goodies_per_player
 402           || islands[1].goodies < total_goodies * (0.5 + 0.8 * efactor)
 403           / (1 + efactor))) {
 404     log_verbose("No good enough island; falling back to startpos=VARIABLE");
 405     mode = MAPSTARTPOS_VARIABLE;
 406   }
 407
 408   /* the variable way is the last possibility */
 409   if (MAPSTARTPOS_VARIABLE == mode) {
 410     min_goodies_per_player = total_goodies * (0.65 + 0.8 * efactor)
 411       / (1 + efactor)  / player_count();
 412   }
 413
 414   {
 415     int nr, to_place = player_count(), first = 1;
 416
 417     /* inizialize islands_index */
 418     for (nr = 1; nr <= wld.map.num_continents; nr++) {
 419       islands_index[islands[nr].id] = nr;
 420     }
 421
 422     /* When placing a fixed number of players per island, for fairness, try
 423      * to avoid sets of populated islands where there is more than 10%
 424      * variation in "goodness" within the entire set. (Fallback if that fails:
 425      * place players on the worst available islands.) */
 426     if (MAPSTARTPOS_SINGLE == mode || MAPSTARTPOS_2or3 == mode) {
 427       float var_goodies, best = HUGE_VAL;
 428       int num_islands = (MAPSTARTPOS_SINGLE == mode
 429                          ? player_count() : player_count() / 2);
 430
 431       for (nr = 1; nr <= 1 + wld.map.num_continents - num_islands; nr++) {
 432         if (islands[nr + num_islands - 1].goodies < min_goodies_per_player) {
 433           break;
 434         }
 435         var_goodies
 436             = (islands[nr].goodies - islands[nr + num_islands - 1].goodies)
 437             / (islands[nr + num_islands - 1].goodies);
 438
 439         if (var_goodies < best * 0.9) {
 440           best = var_goodies;
 441           first = nr;
 442         }
 443       }
 444     }
 445
 446     /* set starters per isle */
 447     if (MAPSTARTPOS_ALL == mode) {
 448       islands[1].starters = to_place;
 449       islands[1].total = to_place;
 450       to_place = 0;
 451     }
 452     for (nr = 1; nr <= wld.map.num_continents; nr++) {
 453       if (MAPSTARTPOS_SINGLE == mode && 0 < to_place && nr >= first) {
 454         islands[nr].starters = 1;
 455         islands[nr].total = 1;
 456         to_place--;
 457       }
 458       if (MAPSTARTPOS_2or3 == mode && 0 < to_place && nr >= first) {
 459         islands[nr].starters = 2 + (nr == 1 ? (player_count() % 2) : 0);
 460         to_place -= islands[nr].total = islands[nr].starters;
 461       }
 462
 463       if (MAPSTARTPOS_VARIABLE == mode && 0 < to_place) {
 464         islands[nr].starters = MAX(1, islands[nr].goodies
 465                                    / MAX(1, min_goodies_per_player));
 466         to_place -= islands[nr].total = islands[nr].starters;
 467       }
 468     }
 469   }
 470
 471   data.value = tile_value;
 472   data.min_value = 900;
 473   data.initial_unit = initial_unit;
 474   sum = 0;
 475   for (k = 1; k <= wld.map.num_continents; k++) {
 476     sum += islands[islands_index[k]].starters;
 477     if (islands[islands_index[k]].starters != 0) {
 478       log_verbose("starters on isle %i", k);
 479     }
 480   }
 481   fc_assert_ret_val(player_count() <= sum, FALSE);
 482
 483   /* now search for the best place and set start_positions */
 484   while (map_startpos_count() < player_count()) {
 485     if ((ptile = rand_map_pos_filtered(&(wld.map), &data,
 486                                        is_valid_start_pos))) {
 487       islands[islands_index[(int) tile_continent(ptile)]].starters--;
 488       log_debug("Adding (%d, %d) as starting position %d, %d goodies on "
 489                 "islands.", TILE_XY(ptile), map_startpos_count(),
 490                 islands[islands_index[(int) tile_continent(ptile)]].goodies);
 491       (void) map_startpos_new(ptile);
 492     } else {
 493       data.min_value *= 0.95;
 494       if (data.min_value <= 10) {
 495         log_normal(_("The server appears to have gotten into an infinite "
 496                      "loop in the allocation of starting positions.\nMaybe "
 497                      "the number of players is too high for this map."));
 498         failure = TRUE;
 499         break;
 500       }
 501     }
 502   }
 503
 504   free(islands);
 505   free(islands_index);
 506   islands = NULL;
 507   islands_index = NULL;
 508
 509   if (!is_tmap) {
 510     destroy_tmap();
 511   }
 512
 513   FC_FREE(tile_value_aux);
 514   FC_FREE(tile_value);
 515
 516   return !failure;
 517 }