[Freeciv-Dev] Re: (PR#6259) iso-map versions of native<->map pos conversion macros

["rwetmore@xxxxxxxxxxxx" <rwetmore@xxxxxxxxxxxx>]

Below is the code from the corecleanups, which can be seen to pretty much
validate Jason's macros below. It has been operational for a long time.
In general, the code below is both operationally correct and reasonably
well implemented.


There are some minor nits that might be incorporrated to improve things.

First as the CC comments state, there is a potential division issue with
transforming negative values that one can get around by using the shift
operator for an integer divide by 2. This guarantees that no matter what
way one sets interger roundoff this code continues to do the right thing.
Otherwise, one has built in an unnecessary, and fairly severe constraint
on the mathematical range of applicability of the APIs.

The second is a minor performance nit in map_to_native_pos(). Basically
one can remove the extra "2 * " for the map_x by moving it outside the
brackets. Since these coordinate calls happen a lot, this is a worthwhile
percentage improvement in the performance. Anyway, there is absolutely no
reason to not do it efficiently.

 > +      *(pnat_x) = (2 * (map_x) - *(pnat_y) - (*(pnat_y) & 1)) / 2)          
 > \

The last issue is one of the ongoing problems with people "seasoning" every
codepath with paranoia checks for the mistakes that were introduced a number
of years back in handling normalization.

In this case the CHECK_MAP_POS() and CHECK_INDEX() calls, break elementary
transformation routines by requiring that coordinates be normalized at some
point. These are *just* low-level simple mathematical coordinate system
transformations that should be usable with normal and unnormal coordinates.
Examples of unnormal values are found in mapping GUI windows with map_views
that extend into wrapped adjacent normal spaces. Any checks of this sort
have no validity inside these basic transformations, but should be moved to
external code locations if it is determined that these locations should be
loaded down with the unnecessary paranoia constraint checks.

Raimar and others have in the past been guilty of breaking a number of
elementary operations by trying to imbed such constraints at a low-level
where they did not apply, and thus severly reduced the value and
effectiveness of the APIs that were so overloaded. This just means that
developers will simply avoid the APIs and hardcode local workarounds that
will result in a future maintenance nightmare.

It is *permissible* to define "checked" and "unchecked" versions of the
transformations, with code locations that care calling the checked form.
Just so long as the core transformations are not obscured or constrained
by unnecessary and artificially limiting behaviour with no way to access
the full range of API validity.

Nesting situations where constraints are involved to provide constrained and
unconstrained versions is always a good thing (TM). Most people see limited
implications, i.e. only their own immediate code issue and/or religious point
of view, in hardwiring such things, but providing flexibility allows one to
recover from this relatively gracefully down the road.

The fix here is to remove the checks from the current macros and optionally
provide checked forms of the macros, and update any code locations where it
is verified that the constraints imposed are not harmful.

Cheers,
RossW
=====

/* Shift operations handle /2 as divide and round up for +ve or -ve cases.
  * Thus the natural iso_x coordinate is compressed with round down for native.
  * Note: operations carefully ordered for inplace conversion
  */
#define map_to_native_pos(PX, PY, MX, MY)        /* standard map to native */ \
( (get_maptype(MAP_TYPE_ISO)                                                  \
   ? (*(PY)= (MX) + (MY) - map.xsize,                                          \
      *(PX)= (MX) - (((*(PY) & 1) + *(PY)) >> 1))                              \
   : (*(PY)= (MY), *(PX)= (MX))), TRUE )


/* Shift operations handle /2 as divide and round up. This recovers the lost
  * natural iso_x bit, since the sum of iso_x + iso_y must be even.
  * Note: operations carefully ordered for inplace conversion
  */
#define native_to_map_pos(PMX, PMY, X, Y)        /* native to standard map */ \
( (get_maptype(MAP_TYPE_ISO)                                                  \
   ? (*(PMX)= ((((Y) & 1) + (Y)) >> 1) + (X), *(PMY)= (Y) - *(PMX) + map.xsize)\
   : (*(PMY)= (Y), *(PMX)= (X))), TRUE )


