mapgen_utils.cpp

Go to the documentation of this file.

/*
_   ._       Copyright (c) 1996-2021 Freeciv21 and Freeciv contributors.
 \  |    This file is part of Freeciv21. Freeciv21 is free software: you
  \_|        can redistribute it and/or modify it under the terms of the
 .' '.              GNU General Public License  as published by the Free
 :O O:             Software Foundation, either version 3 of the License,
 '/ \'           or (at your option) any later version. You should have
  :X:      received a copy of the GNU General Public License along with
  :X:              Freeciv21. If not, see https://www.gnu.org/licenses/.
 */
// utility
#include "fcintl.h"
#include "log.h"
#include "rand.h"
#include "support.h" // bool type
 
// common
#include "map.h"
#include "terrain.h"
#include "tile.h"
 
#include "mapgen_utils.h"
 
static bool *placed_map;
 
bool placed_map_is_initialized() { return placed_map != nullptr; }
 
void create_placed_map()
{
  fc_assert_ret(!placed_map_is_initialized());
  placed_map = new bool[MAP_INDEX_SIZE];
  INITIALIZE_ARRAY(placed_map, MAP_INDEX_SIZE, false);
}
 
void destroy_placed_map()
{
  fc_assert_ret(placed_map_is_initialized());
  delete[] placed_map;
  placed_map = nullptr;
}
 
#define pmap(_tile) (placed_map[tile_index(_tile)])
 
bool not_placed(const struct tile *ptile) { return !pmap(ptile); }
 
void map_set_placed(struct tile *ptile) { pmap(ptile) = true; }
 
void map_unset_placed(struct tile *ptile) { pmap(ptile) = false; }
 
void set_all_ocean_tiles_placed()
{
  whole_map_iterate(&(wld.map), ptile)
  {
    if (is_ocean_tile(ptile)) {
      map_set_placed(ptile);
    }
  }
  whole_map_iterate_end;
}
 
void set_placed_near_pos(struct tile *ptile, int dist)
{
  square_iterate(&(wld.map), ptile, dist, tile1) { map_set_placed(tile1); }
  square_iterate_end;
}
 
void adjust_int_map_filtered(int *int_map, int int_map_max, void *data,
                             bool (*filter)(const struct tile *ptile,
                                            const void *data))
{
  int minval = 0, maxval = 0, total = 0;
  bool first = true;
 
  // Determine minimum and maximum value.
  whole_map_iterate_filtered(ptile, data, filter)
  {
    if (first) {
      minval = int_map[tile_index(ptile)];
      maxval = int_map[tile_index(ptile)];
    } else {
      maxval = MAX(maxval, int_map[tile_index(ptile)]);
      minval = MIN(minval, int_map[tile_index(ptile)]);
    }
    first = false;
    total++;
  }
  whole_map_iterate_filtered_end;
 
  if (total == 0) {
    return;
  }
 
  {
    int const size = 1 + maxval - minval;
    int i, count = 0, frequencies[size];
 
    INITIALIZE_ARRAY(frequencies, size, 0);
 
    /* Translate value so the minimum value is 0
       and count the number of occurencies of all values to initialize the
       frequencies[] */
    whole_map_iterate_filtered(ptile, data, filter)
    {
      int_map[tile_index(ptile)] -= minval;
      frequencies[int_map[tile_index(ptile)]]++;
    }
    whole_map_iterate_filtered_end;
 
    // create the linearize function as "incremental" frequencies
    for (i = 0; i < size; i++) {
      count += frequencies[i];
      frequencies[i] = (count * int_map_max) / total;
    }
 
    // apply the linearize function
    whole_map_iterate_filtered(ptile, data, filter)
    {
      int_map[tile_index(ptile)] = frequencies[int_map[tile_index(ptile)]];
    }
    whole_map_iterate_filtered_end;
  }
}
 
