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

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

At 03:43 AM 02/01/09 -0500, Jason Short wrote:
>Ross W. Wetmore wrote:
>
>> 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.
>
>I am of several minds about native coordinates.
>
>1.  Native iso coordinates are great to do topological calculations in 
>if you have an iso-rectangular topology.  But this can be done entirely 
>internally to the topology code (i.e. without "native coordinates" as a 
>global concept).

It is always nice to have a concept to guide your programming. It is like
a plan before you build. Understanding before you speak.

It simplifies the internal calculations immensely to switch when this
is beneficial instead of slogging through complex mistake prone standard
calculations, or heuristic algorithms that try to mimic them.

>2.  Native iso coordinates are worthless for most game tasks.  This 
>isn't an argument against using them, of course, just an argument in 
>favor of keeping standard coordinates as standard.  As long as there's a 
>well-defined interface for conversions, everything should work out cleanly.

We agree, i.e. not only is this one of the 95% points, but it contains
nothing in the 5% class that can be focussed on :-).

>3.  Native iso coordinates do allow some game tasks, such as 
>whole_map_iterate, to be done more cleanly _and_ efficiently.  This can 
>also be achieved by index positions just as effectively, though.

No. They do not handle savegames or debug output well. They do not
deal with normalization or border computations. All these are 2-D,
while linear coordinates are just good for listing things efficiently.

You need to grasp some of these concepts a little better before making
statements like this.

>4.  Native coordinates for anything other than iso-rectangular and 
>flat-rectangular topologies have not been proposed, or even considered. 

These are part of the "global concept" that you threw out above. There 
is also discussion below of how to handle all wrapping cases, and the
rest are filter cases. This covers, your elliptical, hexagonal, "magic"
and others.

>  Is it possible for a "native coordinate" set meeting the above 
>specifications to be created for, say, a wrapping hexagonal map? 

To help you along. Wrapping hexagonal maps in 2-D still have the same
orthogonal wrapping axes as all wrapping topologies. The native set is
thus bounded by the wrapping dimensions (map.xsize,map.ysize) and the
coordinates are stored as in the article referenced previously. 
Standard coordinates won't be too useful though, as there are 6 and
not 8 directions with a lot of different local algorithms to fix up.

> What 
>about a flat-rectangular map that has unreal positions within the 
>regular set (for instance, an ellipse)?

Your ellipse example is unwrapped. So it is just bounded by a rectangular
(map.xsize,map.ysize) grid with a filter condition to determine realness.
The native and your regular coordinates would be the same (no need to 
rotate the axes unless the ellipse is also rotated).

>  What about in the general case? 

What about it. Since native coordinates can as a first approximation be 
taken as your regular bounding box, except one chosen to minimize the
number of unreal tiles by appropriate rotation of the coordinates axes
(to align with the true-iso rectangle wrap axes for instence), they
should be somewhat more flexible and general than your more limited
case that forces a standard to regular constraint.

>  If we introduce native iso coordinates and then have to fall back on 
>using a "native regular" bounding box for them, then we haven't gained much.

Except to eliminate all the inefficiencies from unreal tiles which I
know is the backwards way to think about this. Or the simplification
of all the wrapping operations, the savegame bloat, the debug print
understanability. I know this isn't much  ...

If you wrap, then the wrap dimension size determines the normal set to 
guarantee real coordinates appear only once in the native space. Once
you are guaranteed of this, filtering removes any unreal tiles within
these bounds. 

The "regular" part of regular native, is the real+unreal native space
that is left when you reduce to a unique normal set. The real subset
of this is what you actually call normal, but I am happy to leave this
regular set as normal, and just worry about real/unreal. The regular
set is what is defined in memory, printed out, put in save games, etc
with some positions marked as unreal.

You've done all this and we can build on it, but you don't really need 
to add any "regular" functions or odd flavours of tests, or inefficiencies
to do all this if you do it right.

normalize_map_pos() and is_real_tile() are all one needs. No is_normal
condition is required for instance.

