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

[Jason Dorje Short <vze2zq63@xxxxxxxxxxx>]

Reinier Post wrote:
> 
> On Fri, Oct 26, 2001 at 03:33:58AM -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
> 
> [...]
> 
> > - Definitions:
> >   - Let Z be the set of all integers.
> >
> > - S=ZxZ is the set of all possible positions, both real and unreal.
> 
> You omit the reason to use S as an index, namely the fact that maps
> are displayed in map views in the client, and these map views can
> be described as rectangular grids of screen positions.

Good point.

> > - R<S is the set of all "real" or "valid" positions.  (< means subset
> > here).  Any position that is real is a valid location on the map for
> > units, cities, tiles, etc (however, these will generally use the
> > "normal" coordinates for describing that position).  An unreal (!real)
> > position does not have these properties.
> >
> > - Coordinate pairs may be considered equivalent.  This means that if a
> > unit on position (x, y) which is equivalent to position (x2, y2) that
> > unit could just as easily be considered to be on position (x2, y2).
> > This property is an equivalence relation [1] - it is reflexive,
> > transitive, and symmetric.  I'll call this relation "wrapping".
> 
> The reason you call it "wrapping" is that by 'it could just as well be'
> you mean that the equivalence relation must be a congruence: it must
> respect the adjacency relation.

Correct, though this is not well defined.  Currently the client requires
not only that adjacency relations be preserved but also that all
elements of a class of positions have the same orientation.  This is not
required in the mathematical definition, though (yet, anyway).

Putting together an actual definition of the adjacency restriction is
tricky.  Eventually, it must be done but I'd like to hold off for now. 
This does not make any difference to the core code (which is what is
being changed now).

> You can still get some very funny maps with it.  A double
> planet for instance, if the map isn't connected.  And patterns:
> 
>       1234
>       2563
>       3652
>       432123
>          25  etc. in all directions.
> 
> To avoid this, you can add the restriction that the congruence
> must be a translation - no rotation or mirroring allowed.  To restrict
> even further, demand that only-horizontal and only-vertical translations
> suffice.

I do not think these definitions are required.  As I said, though, the
client will not be able to handle the full set of mathematically valid
topologies.  This particular one would be fine except that the client
will only draw one tile at a time - should we place a restriction that a
position can be no closer than N units to itself (for some value N)?

> BTW, I think it would be more elegant to have a definition in which the
> map itself is just an adjacency graph on tile structs, constrained by
> properties of the map views displayed in the client (such as the fact
> that a map view is formed by a set of congruent tile shapes that cover
> the 2D plane).  Positions would arise out of the equivalences between
> the positions of tile images in the GUI map views, rather than being the
> fundament on which the rest is built.

One could imagine that that is the more general definition, and the
above definition is just a special case of it.

However, the current code will not allow arbitrary adjacency graphs. 
Ignoring the GUI frontend, all sorts of core code like adjc_iterate
would have to be rewritten.  So some additional assumptions to the
adjacency graph idea are required (at least for now).

> > The new definition is this: (map.xsize, map.ysize) is the dimensions of
> > a small bounding rectangle for N.  (In general, N should be chosen to
> > fit inside as small a rectangle as possible and map.xsize x map.ysize
> > should be as small as possible.)
> >
> > This storage method has the advantage of easy indexing (i.e. a simple
> > map_inx()), but the disadvantage of having wasted space from
> > fragmentation.  For most topologies the wasted space should be less than
> > half of the total array; however, even so that means as much as a
> > doubling of memory consumption in these areas.
> 
> Will anything else be required to define a map?  Does this mean you
> assume 'wrapping-breaking borders' such as the present poles are always
> defined by throwing up borders of non-real positions?

This is a mapgen issue.  I hope to make the current map generators
fairly general by using topological functions (like DISTANCE_FROM_POLE)
to handle all of this stuff.  However, you can only get so far with this
so it may be desirable to write topology-specific map generators.

I think the topology can define DISTANCE_FROM_POLE as it sees fit;
unfortunately this means only one such orientation is possible (so that,
say, under the current topology north-south is always vertical on the
map, which it need not be).  Torus maps might choose to be all-tropical
and so just define distance_from_pole as a constant.

make_passable may want to look at the distance from the pole or the
distance from the edge ("edge" meaning the edge of real positions). 
Again, this will make map generation sensible but not flexible.

> > *** 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.
> >
> > - 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.
> 
> With the assumption of congruence, S = S n N mod (map.xsize,map.ysize).

I'm not familiar with this terminology.  What does 'n' mean?

However, I think you're wrong on several (minor) counts.  The least
residue (normal positions) do not always fit cleanly into the
(map.xsize, map.ysize) region.  For instance, in an iso-rectangular map
the vectors of wrapping are (height/2, height/2) (for NS-wrapping) and
(width/2, -width/2) (for EW-wrapping).

Also, the assumption of congruence doesn't imply anything about the
orientation of the positions.  We could view this as an additional
restriction to the definition, or just as a shortcoming in the client
that needs to be fixed.  Topologies like mobius strips that break this
translational restriction shouldn't be out of reach.

> > - is_normal_map_pos(x, y) returns TRUE iff (x, y) is an element of N.
> >
> > - 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).
> 
> You have ensured that a class representative can always be picked within N,
> but not that it is unique.  You need the translation assumption to guarantee
> that N can be chosen to allow this.

N is defined such that it contains exactly one representative from each
class.  Whoever writes the topology defines N.  The definition of N
shouldn't matter except inasmuch as map.xsize and map.ysize are defined
based upon it.

This should not be an issue to the GUI or any other code since it will
all use manipulation functions (in the GUI's clase,
normalize_map_pos_[rect|iso]) to access specific coordinates.

> (I have no time to look at the rest now.)

Thanks for the feedback.

jason