[Freeciv-Dev] PATCH: rand_pos function and usage

[Jason Dorje Short <vze2zq63@xxxxxxxxxxx>]

The attached patch creates a function, rand_pos(&x, &y) that determines
a random map position.  It also uses it in place of all similar code.

There are two reasons such a change is needed:

1. Current code just does

  x = myrand(map.xsize);
  y = myrand(map.ysize);

and assumes that (x,y) is now a valid position.  Under arbitrary
topologies, this will not be the case.  It is necessary to check the
point for validity:

  do {
    x = myrand(map.xsize);
    y = myrand(map.ysize);
  while (!is_normal_map_pos(x, y));

This is cleaner and easier to enforce if it is encapsulated within the
rand_pos function.

2. Checks are needed for some of the random position generation.  For
instance there is code like

  x = myrand(map.xsize);
  y = myrand(map.ysize-2) + 1;

to generate a random non-polar position.  This code will not work under
arbitrary topologies, since the definition of polar may change (for
instance, under an iso-rectangular map the north polar region runs along
the top left diagonal).  We therefore need to generate the position
first and then check it for validity, for instance:

  do {
    rand_pos(&x, &y);
  } while(y==0 || y==map.ysize-1);

Later, a different check may be replaced for (y==0||y==map.ysize-1) that
is topology-dependent.

This could have efficiency problems if we were looking for a very small
subset of positions on the map.  Fortunately, there is no such code
right now.


The places in the code where random positions are generated is pretty
small.  Most of it is in map generation routines, and so is not an
efficiency concern.  The only other times it is used is for nuclear
winter, global warming, and barbarian generation.  So, the loss of
efficiency this new function provides is not a concern.  I ran a couple
of autogames which confirmed this.

jason

? rc
? old
? topology
? a.out
? check_map_pos
? corecleanup_08.ReadMe
? jasongame-middle3
? topology.c
? client/mapview_common.c
? client/mapview_common.h
Index: common/map.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/map.c,v
retrieving revision 1.97
diff -u -r1.97 map.c
--- common/map.c        2001/10/15 13:42:50     1.97
+++ common/map.c        2001/10/18 04:44:02
@@ -1340,6 +1340,17 @@
 }
 
 /**************************************************************************
+Random square anywhere on the map.  Only "normal" positions will be found.
+**************************************************************************/
+void rand_pos(int *x, int *y)
+{
+  do {
+    *x = myrand(map.xsize);
+    *y = myrand(map.ysize);
+  } while (!is_normal_map_pos(*x, *y));
+}
+
+/**************************************************************************
 Random neighbouring square.
 **************************************************************************/
 void rand_neighbour(int x0, int y0, int *x, int *y)
Index: common/map.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/map.h,v
retrieving revision 1.99
diff -u -r1.99 map.h
--- common/map.h        2001/10/15 13:42:51     1.99
+++ common/map.h        2001/10/18 04:44:02
@@ -243,6 +243,7 @@
 void nearest_real_pos(int *x, int *y);
 
 void rand_neighbour(int x0, int y0, int *x, int *y);
+void rand_pos(int *x, int *y);
 
 int is_water_adjacent_to_tile(int x, int y);
 int is_tiles_adjacent(int x0, int y0, int x1, int y1);
Index: server/barbarian.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/barbarian.c,v
retrieving revision 1.35
diff -u -r1.35 barbarian.c
--- server/barbarian.c  2001/10/14 21:02:16     1.35
+++ server/barbarian.c  2001/10/18 04:44:03
@@ -324,8 +324,10 @@
   struct city *pc;
   struct player *barbarians, *victim;
 
-  x = myrand(map.xsize);
-  y = 1 + myrand(map.ysize-2);  /* No uprising on North or South Pole */
+  /* No uprising on North or South Pole */
+  do {
+    rand_pos(&x, &y);
+  } while (y == 0 || y == map.ysize-1);
 
   if( !(pc = dist_nearest_city(NULL, x, y, 1, 0)) )       /* any city */
     return;
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/18 04:44:04
@@ -199,14 +199,14 @@
   int forestsize=25;
   forestsize=(map.xsize*map.ysize*map.forestsize)/1000;
    do {
-    x=myrand(map.xsize);
-    y=myrand(map.ysize);
+    rand_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);
+      do {
+       rand_pos(&x, &y);
+      } while (y < map.ysize * 4/10 || y >= map.ysize * 6 / 10);
       if (map_get_terrain(x, y)==T_GRASSLAND) {
        make_forest(x,y, hmap(x, y), 25);
       }
@@ -227,8 +227,7 @@
   for (swamps=0;swamps<map.swampsize;) {
     forever++;
     if (forever>1000) return;
-    y=myrand(map.ysize);
-    x=myrand(map.xsize);
+    rand_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) {
@@ -257,14 +256,16 @@
   while (i && j<500) {
     j++;
 
-    y=myrand(map.ysize*10/180)+map.ysize*110/180;
-    x=myrand(map.xsize);
+    do {
+      rand_pos(&x, &y);
+    } while (y < map.ysize * 110/180 || y >= map.ysize * 2/3);
     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);
+    do {
+      rand_pos(&x, &y);
+    } while (y < map.ysize * 1 / 3 || y >= map.ysize * 70/180);
     if (map_get_terrain(x, y)==T_GRASSLAND) {
       make_desert(x,y, hmap(x, y), 50);
       i--;
@@ -672,10 +673,9 @@
         iteration_counter < RIVERS_MAXTRIES) {
 
     /* Don't start any rivers at the poles. */
-    y = myrand(map.ysize - 2) + 1; 
-
-    /* Any x-coordinate is valid. */
-    x = myrand(map.xsize);
+    do {
+      rand_pos(&x, &y);
+    } while (y == 0 || y == map.ysize-1);
  
     /* Check if it is suitable to start a river on the current tile.
      */
@@ -1140,8 +1140,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 +1308,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 +1382,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 +1545,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++) {
Index: server/maphand.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/maphand.c,v
retrieving revision 1.87
diff -u -r1.87 maphand.c
--- server/maphand.c    2001/10/11 12:37:06     1.87
+++ server/maphand.c    2001/10/18 04:44:05
@@ -75,8 +75,7 @@
 
   k = map.xsize * map.ysize;
   while(effect && k--) {
-    x = myrand(map.xsize);
-    y = myrand(map.ysize);
+    rand_pos(&x, &y);
     if (map_get_terrain(x, y) != T_OCEAN) {
       if (is_terrain_ecologically_wet(x, y)) {
        switch (map_get_terrain(x, y)) {
@@ -132,8 +131,7 @@
 
   k =map.xsize * map.ysize;
   while(effect && k--) {
-    x = myrand(map.xsize);
-    y = myrand(map.ysize);
+    rand_pos(&x, &y);
     if (map_get_terrain(x, y) != T_OCEAN) {
       switch (map_get_terrain(x, y)) {
       case T_JUNGLE: