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

[jdorje@xxxxxxxxxxxxxxxxxxxxx]

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?

jason

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/23 15:43:57
@@ -13,6 +13,7 @@
 #ifndef FC__MAP_H
 #define FC__MAP_H
 
+#include "mem.h"
 #include "player.h"
 #include "terrain.h"
 #include "unit.h"
@@ -274,6 +275,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 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)
 /*
  * A "border position" is any one that has adjacent positions that are
  * not normal/proper.
@@ -286,6 +292,70 @@
 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);
+
+/* Chooses "number" random positions from the map that satisfy pos_check,
+   placing them into x_arr and y_arr arrays.  Variables x and y are provided
+   for the pos_check check.  max_count is the number of times to pick
+   coordinates at random; after that a more structured approach is used. Plus
+   one final ugliness: if *number* positions cannot be found, *number* is
+   changed to be the number of positions that are found. */
+/* 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);                                                      \
+  int _i, _tries, _max_count = (max_count);                                   \
+  for (_i=0; _i<number; _i++) {                                               \
+    /* Random algorithm: pick points at random and see if they're valid. */   \
+    for (_tries=0; _tries<max_count; _tries++) {                              \
+      int x = myrand(map.xsize);                                              \
+      int y = myrand(map.ysize);                                              \
+      if (is_normal_map_pos2(x, y) && (pos_check)) {                          \
+       _x_arr[_i] = x, _y_arr[_i] = y;                                       \
+       break;                                                                \
+      }                                                                       \
+    }                                                                         \
+    if (_tries == _max_count) {                                               \
+      break;                                                                  \
+    }                                                                         \
+  }                                                                           \
+  if (_i != number) {                                                         \
+    /* Structured algorithm: assemble a full list of valid points */          \
+    int *_x_vals = fc_malloc(sizeof(*_x_vals) * map.xsize * map.ysize);       \
+    int *_y_vals = fc_malloc(sizeof(*_y_vals) * map.xsize * map.ysize);       \
+    int _count = 0, _rval;                                                    \
+    whole_map_iterate(x, y) {                                                 \
+      if (is_normal_map_pos2(x, y) && (pos_check) ) {                         \
+        _x_vals[_count] = x;                                                  \
+        _y_vals[_count] = y;                                                  \
+        _count++;                                                             \
+      }                                                                       \
+    } whole_map_iterate_end;                                                  \
+    for (_i=0; _i<number; _i++) {                                             \
+      if (_count == 0) {                                                      \
+        number = _i + 1;                                                      \
+        break;                                                                \
+      }                                                                       \
+      _rval = myrand(_count);                                                 \
+      _x_arr[_i] = _x_vals[_rval];                                            \
+      _y_arr[_i] = _y_vals[_rval];                                            \
+      _count--;                                                               \
+      _x_vals[_rval] = _x_vals[_count];                                       \
+      _y_vals[_rval] = _y_vals[_count];                                       \
+    }                                                                         \
+    free(_x_vals);                                                            \
+    free(_y_vals);                                                            \
+  }                                                                           \
+}
 
 int is_water_adjacent_to_tile(int x, int y);
 int is_tiles_adjacent(int x0, int y0, int x1, int y1);