[Freeciv-Dev] Native Coordinates [Was:[PATCH] Map cleanups (PR#1208)

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

I've taken this to a fresh debate forum.

As a quick backgrounder so we can start from a common set of
(mis)understood terms  ...

I am using "standard" or "map" or "game" coordinates to mean the 
internal coordinate system used in most of the current code. The
standard set is 2-D rectangular (x,y) based, and is typified by 
the trident tileset on the usual world map.

I use "native" coordinates to mean a coordinate system which is
generally rectangular in shape, but whose coordinates are not 
necessarily spaced or organized in a standard rectangular grid.
An example is a true isometric map which occupies only even or
odd points (i.e. x+y is even or odd) and is thus diagonal in
spacing. Native isometric coordinates can be mapped to standard
coordinates to give a pi/4 rotated rectangular array.

Compressed native isometric recognizes that every other position
is unoccupied in each row and indexes the row value as x' = x/2.
There is also a shift of 1/2 position in a zigzag pattern that
gets lost when doing this, but the even or oddness of the y or
row value can be used to fix this up in any reverse conversion.

For standard maps, standard and native coordinates are equivalent.

A key property of native coordinates is that no real coordinate 
position appears more than once. 

Another property that must be built in to any native coordinate
system is that wrapping axes are aligned with the rectangular
coordinate axes.

Typically, savegames, debug output and general memory storage are
best dealt with in native coordinates, with rows and columns in
the usual standard layout. It is specifically for these uses that
the native system is chosen or designed for any given topology.

In fact, almost all global game and topology operations are easiest
to handle in this representational form, is_border_tile() for
instance is only slightly more tricky because of the zizag in
native isometric.

Conversely, standard map representations are best used for local
game and directional operations like adjacent iteration.

Making sure one has designed the native representation appropriately
and that there is a reasonably efficient coordinate transformation
process allows one to convert to the representation best suited for 
given operations on the fly in local codepaths. It means one does not 
have to decide up front which is the one-true-representation that has 
to do it all, no matter how cumbersome or complicated things get.


There is a competing term "flat" for standard coordinates. Personally
I think all 2-D coordinates are flat, and "Flat-Earth" is a general
term for a non-wrapping topology, so this is confusing and overloaded.
But we should add "flat" to "standard" or "map" or "game" as an alternate
designation until it's use dies out :-).

Regular is a term that is used to describe a rectangular bounding box
in standard coordinates that encloses a complete normal set such as a
pi/4 rotated true isometric rectangle. 

For standard maps, standard and regular coordinates are equivalent.
For a 100 x 2 isometric map, this would be a 102 x 102 square. 

Typically one iterates over all values of the regular map and selects 
the ones that are normal for global operations (<2% in the above case, 
but never better than 50%). Unfortunately, in wrapping scenarios, there 
may be a lot of equivalent coordinate positions in the regular set that 
map into the normal subset (over a 50 in a torus world for the given 
example, but never less than 2).

Storing savegames, debug printing etc. are all typically done in the
regular coordinate system because of the rectangular axes. Typically
"unreal" or "duplicate" markers are stored for the extra positions.
For the above isometric world, one would see a diagonal band or rectangle
on printout of 102 lines of 102 elements, and a 5200% increase in savegame
size.


Note it is always possible to choose a native or a regular system for
any given 2-D topology, and a coordinate system that maps it to the
standard internal game coordinates and back. 

Choosing a regular system means identifying the extremum points in the 
topology in the axial directions. 

Choosing a native system means choosing a regular system in a rotated 
coordinate frame that is aligned with the topological wrapping axes, or 
in one that minimizes the number of unreal tiles if there is no axial 
constraint.


I suspect that it is a property of wrapping axes in 2-D that they must
be orthogonal. Certainly limiting ones topologies by this constraint will
do much to reduce stress on both game designers and players. 

This makes it relatively easy to guarantee a single normal set in native 
coordinates. With no wrap possibility, unreal conditions are detected by a 
filter operation, which is also not surprisingly the key test condition 
for the regular case.


There is another pre-existing format to which we will give the name 
"linear" or "vector". It is typically only used in a one-way transformation 
handled by map_inx(), though index_to_map_pos() is its reverse.


In standard maps, "standard", "regular", "native" and "linear" usually 
map to the same memory locations, and linear is just the vector form of 
the array storage system. Linear coordinates are optimal for storage, 
and can always be designed to hold exactly one normal set. Printing,
wrapping and other global topology operations are not usually optimal 
in linear coordinates.


Finally, the corecleanups use native coordinates extensively where they
simplify life. There is no trace of any interfaces with "regular" in them,
but map_std_xsize() and map_std_ysize() return regular dimensions where
the native and standard coordinate axes are not aligned, and various
standard objects are regular sized. There are a number of places where a 
native_to_map_pos() transformation has been inserted into code, usually 
where a global iteration is handled in native coordinates, but access is 
needed to standard map operations. Otherwise code and data structures
outside of the topology functions are relatively untouched.

The generalized-topology alternative uses regular coordinates extensively
rather than native. There is a key data structure that are added to hold 
standard coordinates, and a number of changes in code to switch from the
map dimensions that are now subsumed by regular to the topology ones.
Global operations are typically unchanged apart from the is_normal
condition test for the spin checks.

There are considerable performance and general game flow differences 
between the two because of slightly different ways of traversing the 
global coordinate space.


Ok, now for the technical debate on fine points :-).

At 01:18 AM 02/01/07 -0800, jdorje@xxxxxxxxxxxxxxxxxxxxx wrote:
>Ross W. Wetmore wrote:

>>>>>c)  is_normal_map_pos() -> normalize_map_pos()
>>>>>    Returned values must be normalized, so just do it and return.
>>>>>
>>>>
>>>>    do {
>>>>      *x = myrand(map.xsize);
>>>>      *y = myrand(map.ysize);
>>>>-  } while (!is_normal_map_pos(*x, *y));
>>>>+  } while (!normalize_map_pos(x, y));
>>>>  }
>>>>
>>>>This change is incorrect.  Consider an iso-rectangular cylinder.  In 
>>>>this case, all positions will be real, and so will be accepted by 
>>>>normalize_map_pos.  However, it is only normal positions that we are 
>>>>interested in.  Changing the code like this will result in some 
>>>>positions being picked more often than others.
>>>>
>> 
>> Consider the iso-rectangular cylinder, it has a map.xsize x map.ysize
>> native coordinate set where all values are treated exactly the same
>> as the current standard rectangular cylinder.
>> 
>> But what you are missing is the native coordinate conversion because 
>> that isn't in yet. Look at the prototype/corecleanup version.
>>     do {
>>       *x = myrand(map.xsize);
>>       *y = myrand(map.ysize);
>>       native_to_map_pos()&x,&y);
>>     } while (!normalize_map_pos(x, y));
>> which typically takes one pass per coordinate requested. Native 
>> coordinates are by definition normal as they are currently in the 
>> standard map. By normal one means no real coordinate appears twice.
>> 
>> For now, there is only standard == native coordinates, so this is correct.
>> 
>> This solution takes the tack of properly defining the random selection
>> to use the native normal space. Other solutions do things in cruder
>> more expeensive ways but hopefully not in Freeciv.
>
>Again, no.
>
>The current working definition is that everything is in flat 
>coordinates; no concept of "native" coordinates has yet been introduced. 
>  In flat coordinates, is_normal_map_pos is definitely what we want.  We 
>don't want to find any non-normal position, since that will imbalance 
>the probability of finding each position.

