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

["Jason Short" <jshort@xxxxxxxxxxxxxx>]

--On Saturday, April 5, 2003 5:27 PM -0800 Raimar Falke 
<rf13@xxxxxxxxxxxxxxxxx> 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
>> >> past) are a concept Ross came up with to make isometric (and other
>> >> non-standard) maps easier to deal with.  They save around 50% memory
>> >> (and on disk, in savegames) for map storage over "standard" map
>> >> coordinates and make topology operations *much* simpler.  Other
>> >> coordinate systems may share one of these properties, but none have
>> >> both.  In the process, they invalidate the need for "regular" map
>> >> positions.
>> >>
>> >> The patch introduces native_to_map_pos and map_to_native_pos macros
>> >> into map.h, along with one very simple user.  I've also written an
>> >> explanation of the coordinate systems for doc/HACKING.  I'd like
>> >> feedback on this explanation, particularly from people who don't
>> >> already know what "native coordinates" are.
>> >>
>> >> All other explanation is in the patch (or if it isn't, it should be).
>> >
>> >
>> > 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
>
> 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.

Native coordinates aren't any more of a kludge than index coordinates - the 
only reasonable implementation of indexed coordinates is just to project 
native coordinates onto a 1-dimensional space:

  int map_to_index_pos(int map_x, int map_y)
  {
    int nat_x, nat_y;

    map_to_native_pos(&nat_x, &nat_y, map_x, map_y);
    return nat_x * map.ysize + nat_y;
  }

Using indexed coordinates for savegames is fine, but doesn't have any 
advantage that I can see - and it's disadvantages are that savefile 
compatibility is broken and savefiles become less human-readible.

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

it is several times more complex when done in map coordinates.

Other topology operations include is_border_map_pos, is_normal_map_pos, 
is_real_map_pos, whole_map_iterate, etc.  All of these are hard to do in 
map coordinates.

is_normal_map_pos, is_real_map_pos, and normalize_map_pos are all different 
facets of the same operation, so they may be defined in terms of each 
other.  Currently we have both other functions call normalize_map_pos; this 
is quite inefficient (although it probably doesn't matter much).

>> > AFAIK there is no sane way to represent an iso-map in the
>> > 2d layout we have in savegames?!
>>
>> 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?!

Yeah, the least ugly way I can think of is to have a basic topology with a 
mask on the normal set.  This means refining some of the operations (since 
indexed and native coordinates can become sparse), but is not too much of a 
stretch.

There is really no other sensible native or index numbering system that I 
can think of...

jason