[Freeciv-Dev] Re: (PR#9327) rewrite iterate_outward

["Jason Dorje Short" <jdorje@xxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=9327 >

Jason Short wrote:
> <URL: http://rt.freeciv.org/Ticket/Display.html?id=9327 >
> 
> There are a number of problems with iterate_outward:
> 
> 1. It doesn't respect "break".
> 2. It doesn't handle wrapping properly except with topology 1.
> 3. It doesn't work with hex maps.

Here's an updated patch.  I removed the changes to the other macros, 
merged the comparison functions with those in city.c, and fixed a couple 
of errors.  I believe it is now ready.

jason

Index: common/city.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/city.c,v
retrieving revision 1.227
diff -u -r1.227 city.c
--- common/city.c       13 Jul 2004 16:01:42 -0000      1.227
+++ common/city.c       13 Jul 2004 16:32:58 -0000
@@ -155,7 +155,7 @@
   or the sort order will be left up to qsort and will be undefined.  This
   would mean that server execution would not be reproducable.
 ***************************************************************************/
-static int compare_index(const void *a, const void *b)
+int compare_iter_index(const void *a, const void *b)
 {
   const struct iter_index *index1 = a, *index2 = b;
   int value;
@@ -204,7 +204,7 @@
   }
   assert(i == CITY_TILES);
 
-  qsort(array, CITY_TILES, sizeof(*array), compare_index);
+  qsort(array, CITY_TILES, sizeof(*array), compare_iter_index);
 
 #ifdef DEBUG
   for (i = 0; i < CITY_TILES; i++) {
Index: common/city.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/city.h,v
retrieving revision 1.151
diff -u -r1.151 city.h
--- common/city.h       12 Jul 2004 03:03:28 -0000      1.151
+++ common/city.h       13 Jul 2004 16:33:00 -0000
@@ -398,6 +398,9 @@
                         int city_map_y);
 bool city_map_to_map(int *map_x, int *map_y, const struct city *const pcity,
                    int city_map_x, int city_map_y);
+
+/* Initialization functions */
+int compare_iter_index(const void *a, const void *b);
 void generate_city_map_indices(void);
 
 /* shield on spot */
Index: common/map.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/map.c,v
retrieving revision 1.177
diff -u -r1.177 map.c
--- common/map.c        13 Jul 2004 16:01:42 -0000      1.177
+++ common/map.c        13 Jul 2004 16:33:01 -0000
@@ -215,6 +215,98 @@
   map.have_huts             = FALSE;
 }
 
+/**************************************************************************
+  Fill the iterate_outwards_indices array.  This may depend on the topology.
+***************************************************************************/
+static void generate_map_indices(void)
+{
+  int i = 0, nat_x, nat_y, tiles;
+  struct iter_index *array = map.iterate_outwards_indices;
+  int nat_center_x, nat_center_y, nat_min_x, nat_min_y, nat_max_x, nat_max_y;
+  int map_center_x, map_center_y;
+
+  /* These caluclations are done via tricky native math.  We need to make
+   * sure that when "exploring" positions in the iterate_outward we hit each
+   * position within the distance exactly once.
+   *
+   * To do this we pick a center position (at the center of the map, for
+   * convenience).  Then we iterate over all of the positions around it,
+   * accounting for wrapping, in native coordinates.  Note that some of the
+   * positions iterated over before will not even be real; the point is to
+   * use the native math so as to get the right behavior under different
+   * wrapping conditions.
+   *
+   * Thus the "center" position below is just an arbitrary point.  We choose
+   * the center of the map to make the min/max values (below) simpler. */
+  nat_center_x = map.xsize / 2;
+  nat_center_y = map.ysize / 2;
+  native_to_map_pos(&map_center_x, &map_center_y,
+                   nat_center_x, nat_center_y);
+
+  /* If we wrap in a particular direction (X or Y) we only need to explore a
+   * half of a map-width in that direction before we hit the wrap point.  If
+   * not we need to explore the full width since we have to account for the
+   * worst-case where we start at one edge of the map.  Of course if we try
+   * to explore too far the extra steps will just be skipped by the
+   * normalize check later on.  So the purpose at this point is just to
+   * get the right set of positions, relative to the start position, that
+   * may be needed for the iteration.
+   *
+   * If the map does wrap, we go map.Nsize / 2 in each direction.  This
+   * gives a min value of 0 and a max value of Nsize-1, because of the
+   * center position chosen above.  This also avoids any off-by-one errors.
+   *
+   * If the map doesn't wrap, we go map.Nsize-1 in each direction.  In this
+   * case we're not concerned with going too far and wrapping around, so we
+   * just have to make sure we go far enough if we're at one edge of the
+   * map. */
+  nat_min_x = (topo_has_flag(TF_WRAPX) ? 0 : (nat_center_x - map.xsize + 1));
+  nat_min_y = (topo_has_flag(TF_WRAPY) ? 0 : (nat_center_y - map.ysize + 1));
+
+  nat_max_x = (topo_has_flag(TF_WRAPX)
+              ? (map.xsize - 1)
+              : (nat_center_x + map.xsize - 1));
+  nat_max_y = (topo_has_flag(TF_WRAPY)
+              ? (map.ysize - 1)
+              : (nat_center_y + map.ysize - 1));
+  tiles = (nat_max_x - nat_min_x + 1) * (nat_max_y - nat_min_y + 1);
+
+  array = fc_realloc(array, tiles * sizeof(*array));
+
+  for (nat_x = nat_min_x; nat_x <= nat_max_x; nat_x++) {
+    for (nat_y = nat_min_y; nat_y <= nat_max_y; nat_y++) {
+      int map_x, map_y, dx, dy;
+
+      /* Now for each position, we find the vector (in map coordinates) from
+       * the center position to that position.  Then we calculate the
+       * distance between the two points.  Wrapping is ignored at this
+       * point since the use of native positions means we should always have
+       * the shortest vector. */
+      native_to_map_pos(&map_x, &map_y, nat_x, nat_y);
+      dx = map_x - map_center_x;
+      dy = map_y - map_center_y;
+
+      array[i].dx = dx;
+      array[i].dy = dy;
+      array[i].dist = map_vector_to_real_distance(dx, dy);
+      i++;
+    }
+  }
+  assert(i == tiles);
+
+  qsort(array, tiles, sizeof(*array), compare_iter_index);
+
+#if 0
+  for (i = 0; i < tiles; i++) {
+    freelog(LOG_DEBUG, "%5d : (%3d,%3d) : %d",
+           i, array[i].dx, array[i].dy, array[i].dist);
+  }
+#endif
+
+  map.num_iterate_outwards_indices = tiles;
+  map.iterate_outwards_indices = array;
+}
+
 /****************************************************************************
   Set the map xsize and ysize based on a base size and ratio (in natural
   coordinates).
@@ -397,6 +489,7 @@
   } whole_map_iterate_end;
 
   generate_city_map_indices();
+  generate_map_indices();
 }
 
 /***************************************************************
Index: common/map.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/map.h,v
retrieving revision 1.193
diff -u -r1.193 map.h
--- common/map.h        13 Jul 2004 16:01:42 -0000      1.193
+++ common/map.h        13 Jul 2004 16:33:01 -0000
@@ -146,6 +146,8 @@
   int topology_id;
   enum direction8 valid_dirs[8], cardinal_dirs[8];
   int num_valid_dirs, num_cardinal_dirs;
+  struct iter_index *iterate_outwards_indices;
+  int num_iterate_outwards_indices;
   int size; /* used to calculate [xy]size */
   int xsize, ysize; /* native dimensions */
   int seed;
@@ -410,70 +412,31 @@
 
 extern struct terrain_misc terrain_control;
 
-/* This iterates outwards from the starting point (Duh?).
-   Every tile within max_dist will show up exactly once. (even takes
-   into account wrap). All positions given correspond to real tiles.
-   The values given are adjusted.
-   You should make sure that the arguments passed to the macro are adjusted,
-   or you could have some very nasty intermediate errors.
-
-   Internally it works by for a given distance
-   1) assume y positive and iterate over x
-   2) assume y negative and iterate over x
-   3) assume x positive and iterate over y
-   4) assume x negative and iterate over y
-   Where in this we are is decided by the variables xcycle and positive.
-   each of there distances give a box of tiles; to ensure each tile is only
-   returned once we only return the corner when iterating over x.
-   As a special case positive is initialized as 0 (ie we start in step 2) ),
-   as the center tile would else be returned by both step 1) and 2).
-*/
-#define iterate_outward(ARG_start_x, ARG_start_y, ARG_max_dist, ARG_x_itr, 
ARG_y_itr) \
-{                                                                             \
-  int ARG_x_itr, ARG_y_itr;                                                   \
-  int MACRO_max_dx = map.xsize/2;                                             \
-  int MACRO_min_dx = -MACRO_max_dx - 1 + (map.xsize % 2);                     \
-  bool MACRO_xcycle = TRUE;                                                   \
-  bool MACRO_positive = FALSE;                                                \
-  bool MACRO_is_border = IS_BORDER_MAP_POS(ARG_start_x, ARG_start_y,          \
-                                           ARG_max_dist);                     \
-  int MACRO_dxy = 0, MACRO_do_xy;                                             \
-  CHECK_MAP_POS(ARG_start_x, ARG_start_y);                                    \
-  while(MACRO_dxy <= (ARG_max_dist)) {                                        \
-    for (MACRO_do_xy = -MACRO_dxy; MACRO_do_xy <= MACRO_dxy; MACRO_do_xy++) { \
-      if (MACRO_xcycle) {                                                     \
-       ARG_x_itr = (ARG_start_x) + MACRO_do_xy;                              \
-       if (MACRO_positive)                                                   \
-         ARG_y_itr = (ARG_start_y) + MACRO_dxy;                              \
-       else                                                                  \
-         ARG_y_itr = (ARG_start_y) - MACRO_dxy;                              \
-      } else { /* ! MACRO_xcycle */                                           \
-        if (MACRO_dxy == MACRO_do_xy || MACRO_dxy == -MACRO_do_xy)            \
-          continue;                                                           \
-       ARG_y_itr = (ARG_start_y) + MACRO_do_xy;                              \
-       if (MACRO_positive)                                                   \
-         ARG_x_itr = (ARG_start_x) + MACRO_dxy;                              \
-       else                                                                  \
-         ARG_x_itr = (ARG_start_x) - MACRO_dxy;                              \
-      }                                                                       \
-      {                                                                       \
-       int MACRO_dx = (ARG_start_x) - ARG_x_itr;                             \
-       if (MACRO_dx > MACRO_max_dx || MACRO_dx < MACRO_min_dx)               \
-         continue;                                                           \
-      }                                                                       \
-      if (MACRO_is_border && !normalize_map_pos(&ARG_x_itr, &ARG_y_itr)) {    \
-       continue;                                                             \
-      }
+/* This iterates outwards from the starting point. Every tile within max_dist
+ * will show up at exactly once, in an outward (based on real map distance)
+ * order.  The returned values are always real and are normalized.  The
+ * starting position must be normal. */
+#define iterate_outward(start_x, start_y, max_dist, x_itr, y_itr)          \
+{                                                                          \
+  int _start_x = (start_x), _start_y = (start_y), _max_dist = (max_dist);   \
+  bool _is_border = IS_BORDER_MAP_POS(_start_x, _start_y, _max_dist);      \
+  int x_itr, y_itr, _dx_itr, _dy_itr, _index;                              \
+                                                                           \
+  CHECK_MAP_POS(_start_x, _start_y);                                       \
+  for (_index = 0; _index < map.num_iterate_outwards_indices; _index++) {   \
+    if (map.iterate_outwards_indices[_index].dist > _max_dist) {           \
+      break;                                                               \
+    }                                                                      \
+    _dx_itr = map.iterate_outwards_indices[_index].dx;                     \
+    _dy_itr = map.iterate_outwards_indices[_index].dy;                     \
+    x_itr = _dx_itr + _start_x;                                                
    \
+    y_itr = _dy_itr + _start_y;                                                
    \
+    if (_is_border && !normalize_map_pos(&x_itr, &y_itr)) {                \
+      continue;                                                                
    \
+    }
 
-#define iterate_outward_end                                                   \
-    }                                                                         \
-    if (!MACRO_positive) {                                                    \
-      if (!MACRO_xcycle)                                                      \
-       MACRO_dxy++;                                                          \
-      MACRO_xcycle = !MACRO_xcycle;                                           \
-    }                                                                         \
-    MACRO_positive = !MACRO_positive;                                         \
-  }                                                                           \
+#define iterate_outward_end                                                \
+  }                                                                         \
 }
 
 #define rectangle_iterate(map_x0, map_y0, map_width, map_height,            \