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

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

Gregory Berkolaiko wrote:
> On Fri, 4 Apr 2003, Jason Short wrote:
> 
> 
>>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
> 
> 
> I assume this macros will change drastically when iso-rect is implemented?
> Otherwise, they seem a bit pointless...

Yep.  Eventually they may look something like this:

   void map_to_native_pos(int *nat_x, int *nat_y, int map_x, int map_y)
   {
     if (map_is_isometric()) {
       *nat_y = (map_x + map_y - map.xsize);
       *nat_x = (map_x + map_x - *nat_y - (*nat_y & 1)) / 2;
     } else {
       *nat_x = map_x;
       *nat_y = map_y;
     }
   }

   void native_to_map_pos(int *map_x, int *map_y, int nat_x, int nat_y)
   {
     if (map_is_isometric()) {
       *map_x = (nat_y + (nat_y & 1)) / 2 + nat_x;
       *map_y = nat_y - *map_x + map.xsize;
     } else {
       *map_x = nat_x;
       *map_y = nat_y;
     }
   }

   which can easily be written in macro form.

>>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.
> 
> 
> Nice explanation (I didn't know you terminology before).
> Suggestions:
> 1. You might mention that "natural" coordinate system is obtained by 
> sparsing the rectangular one.

Hmm.

> 2. Can you give the index notation along with "X" sketches?
> I mean when you compare
> 
>       X X X            X
>        X X X    to    XXX
>       X X X            XXX
>                         XX
> you wonder which X went to which X. But in 
>       0 1 2            0
>        3 4 5          631
>       6 7 8            742
>                         85
> it is more clear (provided I got it right).

OK.

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 18:16:43
@@ -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 18:16:44
@@ -408,6 +408,116 @@
 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
+
+                     XX                   (2,0)
+                    XXX  <=>        (1,1) (2,1) (3,1)
+                   XXX        (0,2) (1,2) (2,2)
+                    X               (1,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.
+
+- 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
+
+        25        0 1 2         012     
+       148   <=>   3 4 5   <=>  345   <=> 012345678
+      037         6 7 8         678
+       6
+
+  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.
+
+- Natural coordinates.
+
+  These have been hinted at above, but are not actually used in Freeciv.  But
+  they are very helpful for human understanding of non-standard maps.
+
+  Natural coordinates preserve the geometry of map coordinates, but also have
+  the rectangular property of native coordinates.  They are unweildy for
+  some operations because of their sparseness - they may not have the
+  same scale as map coordinates and, in the iso case, there are gaps in
+  the natural representation of a map.
+
+  For an isometric map, natural coordinates are the same as
+  called "isometric coordinates".
+
+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.
+
+Of course, if a future topology does not fit these rules for coordinate
+systems, they will have to be refined.
+
+=========================================================================
 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 18:16:45
@@ -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);
   }