void smooth_int_map(int *int_map, bool zeroes_at_edges)
{
  fc_assert_ret(nullptr != int_map);
 
  static const float weight_standard[5] = {0.13, 0.19, 0.37, 0.19, 0.13};
  static const float weight_isometric[5] = {0.15, 0.21, 0.29, 0.21, 0.15};
  const float *weight;
  bool axe = true;
  int *target_map, *source_map;
  int *alt_int_map = new int[MAP_INDEX_SIZE]();
 
  weight = weight_standard;
  target_map = alt_int_map;
  source_map = int_map;
 
  do {
    whole_map_iterate(&(wld.map), ptile)
    {
      float N = 0, D = 0;
 
      axis_iterate(&(wld.map), ptile, pnear, i, 2, axe)
      {
        D += weight[i + 2];
        N += weight[i + 2] * source_map[tile_index(pnear)];
      }
      axis_iterate_end;
      if (zeroes_at_edges) {
        D = 1;
      }
      target_map[tile_index(ptile)] = N / D;
    }
    whole_map_iterate_end;
 
    if (MAP_IS_ISOMETRIC) {
      weight = weight_isometric;
    }
 
    axe = !axe;
 
    source_map = alt_int_map;
    target_map = int_map;
  } while (!axe);
 
  delete[] alt_int_map;
  alt_int_map = nullptr;
}
 
/* These arrays are indexed by continent number (or negative of the
 * ocean number) so the 0th element is unused and the array is 1 element
 * larger than you'd expect.
 *
 * The lake surrounders array tells how many land continents surround each
 * ocean (or -1 if the ocean touches more than one continent).
 *
 * The _sizes arrays give the sizes (in tiles) of each continent and
 * ocean.
 */
std::vector<Continent_id> lake_surrounders;
std::vector<int> continent_sizes;
std::vector<int> ocean_sizes;
 
static void recalculate_lake_surrounders()
{
  lake_surrounders = std::vector<Continent_id>(wld.map.num_oceans + 1, 0);
 
  whole_map_iterate(&(wld.map), ptile)
  {
    const struct terrain *pterrain = tile_terrain(ptile);
    Continent_id cont = tile_continent(ptile);
 
    if (T_UNKNOWN == pterrain) {
      continue;
    }
 
    if (terrain_type_terrain_class(pterrain) != TC_OCEAN) {
      adjc_iterate(&(wld.map), ptile, tile2)
      {
        Continent_id cont2 = tile_continent(tile2);
 
        if (is_ocean_tile(tile2)) {
          if (lake_surrounders[-cont2] == 0) {
            lake_surrounders[-cont2] = cont;
          } else if (lake_surrounders[-cont2] != cont) {
            lake_surrounders[-cont2] = -1;
          }
        }
      }
      adjc_iterate_end;
    }
  }
  whole_map_iterate_end;
}
 
static void assign_continent_flood(struct tile *ptile, bool is_land, int nr)
{
  struct tile_list *tlist = nullptr;
  const struct terrain *pterrain = nullptr;
 
  fc_assert_ret(ptile != nullptr);
 
  pterrain = tile_terrain(ptile);
  /* Check if the initial tile is a valid tile for continent / ocean. */
  fc_assert_ret(
      tile_continent(ptile) == 0 && T_UNKNOWN != pterrain
      && XOR(is_land, terrain_type_terrain_class(pterrain) == TC_OCEAN));
 
  // Create tile list and insert the initial tile.
  tlist = tile_list_new();
  tile_list_append(tlist, ptile);
 
  while (tile_list_size(tlist) > 0) {
    // Iterate over all unchecked tiles.
    tile_list_iterate(tlist, ptile2)
    {
      // Iterate over the adjacent tiles.
      adjc_iterate(&(wld.map), ptile2, ptile3)
      {
        pterrain = tile_terrain(ptile3);
 
        // Check if it is a valid tile for continent / ocean.
        if (tile_continent(ptile3) != 0 || T_UNKNOWN == pterrain
            || !XOR(is_land,
                    terrain_type_terrain_class(pterrain) == TC_OCEAN)) {
          continue;
        }
 
        // Add the tile to the list of tiles to check.
        if (!tile_list_search(tlist, ptile3)) {
          tile_list_append(tlist, ptile3);
        }
      }
      adjc_iterate_end;
 
      // Set the continent data and remove the tile from the list.
      tile_set_continent(ptile2, nr);
      tile_list_remove(tlist, ptile2);
      // count the tile
      if (nr < 0) {
        ocean_sizes[-nr]++;
      } else {
        continent_sizes[nr]++;
      }
    }
    tile_list_iterate_end;
  }
 
  tile_list_destroy(tlist);
}
 