The difference between your regular and native results from relaxing
the linkage to standard, and making sure that native has some global
concept like "real" or "normal" that is reflected in the topology
functions.

A standard-regular set is some random collection of points that have
little global significance. It is just a bounding box hack.

>5.  Native coordinates are not a necessity but a convenience. 
>Everything that has been discussed can be accomplished without them.  In 
>many cases, it can be done just as cleanly and efficiently using index 
>positions.

For listing or vector operations, yes. For 2-D operations no. Most
topology functions involve 2-D relationships. Generic filters are the 
big class that index coordinates are most useful for and we should 
probably use them for all of this. But filter algorithms are likely
still best done in native coordinates for special cases.

>6.  Finally, I see little reason why native coordinates can't be 
>introduced later (after several different topologies are working), and 
>used as necessary.

You mean do all the complicated general operations in regular or map 
coordinates, then figure out how to simplify them into native operations?

Why not just use native coordinates now for the things where they are 
useful?

You have split regular == map into two sets when you went to true iso
topologies. But a more efficient (rinse my mouth out) split for this
is standard and a (rotated regular == native).

normalize_map_pos() doesn't change if you do it in native coordinates
so what you need to add is a map_to_native() at the start and a 
native_to_map_pos() as you return to have a standard coordinate 
normalize_map_pos().

whole_map_iterate() doesn't change, except if this is iterating over
native coordinates and they are no longer synonymous with standard or
map then you need to add a native_to_map_pos() transformation.

Note, you could use an index_to_map_pos() and use the linear form of
whole_map_iterate() in the corecleanups.

In fact, if you only access normalized coordinates, then all elements
like map.tiles should be be stored in linear coordinates and you need
to do a map_to_index() transform everytime you access them. But wait,
this is what Freeciv does already, why did it need to convert to 
regular :-?. 

There is nothing magic about native, standard, regular, linear. They
are all just ways of looking at similar things. Some ways have useful
properties when doing some things, so one should take advantage of 
this. 

Regular as you have used it just doesn't take the best advantage of 
things that others do, and certainly a lot of the original standard
operations didn't take much advantage of anything in the iso case.
These are the places where things are changing.

>  Most of their uses are local, and so once issue #4 
>has been resolved it should just be a matter of introducing the 
>conversion functions and then using the native coordinates on a 
>case-by-case basis.

That is pretty much what I have done. I used native operations where
I figured out they made sense. There may be some places that I've
missed, of others where standard -> linear or some such can also be 
done the same way.

>  The only problem I can think of is that to make 
>savegames use native coordinates will require some 
>backwards-compatibility hacking.

None really. Native stores a rectangular map.xsize x map.ysize grid
which is (surprise) just what it stored in the old standard == native
cases. What is different is a topology index that tells savegame
how to relate this to map coordinates, which of course will default
to "1", but if set to "7" (MAP_TYPE_TORUS|MAP_TYPE_ISO) would be
a true isometric torus world. These coordinates are stored in linear
mode so that is the storage access transformation - same as it was.

Once you set the map topology parameter, all the <blort>_to_<blah>_pos()
functions do the right things, and any map coordinates stored in
unit structures or wherever can be related to the map, i.e. converted
when necessary. 

It might be nice one day to convert everything to native in a savegame, 
rather than just the global parts. This would mean you could save a 
game as an isometric world, hack the maptype in the savegame and read
it back in as a standard map. All the tile relationships would be
totally wacky, but everything would be in the right spots and it 
would probably play without trouble - sanity_checks of continental
integrity and such tile rearrangements excepted :-).

So as long as you carefully look at the savegame loops and coordinate
handling and recognize when you are working in one form and need to 
convert it at some point to internal map coordinates or back, it all
just works. It is done, so you can probably figure it out faster by
looking at the examples.

>For me, point #4 is the overriding concern.  While Gaute and Ross have 
>proposed systems to hack in the 8 "standard" topologies (Ross's recent 
>corecleanups have taken a somewhat more general approach), most of my 
>changes have been geared toward first separating all topology code. 
>This then allows any topology within a rather loose set of restrictions.

