[Freeciv-Dev] Re: (PR#3936) introducing native coordinates

["rwetmore@xxxxxxxxxxxx" <rwetmore@xxxxxxxxxxxx>]

Raimar Falke wrote:
> On Sat, Apr 05, 2003 at 09:56:05AM -0800, Jason Short wrote:
>>Raimar Falke wrote:
>>>On Fri, Apr 04, 2003 at 07:48:14PM -0800, Jason Short wrote:
>>>
>>>>This is a significant design issue, and should be closely scrutinized. 
>>>>I'd encourage everyone to at least read this patch.
>>>>
>>>>Native coordinates (sometimes called "compressed" coordinates in the
[...]
>>>What operations (would) require native coordinates? I have the feeling
>>>that a lot can be done with indexed coordinates. For example
>>>savegames.
>>
>>True, storage (such as savegames and map storage) can be done either 
>>with native or index coordinates.  
> 
>>The goal here is backward-compatability

It is also true that all maps are going to be 2-D for the forseeable
future. It is also the case that maps are typically displayed in a
cartesian GUI window, even if they consist of a non-rectangular 2-D
object in a masked outline. Furthermore, the internal standard map
coordinates used for local operations and all game mechanics are
based on a 2-D cartesian grid. The basic topology operations for all
such maps are representable in an orthogonal 2-D coordinate space.

The simplest way to display/manipulate all such coordinates is to find
a corresponding 2-D cartesian grid point with a dense one-to-one mapping
to the internal map coordinates. This is just the definition of native
coordinates. The above constraints mean this is always possible.

Using a linear representation loses all the 2-D functionality which
makes it a poor choice for the native representation that deals with
global map perspectives and properties. Linear is easiest for memory
storage, however, and should be used for such.

The conclusion is to use the coordinate system that is best for the
operation at hand, and convert to and from it when needed. Algorithms
become much simpler and thus more robust if phrased in the right
coordinates. Global iterators like whole_map_iterate are trivial and
thus best done in native coordinates rather than standard map coordinates.


> That is the question. Considering how many people look at the
> savegames (almost zero) and how much other more fancy topologies we
> want to support (note that the savegame format lives relative long) I
> would go with indexed coordinates. Native coordinates are here IMHO
> just a kludge to fit into the old 2D savegame format.

Savegames are stored line oriented in a grid that matches the display.
Debug output is also typically dumped to stdout in a line oriented
fashion. When there is need for a compact 2-D representation one should
use native coordinates. There is no need to complicate life by other
changes that are neither needed nor related to the basic coordinate
update, and probably worse in usage/usability anyway.

BTW: I typically look at savegames and it is very useful to have them
display as an ascii representation of a map, and not just some random
string of numbers. This is a key advantage to the ascii format that
should not be lost.

>>; we might as well use native coordinates for 
>>savegames and indexed coordinates for map.tiles because that's 
>>(basically) what's done now.
>>
>>Native coordinates are especially good (compared to map coordinates) for 
>>topology operations.  For instance normalize_map_pos can be written 
>>something like:
> 
> About what other topology operations are we talking here? That
> normalize_map_pos will be more complex is obvious.
> 
> 
>>>AFAIK there is no sane way to represent an iso-map in the
>>>2d layout we have in savegames?!

Native coordinates are by definition the way to do this. If it helps
learn to separate global from local operation concepts. You should
use the internal standard map coordinates for local relationships
like adjacency, and native forms for global operations like wrapping
or display iteration.

It is trivial to iterate the global map with whole_map_iterate() written
in native coordinates and do a conversion to GUI natural coordinates to
populate a GUI window. Trying to work out this iteration in standard map
coordinates has been one of the things that makes the GUI code so hardwired
and inscrutable.

>>No, the iso-map
>>
>>   X X X      XXX
>>    X X   <=> XXX
>>   X X X      XXX
>>
>>can easily be represented in our 2d layout in the second (native) form.
> 
> 
> Ok but how valuable would than this print out of the map at the start
> of the gamelog?
> 
> How will native coordinates (and also the "normal" ones) cope with
> more fancy topologies like this one (should be a circle or an
> ellipse):
> 
>     ##
>    ####
>   ######
>   ######
>  ########
>   ######
>   ######
>    ####
>     ##
> 
> Maybe this is quite easy because you only do a masking operation onto
> a base rectangle?!
> 
>       Raimar

You have basically shown the most probable way this will be done for
non-rectangular 2-D shapes. These are basically going to be an underlying
rectangular grid of normal coordinates filtered through a realness mask.

But one is free to define native in other ways if it servers the basic
purposes and keeps the global iterators and other operations simple.

Another approach that may help understanding. Regular coordinates were
defined as a bounding box oriented along standard map coordinates that
enclosed the normal map. In cases like true isometric maps that look
like a normal rectangular grid, allbeit with even or odd points missing,
using the axes of the standard map to define the bounding box, rather
than the natural rectanglar axes of the actual map resulted in a gross
amount of inefficiency and no ability to take advantage of the natural
wrapping directions from a topology standpoint, etc. Native coordinates
can be thought of as performing the regular bounding box operation
along axes that are more natural to the actual map with some additional
compression along one axis for efficiency purposes to remove the unreal
grid points and simplify the iteration operations along that dimension.

The sort of optimal bounding box and compression steps above can probably
be used as one technique to generate a native coordinate representation
for any cases you might come up with.

Cheers,
RossW
=====