[Freeciv-Dev] Re: PATCH: rand_pos function and usage (PR#1017)

[Jason Dorje Short <vze2zq63@xxxxxxxxxxx>]

Raimar Falke wrote:
> 
> On Tue, Oct 23, 2001 at 09:32:54AM -0700, jdorje@xxxxxxxxxxxxxxxxxxxxx wrote:
> > Raimar Falke wrote:
> > >
> >
> > <snip snip snip>
> >
> > > It looks like the filter approach and the "classical" approach both
> > > have cases were one is faster. What do you think about a general
> > > interface:
> > >
> > > #define RAND_POS(x, y, pos_check,max_count)
> > >    if(max_count==0)
> > >       RAND_POS_CHECKED(x,y,pos_check);
> > >    else
> > >    {
> > >     do {
> > >       x=myrand(map.xsize);
> > >       y=myrand(map.ysize);
> > >     } while (!(pos_check(x,y)) && max_count-->0);
> > >    }
> > >
> > > Now the programmer can choose based on number he collected which
> > > approach he uses.
> >
> > What about something like this?
> 
> Is it needed to have multiple map positions?

Many places in mapgen.c are much simplified by it (see attached patch).

> > +/* Determines whether the position is normal given that it's in
> > +   the range 0<=x<map.xsize and 0<=y<map.ysize.  It's primarily a
> > +   faster version of is_normal_map_pos since such checks are pretty
> > +   common. */
> 
> > +#define is_normal_map_pos2(x, y) (1)
> 
> IMHO this name is still not acceptable.

Ok, I agree...but what should we use?

> > +/* Parameters:
> > + *   x_arr, y_arr: arrays (or single pointers) for the x and y coordinates
> > + *   number: an identifier containing the number of positions desired.  It 
> > is
> > +       modified to contain the number of positions found.
> > + *   pos_check: an expression that determines if position (x, y) is valid.
> > + *   max_count: the maximum number of times a random algorithm should be
> > +       used before the structured algorithm is used.  The random algorithm
> > +       may give duplicate coordinates, so use max_count==0 if you need all
> > +       distinct coordinates. */
> > +#define RAND_POS_CHECKED(x_arr, y_arr, number, pos_check, max_count)       
> >    \
> > +{                                                                          
> >    \
> > +  int *_x_arr = (x_arr); /* if x_arr is "x", it'll conflict down below */  
> >    \
> > +  int *_y_arr = (y_arr);                                                   
> >    \
> 
> In general I think we should use "struct map_position" more. This may
> such a place.

We should use it always or never.  My preference would be for always, but
currently we're much closer to never.

jason

Index: server/mapgen.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/mapgen.c,v
retrieving revision 1.75
diff -u -r1.75 mapgen.c
--- server/mapgen.c     2001/10/14 21:02:16     1.75
+++ server/mapgen.c     2001/10/23 18:04:21
@@ -195,23 +195,30 @@
 **************************************************************************/
 static void make_forests(void)
 {
-  int x,y;
-  int forestsize=25;
-  forestsize=(map.xsize*map.ysize*map.forestsize)/1000;
-   do {
-    x=myrand(map.xsize);
-    y=myrand(map.ysize);
-    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);
-      }
-    }
-  } while (forests<forestsize);
+  int forestsize=(map.xsize*map.ysize*map.forestsize)/1000;
+  int *x = fc_malloc(sizeof(*x) * forestsize);
+  int *y = fc_malloc(sizeof(*y) * forestsize);
+  int num = (forestsize+myrand(4))/4, num2, i;
+
+  /* First make some extra tropical forests. */
+  RAND_POS_CHECKED(x, y, num,
+                  y >= map.ysize * 4/10 && y < map.ysize * 6/10 && 
map_get_terrain(x, y)==T_GRASSLAND,
+                  0);
+
+  /* Now finish by placing forests everywhere. */
+  num2 = forestsize-num;
+  RAND_POS_CHECKED(x+num, y+num, num2,
+                  map_get_terrain(x, y)==T_GRASSLAND,
+                  0);
+
+  /* Now make the forests. */
+  forestsize = num + num2;
+  for (i=0; i<forestsize; i++) {
+    make_forest(x[i], y[i], hmap(x[i], y[i]), 25);
+  }
+
+  free(x);
+  free(y);
 }
 
 /**************************************************************************
@@ -222,23 +229,27 @@
 **************************************************************************/
 static void make_swamps(void)
 {
-  int x,y,swamps;
-  int forever=0;
-  for (swamps=0;swamps<map.swampsize;) {
-    forever++;
-    if (forever>1000) return;
-    y=myrand(map.ysize);
-    x=myrand(map.xsize);
-    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 *x = fc_malloc(sizeof(*x) * map.swampsize);
+  int *y = fc_malloc(sizeof(*y) * map.swampsize);
+  int swamps = map.swampsize, i;
+
+  /* Pick tiles to turn into swamps. */
+  RAND_POS_CHECKED(x, y, swamps,
+                  map_get_terrain(x, y)==T_GRASSLAND && hmap(x, y) < 
maxval*60/100,
+                  0);
+
+  /* Swampify the tiles.  Note that each swamp tile picked will
+     lead to multiple swamped tiles. */
+  for (i=0; i<swamps; i++) {
+    map_set_terrain(x[i], y[i], T_SWAMP);
+    cartesian_adjacent_iterate(x[i], y[i], x1, y1) {
+      if (myrand(10)>5 && map_get_terrain(x1, y1) != T_OCEAN)
+       map_set_terrain(x1, y1, T_SWAMP);
+    } cartesian_adjacent_iterate_end;
   }
+
+  free(x);
+  free(y);
 }
 
 /*************************************************************************
@@ -251,25 +262,18 @@
 **************************************************************************/
 static void make_deserts(void)
 {
-  int x,y,i,j;
-  i=map.deserts;
-  j=0;
-  while (i && 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 deserts = map.deserts; /* FIXME */
+  int *desert_x = fc_malloc(sizeof(*desert_x) * deserts);
+  int *desert_y = fc_malloc(sizeof(*desert_y) * deserts);
+  int i;
+
+  RAND_POS_CHECKED(desert_x, desert_y, deserts,
+                  ((y>=map.ysize*110/180 && y<=map.ysize*120/180) ||
+                   (y >= map.ysize*60/180 && y <= map.ysize*70/180)) &&
+                  map_get_terrain(x, y)==T_GRASSLAND, 0);
+
+  for (i=0; i<deserts; i++)
+    make_desert(desert_x[i], desert_y[i], hmap(desert_x[i], desert_y[i]), 50);
 }
 
 /*********************************************************************
@@ -659,6 +663,7 @@
   int current_riverlength = 0;
 
   int i; /* Loop variable. */
+  int num;
 
   /* Counts the number of iterations (should increase with 1 during
      every iteration of the main loop in this function).
@@ -672,11 +677,10 @@
         iteration_counter < RIVERS_MAXTRIES) {
 
     /* Don't start any rivers at the poles. */
-    y = myrand(map.ysize - 2) + 1; 
+    num = 1;
+    RAND_POS_CHECKED(&x, &y, num, y >= 1 && y < map.ysize-1, 100);
+    if (num < 1) abort();
 
-    /* Any x-coordinate is valid. */
-    x = myrand(map.xsize);
- 
     /* Check if it is suitable to start a river on the current tile.
      */
     if (
@@ -1140,8 +1144,7 @@
   assert(game.nplayers<=nr+sum);
 
   while (nr<game.nplayers) {
-    x=myrand(map.xsize);
-    y=myrand(map.ysize); 
+    rand_pos(&x, &y);
     if (islands[(int)map_get_continent(x, y)].starters) {
       j++;
       if (!is_starter_close(x, y, nr, dist)) {
@@ -1309,7 +1312,9 @@
   } whole_map_iterate_end;
 
   for (i=0;i<1500;i++) {
-    height_map[myrand(map.ysize*map.xsize)]+=myrand(5000);
+    int x, y;
+    rand_pos(&x, &y);
+    hmap(x, y) += myrand(5000);
     if (!(i%100)) {
       smooth_map(); 
     }
@@ -1381,8 +1386,7 @@
   int x,y,l;
   int count=0;
   while ((number*map.xsize*map.ysize)/2000 && count++<map.xsize*map.ysize*2) {
-    x=myrand(map.xsize);
-    y=myrand(map.ysize);
+    rand_pos(&x, &y);
     l=myrand(6);
     if (map_get_terrain(x, y)!=T_OCEAN && 
        ( map_get_terrain(x, y)!=T_ARCTIC || l<3 )
@@ -1545,8 +1549,7 @@
 static int place_island(void)
 {
   int x, y, xo, yo, i=0;
-  yo = myrand(map.ysize);
-  xo = myrand(map.xsize);
+  rand_pos(&xo, &yo);
 
   /* this helps a lot for maps with high landmass */
   for (y = n, x = w ; y < s && x < e ; y++, x++) {