[Freeciv-Dev] Re: [PATCH] cleanup to canvas_pos_to_map_pos (PR#1183)

["Ross W. Wetmore" <rwetmore@xxxxxxxxxxxx>]

This is the simpler version of what you do. Note, these are basically 
equivalent functions in virtually all respects.

>The advantages of this cleanup are:
>
>1.  The code is readable (at least IMO) and (very) well commented.

Fewer lines and convoluted operations make code more readable.

>2.  It can now handle isometric tilesets where the 
>NORMAL_TILE_WIDTH!=2*NORMAL_TILE_HEIGHT.

The fix below is indicated and trivial to implement. It uses the same 
philosophy. Probably isn't worth doing until neeeded though.

>3.  The code used in the two functions is now nearly identical.  The old 
>code used quite different cases for the city_pos and map_pos because the 
>tiles were offset differently.  This is much easier to do by just 
>shifting the canvas position before doing any calculations instead [1]. 

You really need to look at the clumsiness of doing things piecemeal and
fixing up the integer roundoff problems. Just do the rotational 
transformation (equivalent to your moving things to different translated
offsets in tiny steps), then scale. Don't try to fix up individual integer 
truncation of each small scaling step after the fact :-).

>  This means this code could reasonably be combined into a single 
>function, but I don't think that's necessary.

This would be a bad idea, because the two transformations are quite 
different conceptually, even if the code is nearly identical. Just think
about always representing the citymap view in a (compact) trident tileset 
to understand what this would mean. Your instincts are good, even if your
conscious thoughts haven't quite caught up to them.

Note the effective work is done in two lines by a simple rotation, so
code duplication is not a major concern. The key missing element is the
return status which needs to check different things.

Cheers,
RossW
=====

void canvas_to_city_pos(int *city_x, int *city_y, int canvas_x, int canvas_y)
{
  /* Transform: rescale and translate */
  if (is_isometric) {
    /* Transform: compute the x = city_y + city_x position of the sprite.
     *            compute the y = city_y - city_x position of the sprite.
     *
     * Note: use of y*2 and NORMAL_TILE_WIDTH is the optimized form of
     *   (canvas_y*N_T_H + canvas_x*N_T_W)/(N_T_H*N_T_W) which insures
     *   that arbitrary points are correctly assigned to the right tile.
     *   There are four half tiles in the isometric rectangle of dimension
     *   NORMAL_TILE_HEIGHT*NORMAL_TILE_WIDTH at the topleft origin.
     *
     * The Roundoff parameter is set to centre mouse clicks on tiles
     * Play with the origin offsets in city_to_canvas_pos to get these all
     * in sync. There appears to be an odd scaling in the citydlg map
     * as you move away from the x==y line. Remove workers by approaching
     * along various directions until it goes to see the effect.
     */
    int roundoff = NORMAL_TILE_HEIGHT/2;
    assert(NORMAL_TILE_WIDTH == 2 * NORMAL_TILE_HEIGHT);
    *city_x = (canvas_y*2 + canvas_x + roundoff*2) / NORMAL_TILE_WIDTH - 2;
    *city_y = (canvas_y*2 - canvas_x - roundoff/2) / NORMAL_TILE_WIDTH + 2;

  } else {          /* !is_isometric */

    assert(NORMAL_TILE_WIDTH == NORMAL_TILE_HEIGHT);
    *city_x = canvas_x / NORMAL_TILE_WIDTH;
    *city_y = canvas_y / NORMAL_TILE_HEIGHT;
  }

  freelog(LOG_DEBUG, "canvas_to_city_pos(pos=(%d,%d))=(%d,%d)",
    canvas_x, canvas_y, *city_x, *city_y);

  /* Normalize: return valid map coordinates or FALSE if unreal.
  return is_valid_city_coords(*city_x, *city_y);
   */
}  

