[Freeciv-Dev] RFC: 8-topology system

[Jason Dorje Short <vze2zq63@xxxxxxxxxxx>]

Here is a (hopefully) full explanation of how I propose to implement an
8-topology system.  The eight topologies include flat vs isometric,
north-south wrapping vs no wrapping, and east-west wrapping vs no
wrapping.  We also allow the possibility of adding non-rectangular maps
in the future.  Any of these 8 topologies will work under my proposed
general topological system (an earlier post), either with or without the
linear-combination-of-vectors (LCOV) extension (LCOV allows
wrap_map_pos()).

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: 0 for rectangle; no other valid values yet.
- 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.

To implement variations of the flat rectangle is easy.  All of the
wrapping is done along the axes, so if we have ns_wrap we wrap along the
y axis and with ew_wrap we wrap along the x axis.  (Note: "wrap" is an
ill-defined term, but I'm going to use it anyway.  For real tiles, wrap
is well-defined and is the process used to normalize coordinates.  For
unreal tiles, "wrap" is only defined if we're using the LCOV
assumption.)

To implement variations of the iso-rectanglular is much harder.  An
iso-rectangle may be of the form

      X             X             X X           X X
    X X X         X X X         X X X X       X X X X
  X X X X X     X X X X X     X X X X X     X X X X X
X X X X X     X X X X X X   X X X X X     X X X X X X
  X X X         X X X X       X X X         X X X X
    X             X X           X             X X

(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 tiltes 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-left and
top-right.

Note also how all of these different maps have the same xsize and ysize
(6 and 6).  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 topological
transformations.  (Note all division is rounded down.)

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

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

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

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

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

That's all for now.

jason