[Freeciv-Dev] Re: Topologies and coordinates

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Fri, Oct 05, 2001 at 04:36:04PM -0400, Jason Dorje Short wrote:
> 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.

Andrew is right that calculating the 8 positions adjacent to a given
position can be difficult (for example in map2).

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

I still think that you need such code for IS_ARTIC and the isometric
version of normalize_map_pos.

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

Ack.

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

Ack.

> (this is what Raimar wants, I think).

Yes.

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

I don't understand this.

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

I agree that the overhead for isometric maps can be made
small. However I'm not sure about isometric maps.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "How about the new language C&? No, that's not 'c ampersand', 'c reference', 
  'reference to c' or 'c and'. It's pronounced 'campersand', to confuse the 
  hell out of people who are unfamiliar with it, and it will, of course, 
  have no pointers."
    -- Xazziri in comp.lang.c++ about C#