void regenerate_lakes()
{
  struct terrain *lake_for_ocean[2][wld.map.num_oceans];
 
  {
    struct terrain *lakes[2][5];
    int num_laketypes[2] = {0, 0};
    int i;
 
    terrain_type_iterate(pterr)
    {
      if (terrain_has_flag(pterr, TER_FRESHWATER)
          && !terrain_has_flag(pterr, TER_NOT_GENERATED)) {
        int frozen = terrain_has_flag(pterr, TER_FROZEN);
 
        if (num_laketypes[frozen] < ARRAY_SIZE(lakes[frozen])) {
          lakes[frozen][num_laketypes[frozen]++] = pterr;
        } else {
          qDebug("Ruleset has more than %d %s lake types, ignoring %s",
                 static_cast<int> ARRAY_SIZE(lakes[frozen]),
                 frozen ? "frozen" : "unfrozen", terrain_rule_name(pterr));
        }
      }
    }
    terrain_type_iterate_end;
 
    /* We don't want to generate any boundaries between fresh and
     * non-fresh water.
     * If there are no unfrozen lake types, just give up.
     * Else if there are no frozen lake types, use unfrozen lake instead.
     * If both are available, preserve frozenness of previous terrain. */
    if (num_laketypes[0] == 0) {
      return;
    } else if (num_laketypes[1] == 0) {
      for (i = 0; i < wld.map.num_oceans; i++) {
        lake_for_ocean[0][i] = lake_for_ocean[1][i] =
            lakes[0][fc_rand(num_laketypes[0])];
      }
    } else {
      for (i = 0; i < wld.map.num_oceans; i++) {
        int frozen;
        for (frozen = 0; frozen < 2; frozen++) {
          lake_for_ocean[frozen][i] =
              lakes[frozen][fc_rand(num_laketypes[frozen])];
        }
      }
    }
  }
 
  whole_map_iterate(&(wld.map), ptile)
  {
    struct terrain *pterrain = tile_terrain(ptile);
    Continent_id here = tile_continent(ptile);
 
    if (T_UNKNOWN == pterrain) {
      continue;
    }
    if (terrain_type_terrain_class(pterrain) != TC_OCEAN) {
      continue;
    }
    if (0 < lake_surrounders[-here]) {
      if (terrain_control.lake_max_size >= ocean_sizes[-here]) {
        int frozen = terrain_has_flag(pterrain, TER_FROZEN);
        tile_change_terrain(ptile, lake_for_ocean[frozen][-here - 1]);
      }
    }
  }
  whole_map_iterate_end;
}
 
int get_lake_surrounders(Continent_id cont)
{
  return lake_surrounders[-cont];
}
 
int get_continent_size(Continent_id id)
{
  fc_assert_ret_val(id > 0, -1);
  return continent_sizes[id];
}
 
int get_ocean_size(Continent_id id)
{
  fc_assert_ret_val(id > 0, -1);
  return ocean_sizes[id];
}
 
void assign_continent_numbers()
{
  // Initialize
  wld.map.num_continents = 0;
  wld.map.num_oceans = 0;
  continent_sizes = std::vector<int>(1);
  ocean_sizes = std::vector<int>(1);
 
  whole_map_iterate(&(wld.map), ptile) { tile_set_continent(ptile, 0); }
  whole_map_iterate_end;
 
  // Assign new numbers
  whole_map_iterate(&(wld.map), ptile)
  {
    const struct terrain *pterrain = tile_terrain(ptile);
 
    if (tile_continent(ptile) != 0) {
      // Already assigned.
      continue;
    }
 
    if (T_UNKNOWN == pterrain) {
      continue; // Can't assign this.
    }
 
    if (terrain_type_terrain_class(pterrain) != TC_OCEAN) {
      wld.map.num_continents++;
      continent_sizes.push_back(0);
      assign_continent_flood(ptile, true, wld.map.num_continents);
    } else {
      wld.map.num_oceans++;
      ocean_sizes.push_back(0);
      assign_continent_flood(ptile, false, -wld.map.num_oceans);
    }
  }
  whole_map_iterate_end;
 
  recalculate_lake_surrounders();
 
  qDebug("Map has %d continents and %d oceans", wld.map.num_continents,
         wld.map.num_oceans);
}
 
struct terrain *most_shallow_ocean(bool frozen)
{
  bool oceans = false, frozenmatch = false;
  struct terrain *shallow = nullptr;
 
