[Freeciv-Dev] (PR#3936) introducing native coordinates

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

This is a significant design issue, and should be closely scrutinized. 
I'd encourage everyone to at least read this patch.

Native coordinates (sometimes called "compressed" coordinates in the
past) are a concept Ross came up with to make isometric (and other
non-standard) maps easier to deal with.  They save around 50% memory
(and on disk, in savegames) for map storage over "standard" map
coordinates and make topology operations *much* simpler.  Other
coordinate systems may share one of these properties, but none have
both.  In the process, they invalidate the need for "regular" map positions.

The patch introduces native_to_map_pos and map_to_native_pos macros into
map.h, along with one very simple user.  I've also written an
explanation of the coordinate systems for doc/HACKING.  I'd like
feedback on this explanation, particularly from people who don't already
know what "native coordinates" are.

All other explanation is in the patch (or if it isn't, it should be).

jason

Index: common/map.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/map.h,v
retrieving revision 1.143
diff -u -r1.143 map.h
--- common/map.h        2003/04/04 15:47:49     1.143
+++ common/map.h        2003/04/05 03:35:26
@@ -226,6 +226,12 @@
 #define map_adjust_y(Y) \
   (((Y)<0) ? 0 : (((Y)>=map.ysize) ? map.ysize-1 : (Y)))
 
+#define native_to_map_pos(pmap_x, pmap_y, nat_x, nat_y) \
+  (*(pmap_x) = (nat_x), *(pmap_y) = (nat_y))
+
+#define map_to_native_pos(pnat_x, pnat_y, map_x, map_y) \
+  (*(pnat_x) = (map_x), *(pnat_y) = (map_y))
+
 #define map_pos_to_index(map_x, map_y)        \
   (CHECK_MAP_POS((map_x), (map_y)),           \
    (map_x) + (map_y) * map.xsize)
Index: doc/HACKING
===================================================================
RCS file: /home/freeciv/CVS/freeciv/doc/HACKING,v
retrieving revision 1.9
diff -u -r1.9 HACKING
--- doc/HACKING 2003/02/17 02:11:26     1.9
+++ doc/HACKING 2003/04/05 03:35:28
@@ -408,6 +408,99 @@
 be used.
 
 =========================================================================
+Different coordinate systems
+=========================================================================
+
+In Freeciv, we have the general concept of a "position" or "tile"; this
+is self-explanatory.  However, a tile can be referred to in any of several
+coordinate systems.  The distinction becomes important we start to use
+non-standard types of maps.
+
+- Map (or "standard") coordinates.
+
+  All of the map manipulation examples above are in map coordinates.
+  These preserve the local geometry of square tiles, but do not represent
+  the global map geometry well.  In map coordinates, you are guaranteed
+  (so long as we use square tiles) that the tile adjacency rules
+
+      (map_x-1, map_y-1)    (map_x, map_y-1)   (map_x+1, map_y-1)
+      (map_x-1, map_y)      (map_x, map_y)     (map_x+1, map_y)
+      (map_x-1, map_y+1)    (map_x, map_y+1)   (map_x+1, map_y+1)
+
+  are preserved, regardless of what the underlying map or drawing code
+  looks like.  This is the definition of this system.
+
+  Map coordinates are easiest for local operations (like square_iterate
+  or adjc_iterate) but unwieldy for global operations.
+
+- Native coordinates.
+
+  With an iso-rectangular map, global operations are difficult using map
+  coordinates.  Imagine a simple iso-rectangular map.  Its "natural"
+  representation is
+
+      X X X                 (0,0)   (2,0)   (4,0)
+       X X X           <=>      (1,1)   (3,1)   (5,1)
+      X X X                 (0,2)   (2,2)   (4,2)
+
+  while its representation in map coordinates would be
+
+     X                            (1,0)
+    XXX                <=>  (0,1) (1,1) (2,1)
+     XXX                          (1,2) (2,2) (3,2)
+      XX                                (2,3) (3,3)
+
+  Neither is particularly good for a global map operation such as
+  whole_map_iterate.  Something better is needed.
+
+  Native coordinates compress the map into a continuous rectangle, the
+  dimensions are defined as map.xsize x map.ysize.  For instance the
+  above iso-rectangular map is represented in native coordinates by
+  compressing the natural representation in the X axis to get the
+  3x3 iso-rectangle of
+
+    XXX                       (0,0) (1,0) (2,0)
+    XXX                <=>    (0,1) (1,1) (2,1)
+    XXX                       (0,2) (1,2) (3,2)
+
+  The resulting coordinate system is much easier to use than map
+  coordinates in a very limited number of operations.  These include
+  most internal topology operations (e.g., normalize_map_pos,
+  whole_map_iterate) as well as storage (in map.tiles and savegames,
+  for instance).
+
+  In general, native coordinates can be defined based on this property:
+  the basic map becomes a continuous (gap-free) cardinally-oriented
+  rectangle when expressed in native coordinates.  (If any map doesn't
+  follow this propertly, the system will have to be refined.)
+
+- Index coordinates.
+
+  Index coordinates simply reorder the map into a continous (filled-in)
+  one-dimensional system.  For instance the above iso-rectangular map
+  would look like
+
+    0 1 2
+     3 4 5
+    6 7 8
+
+  in index coordinates.  This coordinate system is closely tied to
+  the ordering of the tiles in native coordinates, and is slightly
+  easier to use for some operations (like storage) because it is
+  one-dimensional.
+
+With a standard rectangular map, map and native coordinates are
+equivalent.  When we introduce isometric maps, the distinction becomes
+important, as demonstrated above.  Many places in the code have
+introduced "map_x/map_y" or "nat_x/nat_y" to help distinguish whether
+map or native coordinates are being used.  Other places are not yet
+rigorous in keeping them apart, and will often just name their variables
+"x" and "y".
+
+Note that map.xsize and map.ysize define the dimension of the map in
+_native_ coordinates.
+
+=========================================================================
 Unknown tiles and Fog of War
 =========================================================================
 
Index: server/gamelog.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/gamelog.c,v
retrieving revision 1.27
diff -u -r1.27 gamelog.c
--- server/gamelog.c    2003/04/04 15:47:49     1.27
+++ server/gamelog.c    2003/04/05 03:35:28
@@ -93,16 +93,13 @@
 
 void gamelog_map(void)
 {
-  int x, y;
+  int nat_x, nat_y, map_x, map_y;
   char *hline = fc_calloc(map.xsize+1, sizeof(char));
 
-  for (y = 0; y < map.ysize; y++) {
-    for (x = 0; x < map.xsize; x++) {
-      if (regular_map_pos_is_normal(x, y)) {
-       hline[x] = is_ocean(map_get_terrain(x, y)) ? ' ' : '.';
-      } else {
-       hline[x] = '#';
-      }
+  for (nat_y = 0; nat_y < map.ysize; nat_y++) {
+    for (nat_x = 0; nat_x < map.xsize; nat_x++) {
+      native_to_map_pos(&map_x, &map_y, nat_x, nat_y);
+      hline[nat_x] = is_ocean(map_get_terrain(map_x, map_y)) ? ' ' : '.';
     }
     gamelog(GAMELOG_MAP, "%s", hline);
   }