[Freeciv-Dev] Topologies and coordinates

[Andrew McGuinness <a.mcguinness@xxxxxxxxxxxx>]

I think it is too ambitious to try to code the game to handle an
open-ended variety of map organisations.

The aim needs to be to identify and separate topology-sensitive
parts of the code so that new variants can be added.

What things that parts of the code need to know about can vary?

1  Calculating the 8 positions adjacent to a given position 
   (some of which may be off-map)

2  Iterating over the whole map, for various reasons (generation,
   load/save)

3  Displaying the map, in such a way that displayed adjacency is
   correct, and the orientation of the map is sensible

4  Determining "latitude" for climate purposes, either for map
   generation or AI behaviour

5  Calculating distance or shortest route between two points

6  Generating random positions for game events (barbarians, etc)

7  Other things that I haven't thought of

Depending on how you translate the topology onto a grid, some of those
might go away.

The priority is a simple civII-style map, with isometric view and the
poles at the top and bottom.  I call this a "diagonal" map

a b c       north pole
 d e f
g h i 
 j k l
m n o       south pole

h is adjacent to b,d,e,g,i,j,k,l
g is adjacent to a,f,d,i,h,l,j,m

Three ways of mapping this have been proposed.
("_" represents a coordinate pair that is not a real square - either 
off-map or wrapping to another coordinate pair)

map1:   (5x5)
__cf_
_beil
adhko
_gjn_
__m__

map2:   (3x5)
abc
def
ghi
jkl
mno

map3:   (5x5)
a_b_c_
_d_e_f
g_h_i_
_j_k_l
m_n_o_

Any of the three could work.  
map1 preserves the normal adjacency and distance rules, except for
     wrapping
map2 preserves the orientation and poles, but not adjacency, and
     has an easy check for what coordinates are valid
map3 most closely matches what the player sees, but those gaps are
     rather a headache

Using any one, more would have to be changed than just an adjust_xy
type routine.

I suggest trying to write topology-specific routines for each of the
7 things in my list at the top, and calling them via a case mechanism:

int get_adjacent_tile( int x, int y, int direction, int* newx, int* newy )
{
  switch(global_topology_variable) {
  case 0: return get_adjacent_tile_normal( x,y,direction,newx,newy );
  case 1: return get_adjacent_tile_diagonal( x,y,direction,newx,newy );
  case 2: return get_adjacent_tile_torus( x,y,direction,newx,newy );
  }
}

int calc_distance( int from_x, int from_y, int to_x, int to_y )
{
  switch( global_topology_variable ) {
  case 0: return calc_distance_normal( from_x, from_y, to_x, to_y );
etc...

/* several more functions of this kind */

These could be macros instead of functions, or you could use a kind of
"virtual function table", but it's going to cost some perfomance.  On
the other hand, it will be a great deal easier to deal with than trying
to squeeze the topology-sensitive code down to the lowest possible level.

I showed a get_adjacent_tile(x,y,direction) function above.  This would
be needed for some topologies.  The torus and "diagonal" could be done
without it, provided the diagonal was mapped according to map1 - you could
get away with
adjust_xy(int* x, int* y) which would correct x and y if they had wrapped
off.

showing it again:
map1:   (5x5)
__cf_
_beil
adhko
_gjn_
__m__

if c is (2,0) and i is (3,1), then 
(5,0) would map to (1,3) "g"
(0,3) would map to (3,0) "f"
(0,4) would map to (3,1) "i"
(1,4) would map to (4,1) "l"

the other coordinates that are marked "_" are off the poles and invalid.

i.e.
__cfG
_beil
adhko
Fgjn_
ILm__

where g and G are the same tile, etc.

This is the discussion that has been going on - whether it is general 
enough to assume that:
From (x,y) any tile ( x +/- 1, y +/- 1 ) is either
 a) a valid tile adjacent to (x,y)
 b) wraps to another tile (r,s) which is adjacent to (x,y), 
 c) is invalid

The tradeoff is between generality and performance - having to use
get_adjacent_tile() rather than the current iterate_xy macros would
slow things down a bit, and it is not essential to implement the
new topologies we really need.  On the other hand, not using it does
restrict the wierd and wondeful topologies people might want to play
with.

--
Andrew McGuinness     Luton, UK             a.mcguinness@xxxxxxxxxxxx