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

[Reinier Post <rp@xxxxxxxxxx>]

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.

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

Or do you really want to break this assumption?

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.

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.

[...]

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

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

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

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

> Jason Short
> version 1
> October 26, 2001

-- 
Reinier Post