[Freeciv-Dev] Re: topology RFC (again)

[Jason Dorje Short <vze2zq63@xxxxxxxxxxx>]

"Ross W. Wetmore" wrote:
> 
> Just to correct the minor misunderstanding ...
> 
> "native iso maps that are rectangular in iso coordinates" refers to
> the map topology, or maybe I should have been more careful to add that
> in native iso maps, the wrapping vectors are aligned with rectangular
> map dimensions in iso coordinates. The natural rectangular GUI window
> then trivially displays iso with none of the odd dislocation of having
> a map edge running at 45 degrees. Of course with such a natural iso
> topology, trident tilesets will be the odd case :-).
> 
> About coordinates ...
> 
> You should always pick the coordinate system to work in to make life
> easy, and transform in and out of it where needed. But this doesn't
> mean that you can't do all your mundane arithmetic in one special one
> if that is the way you find it easiest.
> 
> For fun, and because if your are going to misunderstand, you might as
> well misunderstand correctly, I've attached some random notes on what
> might happen if you really did handle rectangular iso in more natural
> coordinates, i.e. focussed on the rectangular topology, and not the
> underlying memory coordinate representation that is the way iso is now
> (historically/hysterically) perceived.
> 
> Notice there is no mention of "regular" sets in these notes, and whole
> map iteration is really not that tricky :-?

Using isometric coordinates to "natively" represent isometric maps is
very cool-sounding, but I think you are misjudging the difficulties and
advantages involved.

For advantages, how is it really any better to do a "translation" from
memory to game coordinates on each whole_map_iterate than it is to do a
check for is_normal_map_pos?  It is no less tricky, and probably not any
faster either.

For difficulties - if some game coordinates use isometric coordinates
and some use flat map coordinates, then there will be great confusion
and high potential for bug-causing mistakes.  On the other hand, if all
game coordinates are isometric coordinates (that is, if all game
coordinates are "native map coordinates", which for iso-rectangular maps
is isometric coordinates), then a large amount of work will be needed to
make all code conform to this convention.  This will not just be a
matter of changing the DIR_DX/DIR_DY arrays, but of fixing
adjc_cartesian_iterate to use them, changing square_iterate and all
citymap iterators to convert from flat coordinates (which is really what
it must use) to "game" coordinates, and (hardest of all) changing all
locations in the code that manually move in one direction to use the
DIR_DX/DIR_DY iterators as well.

In summary, I think this change is really not worth the trouble at this
time.  It's way too ambitious.  At some later point it may be desirable
to allow the map to be any arbitrary graph, subject to the constraints
of the GUI (as Reiner has suggested), but the amount of work necessary
to do this is much larger than the simple changes necessary to achieve
simple cartesian-grid maps.  Or, to put it another way, since the client
must use cartesian-grid ("flat") coordinates anyway, why go to a lot of
trouble to use something different for the "game coordinates" used by
the core code?

jason


The rest of the message read:

