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

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

At 08:38 PM 01/10/28 -0500, Jason Dorje Short wrote:
>"Ross W. Wetmore" wrote:
>So, I think you may be right that such naming is needed - either than or
>my functions must be renamed.

Probably both.

>> "Regular" positions are characteristic of the particular set N(0,0).
>> Condition (2) is only applicable to the "regular" set unless you build
>> normalize_map_pos() into the implementation of these functions which I
>> assume you don't want to do.
>
>Regular positions are those within (0..map.xsize) x (0..map.ysize). 
>N(0, 0) is closely related to this because map.xsize and map.ysize are
>defined by N(0, 0).

I'm getting a sense that regular positions are what you are using to 
describe a bounding rectangle that encloses N(0.0). If this is the case
then state this unambiguosuly, and don't confuse them with normal.

This means you need to do a normalize_map_pos() check on regular positions
before you can use them for things like map access, since some regular
positions will be unreal in cases like iso.

And note, regular in most of this discussion is being used synonymously
with N(0,0), or least belonging to the canonical set that one associates
with N(0,0) in some other coordinate set. Regular here is thus always real.
This concept is perhaps more useful and needs a definition if you define
regular as the bounding rectangle.

>Note, though, that the N(-1, 0) naming doesn't tell you everything.  For
>instance, the function
>
>  normalize_map_pos_rect(&x, &y, x0, y0, width, height);
>
>wraps (x, y) into the specified region.  However, the specified region
>itself doesn't have anything to do with a particular set of class
>representatives (a particular N).  Some positions may have no class
>representative in this region, others may have multiple
>representatives.  In the latter case, the function must be sure to
>always give the same representative no matter which original member of
>the class it is given.  (The function might better be called
>wrap_map_pos_rect, but we've already decided we don't like that name
>:-).)

This function is a mishmosh of several different concepts and operations
that need to be separated and handled in different layers. As it stands
it will cause more pain and grief than benefit. Normalizing map_pos is
one part, but I think it is actually unnormalizing it to a canonical set
that has x0,y0 as origin. Clipping to gui windows is another. And the 
fact that you needed to convert the gui window positions to a map_pos to 
do this should tell you that this is probably not the right spot.

Note, if instead of doing a purely GUI window object operation like this
clip, you were actually implementing a topology specific operation like
apllying a filter which clipped to an ellipical canonical set this might 
be a reasonable map_pos operation. Just don't mix map and GUI operations 
in the same breath.

>To put it another way, N(0, 0) for isometric maps won't even include the
>position (0, 0).  It is therefore a bit of a misnomer.

Ok, but it still needs the concept of the 0'th or first set in some
natural indexing scheme, and it still needs to guarantee that the 
coordinates are in the first positive range to reflect the way in
which they are stored/accesssed :-).

>> To play a little naming game to unscramble past confusion in usage. It
might
>> be easier to use some term like "canonical" in place of "normal" above, and
>> reserve "normal" for the specific "regular" case of canonical.
>
>Hmmm.  I'd rather do it the other way, that is use Gaute's term
>"canonical" or "proper" to mean lying within N(0, 0) and use "normal"
>and "normalize" to refer to whatever particular set you're talking about
>at the time.  This seems more in line with mathematical definitions.
>
>Gaute?

But this is not the current concept that normalized has in the code, 
and therefore means a massive risky and error prone cosmetic rename.

I can accept canonical as defining a more generalized representation, 
i.e. a single valued set of which there can be more than one. I think 
normalized readily conveys the more specific case of canonical.

So on both the practical and conceptual levels, this "renaming" does
not seem to achieve anything except to add confusion.

>> The function normalize_map_pos() is then one which (as it currently does)
>> maps coordinates into their "normal" or "regular" set, or returns a FALSE
>> condition to say that no such element exists (i.e. was an unreal position).
>
>Yes (except that I'd switch the names).

I don't understand the desire to rewrite the language of Freeciv when it
currently is quite well defined and implemented consistently with the 
definitions. This process is really make work - it will make a lot of 
work in cleaning up mistakes and future coding erros :-).

