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

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

Sorry, I didn't sent this to rt the first time.

> > 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.
>
> It's the simplest, but if it really looks better...

Well that's always an opinion sort of thing.  I think it looks better; I
think its worth it.  If you don't agree (or if other people in general
don't agree) then so be it.

> Yes, that's what I had in mind.  So why PLAINS were more convenient for
> you?

Because to place plains on a base of grass I need an inverse height
function and since there are no implicit functions in C (as I understand
it anyway) I would have had one more silly little function cluttering up
the works, wheras changing to plains involved essentially no cost and
I could use the same height function as for oceans and swamps.

> I was just thinking of increasing the probability of desert/jungle/forest
> at (x,y) if there is a forest around and then generating it in three or so
> calls to the same function, so it would imitate the 3 levels of
> recursion...

I hadn't thought of that.  Its not quite this easy because forests you
place during an iteration easily cause the whole thing to run away with
itself.  The best I could come up with is what I have now for
make_forests, it's a bit convoluted.

I set the parameter in forest_fn higher than I think is prettiest, but it
looks more like it used to this way and will make the fairness people
happier (same issue as the parameter in make_grass -- see patch 3 of 3).

When doing the forests, I realized that my calculation of dpart in
desert_fn was wrong on two counts --- 65 and 105 are not equal distances
from 90, and I hadn't normalized properly.  So I've now fixed that as
well.


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 21:38:06
@@ -56,7 +56,6 @@
 
 static int *height_map;
 static int maxval=0;
-static int forests=0;
 
 struct isledata {
   int goodies;
@@ -67,210 +66,310 @@
 /* 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, val;
+  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)) {
+      val = function(x, y);
+      if ((val > 100) || (val < 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", 
+               val, x, y);
+      }
+      else {
+       dist[val]++;
+      }
     }
   } 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;
+  }
 }
 
 /**************************************************************************
- 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. 
+  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_desert(int x, int y, int height, int diff) 
+static void make_mountains()
 {
-  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;
-  }
+  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;
 }
 
 /**************************************************************************
-  a recursive function that adds forest to the current location and try
-  to spread out to the neighbours, it's called from make_forests until
-  enough forest has been planted. diff is again the block function.
-  if we're close to equator it will with 50% chance generate jungle instead
+ 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_forest(int x, int y, int height, int diff)
+static void make_polar(void)
 {
-  if (y==0 || y==map.ysize-1)
-    return;
+  int x;
+  int atotal = (5 * map_num_tiles() * map.landpercent)/20000;
+  int ttotal = atotal;
 
-  if (map_get_terrain(x, y)==T_GRASSLAND) {
-    if (y>map.ysize*42/100 && y<map.ysize*58/100 && myrand(100)>50)
-      map_set_terrain(x, y, T_JUNGLE);
-    else 
-      map_set_terrain(x, y, T_FOREST);
-      if (abs(hmap(x, y)-height)<diff) {
-       cartesian_adjacent_iterate(x, y, x1, y1) {
-         if (myrand(10)>5) make_forest(x1, y1, height, diff-5);
-       } cartesian_adjacent_iterate_end;
-      }
-    forests++;
+  /* 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);
 }
 
 /**************************************************************************
-  makeforest calls make_forest with random grassland locations until there
-  has been made enough forests. (the map.forestsize value controls this) 
+  forest placing function based on a random factor and proximity of forests
 **************************************************************************/
-static void make_forests(void)
+static int forest_fn(int x, int y)
 {
-  int x,y;
-  int forestsize = (map_num_tiles() * map.forestsize) / 1000;
-
-  forests = 0;
+  int count = 0;
+  int parameter = 30;
 
-  do {
-    rand_map_pos(&x, &y);
-    if (map_get_terrain(x, y)==T_GRASSLAND) {
-      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) {
-       make_forest(x,y, hmap(x, y), 25);
-      }
+  adjc_iterate(x, y, x1, y1) {
+    if (map_get_terrain(x1, y1) == T_FOREST){
+      count++;
     }
-  } while (forests<forestsize);
+  } adjc_iterate_end;
+
+  return myrand(parameter) + (8 - count) * (100 - parameter) / 8;
 }
 
 /**************************************************************************
-  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
+  makeforest calls make_forest with random grassland locations until there
+  has been made enough forests. (the map.forestsize value controls this) 
 **************************************************************************/
-static void make_swamps(void)
+static void make_forests(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++;
+  int ftotal = (map_num_tiles() * map.landpercent * map.forestsize) / 10000;
+  int i;
+  
+  /* call place_ter_type three times with one third the forests each time, 
+   * each time through place jungles then afterwards convert to forest; 
+   * this way in a given call to place_ter_type only
+   * forests placed in previous calls are taken into consideration */
+  for (i = 0; i < 3; i++){
+    place_ter_type(T_JUNGLE, forest_fn, ftotal / 3);
+    whole_map_iterate(x, y){
+      if (map_get_terrain(x, y) == T_JUNGLE) {
+       map_set_terrain(x, y, T_FOREST);
+      }
+    } whole_map_iterate_end;
+  }
+
+  /* now put the tropical forests back to jungle */
+  whole_map_iterate(x, y){
+    if ((map_get_terrain(x, y) == T_FOREST) && 
+       ((abs(map.ysize/2 - y) < map.ysize * 10 / 180) || 
+       ((abs(map.ysize/2 - y) < map.ysize * 15 / 180) && 
+        (myrand(100) > 50)))){
+      map_set_terrain(x, y, T_JUNGLE);
     }
+  } whole_map_iterate_end;
+}
+
+/**************************************************************************
+  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 * 115 / 180 - y) ?
+           abs(map.ysize * 115 / 180 - y) : abs(map.ysize * 65 / 180 - y))
+    * parameter * 180 / (65 * map.ysize);
+  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,18 +858,30 @@
 }
 
 /**************************************************************************
-  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);
+}
+
+/**************************************************************************
   we want the map to be sailable east-west at least at north and south pole 
   and make it a bit jagged at the edge as well.
   So this procedure converts the second line and the second last line to
@@ -825,37 +936,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 +1542,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 +1568,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 +1595,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 +1667,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 +1925,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 +2010,7 @@
                  pstate);
   }
 
-  make_plains();  
+  make_grass();  
   free(height_map);
   height_map = NULL;
     
@@ -1987,7 +2086,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;