[Freeciv-Dev] Re: (PR#3936) introducing native coordinates

[Ross Wetmore <rwetmore@xxxxxxxxxxxx>]

Jason Dorje Short wrote:
> Ross Wetmore wrote:
> > Raimar Falke wrote:
[...]
> Really, at this point we don't decide what square_iterate should do - we 
> accomodate square_iterate for what its users do.  All of its users want 
> square_map_iterate.
You are correct that we need to map the flavour required by the current
code for each case of square_iterate or any other macro that may be
ambiguous.

Most of them *do* want a local flavour, yes. I'm not sure all do.
Certainly the generalization to block_iterate with square_iterate as
a special case is a use in a global sense.

Thus there are going to be two flavours. Just highlighting this as a
means to sensitize everyone to the sorts of things that arise in
choosing whether the current code remains standard or goes native
when the conceptual distinction is made.

> > But if you want a block_iterate for dealing with rectangles oriented
> > along the natural map axes as in defining the polar regions of the
> > map, or something that iterated over a region of constant radius with
> > efficient wrapping across map edges, you would do it in native 
> > coordinates
> > and probably call it (block/square)_native_iterate().
> Hmm, here we get into deeper concepts and run into problems...
>
> This is a point I've always been confused on.  Why does your 
> block_iterate orient itself natively?  Shouldn't it be 
> native_block_iterate or some such? 
First, whether it is block_iterate or block_native_iterate is just
a naming choice and a separate issue. We aren't talking about any
difference in implementation.

> Isn't a native block a basically 
> useless concept?  I can (vaguely) imagine a use for a 
> natural_block_iterate, this has _some_ local use. 
One has no need for natural coordinates except in a proper display, i.e.
perhaps as a gui coordinate. They don't have good properties in the
general case for most other uses.

One iterates in native cooordinates because the iteration is simple, no
need to know about skipping unreal grid points, or specialized offsets
of every odd row or any of the complexities that might be specific to
one form of natural coordinates over another.

The conversion to map or indexed doesn't care whether you start with
native or natural. Any local operations, argument passing or data
references are done using converted values.

To drill it in ... use the coordinate system that best suits the purpose
at hand. Native is designed to be topologically neutral, efficient and
suited for global needs. Natural is neither of the first two and thus not
suitable for a block_iterate.

> But when (outside of 
> global operations which should use whole_map_iterate) would one ever use 
> a native_block_iterate?
It is generally a poor choice to iterate over a large set selecting a
small number of elements as when updating the polar regions. One should
always replace such runtime inefficient patterns with a little thought
at design and coding time, i.e. with a block_iterate macro instead of
whole_map_iterate and if-clause.

> > The important thing to remember is that many operations are muddled
> > in the current code which was never written to deal with general
> > topologies, just a simple rectangular map window where the same
> > coordinates are the right ones for multiple contexts.
> This is, by definition, going to be true.  Up until now native, natural, 
> and map coordinates are all the same.  With iso-maps we introduce 
> (separate) native coordinates.  Of course most users won't have thought 
> about which coordinate system they are using!
One correction, native coordinates are not introduced just for iso-maps.
They will be used for standard maps and any future topology as well.

Native vs map is a real conceptual split. The fact that the conversion
between native and map coordinates for current CVS is an identity
transformation does not mean one is not going to use native coordinates
for native operations on the currently support topology. There will be
no switches or special case code. All code will run any (supported)
topology and will now be distinguished by the concept it implements.

> If we later refine/redefine the coordinate systems, we will find
> ourselves in a similar situation.

Because it is a real split based on a real concept, there is no need to
redefine the coordinate system unless the concept changes and local vs
global is not really subject to a lot of change.

Note, local coordinates or at least local operations involving them may
be enhanced for cases like hexagonal (vs the current octagonal) adjacency
relationships. I can't envisage a coordinate system that does fundamentally
depend on the standard map grid though. If this happens *all* of the basic
Freeciv mechanics will need to be rewritten from scratch, or so I suspect.

Similarly, every new topology that is added will have its defined form of
native coordinates and conversion functions to and from map coordinates.
Native coordinates for each topology will be rectangular, aligned with the
natural axes and have the same 2-D wrap directions. Thus there should be no
change to any existing code using native coordinates when they are added
since they will by definition use the generalized native system.

> > But even true isometric which changes the orientation of the natural
> > map axes to be pi/4 rotated wrt the internal standard map ones starts
> > to break down some of these symmetries and thus requires you to think
> > about the real context in each case. map_view complexities with all
> > kinds of ugly special case code are the result of doing things in one
> > coordinate system which happens to be the wrong one in half the cases.
> > Note, *only* map_view is ugly now because the current code does not
> > handle true isometric maps, and only provides an iso view of a
> > standard rectngular map.
> Hmm, upon further review I think mapview issues are more complicated 
> because they deal with both local and global concepts.  Thus neither map 
> (local) nor native (global) concepts will entirely satisfy them.
Actually, mapview does not deal with *any* native/global concepts except
for the overview map. It primarily deals with GUI window coordinates and
the map values that correspond to them. It is a flaw in the current
mapview that it tries to do everything in map coordinates.

Note there will be iso_gui as well as standard_gui coordinates for the
windows to reflect the fact that one is drawing square (standard) or
diamond (iso) tile shapes at appropriate positions.

> > In most spots updates to generalize the core code involve trivial code
> > changes.
> Yes, so long as we choose an appropriate coordinate system.
>
> > What native does is provide an easy context for the global operations,
> > while internal map coordinates deal with local ones. Most of the inner
> > code is of the local variety so most of this code is never touched. The
> > outer loops often contain a global iteration, and thus you loop in
> > native coordinates and provide a conversion at the top of the loop
> > to map coordinates. Since the global loop in the current code is
> > equivalent to native for its limited topologies, the actual code
> > doesn't change except to rename the loop variables and provide the
> > conversion line. Once you have done this, you have genralized the
> > core and all topologies just work.
> This passage is very good.  It may take upon new meaning after 
> considering the mapview situation (see above).
I hope not ... the GUI cleanup (and for each display topology) needs to
invent its own gui window coordinates and rewrite a lot of code that
currently uses map coordinates to use them. Since iso-GUI is for display,
I suspect these will look more like natural coordiantes than native,
though it may still be reasonable to fill a GUI by doing an iteration in a
gui-native flavour with conversion to gui-natural or map as desired.

But note, gui-native is not equivalent to native. The topology of a gui
window is not the same as a native map, and thus gui-native operations
will not be the same as native ones. The simplest example is that
gui window coordinates are always clipped at the window edges, while
native ones may wrap in two directions in some map topologies.

[...]
> The thing is, most pieces of code don't do *anything* with the 
> coordinates - they just pass them off from one operation to another.  So 
> the question is, what coordinate system should the interfaces for all 
> functions use?  Raimar is (I think) suggesting that they should use 
> native coordinates, and convert to map coordinates when necessary.  But 
> our implementation (which involves fewer changes, but may not 
> necessarily be "better") is that they use map coordinates.
> My only answer is that we should use map coordinates for now, since they 
> are much easier - we may consider switching later.
Most of the codebase deals with local operations, and thus most of the
code will use map coordinates. Global coordinates are typically only
used in specialized cases or in the outer iteration loops.

Thus most of the functions will take map coordinates.

It makes sense to define a coordinate conversion to a single common
standard coordinate, rather than between all possible coordinate systems
as this is an O(n) vs O(n^2) set of conversion functions and at most
O(2n) operation from one to any other.

Using standard map coordinates as the universal coordinates stored in
savegames, sent over the wire etc. thus makes sense both for real and
backwards compatibility reasons.

But again I repeat, the one-size-fits-all is an anti-pattern. One should
certainly feel free to pass gui coordinates amongst gui functions or
native coordinates amongst native functions. The interface of the function
should define what it takes and that should be based on real needs and not
some religious edict.

> > [...]
> >
> > > Also I think that in my idea I want to make your native coordinates
> > > the "normal" "map" coordinates.
> "map coordinates" is the name Ross and I have used for the tile-oriented 
> coordinate system.  The coordinates that are 
> stored/passed-around-between-functions I would call "standard coordinates".
Note, map coordinates have nothing to do with tile orientation, or tiles
per se so this comment may be confusing. Tile orientation is a gui display
concept and tiles are accessed in memory by indexed coordinates.

map/standard/internal coordinates are largely synonymous to me. In the code
they are prefixed with "map", and are the common form of rectangular grid
used everywhere today in the internal or core code. This is the internal
playing map on which the logic of the game takes place and the common form
to which all others should have conversion functions.

Standard is a bit of a general/overloaded term. I tend to use standard as
an adjective or qualifier, as when I want to refer to the "standard map",
i.e. the current earth map as displayed by the trident tileset. A true-iso
standard map, or earth-map as displayed naturally in the isometric tileset
would actually be a rotated and shifted rectangle of points in map
coordinates.

> jason
Cheers,
RossW
=====