[Freeciv-Dev] (PR#4648) how to do wrapping in map_to_canvas_pos?

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

map_to_canvas_pos must first wrap the given map position relative to the 
mapview origin, then convert that to a canvas position.

It is the wrapping that is tricky.  The obvious logic is something like:

   if (map_x < map_view_x0) {
     map_x += map.xsize;
   }

and this is basically what is currently used for both iso and non-iso 
views.  But this isn't quite right for iso-view; for instance 
(map_view_x0,map_view_y0-2) will wrap to itself and will never be shown, 
no matter how large you make the window.

When we allow north-south wrapping and iso-maps this becomes 
exponentially more complicated.

One alternative is to do the wrapping explicitly, as is done above. 
Ross has written a function to do this for gen-topologies, called 
unnormalize_map_pos.  It is very complicated.  See the attached 
unnormalize_map_pos.c.

Another alternative is to use map_distance_vector to find the 
representative position "closest" to the center of the mapview window, 
and use that position for the calculations.  This means 
map_distance_vector must be able to deal with unreal positions, as 
map_to_canvas_pos does.  See the attached map_to_canvas_pos.diff (this 
patch fixes the "not quite right" part of the current implementation).

Which is better?

jason

/**************************************************************************
  Generalized rectangular (un)normalize (in map coordinates)

  This finds the point in the (iso-)rectangular normalized set at offset
  (x0, y0). For isometric rectangles, thee wrapping condition test is
  given by a linear combination of the standard map coordinates.

  This still assumes a native rectangular map shape with x and/or y
  wrapping conditions.

  Note: normalize_map_pos is just this function calleed with (x0,y0) of
        the standard map origin and is_iso false.
**************************************************************************/
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] = WRAP(vv[0], map.xsize);
    vv[0] += v0[0];
  }
  if (topo_hasFlag(TFLAG_WRAPY)) {
    vv[1] -= v0[1];
    vv[1] = WRAP(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
}

Index: client/mapview_common.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/client/mapview_common.c,v
retrieving revision 1.52
diff -u -r1.52 mapview_common.c
--- client/mapview_common.c     2003/07/21 14:18:49     1.52
+++ client/mapview_common.c     2003/07/22 19:50:28
@@ -154,6 +154,9 @@
   }
 }
 
+static void base_canvas_to_map_pos(int *map_x, int *map_y,
+                                  int canvas_x, int canvas_y);
+
 /**************************************************************************
   Finds the canvas coordinates for a map position. Beside setting the results
   in canvas_x, canvas_y it returns whether the tile is inside the
@@ -178,23 +181,26 @@
 **************************************************************************/
 bool map_to_canvas_pos(int *canvas_x, int *canvas_y, int map_x, int map_y)
 {
+  int center_map_x, center_map_y, dx, dy;
+
+  /*
+   * First we wrap the coordinates to hopefully be within the the mapview
+   * window.  We do this by finding the position closest to the center
+   * of the window.
+   */
+  base_canvas_to_map_pos(&center_map_x, &center_map_y,
+                        mapview_canvas.width / 2,
+                        mapview_canvas.height / 2);
+  map_distance_vector(&dx, &dy, center_map_x, center_map_y, map_x, map_y);
+  map_x = center_map_x + dx;
+  map_y = center_map_y + dy;
+
   if (is_isometric) {
     /* For a simpler example of this math, see
        city_pos_to_canvas_pos(). */
     int iso_x, iso_y;
 
     /*
-     * First we wrap the coordinates to hopefully be within the the
-     * GUI window.  This isn't perfect; notice that when the mapview
-     * approaches the size of the map some tiles won't be shown at
-     * all.
-     */
-    map_x %= map.xsize;
-    if (map_x < mapview_canvas.map_x0) {
-      map_x += map.xsize;
-    }
-
-    /*
      * Next we convert the flat GUI coordinates to isometric GUI
      * coordinates.  We'll make tile (x0, y0) be the origin, and
      * transform like this:
@@ -230,17 +236,7 @@
        && (*canvas_y > -NORMAL_TILE_HEIGHT)
        && *canvas_y < mapview_canvas.height;
   } else {                     /* is_isometric */
-    if (mapview_canvas.map_x0 + mapview_canvas.tile_width <= map.xsize) {
-      *canvas_x = map_x - mapview_canvas.map_x0;
-    } else if (map_x >= mapview_canvas.map_x0) {
-      *canvas_x = map_x - mapview_canvas.map_x0;
-    } else if (map_x < map_adjust_x(mapview_canvas.map_x0
-                                   + mapview_canvas.tile_width)) {
-      *canvas_x = map_x + map.xsize - mapview_canvas.map_x0;
-    } else {
-      *canvas_x = map_x - mapview_canvas.map_x0;
-    }
-
+    *canvas_x = map_x - mapview_canvas.map_x0;
     *canvas_y = map_y - mapview_canvas.map_y0;
 
     *canvas_x *= NORMAL_TILE_WIDTH;
@@ -252,12 +248,11 @@
 }
 
 /**************************************************************************
-  Finds the map coordinates corresponding to pixel coordinates.  Returns
-  TRUE if the position is real; in this case it will be normalized. Returns
-  FALSE if the tile is unreal - caller may use nearest_real_pos() if
-  required.
+  Finds the map coordinates corresponding to pixel coordinates.  The
+  resulting position is unwrapped and may be unreal.
 **************************************************************************/
-bool canvas_to_map_pos(int *map_x, int *map_y, int canvas_x, int canvas_y)
+static void base_canvas_to_map_pos(int *map_x, int *map_y,
+                                  int canvas_x, int canvas_y)
 {
   const int W = NORMAL_TILE_WIDTH, H = NORMAL_TILE_HEIGHT;
 
@@ -298,7 +293,17 @@
 
   *map_x += mapview_canvas.map_x0;
   *map_y += mapview_canvas.map_y0;
+}
 
+/**************************************************************************
+  Finds the map coordinates corresponding to pixel coordinates.  Returns
+  TRUE if the position is real; in this case it will be normalized. Returns
+  FALSE if the tile is unreal - caller may use nearest_real_pos() if
+  required.
+**************************************************************************/
+bool canvas_to_map_pos(int *map_x, int *map_y, int canvas_x, int canvas_y)
+{
+  base_canvas_to_map_pos(map_x, map_y, canvas_x, canvas_y);
   return normalize_map_pos(map_x, map_y);
 }
 
Index: common/map.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/map.c,v
retrieving revision 1.140
diff -u -r1.140 map.c
--- common/map.c        2003/05/15 12:38:11     1.140
+++ common/map.c        2003/07/22 19:50:29
@@ -1372,9 +1372,6 @@
 **************************************************************************/
 void map_distance_vector(int *dx, int *dy, int x0, int y0, int x1, int y1)
 {
-  CHECK_MAP_POS(x0, y0);
-  CHECK_MAP_POS(x1, y1);
-
   *dx = x1 - x0;
 
   if (*dx > map.xsize / 2) {