int canvas_to_map_pos(
 int *map_x, int *map_y,
 int canvas_x, int canvas_y,
 int map_view_topleft_map_x, int map_view_topleft_map_y)
{
  /* Transform: rescale and translate */
  if (is_isometric) {

    /* Transform: rotate the x = map_y + map_x position of the sprite.
     *            rotate the y = map_y - map_x position of the sprite.
     *
     * Note: use of y*2 and NORMAL_TILE_WIDTH is the optimized form of
     *   (canvas_y*N_T_W + canvas_x*N_T_H)/(N_T_H*N_T_W) which insures
     *   that arbitrary points are correctly assigned to the right tile
     *   without integer truncation that initial scaling would cause.
     *   There are four half tiles in the isometric rectangle of dimension
     *   NORMAL_TILE_HEIGHT*NORMAL_TILE_WIDTH at the topleft origin.
     *
     * The Roundoff parameter is used to centre mouse clicks on tiles
     * Play with the origin offsets in map_to_canvas_pos, and display
     * centering in update_canvas to get these all in sync.
     */
    int roundoff = NORMAL_TILE_HEIGHT;
    assert(NORMAL_TILE_WIDTH == 2 * NORMAL_TILE_HEIGHT);
    *map_y = (canvas_y*2 - canvas_x + roundoff) / NORMAL_TILE_WIDTH;
    *map_x = (canvas_y*2 + canvas_x + roundoff) / NORMAL_TILE_WIDTH;

  } else {          /* !is_isometric */

    assert(NORMAL_TILE_WIDTH == NORMAL_TILE_HEIGHT);
    *map_x = canvas_x / NORMAL_TILE_WIDTH;
    *map_y = canvas_y / NORMAL_TILE_HEIGHT;
  }
  *map_x += map_view_topleft_map_x;
  *map_y += map_view_topleft_map_y;

  /* Normalize: return valid map coordinates or FALSE if unreal.
   return normalize_map_pos(map_x, map_y);
   */

  /*
   * If we are outside the map find the nearest tile, with distance
   * as seen on the map.
   *
   * FIXME: this is a gross hack or a par with void_tile-ism.
   *        Return normalize_map_pos(), find the callers and fix them to
   *        deal with the failure mode on a case-by-case basis.
   */
  return nearest_real_pos(map_x, map_y);
}


      


