[Freeciv-Dev] Re: (PR#3953) Off-canvas coordinates problem

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

a-l@xxxxxxx wrote:
> There are one or two more issues with map_to_canvas_pos() I think
> need to be addressed, and I'm not quite sure how to go about it.
> This is only about tiles outside of the mapview.

[Digression] I don't think it's putting it too strongly to say that 
wrapping a map position so that it can get the "proper" canvas position 
is the most complicated code Freeciv is every likely to see.

The current implementation doesn't work perfectly for iso-view: some 
tiles will inevitebly end up off the canvas (to the top and left), no 
matter how big you make the canvas.  The current code (from 
map_to_canvas_pos) is basically:

   if (is_isometric) {
     map_x %= map.xsize;
     if (map_x < mapview_canvas.map_x0) {
       map_x += map.xsize;
     }
   } else {
     if (mapview_canvas.map_x0
         + mapview_canvas.tile_width <= map.xsize) {

     } else if (map_x >= mapview_canvas.map_x0) {

     } else if (map_x < map_adjust_x(mapview_canvas.map_x0
                                    + mapview_canvas.tile_width)) {
       map_x += map.xsize;
     } else {

     }
   }

There are problems with both the non-iso (which is really ugly, but 
probably correct for *normal* map positions) and iso (which is simply 
incorrect in some cases) versions.

A correct non-iso implementation would probably be:

   CHECK_MAP_POS(map_x, map_y);
   if (map_x < map_view_x0) map_x += map.xsize;

which is simple enough.  The problem with the iso implementation is it 
only wraps based on one criteria, when actually we should check two 
criteria (whether the tile is off the top of the canvas, or off the 
left).  This would be something like:

   CHECK_MAP_POS(map_x, map_y);
   if (map_x + map_y < map_view_x0 + map_view_y0 - 1
       || map_x - map_y < map_view_x0 - map_view_y0) {
     map_x += map.xsize;
   }

...assuming I have my signs right (which I probably don't).  The added 
-1 offset is because the origin of the *mapview* is defined as the top 
corner of the (map_view_x0,map_view_y0) tile - so it is not symmetrical. 
  (I would be in favor of redefining it so that the origin of the 
mapview is at the center of the (map_view_x0,map_view_y0) tile.  Then we 
get rid of that complication and allow more correct wrapping in the 
general case.)

This becomes many times more complicated when you consider topologies 
that may wrap in X and Y directions, or that are isometric.  For 
instance to do iso-view wrapping in an iso-map that wraps in the X 
direction is just:

   map_to_native_pos(&nat_x0, &nat_y0, map_view_x0, map_view_y0);
   map_to_native_pos(&nat_x, &nat_y, map_x, map_y);
   if (nat_x < nat_x0) nat_x += map.xsize;
   native_to_map_pos(&map_x, &map_y, nat_x, nat_y);

which is the easy case, since the axis of wrapping aligns with the 
mapview.  To do this in the general case Ross has written 
unnormalize_map_pos, which is the "most complicated code Freeciv will 
ever see" alluded to above:

bool unnormalize_map_pos(int *un_x, int *un_y, int map_x0, int map_y0,
                         bool is_iso)
{
   static int ij[2][2], uv[2][2], wraptype = 0;
   int tt[2], vv[2], v0[2], mywraptype;

#define DOT(u, v)    (u[0] * v[0] + u[1] * v[1])
#define ADD(t, u, v) (t[0] = u[0] + v[0], t[1] = u[1] + v[1])
#define SUB(t, u, v) (t[0] = u[0] - v[0], t[1] = u[1] - v[1])

   if (!is_real_map_pos(*un_x, *un_y)) {
     return FALSE;
   }

   mywraptype = topo_getMask(TFLAG_WRAPX | TFLAG_WRAPY);
   if (mywraptype == 0) {
     /* No wrappable coordinates - just return is_real */
     return TRUE;
   }

   if (mywraptype != wraptype) {
     /* Define the wrapping transformations once, and save them */
     wraptype = mywraptype;

     switch (wraptype) {
     case TFLAG_WRAPX:
       /* Only wraps in the standard native X direction */
       uv[0][0] = map.xsize;
       uv[0][1] = uv[1][0] = uv[1][1] = 0;
       break;
     case TFLAG_WRAPY:
       /* Only wraps in the standard native Y direction */
       uv[0][0] = uv[0][1] = uv[1][0] = 0;
       uv[1][1] = map.ysize;
       break;
     case TFLAG_WRAPX | TFLAG_WRAPY:
       /* Wraps in both native X and Y directions */
       uv[0][0] = map.xsize;
       uv[0][1] = uv[1][0] = 0;
       uv[1][1] = map.ysize;
       break;
     default:
       /* No wrap - never used */
       uv[0][0] = uv[0][1] = uv[1][0] = uv[1][1] = 0;
       break;
     }

     /* set coordinate transformation vectors to standard identity */
     ij[0][0] = ij[1][1] = 1;
     ij[0][1] = ij[1][0] = 0;
   }

   /* unnormalization is best determined in native coordinates */
   map_to_native_pos(&vv[0], &vv[1], *un_x, *un_y);
   map_to_native_pos(&v0[0], &v0[1], map_x0, map_y0);

   /* pre-unnormalize: vv will have +ve offsets wrt v0 in native 
coordinates */
   if (topo_hasFlag(TFLAG_WRAPX)) {
     vv[0] -= v0[0];
     vv[0] = vv[0] % map.xsize < 0
            ? vv[0] % map.xsize + map.xsize
            : vv[0] % map.xsize;
     vv[0] += v0[0];
   }
   if (topo_hasFlag(TFLAG_WRAPY)) {
     vv[1] -= v0[1];
     vv[1] = vv[1] % map.ysize < 0
            ? vv[1] % map.ysize + map.ysize
            : vv[1]%map.ysize;
     vv[1] += v0[1];
   }

   /* This is a mongrel algorithm to deal with final fixes to pi/4 rotated
    * aka iso rectangluar window in a normal rectangular map or vice versa.
    *
    * Warning: this is almost impossible to understand without drawing am
    *          accurate graph of the two overlayed views and tricky then.
    *          Each operation effectively moves part of one view bounded
    *          by the appropriate lines through a wrapping translation.
    *          For a simple x-wrapping map, it changes a rectangle into a
    *          parallelogram in one step.
    *          For a torus map, not all of the triangular shape above is
    *          taken, but bits are left for wrap in the other direction
    *          to clean up. The final shape is an "L" or "N". Note an "L"
    *          is just an "N" with one leg shrunk and added to the other
    *          reflecting the constraints imposed by the window origin.
    *          Because of the pre-normalization above, and carefully
    *          chosen operations and order, only one final adjustment is
    *          needed in each direction.
    *
    * When adding new target shapes, only this sort of code should be
    * required, i.e. code that maps a native normal set into a defined
    * normal target shape set.
    */

   if (!is_iso != !topo_hasFlag(TFLAG_ISO)) {
     int n0, n1, n2, n3;

     if (is_iso) {
       ij[0][1] = -1;
       ij[1][0] = 1;

       /* x bounds in target view */
       n0 = DOT(v0, ij[0]);
       ADD(tt, v0, uv[0]);
       n2 = DOT(tt, ij[0]);

       /* y bounds in target view */
       n1 = DOT(v0, ij[1]);
       ADD(tt, v0, uv[1]);
       n3 = DOT(tt, ij[1]);

       if (topo_hasFlag(TFLAG_WRAPX)) {
        while (DOT(vv, ij[0]) < n0
               && (!topo_hasFlag(TFLAG_WRAPY) || DOT(vv, ij[1]) < n3)) {
          ADD(vv, vv, uv[0]);
        }
       }

       if (topo_hasFlag(TFLAG_WRAPY)) {
        while (DOT(vv, ij[1]) >= n3
               && (!topo_hasFlag(TFLAG_WRAPX) || DOT(vv, ij[0]) < n2)) {
          SUB(vv, vv, uv[1]);
        }
       }
     } else {
       ij[0][1] = 1;
       ij[1][0] = -1;

       /* x bounds in target view */
       n0 = DOT(v0, ij[0]);
       ADD(tt, v0, uv[0]);
       n2 = DOT(tt, ij[0]);

       /* y bounds in target view */
       n1 = DOT(v0, ij[1]);
       ADD(tt, v0, uv[1]);
       n3 = DOT(tt, ij[1]);

       if (topo_hasFlag(TFLAG_WRAPY)) {
        while (DOT(vv, ij[1]) < n1
               && (!topo_hasFlag(TFLAG_WRAPX) || DOT(vv, ij[0]) < n2)) {
          ADD(vv, vv, uv[1]);
        }
       }
       if (topo_hasFlag(TFLAG_WRAPX)) {
        while (DOT(vv, ij[0]) >= n2
               && (!topo_hasFlag(TFLAG_WRAPY) || DOT(vv, ij[1]) < n1)) {
          SUB(vv, vv, uv[0]);
        }
       }
     }
   }

   /* put things back to standard map coordinates */
   native_to_map_pos(un_x, un_y, vv[0], vv[1]);
   return TRUE;
#undef DOT
#undef ADD
#undef SUB
}

> Issue 1.
> 
> I would like the function to behave so that a tile with a higher map
> Y coordinate always gets a higher canvas Y coordinate.
> 
> In Iso, this is not always true for out-of-sight-tiles.

In some cases, this is not possible - sometimes the tile will wrap 
around to be on the canvas, but at a lower position than the original. 
But the off-canvas errors you're talking about are caused by the bad 
wrapping in map_to_canvas_pos - this can be fixed, although I haven't 
bothered to do so since this code will be replaced eventually anyway.

> However, the reverse function is ok; You can start with a canvas
> coordinate, increase it by a half or full NORMAL_TILE_HEIGHT, and
> always get a tile with a higher map Y coordinate.

Sometimes this may cause it to wrap around.  Consider if you start with 
map position (79,0) which is (canvas_x, canvas_y).  In iso-view you add 
NORMAL_TILE_HEIGHT.  Now you have position (80,1)=>(0,1).

The way I would try to avoid these problems is to only deal in offsets. 
  If you have (canvas_x0, canvas_y0, canvas_dx, canvas_dy) you can 
convert (canvas_x0, canvas_y0) to a (map_x0, map_y0) via 
canvas_to_map_pos, and convert (canvas_dx, canvas_dy) to a (map_dx, 
map_dy) via manual labor.  I think.

> Example:
> 
>   Canvas coordinates given by map_to_canvas_pos().
> 
>   A vertical line drawn with tiles
>   (0,0)  (1,1)  ...  (49,49)
> 
>   on a isometric map:

You mean an isometric mapview.

>      / \
>     /   \______ (0, 0) north pole
>    /    |\
>    \    | \
>     \   |  \
>      \  |  /
>       \ |_/____ (tile_x, tile_y)
>        \|/_____ (49, 49) south pole
> 
>   The problem:
> 
>     The canvas coordinate of tile_y can be the same as the Y canvas
>     coordinate of tile (0, 0) when the mapview is centered about the
>     center of the global map. The X will be different.

Yes.  Sometimes this tile_y will be on the mapview, and in this case it 
is correct.  But sometimes it's off to the left, and in this case it's 
wrong (meaning this tile will never be displayed, no matter how big you 
make the canvas).

>   (0, 0) and (tile_x, tile_y) are clearly not on the same latitude,
>   but they are clearly on the same longitude, so the function's got
>   it backwards in some cases.

Well, from a topology view it's always correct - the wrapping is all 
legal.  But from the mapview's POV it is the wrong wrapping to use - we 
should use a wrapping that gives non-negative canvas positions.

> Issue 2.
> 
> Canvas coordinates can be negative. But the minimum and maximum
> values (the wrapping point) given by map_to_canvas_pos() are
> variable, depending on the mapview's centering and size. Also,
> because of Issue 1) isometric will rarely give negative X
> coordinates.
> 
> So I have to use somewhat special cases when iterating over canvas
> coordinates to determine the wrapping point. (I want to keep them in
> agreement with the canvas coordinates that the function gives for the
> tile they represent, for certain reasons.)
> 
> Maybe the ideal behaviour of map_to_canvas_pos() would be this:
> For tiles outside of mapview, consider the map's X and/or Y wrapping,
> and determine wheter a negative or a very big coordinate should be
> produced based upon the shortest real distance. To the left or right
> of the monitor?

map_to_canvas_pos should never give a canvas position where canvas_x <= 
NORMAL_TILE_WIDHT or canvas_y <= NORMAL_TILE_HEIGHT.

> The reverse function can already coordinate negative or positive
> canvas coordinates to the correct tile, as long as they are whole
> multiples of map size.

Yes, canvas_to_map_pos is much easier since we do the topology operation 
the easy way, i.e. normalize_map_pos.

> Could we have normalize_canvas_pos() ?
> Native canvas coordinates?

You'll have to define these terms before we can think about it :-).  I'm 
interested in introducing GUI coordinates, but I have yet to define 
exactly what they should be...

jason