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

[Jason Dorje Short <vze2zq63@xxxxxxxxxxx>]

"Ross W. Wetmore" wrote:
> 
> Generally, this is pretty much an excellent way to model things, and
> good source of standardizing terms.

Good to hear. :-)

> Some nits/corrections, mostly to remove residual confusion, or
> redefinition of backwards compatible terms in ways that will generate
> unnecessary confusion.

Yes, everything needs to be clarified.

> At 03:33 AM 01/10/26 -0400, Jason Dorje Short wrote:
> >I've placed an updated, more extensive RFC document into the incoming
> directory.
> >
> >ftp://ftp.freeciv.org/freeciv/incoming/topology-rfc.txt
> >----------
> [...]
> >- N<R is the set of all equivalence classes of the wrapping relation.  N
> >is represented as a set of equivalence class representatives [1].  More
> >simply put, N is represented as the set of all "normal" positions;
> >exactly one position from each equivalency class is in N.  A position in
> >N will have at least the following properties: (1) it will have a lot of
> >data stored about it, (2) it will be used as an index to map_inx and
> >map_get_tile.  A non-normal position will not have these properties.
> >
> >- A "regular" position (x, y) is defined as one where x:[0, map.xsize)
> >and y:[0, map.ysize).  This has no mathematical significance but is
> >useful in implementation.
> 
> I think there is some confusion here between N, "normal" and "regular".

Evidently so.

> If is useful to consider different sets of N. The main characteristic of
> each such set is that all real map coordinates will appear exactly once.
> 
> Different N's will be related by a transformation, generally a translation.

I had been thinking that N was a single set of our "preferred" class
representatives.  Other sets of class representatives are possible, but
calling them normal is just confusing.

However, my proposed functions normalize_map_pos_rect and
normalize_map_pos_iso goes against this thinking, because they wrap a
map positions into a set of class representatives that is not the same
as the original N.  I went ahead and defied my own naming convention...

So, I think you may be right that such naming is needed - either than or
my functions must be renamed.

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

> Thus, if I have an object such as a GUI window or a citymap whose internal
> regular coordinate origin lies at position (-1,0) in map or game coordinates
> i.e. translated one position left in x, then it is useful to consider a
> set of "normal" game coordinates N(-1,0) as the game coordinates associated
> with the corresponding GUI or citymap coordinates. To access tile data, one
> will still need to map the "normal" coordinates N(-1,0) to the corresponding
> regular game coordinates N(0,0) since memory is typically addressed in terms
> of regular game coordinates.

Yes, exactly.

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

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.

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

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

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

> One example is accessing unreal positions at the poles to fill in tile data
> - for smoothness, one maps such unreal tiles to a nearby border tile in
> order to access valid tile data for any side and corner sprite elements.
> One could as easily check for unrealness of adjacent positions and
> substitute data from the current tile, as try to find a nearest_real_pos()
> or do a forced map_wrap() on the unreal position. All are equally valid
> implementations for something that is "undefined" :-).

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.

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

> >- nearest_real_pos(&x, &y) adjusts x and y to be one of the nearest
> >positions to (x, y) that is contained in N.  (NOTE that it is misnamed,
> >it should be nearest_normal_pos.)  Since distance is poorly defined and
> >there may be more than one position with equal distance, the new set of
> >coordinates is not well-defined.  Thus you should not assume anything
> >about this function.
> 
> rename misnamed again, try: nearest_normal_map_pos()

Well, I'd like to rename it (nearest_normal_map_pos() is the name I'd
choose as well), but such things are harder to rename than to name.

> > It is definitely needed to keep the same behavior
> >in the user interface, unfortunately; in fact right now it is the same
> >as x=map_adjust_x(x),y=map_adjust_y(y) which is still used in many
> >places (mostly incorrectly).  This should be renamed nearest_real_map_pos.
> 
> Hopefully at some point the programming errors that require such hacks
> will be fixed.

These are not all programming errors.  Look at the stuff in tilespec.c;
here it is used just to make things look pretty.

I agree with you that it is very easy to misuse.

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

> >- map_pos_difference(x1, y1, x2, y2, &dx, &dy) will determine the
> >minimum difference between (x1, y1) and (x2, y2).  The (dx, dy) are the
> >x and y differentials of the two positions; "minimum distance" is
> >defined as having a minimum (max(dx, dy)).  If more than one position
> >has equal minimum difference, the result may be any of the equivalent
> >differences.
> 
> Just use the current map.c functions and don't proliferate noise here.
> 
>   xdist()              - deprecate
>   ydist()              - deprecate
>   real_map_distance()
>   sq_map_distance()
>   map_distance()
> 
> Adding "pos" is perhaps something to do.

Yes.  Essentially, diff_map_pos just replaces xdist/ydist.  Doing
without it is no good - none of these other functions do the same thing.

> (width, height) for wrapping are again too topology specific and are best
> pushed down to any topology specific layer as "context" data. This data is
> already imbedded in the map structure which defines its topology specific
> form. Thus canonicalize_map_pos() doesn't need to specify it. The general
> form would be: canonicalize_pos( POS_TYPE* object, ...) with
> canonicalize_pos( struct map* map, ...) corresponding to the above example.

