[Freeciv-Dev] Re: Topologies and coordinates

[Andrew McGuinness <a.mcguinness@xxxxxxxxxxxx>]

Quoting 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.
> 
Yes, accepting some restrictions, which I agree are not a big deal.

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

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

At the least, the gui needs to know whether the north pole is at y=0
or at x-y=K

> > 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.
> 
I avoided that because of the confusion between isometric view of an
isometric map, and isometric view of a rectangular map (what we already
have)

[snip descriptions of map <-> array translations]

> > 
> > 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.
> 
I think you are right.  I was concerned because in your discussion with
Raimar, small implementation details were obscuring the issues (at least
from me)  I was trying to get back to the fundamentals.

> > map1 preserves the normal adjacency and distance rules, except for
> >      wrapping
> 
> This is the most important thing, since it is EVERYWHERE in the code.
> 
[snip]
> 
> > 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've been writing C++ too long to be much help with the exact
implementation details here.

[my statement of your system of relying on normalise_map_position snipped]

> 
> 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.
> 
Yes, but the semantics of normalise_map_position, and also of things like
get_distance_between (or your get_vector_between) and the like depend on
both the alignment (rectangular/iso-rectangular) and the wrapping
behaviour.

> > 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.
> 
Well, that's what I meant - normalise_map_pos will tell you whether 
a,b or c applies, and in case b what the real coordinates (r,s) are.

If map#2 were used, on the other hand,(x-1,y-1) might be a valid tile
which is not adjacent to (x,y) - that's why it's not a good idea.

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

Yes, your plan is the faster but less general one. There are options that
you could have only if you don't assume that normalise_map_pos is all you
need.  Playing on the surface of a cube, for instance.  That definitely
comes under "wierd and wonderful" rather than "what we really need". It
would also be very difficult to display, compared to the other systems
we have been talking about.
 
> jason
> 

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