>> >- Any position that is not real might as well be considered the equivalent
>> >of every other unreal position.  No assumptions about unreal positions
>> should
>> >be made.  "Wrapping" is not well-defined for unreal coordinates; there are
>> >several conflicting methods for handling it.
>> 
>> There is no valid reason to ever do so. Any code which appears to require
>> this has a programming error, or is abusing the wrapping concept for some
>> specialized reason and should clearly comment this reason.
>
>The reason we'd want to wrap unreal coordinates is so that we can wrap
>vectors (like you tried to do in map_to_city_map).  It is better to
>avoid this.  Aside from that, I agree with you.

Two mistakes you keep making in this broken record refrain ...

Ok, let's be careful to restrict this to the "unnormalizing" operation
that requires you "unwrap" an N(0,0) case to convert it to a canonical
set that has some arbitrary point as its origin. It is a reverse operation
to the normalizing wrap in such things as map_to_city_map, and is used
or valid only when the starting map coordinates are real.

This never does anything to unreal coordinates. You can legitimately 
apply neither wrapping nor unwrapping operations to unreal positions
which is why you always need to be assured the coordinates are real
before you do this or the result is indeterminate/useless. It may in
fact do real damage like change the realness characteristic of the
position.

>Yes.  This isn't quite the same thing, though, since nearest_real_pos is
>pretty well-defined, whereas actually wrapping an unreal position has no
>meaning whatsoever.

So we should really consign this to the dustbin and never try to build
meaningless concepts or code into Freeciv, right?

>> [...]
>> >*** 1c.  Current Operator Functions
>> >
>> >The following functions are necessary to do operations and checks on map
>> >positions.  All should work under the arbitrary topology discussed
>> >above.
>> 
>> It is worth stressing that these are functions that apply to "map"
positions
>> or gaming coordinates.
>> 
>> It is in general meaningless to feed them arbitrary coordinates, GUI or
>> citymap coordinates for instance. There may be corresponding functions
>> which do take GUI or citymap coordinates, and in the simple case where
>> all are rectangular coordinates related by simple translations, they may
>> in fact have similar implementations.
>> 
>> *** IMPORTANT *** SIMILAR IMPLEMENTATION DOES NOT MEAN SAME CONCEPT
>
>Yes, exactly.  However, I think these corresponding functions will have
>to call a topological function to do their dirty work, since both GUI
>and city positions are ingrained within the game map.
>
>So, in fact, they are very different concepts and perhaps should be
>named accordingly.

Just to push what you said a little further. I don't think GUI/citymap
functions should call topological functions directly. The GUI/citymap
coordinates need to be converted to gaming/map coordinates where the
topological characteristics are well defined and call the appropriate
map topological functions. This keeps things straight and code in one
localized spot where it makes sense.

In general this is a one-way layer traversal, as in accessing tile data
from a position in a GUI window. The GUI window position is converted to
some canonical map_pos which may then need to be topologically normalized 
to access the memory where the tile data is stored.

>> [...]>*** 1d.  Future Operator Functions
>> >
>> >The following functions will most likely also be necessary for
manipulating
>> >map positions.  This list may not be complete.
>> >
>> >- regular_map_pos_is_normal(x, y) gives an equivalent return value to
>> >is_normal_map_pos, but assumes that (x, y) is regular.  This makes the
>> >calculation much faster.
>> 
>> This can be dropped if you cleanup the definitions above.
>
>It's not a definition thing; it's included for efficiency.  The reason
>is that for the current topology it evaluates to "1", which is pretty
>good for efficiency purposes :-).  Aside from that, it's the same as
>is_normal_map_pos.  (Using current definitions.)

I am starting to understand "regular", but you need to clarify the two
concepts that are currently associated with this. This is the bounding
rectangle one.

I don't think there is any reason to have "regular_map_pos_is_normal"
other than to hardcode a special is_real_map_pos() check for realness in
cases where you can optimize the check.

If you want to use the positions, normalize_map_pos() should correctly
deal with the operations, and presumably you could provide an optimized
version here too if you aren't coding normalize_map_pos to correctly do
the efficient things.

But the completely different name from these current versions makes
things a lot more difficult to keep straight. Some sort of convention
other than the longest self defining phrase should be applied to 
maintain recognizable relationships and consistency in the sets of 
related functions.

>> (width, height) for wrapping are again too topology specific 
>
>It is shape-specific but not topology-specific. 

