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

[Jason Dorje Short <vze2zq63@xxxxxxxxxxx>]

"Ross W. Wetmore" wrote:
> 
> 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.

Yes.  My preferred naming would be:

"normal": real and lying within a region that we choose

"proper": lying within the unique chosen set of class representatives
(what you call N(0, 0)).

This is really the only correct use of the word "proper", although if
you want to have "normal" mean the unique set than we can come up with
another name for the varying sets.

> >> "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.

That definition is correct: the bounding rectangle of the canonical set
of coordinate class representatives.  By convention, this rectangle is
(0..map.xsize-1)x(0..map.ysize-1), with map.xsize and map.ysize chosen
appropriately.

Regular is not being confused with normal, except in the code (at least,
I don't think it has been...).  I think you may have been confusing
them, though, since you were arguing a check for normalcy was not needed
in whole_map_iterate and elsewhere.

> 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.

Yes.  This is what the changes in savegame.c did and what the
map_iterate patch does.

> 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.

Regular is most certainly not always real.  This is one of the problems
the current code has.

> >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.

Just like normalize_map_pos, this function does several different steps
at once.  This makes it very easy to use.

"Unnormalizing" to a chosen set of representatives would be nice, but we
should not/can not define such a set just by one corder (as in N(0, 0))
or a bounding rectangle, as many such sets may exist. 
normalize_map_pos_iso demonstrates this by "unnormalizing" (as you call
it) to a different set of representatives.  Your concept of an
"unnormalize_map_pos" would not work with isometric maps, since even
after this "unnormalizing" step further wrapping would be needed.

In short, you must make a distinction between the canonical set of
positions and the range into which you are wrapping a position. 
unnormalize_map_pos() does not do this, and so is itself confusing
concepts.

With normalize_map_pos_[rect|iso], we give a whole range of values into
which the position can be wrapped.  This range may contain no
representatives of the position we are wrapping (in which case we return
0 and be done with it), it may contain one representative (in which case
all is well), or it may contain multiple representatives.  For the
latter case, the function must clearly define which representative will
be used.

> 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.

This is not a GUI operation.  It may be used by GUI code, but it is
purely topological.  Any GUI code which takes this functionality away
will itself become topological code, which is what we wish to avoid.

> >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 :-).

No.  There is only one canonical set.  There are infinitely many
(perhaps uncountably infinitely many) possible sets, and trying to
represent such a set by a single coordinate will not work.  The calling
code needs to wrap a position into a fixed area, not into a set that can
be defined however the topology wishes to define it.

> >> 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.

Yes :-(

> 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.

There can only be one canonical position.  So we need a new word.

> >> >- 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.

You keep making this mistake.  A set of class representatives has no
"origin"; it can be distributed in any way possible.

A flat rectangular map uses a rectangular set of class representatives. 
An iso-rectangular map uses an iso-rectangular set.

Overhead view requires that positions be wrapped into a rectangular
set.  Isometric view requires that they be wrapped into an
iso-rectangular set.

They are two different concepts here, and must be kept separate.  You
are trying to merge them, which will only result in problems.

No reverse of normalize_map_pos is possible, because normalize_map_pos
is not injective.  When the GUI code iterates over the selection of GUI
positions, converts them to map positions, and normalizes them it
converts a flat-rectangular set (in the case of overhead view) into an
iso-rectangular set (in the case of an iso-rectangular map).  No
translation of the canonical set will ever return the iso-rectangular
set to a flat-rectangular one.

> This never does anything to unreal coordinates.

What is "this"?  Wrap_map_pos?  It doesn't even require coordinates, so
considering whether they're real or not isn't necessary.

> 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.

Correct.

> It may in
> fact do real damage like change the realness characteristic of the
> position.

Again, I assume you mean wrap_map_pos.  wrap_map_pos is only a valid
function if the topology is defined in a linear-algebra way, i.e. how
Gaute wants it.  If the topology does not fit this restriction, the
function will have no validity and will most certainly change the
realness characteristic of the position.  This is why I wish to avoid
wrap_map_pos - to leave the option open.

> >> [...]
> >> >*** 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.

If you mean something like map_to_city_map and city_map_to_map, then I
agree with you.

> 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.

Yes, except that it should not be called "canonical" since it is, by
definition, not.

A GUI position is converted to a map position which may then need to be
topologically normalized to be canonical.

> >> [...]>*** 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.

No, we are not checking for realness but for normalcy.  The two are not
the same, as a map may have regular coordinates that are real but not
normal.  If you switch "normal" in for "real" then you are correct - the
only purpose is to 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.

I'm sure we could have a normalize_regular_map_pos that would be more
efficient than normalize_map_pos; the question is would it be useful?

> 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.

Yes, we have had no good naming ideas.

> >> (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.

u and v will work, but will be less readable by non-math people.  As
long as it's not x and y, though, I'll be happy.

> >> >- 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.

No, it is a pure topological function that does not deal with GUI's. 
The GUI code uses it, as it uses many other topological functions.

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

I've already answered this.  It is no more of a mishmosh than
normalize_map_pos.

> >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 :-).

You are wrong.  Distance_from_edge is a pure topological function.

> >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.

No, they make it clear and avoid any ad hoc-ery. :-)

These functions should be used within a GUI function that does the
conversions, just like they should be used within map_to_city_map rather
than spread all over the code.  This avoids the confusion you're
speaking of.  However, if you wish to avoid using these functions you
must suggest some alternative.  unnormalize_map_pos will not do it.

> 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.

The topology layer should be kept separate from the GUI layer.  The GUI
code should not be topology-dependent.

> >> 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.

So we're agreed "normal" will keep its same meaning.

> >> 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.

No restrictions are required.

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

No extensive changes are required.

> 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.

Okay.

> >> 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 ordering will not change.  I'm talking about the implementation of
map_pos_to_gui_pos.  This must use either diff_map_pos or
normalize_map_pos_[rect|iso].

> >> 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.

Again, I am not disagreeing with you (not that I agree with everything)
but I'm talking about backend implementation: map_to_citymap_pos.  Sorry
I didn't make that clear.

> >> [...]
> >> >****** 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.

No, you have it backwards.  xsize, ysize duplicate information content
in width, height (or usize, vsize).  It is not necessary to record them
in the savegame.  However different topologies may have the same
xsize/ysize - look at the thread on iso-rectangular maps a little while
back.

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

Because they are all necessary.  map.xsize and map.ysize are the least
necessary since they can be recomputed from usize/vsize on demand, but
it's much easier to compute them once and store them.

You could store all this information in one integer field.  But then
you'd need functions to extract the above information from it.  Doing it
this way is far more readable.

> >> 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.

Width and height does not necessarily imply a rectangle.

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

How about u_size, v_size, u_wrap, v_wrap?

> >> 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.

Yes, I agree the underlying implementation isn't too big of an issue. 
What I do think is that it's easiest to present to the user (for setting
server options) in this way.  Much of the code will be more readable if
stuff is stored in this way, as well.  Ultimately, though, only the
topology backend and communications code needs to access this, so it can
be treated as an opaque object.

jason