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

[jdorje@xxxxxxxxxxxxxxxxxxxxx]

Raimar Falke wrote:

...

> If we now adjust rand_pos accordingly I will be happy.

I'm still not sure what exactly you (and, separately, Ross) want out of
rand_pos.

Anyway, here is another attempt.  Like the other two candidates, this
makes effectively no difference to the speed of the code.  It combines
some of the simplicity of the rand_pos function with the power of the
RAND_POS_CHECKED macro by providing both independently.

Personally, I like this implementation more.

jason

? rc
? old
? topology
? tilespec_patch
? corecleanup_08.ReadMe
? topology.c
? civserver-regular
? 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/26 05:47:09
@@ -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 (!regular_map_pos_is_normal(*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.100
diff -u -r1.100 map.h
--- common/map.h        2001/10/19 08:12:52     1.100
+++ common/map.h        2001/10/26 05:47:10
@@ -274,6 +274,11 @@
 enum known_type tile_is_known(int x, int y);
 int is_real_tile(int x, int y);
 int is_normal_map_pos(int x, int y);
+/* Determines whether the position is normal given that it's "regular"
+   (in he 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 regular_map_pos_is_normal(x, y) (1)
 /*
  * A "border position" is any one that has adjacent positions that are
  * not normal/proper.
@@ -286,6 +291,30 @@
 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);
+/* This picks a random position (x, y) from the map that satisfies POS_CHECK.
+ *   x, y: identifiers to hold the new position
+ *   POS_CHECK: an expression that evaluates if position (x, y) (as above)
+ *              is a valid choice. */
+#define RAND_POS_CHECKED(x, y, POS_CHECK)                                   \
+{                                                                           \
+  /* Structured algorithm: assemble a full list of valid points */          \
+  struct map_position *_pos_arr = fc_malloc(sizeof(*_pos_arr) *             \
+                                           map.xsize * map.ysize);         \
+  int _count = 0;                                                           \
+  whole_map_iterate(x, y) {                                                 \
+    if (POS_CHECK) {                                                        \
+      _pos_arr[_count].x = x;                                               \
+      _pos_arr[_count].y = y;                                               \
+      _count++;                                                             \
+    }                                                                       \
+  } whole_map_iterate_end;                                                  \
+  if (!_count) abort(); /* what else can we do? */                          \
+  _count = myrand(_count);                                                  \
+  x = _pos_arr[_count].x;                                                   \
+  y = _pos_arr[_count].y;                                                   \
+  free(_pos_arr);                                                           \
+}                                                                           \
 
 int is_water_adjacent_to_tile(int x, int y);
 int is_tiles_adjacent(int x0, int y0, int x1, int y1);
@@ -472,9 +501,11 @@
 {                                                                             \
   int WMI_x_itr, WMI_y_itr;                                                   \
   for (WMI_y_itr = 0; WMI_y_itr < map.ysize; WMI_y_itr++)                     \
-    for (WMI_x_itr = 0; WMI_x_itr < map.xsize; WMI_x_itr++)
+    for (WMI_x_itr = 0; WMI_x_itr < map.xsize; WMI_x_itr++)                   \
+      if (regular_map_pos_is_normal(WMI_x_itr, WMI_y_itr)) {
 
 #define whole_map_iterate_end                                                 \
+      }                                                                       \
 }
 
 /*
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/26 05:47:11
@@ -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/26 05:47:13
@@ -199,14 +199,12 @@
   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);
+      RAND_POS_CHECKED(x, y, 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 +225,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 +254,12 @@
   while (i && j<500) {
     j++;
 
-    y=myrand(map.ysize*10/180)+map.ysize*110/180;
-    x=myrand(map.xsize);
+    RAND_POS_CHECKED(x, y, y >= map.ysize * 110/180 && y < map.ysize * 
120/180);
     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);
+    RAND_POS_CHECKED(x, y, y >= map.ysize * 60/180 && y < map.ysize * 70/180);
     if (map_get_terrain(x, y)==T_GRASSLAND) {
       make_desert(x,y, hmap(x, y), 50);
       i--;
@@ -672,10 +667,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 +1134,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 +1302,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 +1376,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 +1539,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/26 05:47:15
@@ -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:
Index: server/savegame.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/savegame.c,v
retrieving revision 1.36
diff -u -r1.36 savegame.c
--- server/savegame.c   2001/10/17 13:16:45     1.36
+++ server/savegame.c   2001/10/26 05:47:18
@@ -68,7 +68,7 @@
                                                         \
   for (y = 0; y < map.ysize; y++) {                     \
     for (x = 0; x < map.xsize; x++) {                   \
-      if (is_normal_map_pos(x, y)) {                    \
+      if (regular_map_pos_is_normal(x, y)) {            \
        line[x] = get_xy_char;                          \
         if(!isprint(line[x] & 0x7f)) {                  \
           freelog(LOG_FATAL, "Trying to write invalid"  \
@@ -127,7 +127,7 @@
     }                                                         \
     for(x = 0; x < map.xsize; x++) {                          \
       char ch = line[x];                                      \
-      if (is_normal_map_pos(x, y)) {                          \
+      if (regular_map_pos_is_normal(x, y)) {                  \
        set_xy_char;                                          \
       } else {                                                \
        assert(ch == '#');                                    \