These are the "critical" or must do cases. And fixing up isometric is
I think probably the most important part.

I think that in doing this we have figured out a lot of the complexity
and experimentally verified the resulting changes. 

Your separation work keeps us honest, and is very useful in pinpointing
the interfaces and structure that local fixing misses. 

The combination of topdown and bottom up can result in more rapid change
and correct change after the initial stages of either are petering out.
So doing things in parallel or differently is not bad.

The trick is to be able to merge and join the two when the time comes.

>> 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.
>
>Yes.
>
>
>> 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.
>
>Topology operations certainly.
>
>For game operations, it depends on what you mean by "global". 
>whole_map_iterate could certainly benefit from using native or index 
>positions, but I'd call this local rather than global.

Global is iterating over the whole map. Local is map_stepping to 
adjacent tiles.

Global parameters are border and wrap dimensions, local are directional
tile relationships and distance computations.

I'm trying to ignore the fact that one of us obviously has ancestors
from down-under or something that has a real effect on perspective.

>> 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 :-).
>
>Well, my interpretation is like this:
>
>* native: whatever system is most convenient for the current topology
>* iso: a native iso-rectangular system
>* flat: the opposite of iso, i.e. a native flat-rectangular system
>* standard / game / map: whatever the game uses as its main coordinate 
>system.  I much prefer "map" to game or standard, since that's what all 
>the functions call it.
>* index: a single integer identifier in the range [0..n].  This is much 
>easier to implement if we allow values within this range to be invalid, 
>i.e. not identified with a unique map position.

I will resist quibbling here ... basically we agree.

>I'm willing to give up flat in favor of map, but not in favor of 
>standard or game.  Currently flat == map == native.  In the foreseeable 
>future we will have map == flat, but this will not necessarily always be 
>the case.

map is the internal standard game coordinates, I'm fine with that.

It should be described as the "standard" that all others need to be
able to convert to and from, but we don't need to label it "standard".

This means we have native iso and native map coordinates as the two
core coordinates systems used in most global operations. They have
4 wrapping flavours each to give 8 topologically distinct maps. The
GUI has two views, isometric and (map) to give 16 unique ways to play
the game.

>> 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. 
>
>While we're on the topic, just to rehash:
>
>- normal: a representative set chosen by us.  It has no significance 
>other than what we give it, but using it makes calculations and 
>debugging much easier.

Normal has some concept of uniqueness associated with the set. There
are never two equivalent positions in a normal set.

>- real.  Duh.

Let me help. Real coordinates are the necessary part of the game. 
Unreal coordinates are an unrecoverable error condition, except to 
void_tile adherents.

>- regular: a convenient bounding box for the normal set.
>
>Currently we talk about "normal map positions" and "regular map 
>positions", but if we introduce native positions and can't figure out 
>how to work different topologies we may end up with regular native 
>positions, and that would IMO suck.

I think (regular == normal) in native coordinates if you are willing
to relax the realness constraint on normal to include filtered unreal
positions. Thus linear coordinates are also always normal even when
they have extra positions to make calculation easier.

The only important condition for map coordinates is realness. It is
the native/regular/index ones that need something like normal to 
make storage and the like work.

>> For standard maps, standard and regular coordinates are equivalent.
>> For a 100 x 2 isometric map, this would be a 102 x 102 square. 
>
>Yep.  Anyone who wants to use a 100x2 isometric map is doomed to a 98% 
>waste of memory if we use regular positions for storing map data.  This 
>was deemed acceptable (Tony, Raimar, and I all agreed IIRC), mostly 
>because nobody would play with a 100x2 map.

Except those that are trying to argue candycaning is necessary :-)

>> 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%).
>
>Yes.  This leads to an inefficient loop, although in most/all cases it 
>will be unnoticable..

All these unnoticeables, especially when they are all in the same
direction, do add up you know :-)

