[Freeciv-Dev] RFC: alternate topologies

[Jason Dorje Short <vze2zq63@xxxxxxxxxxx>]

Here is the proposal, in full (version 1, pretty informal).

1.  Mathematical Definition of a Allowable Topology

Any topology which fits the following informal definition should work
with the proposed changes.

- Definitions:
  - Let Z be the set of all integers.
  - A "position" is the same as a "coordinate set".
  - A "tile" is the same as a "position" but should not be used.

- S=ZxZ is the set of all possible positions, both real and unreal.

- R<S is the set of all "real" or "valid" positions.  (< means subset
here).  Any position that is real has at least the following properties:
(1) units can move there (2) the client can draw a tile for that
positions.  An unreal (not 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".

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


2.  Data Storage

The current map.xsize x map.ysize array format will be kept; however, it
will no longer be entirely populated by "on-map" normal tiles.

The new definition is this: (map.xsize, map.ysize) is the dimensions of
the smallest possible bounding rectangle for N.  (In general, N should
be chosen to fit inside as small a rectangle as possible; this also
makes calculations easier.)  Nice conversion routines will make this
easy - currently map_inx() does this but I expect it will be expanded to
map_pos_to_index(), index_to_map_pos(), and map_index_size() or
something like that so that everyone is happy.

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.


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

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

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

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

- A few other functions may also be needed.


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

- Anything that loops over tiles and assumes every tile within a
rectangle is on-map (normal) is bad.  The fix generally involves
checking for is_normal_map_pos and skipping those which are not proper.

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

- ...?


[1] http://www.math.csusb.edu/notes/rel/node3.html

jason