It is shape-specific but not topology-specific.  Thus there's the need
for separate normalize_map_pos_rect and normalize_map_pos_iso when if we
used a "context" structure the entire map area could be passed in.  This
can be discussed later.

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

> >- distance_from_pole(x, y) returns the distance from (x, y) to the nearest
> >pole (0 for none).  This will most likely be a topology-independent wrapper
> >to another set of functions, but the exact nature has not yet been decided.
> >See the mapgen discussions below and on freeciv-dev.  "Distance" is poorly
> >defined.
> >
> >- distance_from_edge(x, y) may return the distance from (x, y) to the nearest
> >edge (0 for none).  An "edge" is a position that has an adjacent unreal
> >position.  "Distance" is poorly defined.
> 
> Any such functions are almost certainly highly specialized to things like
> map generation for a particular topology/worldview and should be left as
> local implementations in such special generators until there is a real need
> for them in more than one place.

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.

> >- Likewise, anything making hard-coded wrapping of positions is also bad.
> The
> >fix in this case is harder and will probably involve normalize_map_pos_rect
> >or normalize_map_pos_iso.
> 
> I hope not ... normalize_map_pos() should be the preferred implementation
> except for specialized code that may be manipulating unreal coordinates in
> particular ways, and thus deliberately ignores the unrealness.
> 
> Normalize_map_pos() may call one of these internally, but the user code
> should not.

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.

goto code, which is similar, will require diff_map_pos.

> >- Anything that loops over positions and assumes every regular position is
> >normal is bad.  The fix generally involves checking
> regular_map_pos_is_normal
> >and skipping those which are not.
> 
> 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".

> >Specific things that need to be fixed:
> >
> >- The mapgen code must be updated so that (1) it no longer assumes all
> regular
> >positions are normal and (2) it no longer assumes that the y coordinate
> >corresponds exclusively to lattitude.  It may be desirable to write map
> >generators that are specific to specific topologies, but in general it's
> >desirable to make the current map generators generalized.
> 
> I disagree.
> 
> The current mapgen code should be made "safe" wrt arbitrary topologies. But
> this is either by conditions on which of the generators are usable under
> which topologies, or changes to insure there are no faults when used with
> a particular topology that is deemed "safe".
> 
> The form of the current map generation (i.e. standard x-wrapped earth)
> should not be touched wrt "features" like poles, desert latitudes, etc.
> 
> If one develops new map generators for new topologies, or a more general
> form, then this should be done as a new generator. There is no reason not
> to consolidate or update internal functions where this makes sense, but
> a complete retrofit of the current system to "generalize" it is NOT the
> way to go.
>
> 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.

> >- All GUI coordinate code must be fixed.  Right now this code is a huge
> >collection of hacks to manipulate the coordinates by hand.  It must instead
> >use normalize_map_pos_rect and normalize_map_pos_iso (or, rather, it should
> >use a common GUI function that itself uses these functions).  The new code
> >should be careful to distinguish between GUI coordinates (coordinates on the
> >drawing window) and map coordinates.
> 
> 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.

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.

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

> >- Other scattered code assumes that all regular positions are normal.  Right
> >now this includes almost every manual loop over x and y.  See, for example,
> >whole_map_iterate.
> 
> Right ... so don't change this, really ... :-)

The code cannot make this assumption.  It must be changed.

> [...]
> >****** Part 2: Specific Topologies ******
> >
> >*** 2a.  Data Structures
> >
> >The current code defines only map.xsize and map.ysize (henceforth
> >referred to as xsize and ysize).  These currently define the topology
> >itself.  Under the new system, they will only define the bounding
> >rectangle for the topology.  The topology itself will be referred to by
> >another set of values (declared either within the map structure or as
> >part of a separate topology structure):
> 
> Defining a topology structure to collect this is good.
> 
> Imbedding this in the map structure to set the map topology is better.

I was imagining both, actually.

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

> >- shape: the shape of the map.
> >- isometric: is the map isometric or flat?
> >- ns_wrap: does the map wrap north-south
> >- ew_wrap: does the map wrap east-west
> >- (width, height): the dimensions of the shape.
> >  width => east-west; height => north-south
> 
> 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.

> >For a flat rectangle, width==xsize and height==ysize.  Our current
> >topology has ns_wrap==0, ew_wrap==1, isometric==0.
> >
> >Shapes may include rectangular (0), elliptic (1), hexagonal, triangular, etc.
> >
> >Width and height represent the dimensions of the map, but may use whatever
> >units the shape needs.  See below for examples.
> 
> Fix the terminology to not use specific terms like width and height that
> really only apply to rectangular cartesian coordiantes and not even
> strictly isometric.

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.

> >These topologies have shape==0, isometric==0, xsize==width, and
> ysize==height.
> 
> 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.

> [...]
> >*** 2f.  Other shapes
> >
> >Other shapes may include hexagons, triangles, etc.
> 
> Note that in almost all cases, your special shapes are just applying
> different filters to a flat-earth map to restrict the borders. This
> should be a trivial extension to the current system.

Ellipses work that way, but hexagons and triangles will wrap in
different ways.  Using a filter should be simple enough.

jason