server/generator/mapgen_utils.c

   1 /***********************************************************************
   2  Freeciv - Copyright (C) 2004 - Marcelo J. Burda
   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 #ifdef HAVE_CONFIG_H
  14 #include <fc_config.h>
  15 #endif
  16
  17 /* utility */
  18 #include "fcintl.h"
  19 #include "log.h"
  20 #include "rand.h"
  21 #include "support.h"            /* bool type */
  22
  23 /* common */
  24 #include "map.h"
  25 #include "packets.h"
  26 #include "terrain.h"
  27 #include "tile.h"
  28
  29 #include "mapgen_utils.h"
  30
  31 /****************************************************************************
  32  Map that contains, according to circumstances, information on whether
  33  we have already placed terrain (special, hut) here.
  34 ****************************************************************************/
  35 static bool *placed_map;
  36
  37 /**************************************************************************
  38  return TRUE if initialized
  39 *************************************************************************/
  40 bool placed_map_is_initialized(void)
  41 {
  42   return placed_map != NULL;
  43 }
  44
  45 /****************************************************************************
  46   Create a clean pmap
  47 ****************************************************************************/
  48 void create_placed_map(void)
  49 {
  50   fc_assert_ret(!placed_map_is_initialized());
  51   placed_map = fc_malloc (sizeof(bool) * MAP_INDEX_SIZE);
  52   INITIALIZE_ARRAY(placed_map, MAP_INDEX_SIZE, FALSE );
  53 }
  54
  55 /****************************************************************************
  56   Free the pmap
  57 ****************************************************************************/
  58 void destroy_placed_map(void)
  59 {
  60   fc_assert_ret(placed_map_is_initialized());
  61   free(placed_map);
  62   placed_map = NULL;
  63 }
  64
  65
  66
  67 #define pmap(_tile) (placed_map[tile_index(_tile)])
  68
  69 /**************************************************************************
  70   Checks if land has not yet been placed on pmap at (x, y)
  71 **************************************************************************/
  72 bool not_placed(const struct tile *ptile)
  73 {
  74   return !pmap(ptile);
  75 }
  76
  77 /**************************************************************************
  78   Mark tile terrain as placed.
  79 **************************************************************************/
  80 void map_set_placed(struct tile *ptile)
  81 {
  82   pmap(ptile) = TRUE;
  83 }
  84
  85 /**************************************************************************
  86   Mark tile terrain as not placed.
  87 **************************************************************************/
  88 void map_unset_placed(struct tile *ptile)
  89 {
  90   pmap(ptile) = FALSE;
  91 }
  92
  93 /****************************************************************************
  94   set all oceanics tiles in placed_map
  95 ****************************************************************************/
  96 void set_all_ocean_tiles_placed(void)
  97 {
  98   whole_map_iterate(&(wld.map), ptile) {
  99     if (is_ocean_tile(ptile)) {
 100       map_set_placed(ptile);
 101     }
 102   } whole_map_iterate_end;
 103 }
 104
 105 /****************************************************************************
 106   Set all nearby tiles as placed on pmap.
 107 ****************************************************************************/
 108 void set_placed_near_pos(struct tile *ptile, int dist)
 109 {
 110   square_iterate(&(wld.map), ptile, dist, tile1) {
 111     map_set_placed(tile1);
 112   } square_iterate_end;
 113 }
 114
 115 /**************************************************************************
 116   Change the values of the integer map, so that they contain ranking of each
 117   tile scaled to [0 .. int_map_max].
 118   The lowest 20% of tiles will have values lower than 0.2 * int_map_max.
 119
 120   If filter is non-null then it only tiles for which filter(ptile, data) is
 121   TRUE will be considered.
 122 **************************************************************************/
 123 void adjust_int_map_filtered(int *int_map, int int_map_max, void *data,
 124                              bool (*filter)(const struct tile *ptile,
 125                                             const void *data))
 126 {
 127   int minval = 0, maxval = 0, total = 0;
 128   bool first = TRUE;
 129
 130   /* Determine minimum and maximum value. */
 131   whole_map_iterate_filtered(ptile, data, filter) {
 132     if (first) {
 133       minval = int_map[tile_index(ptile)];
 134       maxval = int_map[tile_index(ptile)];
 135     } else {
 136       maxval = MAX(maxval, int_map[tile_index(ptile)]);
 137       minval = MIN(minval, int_map[tile_index(ptile)]);
 138     }
 139     first = FALSE;
 140     total++;
 141   } whole_map_iterate_filtered_end;
 142
 143   if (total == 0) {
 144     return;
 145   }
 146
 147   {
 148     int const size = 1 + maxval - minval;
 149     int i, count = 0, frequencies[size];
 150
 151     INITIALIZE_ARRAY(frequencies, size, 0);
 152
 153     /* Translate value so the minimum value is 0
 154        and count the number of occurencies of all values to initialize the
 155        frequencies[] */
 156     whole_map_iterate_filtered(ptile, data, filter) {
 157       int_map[tile_index(ptile)] -= minval;
 158       frequencies[int_map[tile_index(ptile)]]++;
 159     } whole_map_iterate_filtered_end;
 160
 161     /* create the linearize function as "incremental" frequencies */
 162     for (i =  0; i < size; i++) {
 163       count += frequencies[i];
 164       frequencies[i] = (count * int_map_max) / total;
 165     }
 166
 167     /* apply the linearize function */
 168     whole_map_iterate_filtered(ptile, data, filter) {
 169       int_map[tile_index(ptile)] = frequencies[int_map[tile_index(ptile)]];
 170     } whole_map_iterate_filtered_end;
 171   }
 172 }
 173
 174 /****************************************************************************
 175   Is given native position normal position
 176 ****************************************************************************/
 177 bool is_normal_nat_pos(int x, int y)
 178 {
 179   NATIVE_TO_MAP_POS(&x, &y, x, y);
 180   return is_normal_map_pos(x, y);
 181 }
 182
 183 /*******************************************************************************
 184   Apply a Gaussian diffusion filter on the map. The size of the map is
 185   MAP_INDEX_SIZE and the map is indexed by native_pos_to_index function.
 186   If zeroes_at_edges is set, any unreal position on diffusion has 0 value
 187   if zeroes_at_edges in unset the unreal position are not counted.
 188 *******************************************************************************/
 189 void smooth_int_map(int *int_map, bool zeroes_at_edges)
 190 {
 191   static const float weight_standard[5] = { 0.13, 0.19, 0.37, 0.19, 0.13 };
 192   static const float weight_isometric[5] = { 0.15, 0.21, 0.29, 0.21, 0.15 };
 193   const float *weight;
 194   bool axe = TRUE;
 195   int *target_map, *source_map;
 196   int *alt_int_map = fc_calloc(MAP_INDEX_SIZE, sizeof(*alt_int_map));
 197
 198   fc_assert_ret(NULL != int_map);
 199
 200   weight = weight_standard;
 201   target_map = alt_int_map;
 202   source_map = int_map;
 203
 204   do {
 205     whole_map_iterate(&(wld.map), ptile) {
 206       float N = 0, D = 0;
 207
 208       axis_iterate(&(wld.map), ptile, pnear, i, 2, axe) {
 209         D += weight[i + 2];
 210         N += weight[i + 2] * source_map[tile_index(pnear)];
 211       } axis_iterate_end;
 212       if (zeroes_at_edges) {
 213         D = 1;
 214       }
 215       target_map[tile_index(ptile)] = (float)N / D;
 216     } whole_map_iterate_end;
 217
 218     if (MAP_IS_ISOMETRIC) {
 219       weight = weight_isometric;
 220     }
 221
 222     axe = !axe;
 223
 224     source_map = alt_int_map;
 225     target_map = int_map;
 226
 227   } while (!axe);
 228
 229   FC_FREE(alt_int_map);
 230 }
 231
 232 /* These arrays are indexed by continent number (or negative of the
 233  * ocean number) so the 0th element is unused and the array is 1 element
 234  * larger than you'd expect.
 235  *
 236  * The lake surrounders array tells how many land continents surround each
 237  * ocean (or -1 if the ocean touches more than one continent).
 238  *
 239  * The _sizes arrays give the sizes (in tiles) of each continent and
 240  * ocean.
 241  */
 242 static Continent_id *lake_surrounders = NULL;
 243 static int *continent_sizes = NULL;
 244 static int *ocean_sizes = NULL;
 245
 246 /**************************************************************************
 247   Calculate lake_surrounders[] array
 248 **************************************************************************/
 249 static void recalculate_lake_surrounders(void)
 250 {
 251   const size_t size = (wld.map.num_oceans + 1) * sizeof(*lake_surrounders);
 252
 253   lake_surrounders = fc_realloc(lake_surrounders, size);
 254   memset(lake_surrounders, 0, size);
 255
 256   whole_map_iterate(&(wld.map), ptile) {
 257     const struct terrain *pterrain = tile_terrain(ptile);
 258     Continent_id cont = tile_continent(ptile);
 259
 260     if (T_UNKNOWN == pterrain) {
 261       continue;
 262     }
 263
 264     if (terrain_type_terrain_class(pterrain) != TC_OCEAN) {
 265       adjc_iterate(&(wld.map), ptile, tile2) {
 266         Continent_id cont2 = tile_continent(tile2);
 267
 268         if (is_ocean_tile(tile2)) {
 269           if (lake_surrounders[-cont2] == 0) {
 270             lake_surrounders[-cont2] = cont;
 271           } else if (lake_surrounders[-cont2] != cont) {
 272             lake_surrounders[-cont2] = -1;
 273           }
 274         }
 275       } adjc_iterate_end;
 276     }
 277   } whole_map_iterate_end;
 278 }
 279
 280 /*******************************************************************************
 281   Number this tile and nearby tiles with the specified continent number 'nr'.
 282   Due to the number of recursion for large maps a non-recursive algorithm is
 283   utilised.
 284
 285   is_land tells us whether we are assigning continent numbers or ocean
 286   numbers.
 287 *******************************************************************************/
 288 static void assign_continent_flood(struct tile *ptile, bool is_land, int nr)
 289 {
 290   struct tile_list *tlist = NULL;
 291   const struct terrain *pterrain = NULL;
 292
 293   fc_assert_ret(ptile != NULL);
 294
 295   pterrain = tile_terrain(ptile);
 296   /* Check if the initial tile is a valid tile for continent / ocean. */
 297   fc_assert_ret(tile_continent(ptile) == 0
 298                 && T_UNKNOWN != pterrain
 299                 && XOR(is_land, terrain_type_terrain_class(pterrain) == TC_OCEAN));
 300
 301   /* Create tile list and insert the initial tile. */
 302   tlist = tile_list_new();
 303   tile_list_append(tlist, ptile);
 304
 305   while (tile_list_size(tlist) > 0) {
 306     /* Iterate over all unchecked tiles. */
 307     tile_list_iterate(tlist, ptile2) {
 308       /* Iterate over the adjacent tiles. */
 309       adjc_iterate(&(wld.map), ptile2, ptile3) {
 310         pterrain = tile_terrain(ptile3);
 311
 312         /* Check if it is a valid tile for continent / ocean. */
 313         if (tile_continent(ptile3) != 0
 314             || T_UNKNOWN == pterrain
 315             || !XOR(is_land, terrain_type_terrain_class(pterrain) == TC_OCEAN)) {
 316           continue;
 317         }
 318
 319         /* Add the tile to the list of tiles to check. */
 320         if (!tile_list_search(tlist, ptile3)) {
 321           tile_list_append(tlist, ptile3);
 322         }
 323       } adjc_iterate_end;
 324
 325       /* Set the continent data and remove the tile from the list. */
 326       tile_set_continent(ptile2, nr);
 327       tile_list_remove(tlist, ptile2);
 328       /* count the tile */
 329       if (nr < 0) {
 330         ocean_sizes[-nr]++;
 331       } else {
 332         continent_sizes[nr]++;
 333       }
 334     } tile_list_iterate_end;
 335   }
 336
 337   tile_list_destroy(tlist);
 338 }
 339
 340 /**************************************************************************
 341   Regenerate all oceanic tiles for small water bodies as lakes.
 342   Assumes assign_continent_numbers() and recalculate_lake_surrounders()
 343   have already been done!
 344   FIXME: insufficiently generalized, use terrain property.
 345 **************************************************************************/
 346 void regenerate_lakes(void)
 347 {
 348   struct terrain *lake_for_ocean[2][wld.map.num_oceans];
 349
 350   {
 351     struct terrain *lakes[2][5];
 352     int num_laketypes[2] = { 0, 0 };
 353     int i;
 354
 355     terrain_type_iterate(pterr) {
 356       if (terrain_has_flag(pterr, TER_FRESHWATER)
 357           && !terrain_has_flag(pterr, TER_NOT_GENERATED)) {
 358         int frozen = terrain_has_flag(pterr, TER_FROZEN);
 359
 360         if (num_laketypes[frozen] < ARRAY_SIZE(lakes[frozen])) {
 361           lakes[frozen][num_laketypes[frozen]++] = pterr;
 362         } else {
 363           log_verbose("Ruleset has more than %d %s lake types, ignoring %s",
 364                       (int) ARRAY_SIZE(lakes[frozen]),
 365                       frozen ? "frozen" : "unfrozen",
 366                       terrain_rule_name(pterr));
 367         }
 368       }
 369     } terrain_type_iterate_end;
 370
 371     /* We don't want to generate any boundaries between fresh and
 372      * non-fresh water.
 373      * If there are no unfrozen lake types, just give up.
 374      * Else if there are no frozen lake types, use unfrozen lake instead.
 375      * If both are available, preserve frozenness of previous terrain. */
 376     if (num_laketypes[0] == 0) {
 377       return;
 378     } else if (num_laketypes[1] == 0) {
 379       for (i = 0; i < wld.map.num_oceans; i++) {
 380         lake_for_ocean[0][i] = lake_for_ocean[1][i]
 381           = lakes[0][fc_rand(num_laketypes[0])];
 382       }
 383     } else {
 384       for (i = 0; i < wld.map.num_oceans; i++) {
 385         int frozen;
 386         for (frozen = 0; frozen < 2; frozen++) {
 387           lake_for_ocean[frozen][i]
 388             = lakes[frozen][fc_rand(num_laketypes[frozen])];
 389         }
 390       }
 391     }
 392   }
 393
 394   whole_map_iterate(&(wld.map), ptile) {
 395     struct terrain *pterrain = tile_terrain(ptile);
 396     Continent_id here = tile_continent(ptile);
 397
 398     if (T_UNKNOWN == pterrain) {
 399       continue;
 400     }
 401     if (terrain_type_terrain_class(pterrain) != TC_OCEAN) {
 402       continue;
 403     }
 404     if (0 < lake_surrounders[-here]) {
 405       if (terrain_control.lake_max_size >= ocean_sizes[-here]) {
 406         int frozen = terrain_has_flag(pterrain, TER_FROZEN);
 407         tile_change_terrain(ptile, lake_for_ocean[frozen][-here-1]);
 408       }
 409     }
 410   } whole_map_iterate_end;
 411 }
 412
 413 /**************************************************************************
 414   Get continent surrounding lake, or -1 if there is multiple continents.
 415 **************************************************************************/
 416 int get_lake_surrounders(Continent_id cont)
 417 {
 418   return lake_surrounders[-cont];
 419 }
 420
 421 /*************************************************************************
 422   Return size in tiles of the given continent(not ocean)
 423 *************************************************************************/
 424 int get_continent_size(Continent_id id)
 425 {
 426   fc_assert_ret_val(id > 0, -1);
 427   return continent_sizes[id];
 428 }
 429
 430 /*************************************************************************
 431   Return size in tiles of the given ocean. You should use positive ocean
 432   number.
 433 *************************************************************************/
 434 int get_ocean_size(Continent_id id)
 435 {
 436   fc_assert_ret_val(id > 0, -1);
 437   return ocean_sizes[id];
 438 }
 439
 440 /**************************************************************************
 441   Assigns continent and ocean numbers to all tiles, and set
 442   map.num_continents and map.num_oceans.  Recalculates continent and
 443   ocean sizes, and lake_surrounders[] arrays.
 444
 445   Continents have numbers 1 to map.num_continents _inclusive_.
 446   Oceans have (negative) numbers -1 to -map.num_oceans _inclusive_.
 447 **************************************************************************/
 448 void assign_continent_numbers(void)
 449 {
 450   /* Initialize */
 451   wld.map.num_continents = 0;
 452   wld.map.num_oceans = 0;
 453
 454   whole_map_iterate(&(wld.map), ptile) {
 455     tile_set_continent(ptile, 0);
 456   } whole_map_iterate_end;
 457
 458   /* Assign new numbers */
 459   whole_map_iterate(&(wld.map), ptile) {
 460     const struct terrain *pterrain = tile_terrain(ptile);
 461
 462     if (tile_continent(ptile) != 0) {
 463       /* Already assigned. */
 464       continue;
 465     }
 466
 467     if (T_UNKNOWN == pterrain) {
 468       continue; /* Can't assign this. */
 469     }
 470
 471     if (terrain_type_terrain_class(pterrain) != TC_OCEAN) {
 472       wld.map.num_continents++;
 473       continent_sizes = fc_realloc(continent_sizes,
 474                            (wld.map.num_continents + 1) * sizeof(*continent_sizes));
 475       continent_sizes[wld.map.num_continents] = 0;
 476       assign_continent_flood(ptile, TRUE, wld.map.num_continents);
 477     } else {
 478       wld.map.num_oceans++;
 479       ocean_sizes = fc_realloc(ocean_sizes,
 480                        (wld.map.num_oceans + 1) * sizeof(*ocean_sizes));
 481       ocean_sizes[wld.map.num_oceans] = 0;
 482       assign_continent_flood(ptile, FALSE, -wld.map.num_oceans);
 483     }
 484   } whole_map_iterate_end;
 485
 486   recalculate_lake_surrounders();
 487
 488   log_verbose("Map has %d continents and %d oceans",
 489               wld.map.num_continents, wld.map.num_oceans);
 490 }
 491
 492 /**************************************************************************
 493   Return most shallow ocean terrain type. Prefers not to return freshwater
 494   terrain, and will ignore 'frozen' rather than do so.
 495 **************************************************************************/
 496 struct terrain *most_shallow_ocean(bool frozen)
 497 {
 498   bool oceans = FALSE, frozenmatch = FALSE;
 499   struct terrain *shallow = NULL;
 500
 501   terrain_type_iterate(pterr) {
 502     if (is_ocean(pterr) && !terrain_has_flag(pterr, TER_NOT_GENERATED)) {
 503       bool nonfresh = !terrain_has_flag(pterr, TER_FRESHWATER);
 504       bool frozen_ok = terrain_has_flag(pterr, TER_FROZEN) == frozen;
 505
 506       if (!oceans && nonfresh) {
 507         /* First ocean type seen, reset even if frozenness doesn't match */
 508         oceans = TRUE;
 509         shallow = pterr;
 510         frozenmatch = frozen_ok;
 511         continue;
 512       } else if (oceans && !nonfresh) {
 513         /* Dismiss any step backward on freshness */
 514         continue;
 515       }
 516       if (!frozenmatch && frozen_ok) {
 517         /* Prefer terrain that matches frozenness (as long as we don't go
 518          * backwards on freshness) */
 519         frozenmatch = TRUE;
 520         shallow = pterr;
 521         continue;
 522       } else if (frozenmatch && !frozen_ok) {
 523         /* Dismiss any step backward on frozenness */
 524         continue;
 525       }
 526       if (!shallow
 527           || pterr->property[MG_OCEAN_DEPTH] <
 528           shallow->property[MG_OCEAN_DEPTH]) {
 529         shallow = pterr;
 530       }
 531     }
 532   } terrain_type_iterate_end;
 533
 534   return shallow;
 535 }
 536
 537 /**************************************************************************
 538   Picks an ocean terrain to match the given depth.
 539   Only considers terrains with/without Frozen flag depending on 'frozen'.
 540   Return NULL when there is no available ocean.
 541 **************************************************************************/
 542 struct terrain *pick_ocean(int depth, bool frozen)
 543 {
 544   struct terrain *best_terrain = NULL;
 545   int best_match = TERRAIN_OCEAN_DEPTH_MAXIMUM;
 546
 547   terrain_type_iterate(pterrain) {
 548     if (terrain_type_terrain_class(pterrain) == TC_OCEAN
 549         && TERRAIN_OCEAN_DEPTH_MINIMUM <= pterrain->property[MG_OCEAN_DEPTH]
 550         && !!frozen == terrain_has_flag(pterrain, TER_FROZEN)
 551         && !terrain_has_flag(pterrain, TER_NOT_GENERATED)) {
 552       int match = abs(depth - pterrain->property[MG_OCEAN_DEPTH]);
 553
 554       if (best_match > match) {
 555         best_match = match;
 556         best_terrain = pterrain;
 557       }
 558     }
 559   } terrain_type_iterate_end;
 560
 561   return best_terrain;
 562 }
 563
 564 /**************************************************************************
 565   Determines the minimal distance to the land.
 566 **************************************************************************/
 567 static int real_distance_to_land(const struct tile *ptile, int max)
 568 {
 569   square_dxy_iterate(&(wld.map), ptile, max, atile, dx, dy) {
 570     if (terrain_type_terrain_class(tile_terrain(atile)) != TC_OCEAN) {
 571       return map_vector_to_real_distance(dx, dy);
 572     }
 573   } square_dxy_iterate_end;
 574
 575   return max + 1;
 576 }
 577
 578 /**************************************************************************
 579   Determines what is the most popular ocean type arround (need 2/3 of the
 580   adjcacent tiles).
 581 **************************************************************************/
 582 static struct terrain *most_adjacent_ocean_type(const struct tile *ptile)
 583 {
 584   const int need = 2 * wld.map.num_valid_dirs / 3;
 585   int count;
 586
 587   terrain_type_iterate(pterrain) {
 588     if (terrain_type_terrain_class(pterrain) != TC_OCEAN) {
 589       continue;
 590     }
 591
 592     count = 0;
 593     adjc_iterate(&(wld.map), ptile, atile) {
 594       if (pterrain == tile_terrain(atile) && need <= ++count) {
 595         return pterrain;
 596       }
 597     } adjc_iterate_end;
 598   } terrain_type_iterate_end;
 599
 600   return NULL;
 601 }
 602
 603 /**************************************************************************
 604   Makes a simple depth map for all ocean tiles based on their proximity
 605   to any land tiles and reassignes ocean terrain types based on their
 606   MG_OCEAN_DEPTH property values.
 607 **************************************************************************/
 608 void smooth_water_depth(void)
 609 {
 610   const int OCEAN_DEPTH_STEP = 25;
 611   const int OCEAN_DEPTH_RAND = 15;
 612   const int OCEAN_DIST_MAX = TERRAIN_OCEAN_DEPTH_MAXIMUM / OCEAN_DEPTH_STEP;
 613   struct terrain *ocean;
 614   int dist;
 615
 616   /* First, improve the coasts. */
 617   whole_map_iterate(&(wld.map), ptile) {
 618     if (terrain_type_terrain_class(tile_terrain(ptile)) != TC_OCEAN) {
 619       continue;
 620     }
 621
 622     dist = real_distance_to_land(ptile, OCEAN_DIST_MAX);
 623     if (dist <= OCEAN_DIST_MAX) {
 624       /* Overwrite the terrain (but preserve frozenness). */
 625       ocean = pick_ocean(dist * OCEAN_DEPTH_STEP
 626                          + fc_rand(OCEAN_DEPTH_RAND),
 627                          terrain_has_flag(tile_terrain(ptile), TER_FROZEN));
 628       if (NULL != ocean && ocean != tile_terrain(ptile)) {
 629         log_debug("Replacing %s by %s at (%d, %d) "
 630                   "to have shallow ocean on coast.",
 631                   terrain_rule_name(tile_terrain(ptile)),
 632                   terrain_rule_name(ocean), TILE_XY(ptile));
 633         tile_set_terrain(ptile, ocean);
 634       }
 635     }
 636   } whole_map_iterate_end;
 637
 638   /* Now, try to have something more continuous. */
 639   whole_map_iterate(&(wld.map), ptile) {
 640     if (terrain_type_terrain_class(tile_terrain(ptile)) != TC_OCEAN) {
 641       continue;
 642     }
 643
 644     ocean = most_adjacent_ocean_type(ptile);
 645     if (NULL != ocean && ocean != tile_terrain(ptile)) {
 646       log_debug("Replacing %s by %s at (%d, %d) "
 647                 "to smooth the ocean types.",
 648                 terrain_rule_name(tile_terrain(ptile)),
 649                 terrain_rule_name(ocean), TILE_XY(ptile));
 650       tile_set_terrain(ptile, ocean);
 651     }
 652   } whole_map_iterate_end;
 653 }
 654
 655 /**************************************************************************
 656   Free resources allocated by the generator.
 657 **************************************************************************/
 658 void generator_free(void)
 659 {
 660   if (lake_surrounders != NULL) {
 661     free(lake_surrounders);
 662     lake_surrounders = NULL;
 663   }
 664   if (continent_sizes != NULL) {
 665     free(continent_sizes);
 666     continent_sizes = NULL;
 667   }
 668   if (ocean_sizes != NULL) {
 669     free(ocean_sizes);
 670     ocean_sizes = NULL;
 671   }
 672 }
 673
 674 /****************************************************************************
 675   Return a random terrain that has the specified flag.
 676   Returns T_UNKNOWN when there is no matching terrain.
 677 ****************************************************************************/
 678 struct terrain *pick_terrain_by_flag(enum terrain_flag_id flag)
 679 {
 680   bool has_flag[terrain_count()];
 681   int count = 0;
 682
 683   terrain_type_iterate(pterrain) {
 684     if ((has_flag[terrain_index(pterrain)]
 685          = (terrain_has_flag(pterrain, flag)
 686             && !terrain_has_flag(pterrain, TER_NOT_GENERATED)))) {
 687       count++;
 688     }
 689   } terrain_type_iterate_end;
 690
 691   count = fc_rand(count);
 692   terrain_type_iterate(pterrain) {
 693     if (has_flag[terrain_index(pterrain)]) {
 694       if (count == 0) {
 695         return pterrain;
 696       }
 697       count--;
 698     }
 699   } terrain_type_iterate_end;
 700
 701   return T_UNKNOWN;
 702 }
 703
 704
 705 /****************************************************************************
 706   Pick a terrain based on the target property and a property to avoid.
 707
 708   If the target property is given, then all terrains with that property
 709   will be considered and one will be picked at random based on the amount
 710   of the property each terrain has.  If no target property is given all
 711   terrains will be assigned equal likelihood.
 712
 713   If the preferred property is given, only terrains with (some of) that
 714   property will be chosen.
 715
 716   If the avoid property is given, then any terrain with (any of) that
 717   property will be avoided.
 718
 719   This function must always return a valid terrain.
 720 ****************************************************************************/
 721 struct terrain *pick_terrain(enum mapgen_terrain_property target,
 722                              enum mapgen_terrain_property prefer,
 723                              enum mapgen_terrain_property avoid)
 724 {
 725   int sum = 0;
 726
 727   /* Find the total weight. */
 728   terrain_type_iterate(pterrain) {
 729     if (!terrain_has_flag(pterrain, TER_NOT_GENERATED)) {
 730       if (avoid != MG_UNUSED && pterrain->property[avoid] > 0) {
 731         continue;
 732       }
 733       if (prefer != MG_UNUSED && pterrain->property[prefer] == 0) {
 734         continue;
 735       }
 736
 737       if (target != MG_UNUSED) {
 738         sum += pterrain->property[target];
 739       } else {
 740         sum++;
 741       }
 742     }
 743   } terrain_type_iterate_end;
 744
 745   /* Now pick. */
 746   sum = fc_rand(sum);
 747
 748   /* Finally figure out which one we picked. */
 749   terrain_type_iterate(pterrain) {
 750     if (!terrain_has_flag(pterrain, TER_NOT_GENERATED)) {
 751       int property;
 752
 753       if (avoid != MG_UNUSED && pterrain->property[avoid] > 0) {
 754         continue;
 755       }
 756       if (prefer != MG_UNUSED && pterrain->property[prefer] == 0) {
 757         continue;
 758       }
 759
 760       if (target != MG_UNUSED) {
 761         property = pterrain->property[target];
 762       } else {
 763         property = 1;
 764       }
 765       if (sum < property) {
 766         return pterrain;
 767       }
 768       sum -= property;
 769     }
 770   } terrain_type_iterate_end;
 771
 772   /* This can happen with sufficient quantities of preferred and avoided
 773    * characteristics.  Drop a requirement and try again. */
 774   if (prefer != MG_UNUSED) {
 775     log_debug("pick_terrain(target: %s, [dropping prefer: %s], avoid: %s)",
 776               mapgen_terrain_property_name(target),
 777               mapgen_terrain_property_name(prefer),
 778               mapgen_terrain_property_name(avoid));
 779     return pick_terrain(target, MG_UNUSED, avoid);
 780   } else if (avoid != MG_UNUSED) {
 781     log_debug("pick_terrain(target: %s, prefer: %s, [dropping avoid: %s])",
 782               mapgen_terrain_property_name(target),
 783               mapgen_terrain_property_name(prefer),
 784               mapgen_terrain_property_name(avoid));
 785     return pick_terrain(target, prefer, MG_UNUSED);
 786   } else {
 787     log_debug("pick_terrain([dropping target: %s], prefer: %s, avoid: %s)",
 788               mapgen_terrain_property_name(target),
 789               mapgen_terrain_property_name(prefer),
 790               mapgen_terrain_property_name(avoid));
 791     return pick_terrain(MG_UNUSED, prefer, avoid);
 792   }
 793 }