>> 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).
>
>So?  Just skip those positions.  The fact that they're equivalent is 
>only a problem if you insist on calling normalize_map_pos instead of 
>is_normal_map_pos, which unfortunately you (Ross) do.

Actually, it is the number of times that I FAIL and just spend CPU cycles
spinning that bothers me when I do this.

>> 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.
>
>That's a gross exageration.  It will result in a 5200% increase in the 
>map part of the savegame size.  In a savegame I just looked at, the map 
>data accounted for 12% of the savegame.  So we'd end up with a 
>52*12/100=500% increase in savegame size in this pathological case.  In 
>the median case it will account for about a 15% increase.

In a Savegame of ~4200 lines, ~700 are the initial map, and all but
100 of 500 for each of the 7 players are map-sized objects. These lines
are always 80 columns or better while the residual is typically 20 
characters or less.

So, 16% + 80% * 84% ~= 83% of the save game is of map-sized data in lines
not even data units.

I think you underestimate the effect this is going to have on Renier and
Paul's server hardware budget.

>> 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. 
>
>It is certainly always possible to choose a regular system.  A native 
>system has more restrictions and may not always be possible.

I laugh ... native has more restrictions :-).

At its worst, native == regular. 

It must be my backwards English, and genetic heritage again.

>> 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.
>
>As I understand native coordinates, they have normal==regular.  How can 
>this be guaranteed for unusual topologies?

Good ... (normal == regular) == agreement

It is explained above. 

For 2-D wrapping topologies which have many equivalent positions, 
but two orthogonal rectangular wrap axes with given wrap dimensions, it 
is the rectangle formed by these dimensions. If you have no wrapping it 
is the smallest bounding box that encloses all the points (note that not 
being restricted to alignment with map coordinates means you can often 
find a rotated rectangle that is smaller than your regular case). This 
set guarantees that no two positions in it are ever equivalent, unless 
you are doing really funky warp space stuff (if so it will probably need 
to be special cased up the ying-yang anyway). On top of this set you can
apply shape filters to produce ellipses, etc.

I tend to think of the unique set as a normal set, and the real coordinates
as those that are both normal and survive filtering.

For me realness is the condition that guarantees game utility, and 
normalcy the one that allows utility for topology, storage, etc. or
conversely avoids assert hazards.

>> 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. 
>
>A hexagon does not have orthogonal axes.  A hexagon would be a good 
>shape to play on.

Well it depends on what axes you want to grind, but a 2-D hexagonal world 
has wrapping axes that are. And symmetry operations in these two axial
directions.

For the purposes of doing a Torus world in hex coordinates, you would
choose the appropriate axes, rather than some inappropriate ones.

>If we limit ourselves to axes of wrapping (which both general-topologies 
>and corecleanups do, unfortunately, since otherwise we must normalize 
>vectors just like we normalize map positions), then I can think of only 
>two shapes that will be playable: a rectangle and a hexagon.  With these 
>two shapes we can do any one of (1) rotate them to make iso or some 
>other form; (2) take a subset of them, i.e. make certain positions 
>within them unreal; (3) have them wrap in any valid set of the available 
>directions.

You can play quite usefully on a number of flat-earth (unwrapped) maps
of arbitrary shape using filtering techniques.

You can use rectangular wrapping with square, iso and hexagonal tilesets
without too much pain on rectangular maps, there are two flavours of
hex, one with E-W and one with N-S primary axis, while the secondary 
axis alternately bisects one and separates two tiles.

I don't think there is any useful non-rectangular wrapping shape in 2-D.

It might be interesting to see what you could do by limiting oneself to
a local representation of a hexagonal tiled spherical surface. As one
moves out the 2-D projection gets to be a bit funky, but locally one
would probably be fine.

If one thinks of this as two hemispherical/hexagon grids touching at the
equator or day/night halves it is probably conceivable without requiring
too much therapy. It would be a strain to think about how a centered
view would move tiles around as you stepped along, but it probably
peels off an edge in one of the six directions of motion and adds it
to the otherside of the hexagon across the axis orthogonal to the motion.

