[Freeciv-Dev] Re: [PATCH] cleanup to canvas_pos_to_map_pos (PR#1183)
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
At 02:54 PM 01/12/31 -0500, Jason Short wrote:
>Ross W. Wetmore wrote:
>
>> This is the simpler version of what you do. Note, these are basically
>> equivalent functions in virtually all respects.
>>
[...]
>(2) You add the "roundoff" offset, the effects of which I'm not sure of.
> I think this is intended to fix the rounding problem, but it fails -
>try clicking on a tile in the upper right of the mapview. If it serves
>some other purpose, can you explain?
This is not the roundoff problem that you assume. If it were there would
be a discontinuous shift at some point. Instead, it is a scaling failure
that grows in as you move away from the x==y line, as the comments explain.
I think it might have something to do with the way the tiles are drawn,
in that they overlap one or two pixels and thus near the edges you have
lost almost a full tile. Try locating the edges tile by tile out from
the center rather than just doing one at the edge to get a better handle
on the issue. I think tiles are really (NORMAL_HEIGHT-1) in size :-).
The roundoff parameter I use allows one to fine-tune the mouse clicks
so you get them more or less centered, and yes in part this fixes the
integer scaling truncation issue at a single point, but much more
flexibly. I experimented a lot with this until I gave up and set it to
a best compromise. It is really a two parameter origin shift as the
sign and multiplicative factors are the real twiddle elements.
>(3) I instead use the divide() function. I agree, this is unacceptably
>clumsy. What alternative do you suggest?
Did you look at the map.h macros?
How about choosing an algorithm that removes or minimizes integer
truncation?
If all else fails ...
#define div(x,y) (x%y < 0 ? (x/y-1) : x/y)
>(4) Your math is one line, whereas I separate each step. This is a
>matter of preference. Your way gives fewer lines of code; mine allows a
>more thorough explanation of the steps involved.
The operation is a rotation and the formula for rotation by 45 degrees is
x' = x + y;
y' = -x + y;
or
y' = x - y; going the other way
which are done on two lines. Adding 18 more doesn't really improve the
conceptual understanding IMHO, nor does manufacturing extra steps :-).
>> 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 :-).
>
>I don't quite understand what you're suggesting. We need to first
>scale, then rotate, then un-scale. Both our functions do exactly that.
Why do you need to first scale :-?
Just rotate and do a final scaling, especially since things are nice whole
integers in canvas coordinates all the way.
You may be hung up on the current implementation, and not really thinking
about the real problem. Think out-of-the-box and see if that helps.
>>>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.
>>
>> * 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.
>I would change the following lines
That is what the comments say to do, except get rid of the divide().
But it adds 3-4 more multiplications and isn't currently needed. It is
also trivial to do when the rest of the codebase is updated to handle
this. But it is a nitfix.
> assert(NORMAL_TILE_WIDTH == 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;
>
>to
>
> *map_y = divide(canvas_y * NORMAL_TILE_WIDTH -
> canvas_x * NORMAL_TILE_HEIGHT,
> NORMAL_TILE_WIDTH * NORMAL_TILE_HEIGHT);
> *map_x = divide(canvas_y * NORMAL_TILE_WIDTH -
> canvas_x * NORMAL_TILE_HEIGHT,
> NORMAL_TILE_WIDTH * NORMAL_TILE_HEIGHT);
>
>This way you avoid the off-by-one error and also allow for when
>N_T_W!=2*N_T_H. (Except, of course, that I'd replace "divide" by the
>appropriate division, which has yet to be determined.)
The off by one is simply fixed by choosing the origin point (aka using
the roundoff factors) appropriately so there is no problem. The rotation
is a continuous operation, and you just need to pick the line where you
fall over from one tile to the next.
Note, most of the severity of the problem in your case is due to the
clumsiness of dealing with things piecemeal. It really isn't an issue
if you work in (integral) canvas coordinates, and save the scaling for
the final step only.
>Either one of these functions is an improvement to the current code, so
>I suggest we propose them both and let the list decide.
No problem ... but I really don't understand what you are missing. It
really shouldn't be that difficult to understand both algorithms, and
if you do it is clear that something that takes 20 lines to handle is
really beating about the bush instead of going straight for it :-).
I'd really like to see the functions return proper status values when they
go in. Then other places that use them can be cleaned up to deal with the
failure modes properly. This is for me a far more important concept to
get right.
>jason
>
>
>> 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
>>>
>>>
>>
>>
>>
>>
>
>
>
>
>
|
|
