server/generator/fracture_map.c

   1 /***********************************************************************
   2  Freeciv - Copyright (C) 1996-2016 - 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 #ifdef HAVE_CONFIG_H
  14 #include <fc_config.h>
  15 #endif
  16
  17 /* utility */
  18 #include "rand.h"
  19
  20 /* common */
  21 #include "map.h"
  22
  23 /* server/generator */
  24 #include "height_map.h"
  25 #include "mapgen_topology.h"
  26 #include "mapgen_utils.h"
  27
  28 #include "fracture_map.h"
  29
  30 static void circle_bresenham(int xc, int yc, int r, int nn);
  31 static void fmfill(int x, int y, int c, int r);
  32 static int local_ave_elevation(struct tile *ptile);
  33
  34 extern int *height_map;
  35 int num_landmass = 50;
  36
  37 typedef struct {
  38   int x;
  39   int y;
  40 } map_point;
  41
  42 typedef struct {
  43   int minX, minY;
  44   int maxX, maxY;
  45   int elevation;
  46 } map_landmass;
  47
  48 /* Landmass: a chunk of rock with common properties */
  49 static map_landmass *landmass;
  50 static map_point *fracture_points;
  51
  52 /**************************************************************************
  53   Fracture map generator
  54 **************************************************************************/
  55 void make_fracture_map(void)
  56 {
  57   int nn, mm;
  58   int rad;
  59   int x,y;
  60   struct tile *ptile1;
  61
  62   /* Calculate the mountain level.  map.server.mountains specifies the
  63    * percentage of land that is turned into hills and mountains. */
  64   hmap_mountain_level = (((hmap_max_level - hmap_shore_level)
  65                           * (100 - wld.map.server.steepness))
  66                          / 100 + hmap_shore_level);
  67
  68   /* For larger maps, increase the number of landmasses - makes the map more interesting */
  69   num_landmass = 20 + 15 * get_sqsize();
  70   landmass = (map_landmass *)fc_malloc((wld.map.xsize / 2 + wld.map.ysize / 2 + num_landmass) * sizeof(map_landmass));
  71   fracture_points = (map_point *)fc_malloc((wld.map.xsize / 2 + wld.map.ysize / 2 + num_landmass) * sizeof(map_point));
  72   height_map = fc_malloc(sizeof(*height_map) * MAP_INDEX_SIZE);
  73
  74   /* Setup a whole bunch of landmasses along the view bordere. These will be sunken
  75      to create ocean terrain.*/
  76   nn = 0;
  77   for (x = 3; x < wld.map.xsize; x += 5, nn++) {
  78     fracture_points[nn].x = x;
  79     fracture_points[nn].y = 3;
  80   }
  81   for (x = 3; x < wld.map.xsize; x += 5, nn++) {
  82     fracture_points[nn].x = x;
  83     fracture_points[nn].y = wld.map.ysize - 3;
  84   }
  85   for (y = 3; y < wld.map.ysize; y += 5, nn++) {
  86     fracture_points[nn].x = 3;
  87     fracture_points[nn].y = y;
  88   }
  89   for (y = 3; y < wld.map.ysize; y += 5, nn++) {
  90     fracture_points[nn].x = wld.map.xsize - 3;
  91     fracture_points[nn].y = y;
  92   }
  93
  94   /* pick remaining points randomly */
  95   mm = nn;
  96   for (; nn < mm + num_landmass; nn++) {
  97     fracture_points[nn].x = fc_rand(wld.map.xsize - 6) + 3;
  98     fracture_points[nn].y = fc_rand(wld.map.ysize - 6) + 3;
  99   }
 100   for (nn = 0; nn < mm + num_landmass; nn++) {
 101     landmass[nn].minX = wld.map.xsize - 1;
 102     landmass[nn].minY = wld.map.ysize - 1;
 103     landmass[nn].maxX = 0;
 104     landmass[nn].maxY = 0;
 105     x = fracture_points[nn].x;
 106     y = fracture_points[nn].y;
 107     ptile1 = native_pos_to_tile(&(wld.map), x, y);
 108     ptile1->continent = nn + 1;
 109   }
 110
 111   /* Assign a base elevation to the landmass */
 112   for (nn = 0; nn < mm + num_landmass; nn++) {
 113     if (nn < mm) { /* sink the border masses */
 114       landmass[nn].elevation = 0;
 115     } else {
 116       landmass[nn].elevation = fc_rand(1000);
 117     }
 118   }
 119
 120   /* Assign cells to landmass. Gradually expand the radius of the
 121      fracture point. */
 122   for (rad = 1; rad < (wld.map.xsize >> 1); rad++) {
 123     for (nn = 0; nn < mm + num_landmass; nn++) {
 124       circle_bresenham(fracture_points[nn].x, fracture_points[nn].y, rad, nn+1);
 125     }
 126   }
 127
 128   /* put in some random fuzz */
 129   whole_map_iterate(&(wld.map), ptile) {
 130     if (hmap(ptile) > hmap_shore_level) {
 131       hmap(ptile) = hmap(ptile) + fc_rand(4) - 2;
 132     }
 133     if (hmap(ptile) <= hmap_shore_level) {
 134       hmap(ptile) = hmap_shore_level + 1;
 135     }
 136   } whole_map_iterate_end;
 137
 138   adjust_int_map(height_map, hmap_max_level);
 139   free(landmass);
 140   free(fracture_points);
 141 }
 142
 143 /**************************************************************************
 144   An expanding circle from the fracture point is used to determine the
 145    midpoint between fractures. The cells must be assigned to landmasses
 146    anyway.
 147 **************************************************************************/
 148 static void circle_bresenham(int xc, int yc, int r, int nn)
 149 {
 150   int x = 0;
 151   int y = r;
 152   int p = 3 - 2 * r;
 153
 154   if (!r) {
 155     return;
 156   }
 157
 158   while (y >= x) { /* only formulate 1/8 of circle */
 159     fmfill(xc-x, yc-y, nn, r); /* upper left left */
 160     fmfill(xc-y, yc-x, nn, r); /* upper upper left */
 161     fmfill(xc+y, yc-x, nn, r); /* upper upper right */
 162     fmfill(xc+x, yc-y, nn, r); /* upper right right */
 163     fmfill(xc-x, yc+y, nn, r); /* lower left left */
 164     fmfill(xc-y, yc+x, nn, r); /* lower lower left */
 165     fmfill(xc+y, yc+x, nn, r); /* lower lower right */
 166     fmfill(xc+x, yc+y, nn, r); /* lower right right */
 167     if (p < 0) {
 168       p += 4 * x++ + 6;
 169     } else {
 170       p += 4 * (x++ - y--) + 10;
 171     }
 172   }
 173 }
 174
 175 /**************************************************************************
 176    Assign landmass in 3x3 area increments to avoid "holes" created by the
 177    circle algorithm.
 178 **************************************************************************/
 179 static void fmfill(int x, int y, int c, int r)
 180 {
 181   int x_less, x_more, y_less, y_more;
 182   struct tile *ptileXY;
 183   struct tile *ptileX2Y;
 184   struct tile *ptileX1Y;
 185   struct tile *ptileXY2;
 186   struct tile *ptileXY1;
 187   struct tile *ptileX2Y1;
 188   struct tile *ptileX2Y2;
 189   struct tile *ptileX1Y2;
 190   struct tile *ptileX1Y1;
 191
 192   if (x < 0) {
 193     x = wld.map.xsize + x;
 194   } else if (x > wld.map.xsize) {
 195     x = x - wld.map.xsize;
 196   }
 197   x_less = x - 1;
 198   if (x_less < 0) {
 199     x_less = wld.map.xsize - 1;
 200   }
 201   x_more = x + 1;
 202   if (x_more >= wld.map.xsize) {
 203     x_more = 0;
 204   }
 205   y_less = y - 1;
 206   if (y_less < 0) {
 207     y_less = wld.map.ysize - 1;
 208   }
 209   y_more = y + 1;
 210   if (y_more >= wld.map.ysize) {
 211     y_more = 0;
 212   }
 213
 214   if (y >= 0 && y < wld.map.ysize) {
 215     ptileXY = native_pos_to_tile(&(wld.map), x, y);
 216     ptileX2Y = native_pos_to_tile(&(wld.map), x_more, y);
 217     ptileX1Y = native_pos_to_tile(&(wld.map), x_less, y);
 218     ptileXY2 = native_pos_to_tile(&(wld.map), x, y_more);
 219     ptileXY1 = native_pos_to_tile(&(wld.map), x, y_less);
 220     ptileX2Y1 = native_pos_to_tile(&(wld.map), x_more, y_less);
 221     ptileX2Y2 = native_pos_to_tile(&(wld.map), x_more, y_more);
 222     ptileX1Y2 = native_pos_to_tile(&(wld.map), x_less, y_more);
 223     ptileX1Y1 = native_pos_to_tile(&(wld.map), x_less, y_less);
 224
 225     if (ptileXY->continent == 0 ) {
 226       ptileXY->continent = c;
 227       ptileX2Y->continent = c;
 228       ptileX1Y->continent = c;
 229       ptileXY2->continent = c;
 230       ptileXY1->continent = c;
 231       ptileX2Y2->continent = c;
 232       ptileX2Y1->continent = c;
 233       ptileX1Y2->continent = c;
 234       ptileX1Y1->continent = c;
 235       hmap(ptileXY) = landmass[c-1].elevation;
 236       hmap(ptileX2Y) = landmass[c-1].elevation;
 237       hmap(ptileX1Y) = landmass[c-1].elevation;
 238       hmap(ptileXY2) = landmass[c-1].elevation;
 239       hmap(ptileXY1) = landmass[c-1].elevation;
 240       hmap(ptileX2Y1) = landmass[c-1].elevation;
 241       hmap(ptileX2Y2) = landmass[c-1].elevation;
 242       hmap(ptileX1Y2) = landmass[c-1].elevation;
 243       hmap(ptileX1Y1) = landmass[c-1].elevation;
 244       /* This bit of code could track the maximum and minimum extent
 245        * of the landmass. */
 246       if (x < landmass[c-1].minX) {
 247         landmass[c-1].minX = x;
 248       }
 249       if (x > landmass[c-1].maxX) {
 250         landmass[c-1].maxX = x;
 251       }
 252       if (y < landmass[c-1].minY) {
 253         landmass[c-1].minY = y;
 254       }
 255       if (y > landmass[c-1].maxY) {
 256         landmass[c-1].maxY = y;
 257       }
 258     }
 259   }
 260 }
 261
 262 /**************************************************************************
 263     Determine the local average elevation. Used to determine where hills
 264     and mountains are.
 265 **************************************************************************/
 266 static int local_ave_elevation(struct tile *ptile)
 267 {
 268   int ele;
 269   int n;
 270
 271   n = ele = 0;
 272   square_iterate(&(wld.map), ptile, 3, tile2) {
 273     ele = ele + hmap(tile2);
 274     n++;
 275   } square_iterate_end;
 276   ele /= n;
 277
 278   return ele;
 279 }
 280
 281 /**************************************************************************
 282   make_fracture_relief() Goes through a couple of iterations.
 283   The first iteration chooses mountains and hills based on how much the
 284   tile exceeds the elevation of the surrounding tiles. This will typically
 285   causes hills and mountains to be placed along the edges of landmasses.
 286   It can generate mountain ranges where there a differences in elevation
 287   between landmasses.
 288 **************************************************************************/
 289 void make_fracture_relief(void)
 290 {
 291   bool choose_mountain;
 292   bool choose_hill;
 293   int landarea;
 294   int total_mtns;
 295   int iter;
 296
 297   /* compute the land area */
 298   landarea = 0;
 299   whole_map_iterate(&(wld.map), ptile) {
 300     if (hmap(ptile) > hmap_shore_level) {
 301       landarea++;
 302     }
 303   } whole_map_iterate_end;
 304
 305   /* Iteration 1
 306      Choose hills and mountains based on local elevation.
 307   */
 308   total_mtns = 0;
 309   whole_map_iterate(&(wld.map), ptile) {
 310     if (not_placed(ptile) && hmap(ptile) > hmap_shore_level) {  /* place on land only */
 311       /* mountains */
 312       choose_mountain = (hmap(ptile) > local_ave_elevation(ptile) * 1.20)
 313         || (area_is_too_flat(ptile, hmap_mountain_level, hmap(ptile)) && (fc_rand(10) < 4));
 314
 315       choose_hill = (hmap(ptile) > local_ave_elevation(ptile) * 1.10)
 316         || (area_is_too_flat(ptile, hmap_mountain_level, hmap(ptile)) && (fc_rand(10) < 4));
 317       /* The following avoids hills and mountains directly along the coast. */
 318       if (count_terrain_class_near_tile(ptile, TRUE, TRUE, TC_OCEAN) > 0) {
 319         choose_mountain = FALSE;
 320         choose_hill = FALSE;
 321       }
 322       if (choose_mountain) {
 323         total_mtns++;
 324         tile_set_terrain(ptile,pick_terrain(MG_MOUNTAINOUS, MG_UNUSED, MG_GREEN));
 325         map_set_placed(ptile);
 326       } else if (choose_hill) {
 327         /* hills */
 328         total_mtns++;
 329         tile_set_terrain(ptile,pick_terrain(MG_MOUNTAINOUS, MG_GREEN, MG_UNUSED));
 330         map_set_placed(ptile);
 331       }
 332     }
 333   } whole_map_iterate_end;
 334
 335   /* Iteration 2
 336      Make sure the map has at least the minimum number of mountains according to the
 337      map steepness setting.
 338      The iteration limit is a failsafe to prevent the iteration from taking forever.
 339   */
 340   for (iter = 0; total_mtns < (landarea * wld.map.server.steepness) / 100 && iter < 50;
 341        iter++) {
 342     whole_map_iterate(&(wld.map), ptile) {
 343       if (not_placed(ptile) && hmap(ptile) > hmap_shore_level) {  /* place on land only */
 344         choose_mountain = fc_rand(10000) < 10;
 345         choose_hill = fc_rand(10000) < 10;
 346         if (choose_mountain) {
 347           total_mtns++;
 348           tile_set_terrain(ptile,pick_terrain(MG_MOUNTAINOUS, MG_UNUSED, MG_GREEN));
 349           map_set_placed(ptile);
 350         } else if (choose_hill) {
 351           /* hills */
 352           total_mtns++;
 353           tile_set_terrain(ptile,pick_terrain(MG_MOUNTAINOUS, MG_GREEN, MG_UNUSED));
 354           map_set_placed(ptile);
 355         }
 356       }
 357       if (total_mtns >= landarea * wld.map.server.steepness / 100) {
 358         break;
 359       }
 360     } whole_map_iterate_end;
 361   }
 362 }