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

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

Generally, this is pretty much an excellent way to model things, and
good source of standardizing terms.

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

Cheers,
RossW
=====

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

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.

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

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.

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.

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

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

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

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

This is going to be a very difficult point for the literal minded :-).

To make this clear, consider the case where gaming coordinates are polar
coordinates of the form (r,theta). This would perhaps be useful to play
on a solar system map. GUI coordinates could still remain as rectangular
positions, i.e. the pixel or scaled pixel coordinates used by GTK or XAW.
r is non-wrapped with bound map.rsize, theta wraps at its equivalent of
2*pi.

>- is_real_tile(x, y) returns TRUE iff (x, y) is an element of S.  This
>should be renamed is_real_map_pos for clarity.
>
>- is_normal_map_pos(x, y) returns TRUE iff (x, y) is an element of N.

With the appropriate clarification of N to be N(0,0).

>- normalize_map_pos(&x, &y) returns FALSE if (x, y) are unreal (x and y
>become undefined) and TRUE if (x, y) is real (x and y are adjusted so
>that they are the class representative of the (x, y) equivalency class;
>the new (x, y) will be equivalent to the old one and contained in N).

With the appropriate clarification of N to be N(0,0).

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

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

>- is_border_map_pos(x, y) (currently IS_BORDER_MAP_POS) returns TRUE if
(x, y)
>might be the wrapping border of the topology; that is, if (x, y) might
have an 
>adjacent position that is not normal.  This will be useful only for
>optimizations so it is ok to err on the side of safety (for instance, by 
>having this function always return "1").

The "that is" clause is actually more precise and general and should be 
used as the main definition - the main clause is more the fuzzy specific 
example.

Extensions or generalizations may be useful such as 
  is_border_map_pos2(x, y)  or
  is_border_map_pos(n = CITY_MAP_SIZE/2, x, y)

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

I don't believe there is a real need for is_canonical_map_pos(x,y) which 
is what is_normal_map_pos() above purports to be, but is not currently 
implemented to be.

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

>- normalize_map_pos_rect(&x, &y, x0, y0, width, width) wraps position (x, y)
>to be within the rectangle (x0 .. x0+width-1) x (y0 .. y0+height-1).  It
>returns 0 if the position is unreal or if no such wrapping is possible.
This 
>will be of use in the GUI; for instance wrapping a position to be within the
>overhead-view window.  A better name would be good.

canonicalize_map_pos(&x, &y, x0, y0, width, height)

... if this is needed. I suspect it is not if you do the normalize and 
translation operations in the right order in cases where you are relating
(normal) GUI coordinates to (translated) map coordinates. This builds in
the translation step, i.e. origin shift and it might be advisable to keep
it separate and distinct. 

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

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

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

>- A few other functions may also be needed.
>
>*** 1e.  Necessary Changes
>
>A lot of current code assumes that the topology is flat-rectangular and
>wraps in e-w directions only.  This code must be fixed.  In general, it's 
>difficult to tell if you've found all of the applicable code.  However,
there 
>are a few patterns we can look for:
>
>- Anything using map_adjust_[xy] is bad.  The fix generally involves
>normalize_map_pos and/or is_real_tile.

Caution, some GUI code depends on the map_adjust_y() bug/hack to implement
nearest_real_map_pos(). Some code may also do this to find the border for
clipping operations. Add these warnings.

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

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

>- Anything that uses its own data storage methods rather than the one
>described in part #2 with map_inx() may be unsafe. 

>However, code that uses a
>double array (e.g. seacost[x][y]) should be fine.

This makes no sense. Explain the conditions more fully, or drop this line.

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

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

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

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

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

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

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

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

>*** 2b.  Savegames and communication
>
>The new data will have to be stored in savegame files and communicated from
>server to client, while (possibly) preserving backwards compatibility with
>old savegames and servers/clients.  Capabilities may be needed.
>
>*** 2c.  Flat Rectangle Topologies
>
>Flat rectangle topologies are easy.  There are four of them, corresponding to
>the four possible values for ns_wrap/ew_wrap.  Our current topology has
>ns_wrap==0 and ew_wrap==1.
>
>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.

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

For cases where there is some wrapping operation at the border as
well as filtering, more thought may be needed as to what canonical
set translations really mean. But note the model above tells you 
this is pretty much to localized area of code that needs to be 
changed, and nothing much else should really depend on this if you
implemented things correctly.

>[1] For more information on equivalency classes, see
>http://www.math.csusb.edu/notes/rel/node3.html.
>
>
>Jason Short
>version 1
>October 26, 2001