[Freeciv-Dev] Re: example patch: [xy]_map_iterate

[Jason Dorje Short <vze2zq63@xxxxxxxxxxx>]

[Note: this explanation is long and repetitious.  I'm trying to be as
clear as possible.]

Raimar Falke wrote:

> Now I have another basic question:
> 
>    a
>   bcd
>  efghi
>   jkl
>    m
> 
> For which tiles is y==0? a OR e,b and a? Or isn't this an isometric
> map? And the following is:?

It is an isometric map, but not a correct one if you desire wrapping. 
It can't wrap properly.  A correction would be:

  a     <- y==0
 bcd    <- y==1
efghi      ...
 jkln      ...
  mo    <- y==4

^   ^
|   |
|   x==4
|
x==0

With the addition of n and o it will now successfully wrap in one
direction.  y==0 for just tile a.

> 
>         / North
>    n  /
>   o p
>  q r s
>   t u
>    v
> 
> The same map rotated (non-isometric now):
> 
>  n p s
>  o r u
>  q t v

These two pictures are the same map, but a fundamentally different one
from the one above.  This is a normal 3x3 map.  The first picture is the
way it might be displayed with an isometric tileset, the second is how
it is displayed with a "regular" (cartesian) tileset and also how both
server and client track it internally.  The problem is that under
isometric view, the map is all tilted!  It's pretty ugly.

Doing the same transformation on the first map, we see that

  a
 bcd
efghi
 jkln
  mo

is the same as

a d i
 c h n
b g l
 f k o
e j m

Hopefully you now understand everything :-).

As you can see it will look much better when *viewed* isometrically.  I
think you are confusing an isometric *map* with an isometric *view*. 
The second one we have - it requires a lot of very ugly math in the
client code.  The first one we are not even close to being able to do -
it requires a little bit of ugly code in the server AND everything else
has to be fixed to use the proper map macros and functions.

Putting these directions onto the cartesian representation of the map,
we see that "north" is up-left, "south" is down-right, "east" is
up-right, and "west" is down-left.  Everything's just rotated 45
degrees.  (Note: you can really rotate it 45 degrees in either
direction, but you need to take care that its the same direction every
time.  I don't remember which way the client rotates things, but we
should consider that before choosing.)

> The adjacent property is the same.
> 
>        /
> -     # \4
> |    # # \
> |   # # #  \/
> 6    # # #
> |     # # \
> -      # / 3
>         \
> 
>     |--6-|
> 
> The game has to know somewhere the this map above is 3x4.

Again, it *is* 3x4.  The server would never think of a regular map in
this odd way; it always uses strictly cartesian coordinates.  This is
how you would view it in the client isometrically; so unfortunately the
client is forced to think of it this way (although it still thinks of it
the cartesian way and makes the conversion each time it draws anything).

> The more I think about this the more I think that the easiest way is
> to leave the current system in place and introduce a new name/position
> space. Normal positions are called map positions and the new ones are
> called user positons. If there is a non-isometric map there would a
> 1:1 mapping of map pos to user pos and back. If there is a isometric
> map is used the mapping would be more complicated. Neighbor properties
> and distances are only defined on user positions.

You definitely do not understand.

Client-side, this is basically what is done now.  But that's for an
isometric *view*, not an isometric map.

An isometric map is still cartesian.  The directions are still all the
same.  It's just a different shape, and wraps differently.  So "the
current system" as (I think) you are thinking of it will still work; all
of the changes will be restricted to a few macros and functions within
map.[ch].  But it's simply not possible to make the transformation as
some sort of wrapper as you seem to be suggesting - that's what the
client does with its isometric view, and it is something entirely
different.

All of the changes now come because the current code assumes the
topology is rectangular and wraps in one direction.  This code must be
replaced by code that does not make these assumptions, but instead uses
the correct macros and function calls: is_normal_map_pos instead of
map_adjust_[xy], whole_map_iterate instead of for(x...) for(y...),
is_real_tile instead of (y>=0 && y<map.ysize), etc.

> Summary: before I don't understand this issue and especially the end
> result fully there will be no changes by me.

