[Freeciv-Dev] Re: Topologies and coordinates

[Jason Dorje Short <vze2zq63@xxxxxxxxxxx>]

Andrew McGuinness wrote:
> 
> 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?

Much less than you think.

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

No, this can just use normalize_map_pos.  Currently adjc_dir_iterate
does specialty checking for a border tile, saving a lot of time - this
may become a new function is_border_map_pos.

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

No, this can just use is_normal_map_pos to skip over invalid tiles as it
iterates around the outer rectangle.

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

No, this can use identical methods to those above.  However cleaning up
the GUI so that this will work will be a major undertaking.

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

Yes.

> 5  Calculating distance or shortest route between two points

Yes.

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

No, you can just generate random positions on the outer rectangle until
you get a valid one.

> 7  Other things that I haven't thought of

Yes :-)  nearest_real_map_pos for one.

> 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

We've been calling it isometric.

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

Not really.  If we want to keep our current structures (and avoid HUGE
amounts of extra work) only map#1 will work.  It is the only one that
has been seriously proposed.  Raimar proposed some sort of mapping from
mapspace to userspace, but I don't think he had thought it out fully.

Remember that we don't just look at adjacent positions; that would be
headache enough in itself.  There are lots of square_iterate macros that
iterate over vision range, city range, etc.  Converting all of these
makes #2 or #3 infeasable.

In short, map#1 is the right way to go; there is no doubt in my mind.

> map1 preserves the normal adjacency and distance rules, except for
>      wrapping

This is the most important thing, since it is EVERYWHERE in the code.

> map2 preserves the orientation and poles, but not adjacency, and
>      has an easy check for what coordinates are valid

Checks for orientation are rare, and easily dealt with.

> map3 most closely matches what the player sees, but those gaps are
>      rather a headache

Who cares what the player sees?  The isometric tileset takes care of
this.  Note that using the regular tileset, the player will see map#1.

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

Actually, I think fixing map_adjust_x in the client will be by far the
biggest headache...but yes, more will have to be changed.  I don't think
we're not far off on the server side, though.

> 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 );
>   }
> }

MAPSTEP already does exactly that.  It has no switch statement but
instead calls normalize_map_pos which takes care of all the rest.  So,
this will already work just fine once the appropriate case checks are
added to normalize_map_pos.

The work left is to convert existing code to use these functions instead
of using other macros or just blindly assuming things will work.

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

Rather than calculating the distance I was thinking it should return a
diff_x/diff_y pair.  "Distance" is poorly defined anyway.

> /* several more functions of this kind */

is_normal_map_pos, is_real_tile, etc.

Also (optionally) map_inx (soon to be map_pos_to_index) and
index_to_map_pos, although now I'm thinking we can just forget about
these and always use the rectangular storage system (this is what Raimar
wants, I think).

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

Macros will be very ugly.  Inline functions is the way to go.

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

This is exactly what normalize_map_pos does.  It also returns the
validity so you can skip or do special handling as you wish.

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

Sounds right.

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

Right, assuming you wrap in only the east-west direction.

> i.e.
> __cfG
> _beil
> adhko
> Fgjn_
> ILm__
> 
> where g and G are the same tile, etc.

Yep, you understand.  However you are unnecessarily linking the wrapping
information to the topology.  Either rectangular or iso-rectangular
topologies can wrap in north-south, east-west, both, or none.

> 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

You cannot ever assume this.  However, you *can* assume that
normalize_map_pos will tell you everything you need to know (assuming we
use map#1).  The problem is most of the code doesn't use
normalize_map_pos.

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

As I said before, the current macros will work just fine (although they
too need to be fixed up a little bit).  There will be some slowdown
because the extra check for topology will be added, but this is
absolutely insignificant.  There is further slowdown because
normalize_map_pos and friends are functions rather than macros, but this
can be dealt with by making them inline.

jason