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

["Ross W. Wetmore" <rwetmore@xxxxxxxxxxxx>]

This clearly significantly increases the computation effort, introduces
a lot of almost impossible to solve issues relating to the size of the
allocated arrays vs the selection space and final selection sixe, and
clearly changes the distribution function.

The interface is also so incredibly unwieldy and limiting that you 
really can't do any significant filter operations.

I'm not sure why anyone would waste time trying such things :-).

There are better and higher priority things to do to fix freeciv.

Cheers,
RossW
=====

At 02:05 PM 01/10/23 -0400, Jason Dorje Short wrote:
>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.
>
>jasonIndex: 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++) {
>