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

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

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

This patch is a rework of Remi's patch in PR#7350 to generate the city 
map indices.

I've changed it in several ways:

- Rathar than a linked-list solution with insertion sort I used a purely 
array solution with qsort.  This requires much less code (and is no 
doubt faster but who cares).

- The radius is _not_ passed to the generate function.  Rather the 
generate function should already know the radius.  If the radius is 
loaded from the ruleset, for instance, it will be stored in some global 
variable.

- Rather than calling the function when the ruleset is loaded I call it 
when the game starts.  This is a bit questionable but I'm not sure where 
else it should go.

- I use fc_realloc to avoid memory leaks when generate_indices is called 
multiple times (when the server plays multiple games, or the client 
reconnects).

My goal here is a little broader than Remi's.  His original patch only 
considered that the indices might be changed based on the ruleset. 
However I'm thinking about hex-tiled maps too, where the indices are 
changed based on the topology.

As a side note I would like to use a similar solution (reusing the 
iter_index struct) for iterate_outwards in map.h.  For iterate_outwards 
(and in Remi's city-radius patch) it is actually useful to have the 
distance stored in the array so that you can tell when it's time to stop 
the iteration.  However for the current code the "dist" element is 
unused except in the generation of the array.

As another side note it is easy to make city_map_iterate a wrapper for 
city_map_iterate_outwards.  I believe this is what Ross has suggested. 
In fact it might be simpler to remove city_map_iterate_outwards and just 
make all citymap iteration follow the outwards ordering.

jason

? convert.sh
? flags
? 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  23 May 2004 07:35:00 -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       23 May 2004 07:35:06 -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,62 @@
 }
 
 /**************************************************************************
+  Compare two iter_index values from the city_map_iterate_outward_indices.
+
+  This function will be passed to qsort().
+***************************************************************************/
+static int compare_index(const void *a, const void *b)
+{
+  const struct iter_index *index1 = a, *index2 = b;
+
+  if (index1->dist > index2->dist) {
+    return 1;
+  } else if (index1->dist < index2->dist) {
+    return -1;
+  } else {
+    return 0;
+  }
+}
+
+/**************************************************************************
+  Fill the iterate_outwards_indices array.  This may depend on topology and
+  ruleset settings.
+***************************************************************************/
+void generate_city_map_indices(void)
+{
+  int i = 0, x, y;
+  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 (x = 0; x < CITY_MAP_SIZE; x++) {
+    for (y = 0; y < CITY_MAP_SIZE; y++) {
+      if (is_valid_city_coords(x, y)) {
+       int dx = x - CITY_MAP_RADIUS, dy = y - CITY_MAP_RADIUS;
+
+       array[i].x = x;
+       array[i].y = y;
+       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_NORMAL, "%2d : (%2d,%2d) : %d",
+           i, array[i].x, array[i].y, 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       23 May 2004 07:35:06 -0000
@@ -102,26 +102,22 @@
 }
 
 /* Iterate a city map, from the center (the city) outwards */
+extern struct iter_index {
+  int x, y, 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].x;                  \
+    city_y = city_map_iterate_outwards_indices[_index].y;
 
-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   23 May 2004 07:35:06 -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));