[Freeciv-Dev] topology RFC (again)

[Jason Dorje Short <vze2zq63@xxxxxxxxxxx>]

I've placed an updated, more extensive RFC document into the incoming directory.

ftp://ftp.freeciv.org/freeciv/incoming/topology-rfc.txt

----------

This document describes a proposed system to allow arbitrary topologies in
FreeCiv, and some of those topologies specifically.

****** Terms ******

- A "map position" or "map pos" is an (x, y) tuple representing a position on
  the map.  It may also be called a "coordinate set" (although "set"
  incorrectly implies that it's unordered), a "position" (although this does
  not distinguish from GUI positions; context usually makes it clear), or a 
  "tile" (although tile is usually used to mean something completely 
  different).

- A "tile" is not well defined.  In the code, it refers to data being stored
  about a particular map position.  It may be used to describe this data, a 
  normal map position, a real map position, or even any map position.

****** Part 1: General Topologies ******

*** 1a.  Mathematical Definition of a Allowable Topology

Any topology which fits the following informal definition should work
with the proposed changes (and vice versa).

- Definitions:
  - Let Z be the set of all integers.

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

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

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

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

*** 1b.  Data Storage

The current map.xsize x map.ysize array format (representing all 
regular positions) 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
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.

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

- 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).  This should be renamed nearest_real_map_pos.

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

Note: map_adjust_x and map_adjust_y must no longer be used.  Hard-coded
wrapping of map positions must also not be used.  Both of these are present
only in the client.

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

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

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

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

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

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

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

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

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

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.

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

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

*** 1f.  Limitations

The limitation is that this will only allow topologies that fit the 
definition in (1a).  This means hexagonally-tiled maps and arbitrary digraphs
are out.  This is a tradeoff for how much easier it will be to implement this
set of topologies; but designs should think about what future enhancements are
possible.


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

- 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

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.

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

*** 2d.  Isometric Rectangle Topologies

To implement variations of the iso-rectanglular is much harder.  An
iso-rectangle has shape==0 and isometric==1.  An iso-rectangle may be of the 
form

- - - - - - - - 
|       #     | 
|     # # #   | 
|   # # # # # | 
| # # # # #   | 
|   # # #     | 
|     #       | 
- - - - - - - - 
   (1) - 7x5

- - - - - - - - 
|       #     | 
|     # # #   | 
|   # # # # # | 
| # # # # # # | 
|   # # # #   | 
|     # #     | 
- - - - - - - - 
   (2) - 7x6

- - - - - - - - 
|       # #   | 
|     # # # # | 
|   # # # # # | 
| # # # # #   | 
|   # # #     | 
|     #       | 
- - - - - - - - 
   (3) - 8x5

- - - - - - - - - 
|       # #     | 
|     # # # #   | 
|   # # # # # # | 
| # # # # # #   | 
|   # # # #     | 
|     # #       | 
- - - - - - - - - 
   (4) - 8x6

These maps show a world tilted 45 degrees counterclockwise.  North is
therefore in the upper left and so on.  When viewed under an isometric
tileset (which tilts 45 degrees clockwise) the maps will appear flat.

Map#1 has width==7 and height==5.  Tilt your head to the left and you'll
see where these numbers come from.  The number of tiles is 7*5/2==18. 
We round up by definition; although it would be possible to make a 7x5
map with 17 tiles we will define all odd-dimensioned maps to have the
greater number of tiles.  More specifically, we'll define the upper-left
row and lower-left column to each have the greatest possible size.

An isometric map cannot wrap in a given direction if its dimension in
that direction is odd.  Thus, the above map cannot wrap either
north-south or east-west.  If we are given such a map and are told to
make it wrap, we'll just bump up the coordinates accordingly.  Map#2
will therefore allow ns_wrap, map#3 will allow ew_wrap, and map#4 will
allow both.  Note how the short rows are added at the bottom-right and
top-right.

Note also how all of these different maps have similar xsize and ysize.  This 
is the reason why xsize and ysize will no longer be used to store topological 
information.

So, we have now defined each widthxheight map.  What remains is to
figure out the calculations that will be needed for the basic topological
transformations.  (Note all division is rounded down.)

- xsize = (height + width) / 2
  ysize = (height-1)/2 + (width-1)/2 + 1

- The wrapping vectors are {(width/2, -width/2), (height/2, height/2)}. 
  That is, the wrapping in the east-west direction is done by
  adding/subtracting a vector (width/2, -width/2) and in the north-south
  direction with a vector (height/2, height/2).  Again, the dimension
  (width or height, respectively) must be even for the map to be able to
  wrap in that direction.  (This would be a good time to point out that y==0
  is at the top of the map, with x==0 at the left.)

- The western (bottom left) end of the world is defined by the line 
  x-y=-(width-1)/2.  A point is off the map to the west if 
  x-y<-(width-1)/2.

- The northern (top left) end of the world is defined by the line
  x+y=(width-1)/2.  A point is off the map to the north if
  x+1<(width-1)/2.

- The eastern (top right) end of the world is defined by the line
  x-y=-(width-1)/2+width-1.  A point is off the map to the east if
  x-y>-(width-1)/2+widht-1.

- The southern (bottom right) end of the world is defined by the line
  x+y=(width-1)/2+height-1.  A point is off the map to the south if
  x+y>(width-1)/2+height-1.

*** 2e. Ellipses

An ellipse has shape==1.  An ellipse may not wrap.  A flat ellipse is of the
form

- - - - - - - - - - - - - 
|   # # # # # # # # #   | 
| # # # # # # # # # # # | 
| # # # # # # # # # # # | 
| # # # # # # # # # # # | 
|   # # # # # # # # #   | 
- - - - - - - - - - - - - 
          11x5

For symmetry and easy calculations, a flat ellipse must have odd dimensions.

xsize and ysize are defined by 

  xsize==width
  ysize == height

and a position (x, y) is normal and real if
  let
    xr = width/2
    yr = height/2
    x' = x - xr
    y' = y - yr
  in
    (x' * x' * yr * yr) + (y' * y' * xr * xr) < xr * xr * yr * yr

An isometric ellipse has isometric==1 (of course) and may be of the form

- - - - - - - - - - - 
|                   | 
|           # #     | 
|         # # # #   | 
|       # # # # #   | 
|     # # # # #     | 
|   # # # # #       | 
|   # # # #         | 
|     # #           | 
|                   | 
- - - - - - - - - - - 
        11x5

The definition here has not been finalized.  Here we have
  xsize == ysize == (width+height)/2 + 1
and a coordinate (x, y) is real and normal iff
  let
    xr = width/2
    yr = height/2
    d = (xr + yr + 1)/2
    x' = x-d
    y- = y-d
  in
    (x' * x' * yr * yr) + (y' * y' * xr * xr) < xr * xr * yr * yr

Notice that the (xsize, ysize) rectangle of regular positions is much larger
than the inner ellipse; this makes the math easier but is less than ideal.

*** 2f.  Other shapes

Other shapes may include hexagons, triangles, etc.



[1] For more information on equivalency classes, see
http://www.math.csusb.edu/notes/rel/node3.html.


Jason Short
version 1
October 26, 2001