At 06:14 AM 01/12/31 -0500, Jason Short wrote:
>The attached patch provides a cleanup to canvas_pos_to_map_pos and 
>canvas_pos_to_city_pos.  This is similar to what Ross does in his 
>corecleanups, but more thorough/focused.
>
>The advantages of this cleanup are:
>
>1.  The code is readable (at least IMO) and (very) well commented.
>
>2.  It can now handle isometric tilesets where the 
>NORMAL_TILE_WIDTH!=2*NORMAL_TILE_HEIGHT.
>
>3.  The code used in the two functions is now nearly identical.  The old 
>code used quite different cases for the city_pos and map_pos because the 
>tiles were offset differently.  This is much easier to do by just 
>shifting the canvas position before doing any calculations instead [1]. 
>  This means this code could reasonably be combined into a single 
>function, but I don't think that's necessary.
>
>
>The big disadvantage of this patch is that I'm not sure how to cleanly 
>do integer division.  After the translation, getting the map position 
>out of the canvas position should be as simple as
>   map_x = canvas_translated_x / TRANSLATED_WIDTH;
>   map_y = canvas_translated_y / TRANSLATED_HEIGHT;
>but, this doesn't work because the translated position can be negative, 
>and the rounding won't be done properly in this case (-5/2==-2).  My 
>temporary solution is to add a divide() function, but this isn't really 
>acceptable.  So what should I do?  Surely there's a "real" way to do 
>such calculations?  (Note to Ross: you don't account for this in the 
>corecleanups, so there's an off-by-one error for some tiles.)
[...]
>jason
>
>? diff
>? jason-game.gz
>? jason.gz
>? old
>? test
>? test.pl
>? topology
>Index: client/citydlg_common.c
>===================================================================
>RCS file: /home/freeciv/CVS/freeciv/client/citydlg_common.c,v
>retrieving revision 1.3
>diff -u -r1.3 citydlg_common.c
>--- client/citydlg_common.c    2001/12/13 15:30:30     1.3
>+++ client/citydlg_common.c    2001/12/31 10:29:53
>@@ -45,38 +45,57 @@
> }
> 
> /**************************************************************************
>+It baffles me that -5/2==-2 instead of -3.  But since it does, to do
>+worthwhile integer division we use this function instead.
>+
>+This function is currently duplicated, but shouldn't be used in any
>+case.
>+**************************************************************************/
>+static int divide(int numerator, int denominator)
>+{
>+  div_t division = div(numerator, denominator);
>+  if (division.rem < 0) {
>+    division.quot--;
>+  }
>+  return division.quot;
>+}
>+
>+/**************************************************************************
> This converts a citymap canvas position to a city coordinate position
> (either isometric or overhead).  It should be in cityview.c instead.
> **************************************************************************/
> void canvas_pos_to_city_pos(int canvas_x, int canvas_y, int *map_x, int
*map_y)
> {
>+  int orig_canvas_x = canvas_x, orig_canvas_y = canvas_y;
>   if (is_isometric) {
>-    *map_x = -2;
>-    *map_y = 2;
>+    /*
>+     * The top-left corner is in the center of tile (-2, 2).  The math used
>+     * here is identical to that used in canvas_pos_to_map_pos; see that
>+     * function for a full explanation.
>+     */
>+    int flat_canvas_x, flat_canvas_y;
>+
>+    /* Shift the tile right so the top corner of tile (-2,-2) is at
(0,0). */
>+    canvas_y += NORMAL_TILE_HEIGHT / 2;
>+
>+    /* First we scale it to a square. */
>+    canvas_x *= NORMAL_TILE_HEIGHT;
>+    canvas_y *= NORMAL_TILE_WIDTH;
>+
>+    /* Then we transform it to make it flat. */
>+    flat_canvas_x = canvas_x + canvas_y;
>+    flat_canvas_y = canvas_y - canvas_x;
> 
>-    /* first find an equivalent position on the left side of the screen. */
>-    *map_x += canvas_x / NORMAL_TILE_WIDTH;
>-    *map_y -= canvas_x / NORMAL_TILE_WIDTH;
>-    canvas_x %= NORMAL_TILE_WIDTH;
>-
>-    /* Then move op to the top corner. */
>-    *map_x += canvas_y / NORMAL_TILE_HEIGHT;
>-    *map_y += canvas_y / NORMAL_TILE_HEIGHT;
>-    canvas_y %= NORMAL_TILE_HEIGHT;
>-
>-    assert(NORMAL_TILE_WIDTH == 2 * NORMAL_TILE_HEIGHT);
>-    canvas_y *= 2;            /* now we have a square. */
>-    if (canvas_x + canvas_y > NORMAL_TILE_WIDTH / 2)
>-      (*map_x)++;
>-    if (canvas_x + canvas_y > 3 * NORMAL_TILE_WIDTH / 2)
>-      (*map_x)++;
>-    if (canvas_x - canvas_y > NORMAL_TILE_WIDTH / 2)
>-      (*map_y)--;
>-    if (canvas_y - canvas_x > NORMAL_TILE_WIDTH / 2)
>-      (*map_y)++;
>+    /* Now we've got a square, so it's a simple matter to find the
>+       position. */
>+    *map_x = -2 + divide(flat_canvas_x,
>+                       NORMAL_TILE_WIDTH * NORMAL_TILE_HEIGHT);
>+    *map_y = 2 + divide(flat_canvas_y,
>+                      NORMAL_TILE_WIDTH * NORMAL_TILE_HEIGHT);
>   } else {
>     *map_x = canvas_x / NORMAL_TILE_WIDTH;
>     *map_y = canvas_y / NORMAL_TILE_HEIGHT;
>   }
>-  freelog(LOG_DEBUG, "canvas_pos_to_city_pos(pos=(%d,%d))=(%d,%d)",
canvas_x, canvas_y, *map_x, *map_y);
>+  freelog(LOG_DEBUG, "canvas_pos_to_city_pos(pos=(%d,%d))=(%d,%d)",
>+        orig_canvas_x, orig_canvas_y, *map_x, *map_y);
> }
>Index: client/mapview_common.c
>===================================================================
>RCS file: /home/freeciv/CVS/freeciv/client/mapview_common.c,v
>retrieving revision 1.4
>diff -u -r1.4 mapview_common.c
>--- client/mapview_common.c    2001/12/21 16:53:10     1.4
>+++ client/mapview_common.c    2001/12/31 10:29:54
>@@ -176,6 +176,22 @@
> }
> 
> /**************************************************************************
>+It baffles me that -5/2==-2 instead of -3.  But since it does, to do
>+worthwhile integer division we use this function instead.
>+
>+This function is currently duplicated, but shouldn't be used in any
>+case.
>+**************************************************************************/
>+static int divide(int numerator, int denominator)
>+{
>+  div_t division = div(numerator, denominator);
>+  if (division.rem < 0) {
>+    division.quot--;
>+  }
>+  return division.quot;
>+}
>+
>+/**************************************************************************
>   Finds the map coordinates corresponding to pixel coordinates.
> **************************************************************************/
> void canvas_pos_to_map_pos(int canvas_x, int canvas_y,
>@@ -184,34 +200,67 @@
>                          int map_view_topleft_map_y)
> {
>   if (is_isometric) {
>-    *map_x = map_view_topleft_map_x;
>-    *map_y = map_view_topleft_map_y;
>+    /* For another example of this math, see canvas_pos_to_city_pos(). */
>+    int flat_canvas_x, flat_canvas_y;
>+
>+    /* If the tile width and height are not equal, then it will take very
>+     * ugly math to figure anything out about it.  The easiest solution is
>+     * just to "scale" the tile so that it's a perfect (diamond) square.  We
>+     * are doing the following transformation to a tile:
>+     *
>+     *                                 XX  <- height=18, width=18
>+     *   XX   <- height=3, width=6
>+     * XXXXXX                        XXXXXX
>+     *   XX   -----> becomes ----->
>+     *                                 XX
>+     *
>+     * Note that all we really need to do is scale to the LCM of the width
>+     * and height (in the above example, 6x6).  But it's easier just to
scale
>+     * to WIDTH*HEIGHT (18x18).
>+     */
>+    canvas_x *= NORMAL_TILE_HEIGHT;
>+    canvas_y *= NORMAL_TILE_WIDTH;
>+    assert(canvas_x >= 0 && canvas_y >= 0);
> 
>-    /* first find an equivalent position on the left side of the screen. */
>-    *map_x += canvas_x / NORMAL_TILE_WIDTH;
>-    *map_y -= canvas_x / NORMAL_TILE_WIDTH;
>-    canvas_x %= NORMAL_TILE_WIDTH;
>-
>-    /* Then move op to the top corner. */
>-    *map_x += canvas_y / NORMAL_TILE_HEIGHT;
>-    *map_y += canvas_y / NORMAL_TILE_HEIGHT;
>-    canvas_y %= NORMAL_TILE_HEIGHT;
>-
>-    /* We are inside a rectangle, with 2 half tiles starting in the
>-       corner, and two tiles further out. Draw a grid to see how this
>-       works :). */
>-    assert(NORMAL_TILE_WIDTH == 2 * NORMAL_TILE_HEIGHT);
>-    canvas_y *= 2;            /* now we have a square. */
>-    if (canvas_x > canvas_y) {
>-      *map_y -= 1;
>-    }
>-    if (canvas_x + canvas_y > NORMAL_TILE_WIDTH) {
>-      *map_x += 1;
>-    }
>+    /*
>+     * The "canvas coordinates" we're given look flat, but they're really
>+     * isometric coordinates.  So we next want to convert them back to
>+     * "flat" coordinates.  We'll keep the top-left corner of the canvas
>+     * as (0,0) so that we have an easy frame of reference.  The
>+     * transformation, which we're applying to a square tile, becomes:
>+     *
>+     *   1      1 4
>+     *  234  ->  3
>+     *   5      2 5
>+     *
>+     * This is (ignoring scale) the inverse of the transformation being
>+     * done in map_pos_to_canvas_pos.
>+     */
>+    flat_canvas_x = canvas_x + canvas_y;
>+    flat_canvas_y = canvas_y - canvas_x;
>+
>+    /*
>+     * Now the (x0, y0) tile originally had its top corner at (0,0) and
>+     * its bottom corner at (0,NORMAL_MAP_HEIGHT).  These are positions 1
>+     * and 5 on the diagram above.  We have transformed these two positions:
>+     *   (0,0) -> (0,0) -> (0,0)
>+     *   (0,H) -> (0,W*H) -> (W*H,W*H)
>+     * The tile is now a flat rectangle with these as its opposite corners.
>+     * This makes it easy to tell what tile our coordinates belong to!
>+     *
>+     * Unfortunately, integer division doesn't work so well for negative
>+     * numbers; -5/2==-2 while we're looking for -3.  So this is a bit
>+     * uglier than it would otherwise be.
>+     */
>+    *map_x = divide(flat_canvas_x, NORMAL_TILE_WIDTH * NORMAL_TILE_HEIGHT);
>+    *map_y = divide(flat_canvas_y, NORMAL_TILE_WIDTH * NORMAL_TILE_HEIGHT);
>   } else {                    /* is_isometric */
>-    *map_x = map_view_topleft_map_x + canvas_x / NORMAL_TILE_WIDTH;
>-    *map_y = map_view_topleft_map_y + canvas_y / NORMAL_TILE_HEIGHT;
>+    *map_x = canvas_x / NORMAL_TILE_WIDTH;
>+    *map_y = canvas_y / NORMAL_TILE_HEIGHT;
>   }
>+
>+  *map_x += map_view_topleft_map_x;
>+  *map_y += map_view_topleft_map_y;
> 
>   /*
>    * If we are outside the map find the nearest tile, with distance as
>