> At 12:03 AM 01/11/08 -0500, Jason Dorje Short wrote:
> >"Ross W. Wetmore" wrote:
> [...]
> >> Finally, once you have the ability to work with native iso maps
> >> that are rectangular in iso coordinates, as opposed to rotating a
> >> normal map into a display where the wrapping dimensions are at
> >> skewed angles to the GUI axes, you should never need to worry or
> >> have any desire to use these things.
> >
> >I can see no advantage to using "native" iso coordinates versus using
> >flat (cartesian?) coordinates.  While striving for an arbitrary-graph
> >map system would be nice, there's really no reason to do it for this
> >topology.
> [...]
> 
> Random notes on possible implementations for natural
> rectangular iso maps.
> 
> Normalized spaces and Storage options
> 
>     . . . . . . . . + o . . .
>     . . . . . . . + o + o . .
>     . . . . . . + o . . + o .
>     . . . . . + o . . . . + o
>     . . . . + o . . . . + o .
>     . . . + o . . . . + o . .
>     . . + o . . . . + o . . .
>     . + o . . . . + o . . . .
>     + o . . . . + o . . . . .
>     . + o . . + o . . . . . .
>     . . + o + o . . . . . . .
>     . . . + o . . . . . . . .
> 
>     | y=4 |      x = 9    |
> 
> In the 12x12 square touched by the 9x4 "+" rectangle one quickly
> sees that the corner triangles form 3x4 and 8x9 rectangles leaving
> 36 + 24 tiles for the "+" rectangle.
> 
> If one looks a little more, it is clear that 36 of them form a
> nice rectangular grid corresponding to the x' and y' offsets from
> the corner at (3,0). The other 24 are the interior "o" points at
> 1/2 step values.
> 
> You can add an extra column and complete a similar "o" rectangle.
> All the enclosed "x" + "o" points form a wrappable isometric grid.
> 
> If you rotate everything 45 degrees and renumber the x',y'
> coordinates to get rid of the 1/2, you see they form half a full
> rectangular grid with every even or odd point missing, where
> even is (x+y)%2 = 0.
> 
>  _  x . x . x . x . x . x . x . x . x .
>     . o . o . o . o . o . o . o . o . o
>     x . x . x . x . x . x . x . x . x .
>  y  . o . o . o . o . o . o . o . o . o
>  =  x . x . x . x . x . x . x . x . x .
>  8  . o . o . o . o . o . o . o . o . o
>     x . x . x . x . x . x . x . x . x .
>  _  . o . o . o . o . o . o . o . o . o
> 
>     |             x = 18              |
> 
> What does this mean in terms of natural iso coordinates in Freeciv?
> 
> If you store the game coordinates in the diagonal shape you have 72
> active tiles in a 12x13 array that holds 156.
> 
> If you stored them in an 8x18 rectangle skipping every other point
> this would take 144 positions, i.e. (2x * 2y)/2.
> 
> And if you compressed the x axis you could store the map in just
> and 8x9 grid for 72.
> 
> Whole Map Iteration for iso-rectangular maps
> 
>  ... would be something like this
> 
>   map.ysize = 8, map.xsize = 9;
>   for(y = 0; y < map.ysize; y++)
>   for(x = 0; x < map.xsize; x++) {
>     map_y = y, map_x = x * 2 + (y & 1);
>   }
> 
> or alternatively
> 
>   map.ysize = 8, map.xsize = 18;
>   for(y = 0; y < map.ysize; y++)
>   for(x = (y & 1); x < map.xsize; x+= 2) {
>     mem_y = y, mem_x = x / 2;
>   }
> 
> One might define a function mem_to_map like
> 
> int mem_to_map(&map_x, &map_y, x, y) {
>   return (map_y = y, map_x = x, TRUE);
> }
> 
> int mem_to_isomap(&map_x, &map_y, x, y) {
>   return (map_y = y, map_x = x * 2 + (y & 1), TRUE);
> }
> 
> and then we have a general rectangular or iso rectangular map
> iterator.
> 
> #define whole_map_iterate(map_x, map_y, mem_x, mem_y) {
>   int map_x, map_y, mem_x, mem_y;
>   for(mem_y = 0; mem_y < map.ysize; mem_y++)
>   for(mem_x = 0; mem_x < map.xsize; mem_x++) {
>     *(map.mem_to_map)(&map_x, &map_y, mem_x, mem_y);
> 
> #define whole_map_iterate_end
>   }
> 
>  ... or better ...
> 
> #define whole_map_xy_iterate(map_x, map_y, mem_xy) {
>   int map_x, map_y, mem_xy;
>   for(mem_xy = map.xsize * map.ysize; mem_xy-- > 0; ) {
>     if( *(map.mem_to_map)(&map_x, &map_y, mem_xy) ) {
> 
> #define whole_map_xy_iterate_end
>     }
>   }
> 
> The change that will be pervasive here, is that map and mem
> coordinates are now no longer the same. And one will have to
> do an appropriate transformation when doing memory accesses.
> This means everyone needs to use map_to_mem(), map_index(x,y)
> or similar function to access stored memory values.
> 
> But interestingly, the normalize_map_pos() and associates are
> trivially related. In memory coordinates they are exactly the
> same. In map coordinates, the X-wrap is twice as large for iso.
> This is because both topologies are basically rectangular.
> 
> It might be fun to look at a trident tileset GUI transformation
> for natural isomap coordinates.
> 
> Other code changes for generalized rectangular topologies
> 
> Note, the values for the DIR_D[XY] isomap game coordinates are
> now in rotational order:
> 
> DIR_DX = { -1,  0,  1, 2, 1, 0, -1, -2 };
> DIR_DY = { -1, -2, -1, 0, 1, 2,  1,  0 };
> 
> But with an added index to select between regular and iso, this
> fixes all adjacent iterators and map_step().
> 
> Map distances may need to be recomputed, but instead of
> MAX(ABS(dx), ABS(dy)) something like (ABS(dx)+ABS(dy))/2 might
> work.