Width and height are meaningless for a topology represented by polar 
coordinates. This is enough of an example to show that they are bad
names. Use dx,dy or du,dv if you think x,y is too closely associated
with rectangular coordinates. 

>> >- normalize_map_pos_iso(&x, &y, x0, y0, width, ywidth) wraps position
(x, y)
>> >to be within the isometric rectangle defined by (x0, y0, width,
height).  The
>> >definition is incomplete, but should match normalize_map_pos_rect.  A
better
>> >name would be good.
>> 
>> I would definitely wait until you had a consistent way/prototype for
>> handling iso before coming up with such things.
>
>This has nothing to do with isometric maps and everything to do with
>isometric views.
>
>Using this function I have implemented a topology-independent
>isometric-view GUI.  It's pretty sweet.

If this is a pure GUI function that does not deal with maps, then the
map_pos in the name is a mistake, and the coordinates which are passed
in that I believe are map_pos coordinates seem to refute your claims.

Really this is a very confusing mishmosh functions that needs to be
split up and handled in a clean layered way.

>distance_from_pole is map-specific, not just topology-specific so could
>be a part of mapgen except that this would mean all current generators
>would break.
>
>distance_from_edge has nothing to do with the map, it's entirely
>topology-related.

These two statements are clearly so inextricably intertwined with the
standard wrap_x world definitions that it should be clear they contribute
no generic value and are patently contradictory. Just leave the current 
code alone to deal with things in coordinates it understands rather 
than converting to something even you don't understand :-).

>GUI code will require normalize_map_pos_iso or normalize_map_pos_rect
>(or whatever they end up being called).  These functions are ugly but
>necessary.  They make the GUI conversions (map pos<->canvas pos) very
>simple.

No, they make it horribly confused and filled with ad hoc-ery.

Simple is to keep the GUI and map stuff in separate layers, and thus you 
can plug different map layers underneath the GUI without needing to 
change it. One GUI clipping window routine can handle all topologies
if you don't first have to convert to map coordinates to do the clip.