A wise plan in general, but with most of these changes I think it'll be
clear that they are cleanups to the code that make things better and
remove the assumptions above.

> What
> coordinates/positions are there? What semantic they represent (where
> is north and south)?

Here is an isometric map as the user would see it under isometric
tileset:

a d i
 c h n
b g l
 f k o
e j m

I think this is the easiest way to visualize it.  North, south, east,
and west are obvious.  Note that this map can wrap east-west, but cannot
possibly wrap north-south - the tiles won't line up.  If you try to do
any actual calculations with this representation, though, it's very
difficult - hence the difficulty of having an isometric tileset.

  a
 bcd
efghi
 jkln
  mo

This is how the server will represent it, and almost all current
operations will continue to still work.

The most likely way it'll store the data is in a 5x5 array, although
this wastes space.  A more general method would be in a single-index
array using map_pos_to_index to index into it (it's more general because
it can easily be extended to more extreme topologies).

Almost all calculations can be done exactly the same way on this
isometric map as on the current map.  The neighbor property remains
exactly the same.  The only real differences are with border tiles,
wrapping/normalcy, and realness.  is_real_tile and normalize_map_pos
will contain some rather complicated code that will take some time to
understand (if you don't believe me, look at the transformations Thue
does to get an isometric view).  Also whole_map_iterate and the like
won't work as-is because you can't iterate over it rectangularly; but
you can still either iterate over the whole 5x5 space and filter out the
bad positions or iterate over the index and use index_to_map_pos.  This
issue really doesn't affect the [xy]_map_iterate I've been proposing;
they're not directly needed because of the isometric map but are needed
because some places can't use whole_map_iterate to do the iteration. 
The reason these changes are important for the isometric map is that the
filter (on is_normal_map_pos) is still needed and will have to be added
(we could theoretically go ahead and write the for loops out in each
case and filter for normal coordinates manually...but it's better to
have the macros do it).

Counting the dimensions of an isometric map is tricky as well.  You can
think of the above map as a 6x5 isometric map (see the isometric
representation).  It therefore has 6x5/2==15 tiles.  (The 2 factor comes
because we're overcounting by a factor of sqrt(2) in each direction.)  A
map will only wrap in a direction if its dimension is even (as opposed
to odd) in that direction.  (Clarification: if you have a 5x5 map you
get 5x5/2=12.5 tiles.  This is because the 5x5 map can be drawn to have
either 12 or 13 tiles.  In the above example, remove either the leftmost
or rightmost column (isometric view) to see.)  Alternately, you could
count the map as a 3x2.5 isometric map; in this case you'd probably want
to impose the restriction of integer dimensions (which also assures
wrapping).  In this case the number of tiles is 3x2.5x2=15 tiles.  (This
time the 2 factor comes because we're undercounting by a factor of
sqrt(2) in each direction.)

Understand this: I'm not currently proposing anything directly related
to an isometric map.  All of my proposed patches to date are merely
cleanups that make the changes I mentioned above.  The only thing that
isn't directly productive is that we filter over normal tiles in my most
recent patch.  However, this also makes possible other things that have
been proposed like invalid tiles in the middle of the map that represent
impassable mountains - so again they're not directly related to an
isometric map.  We also make possible other simpler things like wrapping
the rectangular map in different directions (which Ross's patch already
accomplishes, but does not do so in the correct manner because it still
assumes a rectangular map).  In short: all we're doing at this point is
removing assumptions from the code.

I don't think it's entirely necessary that you understand isometric
maps.  Once all assumptions in the code are removed, a very few pieces
of code will have to deal with the isometricness: normalize_map_pos,
is_normal_map_pos, is_real_tile, index_to_map_pos, and map_pos_to_index
may be all.  The act of removing those assumptions has nothing to do
with isometric maps itself; it applies equally well to other maps like

     ^ ^ ^
     | | |
<- a b c d
<- e f g h   /* weird approximation of a hemisphere */
<- i j k l

<- a b c d e ->
<- f g   i j -> /* an invalid position to signify
<- k l m n o ->    impassable mountains */

We are a very long way off from having an actual isometric map.

jason