  terrain_type_iterate(pterr)
  {
    if (is_ocean(pterr) && !terrain_has_flag(pterr, TER_NOT_GENERATED)) {
      bool nonfresh = !terrain_has_flag(pterr, TER_FRESHWATER);
      bool frozen_ok = terrain_has_flag(pterr, TER_FROZEN) == frozen;
 
      if (!oceans && nonfresh) {
        // First ocean type seen, reset even if frozenness doesn't match
        oceans = true;
        shallow = pterr;
        frozenmatch = frozen_ok;
        continue;
      } else if (oceans && !nonfresh) {
        // Dismiss any step backward on freshness
        continue;
      }
      if (!frozenmatch && frozen_ok) {
        /* Prefer terrain that matches frozenness (as long as we don't go
         * backwards on freshness) */
        frozenmatch = true;
        shallow = pterr;
        continue;
      } else if (frozenmatch && !frozen_ok) {
        // Dismiss any step backward on frozenness
        continue;
      }
      if (!shallow
          || pterr->property[MG_OCEAN_DEPTH]
                 < shallow->property[MG_OCEAN_DEPTH]) {
        shallow = pterr;
      }
    }
  }
  terrain_type_iterate_end;
 
  return shallow;
}
 
struct terrain *pick_ocean(int depth, bool frozen)
{
  struct terrain *best_terrain = nullptr;
  int best_match = TERRAIN_OCEAN_DEPTH_MAXIMUM;
 
  terrain_type_iterate(pterrain)
  {
    if (terrain_type_terrain_class(pterrain) == TC_OCEAN
        && TERRAIN_OCEAN_DEPTH_MINIMUM <= pterrain->property[MG_OCEAN_DEPTH]
        && frozen == terrain_has_flag(pterrain, TER_FROZEN)
        && !terrain_has_flag(pterrain, TER_NOT_GENERATED)) {
      int match = abs(depth - pterrain->property[MG_OCEAN_DEPTH]);
 
      if (best_match > match) {
        best_match = match;
        best_terrain = pterrain;
      }
    }
  }
  terrain_type_iterate_end;
 
  return best_terrain;
}
 
static int real_distance_to_land(const struct tile *ptile, int max)
{
  square_dxy_iterate(&(wld.map), ptile, max, atile, dx, dy)
  {
    if (terrain_type_terrain_class(tile_terrain(atile)) != TC_OCEAN) {
      return map_vector_to_real_distance(dx, dy);
    }
  }
  square_dxy_iterate_end;
 
  return max + 1;
}
 
static struct terrain *most_adjacent_ocean_type(const struct tile *ptile)
{
  const int need = 2 * wld.map.num_valid_dirs / 3;
  int count;
 
  terrain_type_iterate(pterrain)
  {
    if (terrain_type_terrain_class(pterrain) != TC_OCEAN) {
      continue;
    }
 
    count = 0;
    adjc_iterate(&(wld.map), ptile, atile)
    {
      if (pterrain == tile_terrain(atile) && need <= ++count) {
        return pterrain;
      }
    }
    adjc_iterate_end;
  }
  terrain_type_iterate_end;
 
  return nullptr;
}
 
void smooth_water_depth()
{
  const int OCEAN_DEPTH_STEP = 25;
  const int OCEAN_DEPTH_RAND = 15;
  const int OCEAN_DIST_MAX = TERRAIN_OCEAN_DEPTH_MAXIMUM / OCEAN_DEPTH_STEP;
  struct terrain *ocean;
  int dist;
 
  // First, improve the coasts.
  whole_map_iterate(&(wld.map), ptile)
  {
    if (terrain_type_terrain_class(tile_terrain(ptile)) != TC_OCEAN) {
      continue;
    }
 
    dist = real_distance_to_land(ptile, OCEAN_DIST_MAX);
    if (dist <= OCEAN_DIST_MAX) {
      // Overwrite the terrain (but preserve frozenness).
      ocean = pick_ocean(dist * OCEAN_DEPTH_STEP + fc_rand(OCEAN_DEPTH_RAND),
                         terrain_has_flag(tile_terrain(ptile), TER_FROZEN));
      if (nullptr != ocean && ocean != tile_terrain(ptile)) {
        log_debug("Replacing %s by %s at (%d, %d) "
                  "to have shallow ocean on coast.",
                  terrain_rule_name(tile_terrain(ptile)),
                  terrain_rule_name(ocean), TILE_XY(ptile));
        tile_set_terrain(ptile, ocean);
      }
    }
  }
  whole_map_iterate_end;
 
  // Now, try to have something more continuous.
  whole_map_iterate(&(wld.map), ptile)
  {
    if (terrain_type_terrain_class(tile_terrain(ptile)) != TC_OCEAN) {
      continue;
    }
 
    ocean = most_adjacent_ocean_type(ptile);
    if (nullptr != ocean && ocean != tile_terrain(ptile)) {
      log_debug("Replacing %s by %s at (%d, %d) "
                "to smooth the ocean types.",
                terrain_rule_name(tile_terrain(ptile)),
                terrain_rule_name(ocean), TILE_XY(ptile));
      tile_set_terrain(ptile, ocean);
    }
  }
  whole_map_iterate_end;
}
 
