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

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

<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.

The second is a long-hidden bug.  The X distance is limited to 
map.xsize/2 so as to prevent duplicate entries.  However this only works 
for non-iso X-wrapping topologies.

I think the best way to do this is to pre-generate the indices, the way 
the citymap indices are done.  The distance can be calculated via 
map_vector_to_real_distance (see PR#9043) so that it will work with hex 
maps.  A single loop is easy so break will work.  And it's easy to fix 
the missing-positions wrapping bug.

This is a demo implementation of that system.  It includes the PR#9043 
patch so that it can use map_vector_to_real_distance.  I also rewrote 
square_dxy_iterate and iterate_outward to be wrappers for a new macro 
iterate_outward_dxy - this simplifies square_dxy_iterate significantly 
and allows easier debugging since it is used so often.  It also improves 
square_dxy_iterate (and its users, circle_iterate and square_iterate) 
because iterate_outward handles wrapping better.

The generation of the indices uses some quite tricky native math so as 
to handle wrapping correctly.  For linear maps (e.g., not quincunxes) 
this will handle wrapping properly (no missing or duplicated positions). 
  I documented this as best I could; if it's unclear we should try to 
improve the documentation.

Finally, cmp() and compare_index() are identical to the same functions 
in city.c.  These should be merged somehow.

jason

Index: common/map.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/map.c,v
retrieving revision 1.176
diff -u -r1.176 map.c
--- common/map.c        9 Jul 2004 19:30:58 -0000       1.176
+++ common/map.c        10 Jul 2004 07:44:59 -0000
@@ -215,6 +215,139 @@
   map.have_huts             = FALSE;
 }
 
+/**************************************************************************
+  Compare two integer values, as required by qsort.
+***************************************************************************/
+static int cmp(int v1, int v2)
+{
+  if (v1 == v2) {
+    return 0;
+  } else if (v1 > v2) {
+    return 1;
+  } else {
+    return -1;
+  }
+}
+
+/**************************************************************************
+  Compare two iter_index values from the city_map_iterate_outward_indices.
+
+  This function will be passed to qsort().  It should never return zero,
+  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)
+{
+  const struct iter_index *index1 = a, *index2 = b;
+  int value;
+
+  value = cmp(index1->dist, index2->dist);
+  if (value != 0) {
+    return value;
+  }
+
+  value = cmp(index1->dx, index2->dx);
+  if (value != 0) {
+    return value;
+  }
+
+  value = cmp(index1->dy, index2->dy);
+  assert(value != 0);
+  return value;
+}
+
+/**************************************************************************
+  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;
+  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));
+  int 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 - this too accounts for wrapping so
+       * that the shortest distance will always be used. */
+      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_index);
+
+#if 1
+  for (i = 0; i < tiles; i++) {
+    freelog(LOG_NORMAL, "%d/%d", map.xsize, map.ysize);
+    freelog(LOG_NORMAL, "%2d : (%2d,%2d) : %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 +530,7 @@
   } whole_map_iterate_end;
 
   generate_city_map_indices();
+  generate_map_indices();
 }
 
 /***************************************************************
@@ -452,6 +586,31 @@
   return NULL;
 }
 
+/****************************************************************************
+  Return the "distance" (which is really the Manhattan distance, and should
+  rarely be used) for a given vector.
+****************************************************************************/
+static int map_vector_to_distance(int dx, int dy)
+{
+  return abs(dx) + abs(dy);
+}
+
+/****************************************************************************
+  Return the "real" distance for a given vector.
+****************************************************************************/
+int map_vector_to_real_distance(int dx, int dy)
+{
+  return MAX(abs(dx), abs(dy));
+}
+
+/****************************************************************************
+  Return the sq_distance for a given vector.
+****************************************************************************/
+int map_vector_to_sq_distance(int dx, int dy)
+{
+  return dx * dx + dy * dy;
+}
+
 /***************************************************************
 ...
 ***************************************************************/
