[Freeciv-Dev] cleanup to canvas_pos_to_map_pos, take II (PR#1183)

[Jason Short <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

I would like to again propose this cleanup to the canvas_pos_to_map_pos 
and canvas_pos_to_city_pos functions.
The code that is currently used in these functions is the original code 
written by Thue.  This was a good first implementation, but after over a 
year of re-examining the problem we can do better.
This code reduces the operation to its basic mathematical components: a 
scaling, then a rotation, then another scaling.  It is far cleaner and 
more legible than the current code.  It is probably also faster 
(although I'm not ready to back this up).
Additionally, this change removes the assumption that 
NORMAL_TILE_WIDTH==2*NORMAL_TILE_HEIGHT.  Currently isometric tilesets 
must follow this restriction.
When I originally proposed this change, Ross objected for several reasons:

1.  It is really long.  In Ross's implementation, the three operations 
are conducted in a single pair of lines.  In this patch I have separated 
them and added in verbose descriptions of each operation.  My goal is to 
make it more readible for people who don't already have an understanding 
of the isometric system; other than that I would be happy to condense them.
2.  Ross claimed the use of the DIVIDE operator was incorrect.  He later 
recanted on this.  However, it is still the case that DIVIDE is really 
ugly here - if anyone has an alternative suggestion, please let me know.
3.  He did not believe it was worthwhile to remove the width/height 
assumption.  This assumption cuts down on a couple words of code, and 
removes a couple of instructions of machine code.  But I think it's 
definitely time to get rid of it - Daniel asked about this several 
months ago.
I think a patch like this would be a very good first step in returning 
to work on alternate topologies.  The above arguments aside, the code 
that is currently there is mathematically vague and very difficult to 
comprehend.  Trying to prove (or even convince yourself) that it is 
correct is very difficult.  It has always bugged me, and I think it 
should be replaced as soon as possible.
As an aside, understanding of this code would be a very good first step 
for anyone who wants to understand the isometric system used in 
isometric view and (in the future) in an iso-rectangular map.
jason

Index: client/citydlg_common.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/client/citydlg_common.c,v
retrieving revision 1.7
diff -u -r1.7 citydlg_common.c
--- client/citydlg_common.c     2002/07/01 21:13:30     1.7
+++ client/citydlg_common.c     2002/07/15 19:26:47
@@ -54,35 +54,38 @@
 **************************************************************************/
 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;
 
-    /* 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;
+    /* Shift the tile right so the top corner of tile (-2,-2) is at (0,0). */
+    canvas_y += NORMAL_TILE_HEIGHT / 2;
 
-    /* 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;
+    /* First we scale it to a square. */
+    canvas_x *= NORMAL_TILE_HEIGHT;
+    canvas_y *= NORMAL_TILE_WIDTH;
 
-    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)++;
+    /* Then we transform it to make it flat. */
+    flat_canvas_x = canvas_x + canvas_y;
+    flat_canvas_y = canvas_y - canvas_x;
+
+    /* 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.12
diff -u -r1.12 mapview_common.c
--- client/mapview_common.c     2002/03/19 15:48:38     1.12
+++ client/mapview_common.c     2002/07/15 19:26:48
@@ -187,34 +187,66 @@
                           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;
 
-    /* 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;
+    /* 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;
 
-    /* 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;
+    /*
+     * 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;
 
-    /* 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;
-    }
+    /*
+     * 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
Index: common/shared.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/shared.h,v
retrieving revision 1.95
diff -u -r1.95 shared.h
--- common/shared.h     2002/05/25 17:44:08     1.95
+++ common/shared.h     2002/07/15 19:26:48
@@ -52,6 +52,13 @@
 
 #define BOOL_VAL(x) ((x)!=0)
 
+/*
+ * DIVIDE() divides and rounds down, rather than just divides and
+ * rounds toward 0.
+ */
+#define DIVIDE(n, d) \
+    ((n) % (d) < 0 ? (n) / (d) - 1 : (n) / (d))
+
 /* Deletes bit no in val,
    moves all bits larger than no one down,
    and inserts a zero at the top. */