[Freeciv-Dev] Re: (PR#2749) place_land_type in mapgen

["kayeats@xxxxxxxxxxxxxxxxxxxxxxxxx via RT" <rt@xxxxxxxxxxxxxx>]

> 1. Why you don't like calloc?

Well the truth is I've just been copying what was done elsewhere in mapgen
when I needed to allocate memory.  Calloc seems much nicer now that I look
into it.

> 2. You should check in place_land_type (which is really place_ter_type) if
> the function returns value within the bounds.  "We require" put in the
> comment doesn't always help.

Would I be correct that at run-time the name of the function that
place_land_type was called with is not availiable (because at the linking
stage it was replaced with an explicit pointer) and hence that there is no
easy way to return in my error message what the function was?

> 3. Placing mountains and hills depending not only on height but on
> gradient too is a very noble aim, but maybe a bit excessive at this time
> (this is directed to Ross too, who I believe started it in his cleanups).
> I seem to recollect how someone was arguing against artillery bombarding
> ships: "the scale is wrong".  I feel similar arguments are applicable
> here.  Even if they aren't, we can still use the height as the first
> approximation of whether it's a hill or plains.

I think that using gradient simply looks nicer.  Instead of always getting
big piles of mountains in the middle of the continent (which in reality
occurs only when two land plates meet (eg India and Asia)) you sometimes
get that and sometimes get coastal mountain ranges.  Try a really big map
and I think you'll see that just using height looks rather funny.  Maybe
this is really a problem with the heightmap generation, I don't know.
I've left it for the time being; its just a case of changing "parameter"
in the function in question, which I'll do if you're really convinced just
using height is best.

> 5. Recursive placing of deserts was removed.  But you can do it even in
> you framework (and then do forests similarly).

Deserts I placed based on closeness to tropics with a bit of flatness
added in to make them blob shaped.  Forests however occur at almost all
altitudes, at all slopes, and at almost all latitudes.  Could you suggest
what function I could use?  (jungles could be closeness to equator with
some flatness to make them blob shaped, but I hesitate to separate out
jungles when I can't improve forests)

> 7. How is it more convenient?  In any case, I feel we should have a
> function is_been_placed(x, y) rather then explicit check for the GRASS or
> PLAIN.

Would you hide a check for GRASS or PLAINS inside this function or do you
have in mind a more complicated way of keeping track?  I went for the
former option in the attached version of the patch.


Index: server/mapgen.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/mapgen.c,v
retrieving revision 1.105
diff -u -r1.105 mapgen.c
--- server/mapgen.c     2003/01/05 23:24:52     1.105
+++ server/mapgen.c     2003/01/07 17:54:29
@@ -67,102 +67,204 @@
 /* this is used for generator>1 */
 #define MAP_NCONT 255
 
+
 /**************************************************************************
-  make_mountains() will convert all squares that are higher than thill to
-  mountains and hills. Notice that thill will be adjusted according to
-  the map.mountains value, so increase map.mountains and you'll get more 
-  hills and mountains (and vice versa).
-**************************************************************************/
-static void make_mountains(int thill)
-{
-  int mount;
-  int j;
-  for (j=0;j<10;j++) {
-    mount=0;
-    whole_map_iterate(x, y) {
-      if (hmap(x, y)>thill) 
-       mount++;
-    } whole_map_iterate_end;
-    if (mount < (map_num_tiles() * map.mountains) / 1000)
-      thill*=95;
-    else 
-      thill*=105;
-    thill/=100;
-  }
+  Checks if land has not yet been placed on tile at (x, y) (because land is 
+  plains based this just means checking if there are plains at (x, y))
+**************************************************************************/
+static bool not_placed(x, y)
+{
+  return map_get_terrain(x, y) == T_PLAINS;
+}
+
+/**************************************************************************
+  Places land according to a function, used for mountains, hills, 
+  swamps, deserts, oceans, and grassland/plains.  "function" is assumed
+  to have range at most 0 to 100 inclusive
+ *************************************************************************/
+static void place_ter_type(enum tile_terrain_type ter, 
+                           int function(int, int), int total)
+{
+  int count = 0;
+  int percent, i;
+  int level = - 1;
+  int max = 100;
+  int *dist;
+  
+  /* make the distribution of the placing function */
+  dist = fc_calloc (max + 1, sizeof(int));
+  for (i = 0; i <= max; i++){
+    dist[i]=0;
+  }  
   
   whole_map_iterate(x, y) {
-    if (hmap(x, y)>thill &&map_get_terrain(x,y)!=T_OCEAN) { 
-      if (myrand(100)>75) 
-       map_set_terrain(x, y, T_MOUNTAINS);
-      else if (myrand(100)>25) 
-       map_set_terrain(x, y, T_HILLS);
+    if (not_placed(x, y)) {
+      /* that is tile at (x, y) is as of yet unset (plains are the default) */
+      if ((function(x, y) > 100) || (function(x, y) < 0)) {
+       freelog(LOG_VERBOSE, "Value %d of function in place_ter_type is not"
+               " in the range 0 to 100 inclusive at (%d, %d); ignoring \n", 
+               function(x, y), x, y);
+      }
+      else {
+       dist[function(x, y)]++;
+      }
     }
   } whole_map_iterate_end;
+  
+  
+  /* Now place land according to the distribution. */
+  
+  /* First determine the maximum value (level) of function such that
+   * the number of tiles that have function value less than level is
+   * at most total  */
+  while ((level < max) && (count <= total)) {
+    level++;
+    count += dist[level];
+  }
+  
+  /* now place land of type ter at all tiles with function value
+   * less than level along with the appropriate fraction of tiles with
+   * function value equal to level so as to get the correct total */
+  if (level < 0) {
+    /* didn't go through the while loop successfully, so we want to place
+     * none of this tile type, thus do nothing */
+  } else{
+    percent = dist[level] ? 100 - (count - total) * 100 / dist[level] : 0;
+    
+    whole_map_iterate(x, y){
+      if ((function(x, y) < level) && not_placed(x, y)){
+       map_set_terrain(x, y, ter);
+      }
+      else if ((function(x, y) == level) && (myrand(100) < percent) 
+              && not_placed(x, y)) {
+       map_set_terrain(x, y, ter);
+      }
+    } whole_map_iterate_end;
+  }
+  free(dist);
 }
 
 /**************************************************************************
- add arctic and tundra squares in the arctic zone. 
- (that is the top 10%, and low 10% of the map)
-**************************************************************************/
-static void make_polar(void)
+  One widely used function for place_ter_type is the height recalibrated
+  this assumes that the minimum value of hmap is 0 as is the case if 
+  adjust_map has been called.
+*************************************************************************/
+static int height_fn(int x, int y)
 {
-  int y,x;
+  return hmap(x, y) * 100 / maxval;
+}
 
-  for (y=0;y<map.ysize/10;y++) {
-    for (x=0;x<map.xsize;x++) {
-      if ((hmap(x, y)+(map.ysize/10-y*25)>myrand(maxval) &&
-          map_get_terrain(x,y)==T_GRASSLAND) || y==0) { 
-       if (y<2)
-         map_set_terrain(x, y, T_ARCTIC);
-       else
-         map_set_terrain(x, y, T_TUNDRA);
-         
-      } 
-    }
-  }
-  for (y=map.ysize*9/10;y<map.ysize;y++) {
-    for (x=0;x<map.xsize;x++) {
-      if ((hmap(x, y)+(map.ysize/10-(map.ysize-y)*25)>myrand(maxval) &&
-          map_get_terrain(x, y)==T_GRASSLAND) || y==map.ysize-1) {
-       if (y>map.ysize-3)
-         map_set_terrain(x, y, T_ARCTIC);
-       else
-         map_set_terrain(x, y, T_TUNDRA);
-      }
-    }
+/**************************************************************************
+  For use in make_mountains and make_swamps, gets the maximum difference in 
+  height between the given tile and 8 surrounding tiles
+ *************************************************************************/
+static int tile_max_steepness(int x, int y)
+{
+  int slope;
+ 
+  slope = -FC_INFINITY;
+  adjc_iterate(x, y, a, b){
+    if (hmap(x, y) - hmap(a, b) > slope)
+      slope = hmap(x, y) - hmap(a, b);
+  } adjc_iterate_end;
+
+  return slope;
+}
+
+/**************************************************************************
+  The function which determines the distribution of mountains and hills
+ *************************************************************************/
+static int mountain_fn(int x, int y)
+{
+  int parameter; /* a percent determining relative importance of
+                  * absolute height and steepness */
+  int slopepart, heightpart, val;
+  static int slopemax = -1;
+  static int slopemin = -1;
+  
+  /* if its the first time through calculate slopemax and slopemin */
+  if (slopemax == -1) {
+    slopemin = tile_max_steepness(1, 1);
+    slopemax = slopemin;
+    whole_map_iterate(x, y){
+      val = tile_max_steepness(x, y);
+      if (slopemin > val)
+       slopemin = val;
+      if (slopemax < val)
+       slopemax = val;
+    } whole_map_iterate_end;
   }
 
-  /* only arctic and tundra allowed at the poles (first and last two lines,
-     as defined in make_passable() ), to be consistent with generator>1. 
-     turn every land tile on the second lines that is not arctic into tundra,
-     since the first lines has already been set to all arctic above. */
-  for (x=0;x<map.xsize;x++) {
-    if (map_get_terrain(x, 1)!=T_ARCTIC &&
-       map_get_terrain(x, 1)!=T_OCEAN)
-      map_set_terrain(x, 1, T_TUNDRA);
-    if (map_get_terrain(x, map.ysize-2)!=T_ARCTIC && 
-       map_get_terrain(x, map.ysize-2)!=T_OCEAN)
-      map_set_terrain(x, map.ysize-2, T_TUNDRA);
+  /* set up parameter */
+  if (map.generator == 1){
+    parameter = 95;
   }
+  else {
+    parameter = 30;
+  }
+
+  /* now computed the weighted function of slope and absolute height */
+  if (slopemax == slopemin)
+    slopepart = (100 - parameter) / 2;
+  else
+    slopepart = (tile_max_steepness(x, y) - slopemin) * (100 - parameter)
+      / (slopemax - slopemin);
+  if (maxval == 0)
+    heightpart = parameter / 2;
+  else
+    heightpart = hmap(x, y) * parameter / maxval; 
+  return 100 - slopepart - heightpart;
 }
 
 /**************************************************************************
-  recursively generate deserts, i use the heights of the map, to make the
-  desert unregulary shaped, diff is the recursion stopper, and will be reduced
-  more if desert wants to grow in the y direction, so we end up with 
-  "wide" deserts. 
-**************************************************************************/
-static void make_desert(int x, int y, int height, int diff) 
-{
-  if (abs(hmap(x, y)-height)<diff && map_get_terrain(x, y)==T_GRASSLAND) {
-    map_set_terrain(x, y, T_DESERT);
-    cartesian_adjacent_iterate(x, y, x1, y1) {
-      if (x != x1)
-       make_desert(x1, y1, height, diff-1);
-      else /* y != y1 */
-       make_desert(x1, y1, height, diff-3);
-    } cartesian_adjacent_iterate_end;
+  make_mountains uses place_ter_type with a function of both height and 
+  steepness to place mountains and hills in accordance with map.mountains
+**************************************************************************/
+static void make_mountains()
+{
+  int mtotal = (map_num_tiles() * map.mountains * map.landpercent) / 20000;
+  int htotal = mtotal; 
+
+  place_ter_type(T_MOUNTAINS, mountain_fn, mtotal);
+  place_ter_type(T_HILLS, mountain_fn, htotal);
+}
+
+/**************************************************************************
+  The placing function for arctic and tundra
+ *************************************************************************/
+static int polar_fn(int x, int y)
+{
+  return y > map.ysize - y - 1 ? map.ysize - y - 1 : y;
+}
+
+/**************************************************************************
+ Place arctic and tundra by first making a strip of arctic and then calling
+ place_ter_type for the rest with a function based on distance from poles,
+ there is no server option for amount of polar land so we have to guess
+**************************************************************************/
+static void make_polar(void)
+{
+  int x;
+  int atotal = (5 * map_num_tiles() * map.landpercent)/20000;
+  int ttotal = atotal;
+
+  /* first the polar strip must be placed */
+  /* note that atotal is keeping track of the glaciers over land, not
+     glaciers over water as well */
+  for (x=0;x<map.xsize;x++) {
+    map_set_terrain(x, 0, T_ARCTIC);
+    if (not_placed(x, 0)){
+        atotal --;
+    }
+    map_set_terrain(x, map.ysize-1, T_ARCTIC);
+    if (not_placed(x, map.ysize-1)){
+        atotal --;
+    }
   }
+
+  /* now use place_ter_type for the rest */
+  place_ter_type(T_ARCTIC, polar_fn, atotal);
+  place_ter_type(T_TUNDRA, polar_fn, ttotal);
 }
 
 /**************************************************************************
@@ -176,7 +278,7 @@
   if (y==0 || y==map.ysize-1)
     return;
 
-  if (map_get_terrain(x, y)==T_GRASSLAND) {
+  if (not_placed(x, y)) {
     if (y>map.ysize*42/100 && y<map.ysize*58/100 && myrand(100)>50)
       map_set_terrain(x, y, T_JUNGLE);
     else 
@@ -197,19 +299,19 @@
 static void make_forests(void)
 {
   int x,y;
-  int forestsize = (map_num_tiles() * map.forestsize) / 1000;
+  int forestsize = (map_num_tiles() * map.landpercent * map.forestsize) / 
10000;
 
   forests = 0;
 
   do {
     rand_map_pos(&x, &y);
-    if (map_get_terrain(x, y)==T_GRASSLAND) {
+    if (not_placed(x, y)) {
       make_forest(x,y, hmap(x, y), 25);
     }
     if (myrand(100)>75) {
       y=(myrand(map.ysize*2/10))+map.ysize*4/10;
       x=myrand(map.xsize);
-      if (map_get_terrain(x, y)==T_GRASSLAND) {
+      if (not_placed(x, y)) {
        make_forest(x,y, hmap(x, y), 25);
       }
     }
@@ -217,60 +319,60 @@
 }
 
 /**************************************************************************
-  swamps, is placed on low lying locations, that will typically be close to
-  the shoreline. They're put at random (where there is grassland)
-  and with 50% chance each of it's neighbour squares will be converted to
-  swamp aswell
-**************************************************************************/
-static void make_swamps(void)
-{
-  int x,y,swamps;
-  int forever=0;
-  for (swamps=0;swamps<map.swampsize;) {
-    forever++;
-    if (forever>1000) return;
-    rand_map_pos(&x, &y);
-    if (map_get_terrain(x, y)==T_GRASSLAND && hmap(x, y)<(maxval*60)/100) {
-      map_set_terrain(x, y, T_SWAMP);
-      cartesian_adjacent_iterate(x, y, x1, y1) {
-       if (myrand(10)>5 && map_get_terrain(x1, y1) != T_OCEAN) 
-         map_set_terrain(x1, y1, T_SWAMP);
-       /* maybe this should increment i too? */
-      } cartesian_adjacent_iterate_end;
-      swamps++;
-    }
+  swamps are placed on low lying locations using place_ter_type
+  (I have tried also taking into account steepness (putting them on flat
+  land only), it is a tough call as to which is better)
+**************************************************************************/
+static void make_swamps()
+{
+  int stotal=(map_num_tiles() * map.landpercent * map.swampsize) / 10000;
+  place_ter_type(T_SWAMP, height_fn, stotal);
+}
+
+/**************************************************************************
+  Placing function for deserts, based on distance from tropics of cancer or
+  capricorn and on flatness
+ *************************************************************************/
+static int desert_fn(int x, int y)
+{
+  int parameter = 70;
+  int dpart, slopepart, val;
+  static int slopemax = -1;
+  static int slopemin = -1;
+
+  /* if its the first time through calculate slopemax and slopemin */
+  if (slopemax == -1) {
+    slopemin = tile_max_steepness(1, 1);
+    slopemax = slopemin;
+    whole_map_iterate(x, y){
+      val = tile_max_steepness(x, y);
+      if (slopemin > val)
+       slopemin = val;
+      if (slopemax < val)
+       slopemax = val;
+    } whole_map_iterate_end;
   }
+
+  /* now calculate the weighted function of slope and distance from tropics */
+  if (slopemax == slopemin)
+    slopepart = (100 - parameter) / 2;
+  else
+    slopepart = (tile_max_steepness(x, y) - slopemin) * (100 - parameter)
+      / (slopemax - slopemin);
+  dpart = (abs(map.ysize * 65 / 180 - y) > abs(map.ysize * 105 / 180 - y) ?
+           abs(map.ysize * 105 / 180 - y) : abs(map.ysize * 65 / 180 - y))
+    * parameter / 65;
+  return slopepart + dpart;
 }
 
 /*************************************************************************
-  make_deserts calls make_desert until we have enough deserts actually
-  there is no map setting for how many we want, what happends is that
-  we choose a random coordinate between 20 and 30 degrees north and south 
-  (deserts tend to be between 15 and 35, make_desert will expand them) and 
-  if it's a grassland square we call make_desert with this coordinate, we 
-  try this 500 times for each region: north and south.
+  Uses place_ter_type to place deserts
 **************************************************************************/
 static void make_deserts(void)
 {
-  int x,y,i,j;
-  i=map.deserts;
-  j=0;
-  while (i > 0 && j < 500) {
-    j++;
-
-    y=myrand(map.ysize*10/180)+map.ysize*110/180;
-    x=myrand(map.xsize);
-    if (map_get_terrain(x, y)==T_GRASSLAND) {
-      make_desert(x,y, hmap(x, y), 50);
-      i--;
-    }
-    y=myrand(map.ysize*10/180)+map.ysize*60/180;
-    x=myrand(map.xsize);
-    if (map_get_terrain(x, y)==T_GRASSLAND) {
-      make_desert(x,y, hmap(x, y), 50);
-      i--;
-    }
-  }
+  int dtotal = (map_num_tiles() * map.deserts * map.landpercent)/10000;
+
+  place_ter_type(T_DESERT, desert_fn, dtotal);
 }
 
 /*********************************************************************
@@ -759,15 +861,27 @@
 }
 
 /**************************************************************************
-  make_plains converts 50% of the remaining grassland to plains, this should
-  maybe be lowered to 30% or done in batches, like the swamps?
+  distribution function for grasslands, based on height and a random factor
 **************************************************************************/
-static void make_plains(void)
+static int grass_fn(int x, int y)
 {
-  whole_map_iterate(x, y) {
-    if (map_get_terrain(x, y) == T_GRASSLAND && myrand(100) > 50)
-      map_set_terrain(x, y, T_PLAINS);
-  } whole_map_iterate_end;
+  int parameter = 50;
+
+  if ((map.generator >= 2) && (map.generator <= 4)){
+    return myrand(100);
+  }
+
+  return myrand(parameter) + height_fn(x, y) * (100 - parameter) / 100;
+}
+
+/**************************************************************************
+  make_grass makes grassland on the lowlands that remain using place_ter_type
+**************************************************************************/
+static void make_grass(void)
+{
+  int gtotal = (map_num_tiles() * map.landpercent * map.grasssize) / 20000;
+
+  place_ter_type(T_GRASSLAND, grass_fn, gtotal);
 }
 
 /**************************************************************************
@@ -825,37 +939,25 @@
 **************************************************************************/
 static void make_land(void)
 {
-  int tres=(maxval*map.landpercent)/100;
-  int count=0;
-  int total = (map_num_tiles() * map.landpercent) / 100;
-  int forever=0;
-  do {
-    forever++;
-    if (forever>50) break; /* loop elimination */
-    count=0;
-    whole_map_iterate(x, y) {
-      if (hmap(x, y) < tres)
-       map_set_terrain(x, y, T_OCEAN);
-      else {
-       map_set_terrain(x, y, T_GRASSLAND);
-       count++;
-      }
-    } whole_map_iterate_end;
-    if (count>total)
-      tres*=11;
-    else
-      tres*=9;
-    tres/=10;
-  } while (abs(total-count)> maxval/40);
+  int ototal = (map_num_tiles() * (100 - map.landpercent)) / 100;
+
+  /* set all tiles to plains */
+  whole_map_iterate(x, y){
+    map_set_terrain(x, y, T_PLAINS);
+  } whole_map_iterate_end;
+
+  /* now fill in the oceans and do call the functions which do the rest */
+  place_ter_type(T_OCEAN, height_fn, ototal);
+
   if (map.separatepoles) {
     make_passable();
   }
-  make_mountains(maxval*8/10);
+  make_polar();
+  make_mountains();
+  make_deserts();
   make_forests();
   make_swamps();
-  make_deserts();
-  make_plains();
-  make_polar();
+  make_grass();
   make_fair();
   make_rivers();
 }
@@ -1443,7 +1545,7 @@
     get_random_map_position_from_state(&x, &y, pstate);
 
     if (map_get_continent(x, y, NULL) == pstate->isleindex &&
-       map_get_terrain(x, y) == T_GRASSLAND) {
+       not_placed(x, y)) {
 
       /* the first condition helps make terrain more contiguous,
         the second lets it avoid the coast: */
@@ -1469,7 +1571,7 @@
            map_set_terrain(x, y, T_RIVER);
        }
       }
-      if (map_get_terrain(x,y) != T_GRASSLAND) i--;
+      if (!not_placed(x,y)) i--;
     }
   }
 }
@@ -1496,7 +1598,7 @@
   while (i > 0 && (failsafe--) > 0) {
     get_random_map_position_from_state(&x, &y, pstate);
     if (map_get_continent(x, y, NULL) == pstate->isleindex &&
-       map_get_terrain(x, y) == T_GRASSLAND) {
+       not_placed(x, y)) {
 
       /* the first condition helps make terrain more contiguous,
         the second lets it avoid the coast: */
@@ -1568,7 +1670,7 @@
          return i != 0;
        }
 
-        map_set_terrain(map_x, map_y, T_GRASSLAND);
+        map_set_terrain(map_x, map_y, T_PLAINS);
        map_set_continent(map_x, map_y, NULL,  pstate->isleindex);
         i++;
       }
@@ -1826,7 +1928,7 @@
   for (i = game.nplayers; i > 0; i--) {
     make_island(10 * pstate->totalmass / totalweight, 0, pstate);
   }
-  make_plains();  
+  make_grass();  
   free(height_map);
   height_map = NULL;
 
@@ -1911,7 +2013,7 @@
                  pstate);
   }
 
-  make_plains();  
+  make_grass();  
   free(height_map);
   height_map = NULL;
     
@@ -1987,7 +2089,7 @@
   for (i = game.nplayers; i > 0; i--) {
     make_island(10 * pstate->totalmass / totalweight, 0, pstate);
   }
-  make_plains();  
+  make_grass();  
   free(height_map);
   height_map = NULL;