Non-normal is ambiguous and thus is is clear why such things are useless
to you. 

Unreal are trapped by both cases. Real but unnormalized is the only case 
in question.

In the current standard == regular == native there are no unnormalized
coordinates. It doesn't matter, there is by definition no problem.

In a regular system like the isometric band above, I agree you are 
not going to get precisely the ratios you want. 

But the current code would have a 2% hit rate on returning any valid
coordinate, and the ratio is going to be off by 4 tiles in 10404 which
is the residual amount after filling with 2x100 duplicates. I'm not sure
the added accuracy for returning a random tile is worth it.

Getting rid of an is_normal_map_pos() in itself is worth it, not
counting the performance benefits.

On the otherhand a native system guarantees, like the current standard
case that elements will only appear once. is_real_tile() would be 
sufficient check here, but normalize_map_pos() is equally valid, and
has the warm fuzzy benefit of trashing another is_normal_map_pos() use
before it takes root and spreads :-).

>In native coordinates each position will be guaranteed to be normal.  So 
>in this case the normalize_map_pos is unnecessary; we might as well 
>stick with is_normal or leave the check out entirely.

Leaving the check out means that filter-realness is not checked. So it
would not work for elliptical coordinates that filter out some of the
rectangular set.

>Given that neither of these systems have been implemented, we should 
>stick by the method that will work equally well for either of them; 
>especially since that's the way the function was originally designed and 
>written.

The best method is one that is good-enough-but-no-better and efficient
at what it does.

>As another side note, "native" coordinates are not guaranteed to be flat 
>or even to exist, so relying on something like this is unsafe in the 
>general case.  It is better to write something of this form:

Native coordinates are guaranteed to be what you design them to be. In
all cases of interest, rectangular and consisting of a single normal set.

There is only a problem if you choose bad native sets.

>   int index = myrand(map_index_size());
>   index_to_map_pos(index, *x, *y);

Yes, this is a valid choice with the normalize_map_pos() to filter out
unreal cases which one may have been inserted to make things "easier"
for transformation or some other reason. 

>even this assumes that a continuous index_to_map_pos is possible, which 
>may not be feasible (though it's certainl _possible_) under all 
>topologies, so it might be best to do
>   int index;
>   do {
>     index = myrand(map_index_size());
>   } while (!index_to_map_pos(index, *x, *y));
>I had thought we were tentatively agreed on this index_to_map_pos system...

One could rely on index_to_map_pos() returning a valid condition, and
make it conform to the general transformation function standard, which
up to now I have not really tried to insure. Or rather have explictly
not done to the native and linear transformations, as they are used a 
lot and I think generally in a manner where the normalization is already
guaranteed. But one could do a checked and unchecked version.

This would mean adding a normalize_map_pos() as a final step in the
checked case.

I actually like it a lot because, while it doesn't really save a lot
in the normalize part, it is only one myrand() call.

But then I'm sort of backwards to the rest of you in considering tight
clean efficient code generally beneficial, rather than something to try
and eradicate as "ugly" or bury in out of the way nested functions :-).

[...]
>> No, it is perfectly safe. Since in fact is_normal_map_pos() just calls 
>> normalize_map_pos() and throws away the values, using an extra function 
>> call in the process, this change is actually more efficient so it is 
>> worth doing this part now.
>
>It is certainly unsafe in my implementation of general-topologies.

That might be a thought on which to ponder ...

>jason

Chers,
RossW
=====