[Freeciv-Dev] Re: (PR#8817) generate city map indices

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

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

Gregory Berkolaiko wrote:
> <URL: http://rt.freeciv.org/Ticket/Display.html?id=8817 >
> 
> A somewhat useless comment.
> 
> You can also sort the indices of the same distance, to guarantee that the
> iteration "on the circle" is done, say, clockwise from 12 o'clock
> 
> if (dx1 >= 0) {
>   if (dx2 < 0) return -1;
>   if (dy2 >= dy1) return -1;
>   return 1;
> }
> 
> etc

True but the "etc" is very long and confusing (it becomes even more 
complex with hex tiles).  And using an angular ordering doesn't give any 
particular advantage, does it?

However it _is_ important that the comparison function not return 0.  We 
don't want to leave the sorting up to qsort because that could sort 
differently on different machines, breaking the reproducablility of 
autogames.

This patch makes two changes:

- Store dx,dy in the array instead of city_x, city_y.  This will work 
better when extended to map iteration.

- Add extra comparison checks to make sure the sort is well-defined.

jason

? convert.sh
? flags
? output
? data/flags
Index: client/civclient.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/client/civclient.c,v
retrieving revision 1.187
diff -u -r1.187 civclient.c
--- client/civclient.c  21 Apr 2004 19:46:37 -0000      1.187
+++ client/civclient.c  24 May 2004 20:02:31 -0000
@@ -405,6 +405,7 @@
     client_state=newstate;
 
     if (client_state == CLIENT_GAME_RUNNING_STATE) {
+      generate_city_map_indices();
       load_ruleset_specific_options();
       create_event(-1, -1, E_GAME_START, _("Game started."));
       update_research(game.player_ptr);
Index: common/city.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/city.c,v
retrieving revision 1.211
diff -u -r1.211 city.c
--- common/city.c       21 May 2004 19:03:43 -0000      1.211
+++ common/city.c       24 May 2004 20:02:32 -0000
@@ -16,6 +16,7 @@
 #endif
 
 #include <assert.h>
+#include <stdlib.h>
 #include <string.h>
 
 #include "fcintl.h"
@@ -52,20 +53,7 @@
                                      bool asmiths);
 
 /* Iterate a city map, from the center (the city) outwards */
-
-int city_map_iterate_outwards_indices[CITY_TILES][2] =
-{
-  { 2, 2 },
-
-  { 1, 2 }, { 2, 1 }, { 3, 2 }, { 2, 3 },
-  { 1, 3 }, { 1, 1 }, { 3, 1 }, { 3, 3 },
-
-  { 0, 2 }, { 2, 0 }, { 4, 2 }, { 2, 4 },
-  { 0, 3 }, { 0, 1 },
-  { 1, 0 }, { 3, 0 },
-  { 4, 1 }, { 4, 3 },
-  { 3, 4 }, { 1, 4 }
-};
+struct iter_index *city_map_iterate_outwards_indices;
 
 struct citystyle *city_styles = NULL;
 
@@ -168,6 +156,84 @@
 }
 
 /**************************************************************************
+  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 topology and
+  ruleset settings.
+***************************************************************************/
+void generate_city_map_indices(void)
+{
+  int i = 0, dx, dy;
+  struct iter_index *array = city_map_iterate_outwards_indices;
+
+  /* Realloc is used because this function may be called multiple times. */
+  array = fc_realloc(array, CITY_TILES * sizeof(*array));
+
+  for (dx = -CITY_MAP_RADIUS; dx <= CITY_MAP_RADIUS; dx++) {
+    for (dy = -CITY_MAP_RADIUS; dy <= CITY_MAP_RADIUS; dy++) {
+      if (is_valid_city_coords(dx + CITY_MAP_RADIUS, dy + CITY_MAP_RADIUS)) {
+       array[i].dx = dx;
+       array[i].dy = dy;
+       array[i].dist = dx * dx + dy * dy;
+       i++;
+      }
+    }
+  }
+  assert(i == CITY_TILES);
+
+  qsort(array, CITY_TILES, sizeof(*array), compare_index);
+
+#ifdef DEBUG
+  for (i = 0; i < CITY_TILES; i++) {
+    freelog(LOG_DEBUG, "%2d : (%2d,%2d) : %d", i,
+           array[i].dx + CITY_MAP_RADIUS, array[i].dy + CITY_MAP_RADIUS,
+           array[i].dist);
+  }
+#endif
+
+  city_map_iterate_outwards_indices = array;
+}
+
+/**************************************************************************
   Set the worker on the citymap.  Also sets the worked field in the map.
 **************************************************************************/
 void set_worker_city(struct city *pcity, int city_x, int city_y,
Index: common/city.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/city.h,v
retrieving revision 1.143
diff -u -r1.143 city.h
--- common/city.h       20 May 2004 21:38:53 -0000      1.143
+++ common/city.h       24 May 2004 20:02:32 -0000
@@ -102,26 +102,22 @@
 }
 
 /* Iterate a city map, from the center (the city) outwards */
+extern struct iter_index {
+  int dx, dy, dist;
+} *city_map_iterate_outwards_indices;
+
+/* Iterate a city map, from the center (the city) outwards.
+ * (city_x, city_y) will be the city coordinates. */
+#define city_map_iterate_outwards(city_x, city_y)                          \
+{                                                                          \
+  int city_x, city_y, _index;                                              \
+                                                                           \
+  for (_index = 0; _index < CITY_TILES; _index++) {                        \
+    city_x = city_map_iterate_outwards_indices[_index].dx + CITY_MAP_RADIUS;\
+    city_y = city_map_iterate_outwards_indices[_index].dy + CITY_MAP_RADIUS;
 
-extern int city_map_iterate_outwards_indices[CITY_TILES][2];
-
-/* Iterate a city map, from the center (the city) outwards. x and y
-   will be elements of [0, CITY_MAP_SIZE). */
-#define city_map_iterate_outwards(x, y) {                                      
\
-  int x, y;                                                                    
\
-  int city_map_iterate_outwards_index;                                         
\
-  for                                                                          
\
-  (                                                                            
\
-    city_map_iterate_outwards_index = 0;                                       
\
-    city_map_iterate_outwards_index < CITY_TILES;                              
\
-    city_map_iterate_outwards_index++                                          
\
-  )                                                                            
\
-  {                                                                            
\
-    x = city_map_iterate_outwards_indices[city_map_iterate_outwards_index][0]; 
\
-    y = city_map_iterate_outwards_indices[city_map_iterate_outwards_index][1];
-
-#define city_map_iterate_outwards_end                                          
\
-  }                                                                            
\
+#define city_map_iterate_outwards_end                                       \
+  }                                                                         \
 }
 
 /*
@@ -395,6 +391,7 @@
                         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);
+void generate_city_map_indices(void);
 
 /* shield on spot */
 int city_get_shields_tile(int city_x, int city_y, struct city *pcity);
Index: server/srv_main.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/srv_main.c,v
retrieving revision 1.160
diff -u -r1.160 srv_main.c
--- server/srv_main.c   2 May 2004 14:47:12 -0000       1.160
+++ server/srv_main.c   24 May 2004 20:02:33 -0000
@@ -1544,6 +1544,7 @@
     load_rulesets();
     /* otherwise rulesets were loaded when savegame was loaded */
   }
+  generate_city_map_indices();
 
   nations_avail = fc_calloc(game.playable_nation_count, sizeof(int));
   nations_used = fc_calloc(game.playable_nation_count, sizeof(int));