[Freeciv-Dev] [PATCH] cleanup to canvas_pos_to_map_pos (PR#1180)

[jdorje@xxxxxxxxxxxxxxxxxxxxx]

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.)

Behavior should be identical under this patch.


[1] Another word on this: in the mapview, the (x0, y0) tile has its top 
corner at canvas position (0,0).  The mapview tiles are therefore set up 
something like:
 x x x
x x x
 x x x
x x x

Meanwhile, in the city view the (x0, y0) tile (which is (-2,2)) has its 
_center_ at canvas position (0,0).  The mapview tiles are here set up 
something like:
x x x
 x x x
x x x
 x x x

Because of this difference the old code used different checks for the 
city and map cases.  But it's easier to just shift the canvas position 
before doing the calculation (or after translating the position).

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