Jason Short wrote:
> For iso-maps to work native coordinates have to work for them.  This 
> patch changes native_to_map_pos, map_to_native_pos, map_to_native_x, and 
> map_to_native_y to do that.  I also add a section to doc/HACKING.
> 
> This doesn't mean iso-maps will fully work yet, though.  So there's 
> really no way to test this code outside of the rest of the patch 
> (gen-topologies.diff in the 'patches' module of the freeciv-test 
> repository).
> 
> This patch deserves scrutiny since the math is pretty obscure.
> 
> jason
> 
> ------------------------------------------------------------------------
> 
> ? rc
> Index: common/map.h
> ===================================================================
> RCS file: /home/freeciv/CVS/freeciv/common/map.h,v
> retrieving revision 1.154
> diff -u -r1.154 map.h
> --- common/map.h      2003/09/23 19:47:22     1.154
> +++ common/map.h      2003/09/23 20:30:27
> @@ -235,15 +235,28 @@
>  #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 native_to_map_pos(pmap_x, pmap_y, nat_x, nat_y)                     \
> +  (topo_has_flag(TF_ISO)                                                    \
> +   ? (*(pmap_x) = ((nat_y) + ((nat_y) & 1)) / 2 + (nat_x),                  \
> +      *(pmap_y) = (nat_y) - *(pmap_x) + map.xsize)                          \
> +   : (*(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_to_native_pos(pnat_x, pnat_y, map_x, map_y)                     \
> +  (topo_has_flag(TF_ISO)                                                    \
> +   ? (*(pnat_y) = (map_x) + (map_y) - map.xsize,                            \
> +      *(pnat_x) = (2 * (map_x) - *(pnat_y) - (*(pnat_y) & 1)) / 2)          \
> +   : *(pnat_x) = (map_x), *(pnat_y) = (map_y))
>  
>  /* Use map_to_native_pos instead unless you know what you're doing. */
> -#define map_pos_to_native_x(map_x, map_y) (map_x)
> -#define map_pos_to_native_y(map_x, map_y) (map_y)
> +#define map_pos_to_native_x(map_x, map_y)                                   \
> +  (topo_has_flag(TF_ISO)                                                    \
> +   ? (((map_x) - (map_y) + map.xsize                                        \
> +       - (((map_x) + (map_y) - map.xsize) & 1)) / 2)                        \
> +   : (map_x))
> +#define map_pos_to_native_y(map_x, map_y)                                   \
> +  (topo_has_flag(TF_ISO)                                                    \
> +   ? ((map_x) + (map_y) - map.xsize)                                        \
> +   : (map_y))
>  
>  #define map_pos_to_index(map_x, map_y)        \
>    (CHECK_MAP_POS((map_x), (map_y)),           \
> Index: doc/HACKING
> ===================================================================
> RCS file: /home/freeciv/CVS/freeciv/doc/HACKING,v
> retrieving revision 1.12
> diff -u -r1.12 HACKING
> --- doc/HACKING       2003/07/23 20:24:36     1.12
> +++ doc/HACKING       2003/09/23 20:30:27
> @@ -556,6 +556,49 @@
>  systems, they will have to be refined.
>  
>  =========================================================================
> +Native coordinates on an isometric map
> +=========================================================================
> +
> +An isometric map is defined by the operation that converts between map
> +(user) coordinates and native (internal) ones.  In native coordinates, an
> +isometric map behaves exactly the same way as a standard one.  (See
> +"native coordinates", above.
> +
> +Converting from map to native coordinates involves a pi/2 rotation (which
> +scales in each dimension by sqrt(2)) followed by a compression in the X
> +direction by a factor of 2.  Then a translation is required since the
> +"normal set" of native coordinates is defined as
> +  {(x, y) | x: [0..map.xsize) and y: [0..map.ysize)}
> +while the normal set of map coordinates must satisfy x >= 0 and y >= 0.
> +
> +Converting from native to map coordinates (a less cumbersome operation) is
> +the opposite.
> +                                        EJ
> +           ABCDE     A B C D E         DIO
> +  (native) FGHIJ <=>  F G H I J <=>   CHN  (map)
> +           KLMNO     K L M N O       BGM
> +                                    AFL
> +                                     K
> +
> +Note that
> +
> +  native_to_map_pos(0, 0) == (0, map.xsize-1)
> +  native_to_map_pos(map.xsize-1, 0) == (map.xsize-1, 0)
> +  native_to_map_pos(x, y+2) = native_to_map_pos(x,y) + (1,1)
> +  native_to_map_pos(x+1, y) = native_to_map_pos(x,y) + (1,-1)
> +
> +The math then works out to
> +
> +  map_x = ceiling(nat_y / 2) + nat_x
> +  map_y = floor(nat_y / 2) - nat_x + map.xsize - 1
> +
> +  nat_y = map_x + map_y - map.xsize
> +  nat_x = floor(map_x - map_y + map.xsize / 2)
> +
> +which leads to the macros native_to_map_pos, map_to_native_pos,
> +map_pos_to_native_x, and map_pos_to_native_y that are defined in map.h.
> +
> +=========================================================================
>  Unknown tiles and Fog of War
>  =========================================================================
>