@@ -460,8 +619,7 @@
   int dx, dy;
 
   map_distance_vector(&dx, &dy, x0, y0, x1, y1);
-
-  return MAX(abs(dx), abs(dy));
+  return map_vector_to_real_distance(dx, dy);
 }
 
 /***************************************************************
@@ -474,8 +632,7 @@
   int dx, dy;
 
   map_distance_vector(&dx, &dy, x0, y0, x1, y1);
-
-  return (dx*dx + dy*dy);
+  return map_vector_to_sq_distance(dx, dy);
 }
 
 /***************************************************************
@@ -488,8 +645,7 @@
   int dx, dy;
 
   map_distance_vector(&dx, &dy, x0, y0, x1, y1);
-
-  return abs(dx) + abs(dy);
+  return map_vector_to_distance(dx, dy);
 }
 
 /***************************************************************
Index: common/map.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/map.h,v
retrieving revision 1.192
diff -u -r1.192 map.h
--- common/map.h        9 Jul 2004 19:30:58 -0000       1.192
+++ common/map.h        10 Jul 2004 07:44:59 -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;
@@ -198,9 +200,12 @@
 const char *map_get_tile_fpt_text(int x, int y);
 struct tile *map_get_tile(int x, int y);
 
+int map_vector_to_real_distance(int dx, int dy);
+int map_vector_to_sq_distance(int dx, int dy);
 int map_distance(int x0, int y0, int x1, int y1);
 int real_map_distance(int x0, int y0, int x1, int y1);
 int sq_map_distance(int x0, int y0, int x1, int y1);
+
 bool same_pos(int x1, int y1, int x2, int y2);
 bool base_get_direction_for_step(int start_x, int start_y, int end_x,
                                int end_y, int *dir);
@@ -407,72 +412,41 @@
 
 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 least once (it may show up more
+ * than once if the map wraps), 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_dxy(start_x, start_y, max_dist, x_itr, y_itr,       \
+                           dx_itr, dy_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_dxy_end                                                
    \
+  }                                                                         \
 }
 
+#define iterate_outward(start_x, start_y, max_dist, x_itr, y_itr)          \
+  iterate_outward_dxy(start_x, start_y, max_dist, x_itr, y_itr, _dx, _dy)
+
+#define iterate_outward_end                                                \
+  iterate_outward_dxy_end
+
 #define rectangle_iterate(map_x0, map_y0, map_width, map_height,            \
                           x_itr, y_itr)                                     \
 {                                                                           \
@@ -496,23 +470,13 @@
  * position. Note that when the square is larger than the map the
  * distance vector may not be the minimum distance vector.
  */
-#define square_dxy_iterate(center_x, center_y, radius, x_itr, y_itr,          \
-                           dx_itr, dy_itr)                                    \
-{                                                                             \
-  int dx_itr, dy_itr;                                                         \
-  bool _is_border = IS_BORDER_MAP_POS((center_x), (center_y), (radius));      \
-  CHECK_MAP_POS((center_x), (center_y));                                      \
-  for (dy_itr = -(radius); dy_itr <= (radius); dy_itr++) {                    \
-    for (dx_itr = -(radius); dx_itr <= (radius); dx_itr++) {                  \
-      int x_itr = dx_itr + (center_x), y_itr = dy_itr + (center_y);           \
-      if (_is_border && !normalize_map_pos(&x_itr, &y_itr)) {                 \
-        continue;                                                             \
-      }
+#define square_dxy_iterate(center_x, center_y, radius, x_itr, y_itr,        \
+                           dx_itr, dy_itr)                                  \
+  iterate_outward_dxy(center_x, center_y, radius, x_itr, y_itr,                
    \
+                     dx_itr, dy_itr)
 
-#define square_dxy_iterate_end                                                \
-    }                                                                         \
-  }                                                                           \
-}
+#define square_dxy_iterate_end                                              \
+  iterate_outward_dxy_end
 
 /*
  * Iterate through all tiles in a square with given center and radius.