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

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

You are decidedly defensive (as I think you remarked in January about
a patch I submitted then).

Seriously, we just need to find agreement on some of the foolish
stumbling blocks that get in the way here. Most of the code and
algorithmic form with a few notable exceptions are agreed upon.

I would prefer to move forward constructively on paths where we can 
find agreement, and not waste time arm wrestling on points neither of 
us are going to accept.

Cheers,
RossW
=====

At 12:45 PM 02/07/15 -0700, Jason Short wrote:
>I would like to again propose this cleanup to the canvas_pos_to_map_pos 
>and canvas_pos_to_city_pos functions.

For my part, I think we really just need to do all the coordinate 
transformation functions at once rather than piecemeal.

There is a lot of good symmetry that can be built-in, and a number
of issues that dealing with all at once would hopefully resolve.

Otherwise we get partial fixes like linking the core and GUI that 
effectively killed the rotational coordinate update it was supposed
to help fix. Or the regular coordinate mess that needs to be removed,
a part of which slipped in while hiding the full scope of its
implications - your record in these partial fixes is not good 
though infinitely better/worse than mine to date :-).

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

Agreed.

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

The actual operation is a simple transformation. You make it much more
complicated than it really is. That is why it can be done in two lines.

>Additionally, this change removes the assumption that 
>NORMAL_TILE_WIDTH==2*NORMAL_TILE_HEIGHT.  Currently isometric tilesets 
>must follow this restriction.

Agreed.

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

More reading doesn't necessarily make for better understanding :-).

And sometimes concise code that follows normal patterns is clearer
than piecemeal sections.

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

We agree that the fixup handled by your DIVIDE is required, and the 
operation doesn't need to be done with this piece of ugliness.

The corecleanups use a term of the form "- (*city_x < 0)" to add the 
negative roundoff factor. There are many others possible that are more
efficient than yours if you simply can't allow Ross code into CVS :-).

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

Not to beat a dead horse, it was more your stating that this was 
required. I simply note that a lot of other code needs to change 
before this has any effect other than to reduce current performance. 
The fix is trivial, and can be applied anytime, so leaving the 
more efficient form in for now was not unreasonable. But I don't
really care that much either way.

We agree that it needs to go in at some point.

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

With a few minor cleanups, I agree that moving this into CVS is good. 
I'd still like to see it part of a comprehensive coordinate function
cleanup with agreed upon standard forms, and not done as a oneoff.

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

Well, as long as we get reasonable code in place, I'll try not to wince 
too audibly at the explanations :-).

And now for the real stumbling blocks you didn't mention :-) 

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

The nomenclature here is in dispute.

There are too many pos-es. <type1>_to_<type2>_pos is the standard that
keeps typing cramps to a minimum.

> {
>+  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;

Your use of flat is always a problem. 

It really needs to be reserved for the unwrapped or flat-earth topologies
and not applied to standard/internal map coordinates or random things it
keeps getting tacked onto.

Once this code gets into CVS, it becomes difficult to change. So this
global sort of issue needs to be resolved and not by incremental hacking
of bits here and there.

I really, really wish you would quit pushing this when you know it just
won't fly.

>-    /* 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;

In addition to a pi/4 rotation, you need a coordinate origin shift
and GUI tile scaling to bring the x and y axes to an equivalent pointsize.

It is easier to explain as simple math operations than incomplete 
statements like moving corners and doing something with squares.

The second explanation below, though overly long-winded is needed to
make any sense of this. That shouldn't be the case.

>-    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;

It isn't "flat" :-) 

It is the "standard" or "internal" form for rectangular axis alignment
that all core operations use as a common reference.

>+    /* 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);

Note the magic "2"s are part of the origin shift, a comment would 
help and be more in sync with your stated goal.

And this is what you needed to do, which apart from some minor 
differences is pretty close to your code. The compiler will 
optimize any redundant multiplications, or constant folding,
so except for DIVIDE, we are probably down to the nomenclature
and style issues. 

On divide, get rid of the % and don't try to fold it into a 
general macro - the generality isn't really needed here, and 
there really isn't a lot of use for it except here.

    int roundoff = (NORMAL_TILE_HEIGHT*NORMAL_TILE_WIDTH)/2;
    *city_x = canvas_y*NORMAL_TILE_WIDTH + canvas_x*NORMAL_TILE_HEIGHT
            + roundoff;
    *city_y = canvas_y*NORMAL_TILE_WIDTH - canvas_x*NORMAL_TILE_HEIGHT
            + roundoff;

    *city_x = *city_x / (NORMAL_TILE_HEIGHT*NORMAL_TILE_WIDTH)
            - 2 - (*city_x < 0);
    *city_y = *city_y / (NORMAL_TILE_HEIGHT*NORMAL_TILE_WIDTH)
            + 2 - (*city_y < 0);
   


Finally, If you add this, then the routine follows a useful standard 
for all coordinate transformations.

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

>   } 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;

Flat problems ...

>-    /* 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

Canvases all tend to be flat :-). And so is this refrain ...

>+     * isometric coordinates.  So we next want to convert them back to
>+     * "flat" coordinates.  We'll keep the top-left corner of the canvas

The term "flat" coordinates needs to change to something meaningful. 

>+     * 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;

More de-flat-ing required ...

>-    /* 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.

Flat problems ...

>+     * 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);

And again, all that is really required ...

    int roundoff = (NORMAL_TILE_HEIGHT*NORMAL_TILE_WIDTH)/2;
    *map_x = canvas_y*NORMAL_TILE_WIDTH + canvas_x*NORMAL_TILE_HEIGHT
           + roundoff;
    *map_y = canvas_y*NORMAL_TILE_WIDTH - canvas_x*NORMAL_TILE_HEIGHT
           + roundoff;

    *map_x = *map_x / (NORMAL_TILE_HEIGHT*NORMAL_TILE_WIDTH) - (*map_x < 0);
    *map_y = *map_y / (NORMAL_TILE_HEIGHT*NORMAL_TILE_WIDTH) - (*map_y <
0);   


If you add this, then the routine follows a useful standard for all 
coordinate transformations.
        
  /* Normalize: return valid map coordinates or FALSE if unreal.
   return normalize_map_pos(map_x, map_y);
   */
 

>   } 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. */
>