>> Change "normal"/"canonical" as appropriate to resolve the confusion and
>> implementation backwards compatibility issues.
>
>Yes, but we must decide on the naming.  Current code uses your naming
>system, but mine (Gaute's) is more "correct".

Correct is what is consistent, well-defined and implemented with 
backwards compatibility always holding the deciding vote, i.e. practical 
considerations.

Subjective interpretation wars should have nothing to do with this. And
certainly not this discreditted venture into the sublimely subjective.

>> Map_generators are trivial to add and make life much simpler.
>
>I very strongly disagree; since it's trivial to make the current map
>generators topology-independent I see no reason not to do so.  If new
>mapgen code needs features that are not general, a new generator can
>easily be made and these restrictions imposed.

Imposing restrictions on the way the current generators build existing
topology maps should be the first signal that this is bad.

Overgeneralization and extensive changes to do this are the WRONG way
to go here. 

Do your experiments with new a new generator, and leave the current
ones alone.

No one is stopping you from pursuing your own wrong-headed ideas, just
don't try to force them on others.

>> Ignoring any implementation restrictions imposed by the limitation to
>> the _rect and _iso functions, this is essentially correct.
>> 
>> Another way to model this is through a strictly ordered layering ...
>> 
>>   various GUI (drawing) primitives
>>     *** use ***
>>   normal_GUI_pos             - gui pos clipped to the current window object
>>   GUI_pos                    - rectangular (x,y), window origin (no wrap
sets)
>>   <-map_to_gui_pos->         - game/map to gui coordinate transformation
>>   map_view_filter            - topology specific filters, e.g. ellipse
cutout
>>   canonical_map_pos          - map pos in a translated set, e.g. gui
origin,
>>   normal_map_pos             - map pos in "normal"/"regular" form
>>     *** refers to ***
>>   game memory storage
>> 
>> One, does normalize or translation/transformation operations to move from
>> one form to its adjacent level form.
>
>This is the same model, you've just put "gui" functions in front of the
>normalize_map_pos_[rect|iso] calls.  The exact same backend code will be
>necessary.

No, the ordering is actually a really important part and the fact that
GUI functions work only on GUI coordinates means they work with any
topology or underlying map_pos implementation. The glue layer between
the two is the (easily parameterizable) transformation step.

The difference is the same as between a sum of squares and square of
sums. If you do the operation in separate serial fashion, then all the
messy cross product elements go away.

>A different model could use diff_map_pos instead of the other two calls,
>but this would make things uglier for the frontend.  I'll give this some
>more thought.

Ok. 

Think about it from the clean identification and separation of function.

>> A similar layering can be done for citymap/map, noting that many operations
>> here are identity operations, so are usually not explicitly coded.
>> 
>>   various citymap primitives
>>     *** use ***
>>   citymap_filtered_pos       - is_valid_citymap_pos() conditions
>>   normal_citymap_pos         - citymap pos clipped to CITYMAP_SIZE object
>>   citymap_pos                - rectangular (x,y), citymap origin (no wrap
>> sets)
>>                                Note: the above three are usually combined
>>   <-map_to_citymap_pos->     - game/map to citymap coordinate
transformation
>>                                Note: this is currently an identity
transform
>>   canonical_map_pos          - map pos in translated set, e.g. citymap
origin,
>>                                Note: this specific translation is usually
>>                                      imbedded in the transform step above
>>   normal_map_pos             - map pos in "normal"/"regular" form
>>     *** refers to ***
>>   game memory storage
>
>citymap<->map is much easier because the citymap is currently of fixed
>size.  diff_map_pos alone will work quite well here.

(Sigh) the whole purpose of this is to show that a clean well organized
approach makes things very simple at the conceptual layer and tells
you just what individual steps need to be done.

Any optimized flavour should still reflect this model and clearly 
document the optimizing elements and assumptions.

Ad hoc implementations that use radically different ways to do things
is the basic daemon that the last several months of corecleanups has
been trying to eradicate.

Don't backslide here where it actually is fundamental to get a generic
solution right.

>> [...]
>> >****** Part 2: Specific Topologies ******
>> >
>> >*** 2a.  Data Structures
[...]
>> Consolidating current map paramters to refer to the corresponding
>> topology structure elements is nirvana (e.g. via global rename like:
>> #define map.xsize = map.topo.xsize
>> which really should be a field rename mp_xsize = mp_topo.xsize if the
>> map structure were properly defined to have unique field names).
>
>xsize/ysize is a map issue, not a topology issue as I see it.  So I'd
>have
>
>struct civ_map {
>  int xsize, ysize;
>  struct civ_topology {
>    int shape;
>    int isometric;
>    int horiz_wrap, vert_wrap;
>    int width, height;
>  } topology;
>  ...
>}

You are right. xsize, ysize is an instance variable that needs to be
recorded in the savegame. Whereas the topology structure should contain 
only static values applicable to all instances.

I think that width, height in the above are bad for these reasons and
duplicate the information content in xsize,ysize. 

But maybe you have an explanation why there are so many confusing 
elements in it.

>> ns and ew are bad name choices, stick with x,y or some generic coordinate
>> flavour so you don't have problems when the wrap is in a polar coordinate
>> like theta (wrap_x and wrap_y).
>> 
>> Same for height and width (size_x, size_y).
>
>You're right that ns and ew imply orderings that aren't necessary there,
>but calling these directions x and y is downright wrong.  I chose
>"width" and "height" because it does not imply any particular
>directions.  For the wrapping I'd use vert_wrap and horiz_wrap.
[...]
>What else can they be called?  Width and height is as general as I can
>think of.  size_x and size_y is wrong.  size_h and size_v could be used,
>but aren't really any different.

Still wrong ... you are hooked on a rectangular topology and really
can't shake it.

Use u,v as general coordinates, and du,dv, size_u,size_v as offsets or 
ranges or something similar.

>> Note: the only new parameter needed is map_type, which should be thought
>>       of as an index into a static type array that understands the finer
>>       elements that don't need to be recorded in every savegame file.
>
>Doing it this way is much easier IMO.  You can think of map_type as an
>integer index, but I'd much rather represent it as a struct - it makes
>for far greater code readability.

BTW: I think you can combine shape, isometric, and the wrapping flags
into a single map_type index with macros/functions to return the
quantities in the struct. But the underlying implementation is not
that critical as long as one thinks of these elements as a single
object, and not a collection of unrelated characteristics. For example
all you need to save/load in savegames is the index this way. And
underlying code implementations can switch on this index.

>jason

Cheers,
RossW
=====