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

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

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 :-?

Cheers,
RossW
=====

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.