[Freeciv-Dev] (PR#10047) RFC: restructuring map code to not use cartesian coordinates

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=10047 >

Currently the usual interface to the map code is through cartesian (aka 
map) coordinates.  See map_get_tile() and friends.  In fact almost every 
piece of code outside of the map uses cartesian coordinates: see 
whole_map_iterate, adjc_dir_iterate, etc.

Of course this has always been the case.  When Raimar asked why we used 
cartesian coordinates here instead of native coordinates (see 
doc/HACKING for an explanation of native coordinates) Ross and I had no 
particular answer.  There is no real reason why either cartesian or 
native coordinates would be superior.  However switching would take a 
lot of work.

Of course this is still true today...

However there are some reasons why cartesian coordinates are not ideal 
for accessing.

- They are two-dimensional.  This means you need two variables for them. 
  it also makes the interfaces for functions longer: see functions like 
city_map_to_map or find_closest_owned_city.
- They aren't particularly type-safe.  It's easy to mix the (x,y) values 
or get them out-of-order in function calls.
- They aren't entirely extensible.  Of course we can always use some 2d 
coordinate system to hold cartesian tile positions.  But even in hex 
topologies the cartesian coordinate system has little meaning.  In 
future even more general systems we could have arbitrary adjacency 
relations between tiles (like provinces in the Total War games) and they 
would have even less meaning.

-----

There are several other forms of data storage we could use.

Index coordinates correspond closely to native coordinates.  They have 
the advantage of being one-dimensional, which not only reduces the 
number of variables lying around but avoids the need for tuples in 
expressions.  For instance you can't say

   native_to_index_pos(map_to_native_pos(x, y))

in C, but you can say

   index_to_natural_pos(map_pos_to_index(x, y))

.  Using these exclusively would make the interfaces to many functions 
simpler since instead of whole_map_iterate(x, y) you have 
whole_map_iterate(idx).  However it's still a lot of work to switch. 
Using them may be faster or slower depending on the operation: cartesian 
coordinates are at one end of the conversion scale and index coordinates 
are at the other (cartesian <-> natural <-> native <-> index).


Using natural coordinates (see doc/HACKING) offers no advantage over 
cartesian or native coordinates.  No reason to do that.


We could just use a "struct map_position" for it.  This is 
one-dimensional, sort of.  The struct itself would just hold the 
cartesian(x,y) values.


The last solution is to use tile values directly.  Now instead of 
holding coordinate values everyone tracks "struct tile *" values.  This 
has several advantages:

   - It is typesafe.
   - It is potentially very fast, since the tile structure can hold the
     coordinates of the tile in any or all coordinate systems.
   - Like index coordinates, it is one-dimensional.
   - There is an implicit NULL value as a special-case.  Using NULL
     is a better method than the current (-1,-1) hacks we have in
     a few places.  Similarly there is an implicit CHECK_MAP_POS
     any time you work with a tile.  Either the tile is NULL or it is
     valid.  It's not likely to be garbage and there's no way
     it's non-normalized.

-----

My proposal for long-term restructuring of the map code is this:

- Code outside of the map tracks tiles.  Thus whole_map_iterate, 
map_get_terrain, and all friends operate on tiles.  In particular the 
unit and city structures will hold tile values rather than (x,y) pairs.

- Eventually we can separate the map code out entirely.  The map is not 
freeciv-centric.  The same map system we use could be used by just about 
any tile-based game.  And even in freeciv there are multiple maps.  The 
warmap is just like the map structure but with a different type.  Even 
city maps follow the same system!  (Of course struct tile * is 
freeciv-centric.  Most of the values in civ_map are freeciv-centric but 
only indirectly related to the map.  I'm really talking about map.tiles 
and all related accessor and iterator functions here.)  To enforce 
typesafety we could have a specmap or something like it.

I don't plan to begin on this soon.  But I'd like to get other people's 
thoughts on it.

-----

Side note:

In MoM or that CivII variant where you could play on alpha centauri and 
earth at the same time, there were "multiple maps".  The MoM map was 
really just one map, since certain tiles existed on both maps 
simultaneously.  I never played the civ2 variant, so I'm not sure about 
that.  I don't know if these would be done as an even more general 
system of the current map, or as a wrapper holding two maps.

-jason