Native coordinates would of course be the rectangle bounding two joined
hexagons with a filter to cut out the non-real positions.

There are an infinity of Great Circles or wrapping coordinates on a 
sphere, but this is probably limited to the number of hexagons around
the equatorial edge with some interesting paths being traced in the 
process. Wrapping operations would be interesting.

>> 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.
>
>Nit: regular isn't a different coordinate system; i.e. opposing native 
>or standard, it's just a different classification of a position.

Nit on nit ... it really is, but it is heavily constrained so it isn't
really that obvious.

>  The 
>only thing bad about it is that it typically leads to an inefficiency in 
>storage and execution.  For an iso-rectangular map this would be about 
>60%, for a flat-hexagonal map it would be about 30%.  The advantage is 
>that it required minimal changes from the current code to implement; we 
>just fixed certain constructs that thought they were operating on normal 
>positions to instead be operating on regular coordinates.

There aren't a lot of changes for either system. Native has close to
zero conceptual change in the basic global elements, and only requires
inserting transformations when you switch coordinates from global to local 
operations. This is equivalent to looking for places to linearize array
lookups using map_inx() - not rocket science.

>> 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.
>
>Yes.  The changes from normal->regular are already in CVS, and what 
>remains is just the tough changes: mapgen, GUI, communication, internals.

To bad you couldn't have finished the topology work, then switched things
to regular coordinates as you suggested above for native, and which in
fact is pretty much the way the corecleanups went except for the last
push.

That would mean less of the useless grunge would need to be removed from 
CVS now, or the corecleanups when I had to tidy them up.

>> There are considerable performance and general game flow differences 
>> between the two because of slightly different ways of traversing the 
>> global coordinate space.
>
>Optimizations aside, I seriously doubt there is a considerable 
>performance in the general case.  This is difficult to measure because 
>of all the optimizations, of course.

Yup, when it is not going to improve efficiency there is no need for
numbers or serious analysis. I'm sure the spin loops are almost noise
even at 2% hit rates :-).

>And from what I've seen, there is very little game flow difference.  All 
>of the changes corecleanups introduces with native coordinates are 
>localized; i.e. one section of code converting to native coordinates, 
>doing some work, and (if necessary) converting back.

Except for the global loop order though.

[...]
>>>It is certainly unsafe in my implementation of general-topologies.
>>>
>> 
>> That might be a thought on which to ponder ...
>
>It should go without saying that until native coordinates are 
>implemented they should not be used.  This is true of both 
>general-topologies and of current CVS.

And Raimar always says that until used, they cannot be implemented.

How did regular slip through this catch-22 situation to foul up CVS 
so badly :-)

>General-topologies is also 70k instead of 800k, and consequently has a 
>good (well, better) chance of being realized in the foreseeable future. 

Corecleanups has a lot of stuff besides topology. It has also been
diverging from a lot of the ongoing experimentation hacks.

If we remove the ?? K of regular changes from the topology diffs of
the corecleanup stuff you might be surprised to see what the ratios
are.

But corecleanups was touted as a mega-patch when it was the current
size of general-topologies. 

>  I have taken the opposite approach from that of corecleanups; i.e. 
>making the minimum number of changes necessary to implement a more 
>general system.  My opinion is that once the more general system is in 
>place, it will be much easier to justify optimizations like native 
>and/or index positions to make calculations easier.  This is why I have 
>implemented neither of them, although at least index positions are 
>necessary to make the code cleaner and more efficient.
>
>jason

Once it is in place there will be a lot of breakage and an incredibly
unwieldy system to ever unscramble. The effort required to do core
cleanups of similar grunge tells me this is not a good way to go. This 
usually happens with piecemeal development and no concern for global 
concepts, and no opportunity for real review of what is being done
or where it is leading.

But I agree, it will open the door to lots of fixup patching :-).

Cheers,
RossW
=====