void generator_free()
{
  lake_surrounders.clear();
  continent_sizes.clear();
  ocean_sizes.clear();
}
 
struct terrain *pick_terrain_by_flag(enum terrain_flag_id flag)
{
  bool has_flag[terrain_count()];
  int count = 0;
 
  terrain_type_iterate(pterrain)
  {
    if ((has_flag[terrain_index(pterrain)] =
             (terrain_has_flag(pterrain, flag)
              && !terrain_has_flag(pterrain, TER_NOT_GENERATED)))) {
      count++;
    }
  }
  terrain_type_iterate_end;
 
  count = fc_rand(count);
  terrain_type_iterate(pterrain)
  {
    if (has_flag[terrain_index(pterrain)]) {
      if (count == 0) {
        return pterrain;
      }
      count--;
    }
  }
  terrain_type_iterate_end;
 
  return T_UNKNOWN;
}
 
struct terrain *pick_terrain(enum mapgen_terrain_property target,
                             enum mapgen_terrain_property prefer,
                             enum mapgen_terrain_property avoid)
{
  int sum = 0;
 
  // Find the total weight.
  terrain_type_iterate(pterrain)
  {
    if (!terrain_has_flag(pterrain, TER_NOT_GENERATED)) {
      if (avoid != MG_UNUSED && pterrain->property[avoid] > 0) {
        continue;
      }
      if (prefer != MG_UNUSED && pterrain->property[prefer] == 0) {
        continue;
      }
 
      if (target != MG_UNUSED) {
        sum += pterrain->property[target];
      } else {
        sum++;
      }
    }
  }
  terrain_type_iterate_end;
 
  // Now pick.
  sum = fc_rand(sum);
 
  // Finally figure out which one we picked.
  terrain_type_iterate(pterrain)
  {
    if (!terrain_has_flag(pterrain, TER_NOT_GENERATED)) {
      int property;
 
      if (avoid != MG_UNUSED && pterrain->property[avoid] > 0) {
        continue;
      }
      if (prefer != MG_UNUSED && pterrain->property[prefer] == 0) {
        continue;
      }
 
      if (target != MG_UNUSED) {
        property = pterrain->property[target];
      } else {
        property = 1;
      }
      if (sum < property) {
        return pterrain;
      }
      sum -= property;
    }
  }
  terrain_type_iterate_end;
 
  /* This can happen with sufficient quantities of preferred and avoided
   * characteristics.  Drop a requirement and try again. */
  if (prefer != MG_UNUSED) {
    log_debug("pick_terrain(target: %s, [dropping prefer: %s], avoid: %s)",
              mapgen_terrain_property_name(target),
              mapgen_terrain_property_name(prefer),
              mapgen_terrain_property_name(avoid));
    return pick_terrain(target, MG_UNUSED, avoid);
  } else if (avoid != MG_UNUSED) {
    log_debug(
        "pick_terrain(target: %s, prefer: MG_UNUSED, [dropping avoid: %s])",
        mapgen_terrain_property_name(target),
        mapgen_terrain_property_name(avoid));
    return pick_terrain(target, prefer, MG_UNUSED);
  } else {
    log_debug("pick_terrain([dropping target: %s], prefer: MG_UNUSED, "
              "avoid: MG_UNUSED)",
              mapgen_terrain_property_name(target));
    return pick_terrain(MG_UNUSED, prefer, avoid);
  }
}