[Freeciv-Dev] Re: Native Coordinates [Was:[PATCH] Map cleanups (PR#1208)

["Ross W. Wetmore" <rwetmore@xxxxxxxxxxxx>]

At 05:49 AM 02/01/10 -0500, Jason Short wrote:
>Ross W. Wetmore wrote:
>
>> At 03:43 AM 02/01/09 -0500, Jason Short wrote:
>> 
>>>Ross W. Wetmore wrote:

>If native coordinates had been implemented before the regular system was 
>developed, things might have gone differently (or maybe not).  But since 
>you implemented native coordinates as a reaction to the "regular" 
>system, this was impossible :-).

I'm glad we have reached the nub of it, that this is an ego thing on
your part, and technical merit or value to Freeciv code is not a strong 
part of your solution. Hopefully you can overcome this though for the
good of Freeciv :-).


Native was implemented as the natural way to go about this with a solid
conceptual underpinning. That it is cleaner, more efficient, less
intrusive on the code base as well as more generally flexible has a lot 
to do with its development process and the thought that preceded it.

Native isn't a set of coordinates, it is a conceptual recognition of one 
of the natural interfaces. In the standard map, (native == map == regular).
But once you have found and split the map from the topology along the 
interface lines, things become much cleaner and easier. 

Because you have refused to split regular out in the same way, but are 
using it in a way that rewrites and expands standard until it holds 
everything, you end up in a woefully inefficient loop all the time 
selecting the small subset that is useful. You gain nothing from this 
except for some fuzzy feeling you have a general way to spend CPU cycles.

Native changes involve two coordinate transformations per topology, and 
the insertion of these into global operations that need to convert to map 
coordinates at some point. It really is simple. It really is effective. It 
really is no harder than looking for places to convert 2-D map coordinates 
to use linear map_indexing.

Regular was a hack, rushed in with all kinds of weird things like
 regular_map_pos_is_normal(1) 
and other unexplained and intrusive code inserted in many different
places. 

It has no concept behind it, it required/requires major surgery to core 
Freeciv map elements and operations, in its best case it introduces an 
inefficiency factor of 2 but goes up from there. It is completely
inflexible because it is hardwired to the standard map coordinates
in code with no interface to distinguish it or change it. You tout this
as a feature. It really marks your conceptual failure here.

Thus you are never going to break the (map == regular) constraint in the 
way (iso native != map) has made the sorts of simplifications you admit
are real. That you refuse or are incapable of recognizing this extends 
beyond this undeniably proven case in spite of the explanations is a 
problem that will just come back to plague the next discussion and the
one after it. You need to shake off your biases and be able to accept
and improve on your work by accepting a few hard truths.

But you are right that anything that reduces the regular hack and the
gross inefficiencies it builds into the system is always going to be
a preferred solution. Any unbiased programmer that looked into the 
issues would welcome any serious effort that could improve on it. They
would not want to see it damage the codebase any more.

>> But I agree, it will open the door to lots of fixup patching :-).
>
>Only a little, I think.  And it will be easier to justify the fixups 
>then because they will actually gain something (efficiency).

How about we just do it correctly *and* efficiently the first time.

>Ok, I think the squabbling has gone on long enough.  Here is what I 
>propose.  As I see it, there are just a few pieces of cleanup necessary 
>to implement iso-rectangular maps:

The zeroth step really is removing regular from the codebase and discussing
how it really should have been done.

Sorry, this is one of the major impediments to actually making progress.

If you look at the corecleanups, you will see that most of the global
and topology code is smaller in size, simpler in form, faster in execution
and easier to understand. 

There is simply no point in discussing a find_representative_map_pos()
vs unnormalize_map_pos() when one in a scrambled mess of things that you
refuse to simplify or discuss because that would involve talking about
native coordinates.

If you choose the proper coordinate representation and separate the
layers of find_*() you will end up with unnormalize. Your unwillingness
to consider such things is not going to make the discussion of much use.


>1.  find_representative_map_pos/unnormalize_map_pos.  We have to agree 
>to something on this.

There are two conceptual and religious (on your part) barriers here.

The first is the split into layered steps that involve pure concepts.

The second is the use of alternate representations.

This can be native coordinates to reduce the complexity of a step like 
topology operations, or what GUI coordinates are really about and how 
clipping at the end allows one to deal with things like EXTRA_BOTTOM_ROWS 
and in a flewxible/clean manner.

>2.  mapgen changes.  You had wanted to do this; now is the time IMO.  My 
>only request is that there is at least one map generator that is 
>topology-independent, and that the code fall back upon this one if 
>necessary (rather than segfaulting as it will do with no changes).

Mapgen is complete and working. The issue here is upgrading CVS to
the point where it supplies the necessary macro tools so that it 
can be dropped in.

The other alternative is to leave those tools in mapgen as was done
in the earlier May-June versions. But the corecleanup was supposed to
accomplish this at the same time it stabilized the core and converted
most of it to iterator macros and other such interfaces.

>3.  miscellaneous changes.  There are just a few of these (like the 
>vnotify_conn_ex thing), and they should (but generally aren't) 
>straightforward.

They are simple. That they are being used as vehicles for promoting
other agendas is where they run into difficulty. You can still go for
the simple bug fix without the extra baggage and it will be fine.

>4.  the map overview.  This depends on #1, and will probably require 
>extensive discussion.

Actually, corecleanups implements the overview in native coordinates.
This means that true isometric maps are properly rectangular, so fit
the overview canvas topology. Also since this is a global view that
does a whole_map_iterate, it is efficient and involves no bounding
box issues or odd rotations. Computations are simple in x and y 
coordinates - always, and for all topologies. 

There is a wrap operation (trivial in a native space) that positions 
the centerpoint of the map canvas in the center of the overview for
cases where the topology wraps in X. Otherwise the overview is not
shifted as in a Flat-Earth scenario. 

So, no you don't need to resolve #1 for this.

>5.  the topology system; i.e. a global topology struct or ID, plus code 
>to transfer it server->client and store it in the savegame, plus 
>capabilities and other necessary backwards-compatibility, plus code for 
>specifying it as pre-game server options.  This doesn't depend on any of 
>the above, although it doesn't make sense to introduce it much before 
>we're ready for #6.

Since this adds a single int value to the map struct if you use an
index and no changes to any other part of it unless you fully implement
regular and usurp these current uses, it is something that can go in
with minimal impact. 

One can also add all the topology definitions and macros, with the index 
defaulted to standard earth map so any of the actual cleanup of functions 
like unnormalize or map_distance_vector can all be introduced and the 
hardcoded parts of Freeciv switched to the interface format.

>6.  the iso-rectangular topology itself, implemented as changes to the 
>backend topology functions plus necessary additions to the topology 
>system (i.e. new values for the topology struct/id).  This depends on 
>all of the above.

The core elements can be installed without impacting the GUI in a 
properly layered system. This is afterall just a map, and the fact 
that some elements are in different places on it doesn't really change
things.

You will not be able to use it in all views, or with proper features
like scrolling in the Y direction until the GUI parts are updated.

>Only #4 has any chance of introducing further regular map coordinates, 
>and I'm sure there will be extensive discussion about that.

Actually there shouldn't be any problem with #4. It is #0 that will be
the good show :-).

>  In the 
>meantime, we can introduce any other desirable changes as well - as I 
>said, I will support a patch that (correctly) provides native 
>coordinates, although there is no use for them yet (it makes more sense 
>IMO to focus on index/linear positions first).

How about working together to define what the shape of that should be.

It would be a useful educational process for you, and would hopefully
reduce the level of spurious noise and bickering if you felt you had 
some part in it, I'm sure :-).

We could move on from there to using them to simplify unnormalize or
whatever.


As a start, here are the transformations from the current two topologies
(compact iso, standard) to map coordinates. The macro forms are almost
identical.

/**************************************************************************
Convert from standard map to compact native coordinates
Note: explicitly handle odd x to force round down, even when negative
**************************************************************************/
#undef map_to_native
int map_to_native(int *px, int *py, int mx, int my)
{
  if( get_maptype(MAP_TYPE_ISO) )
    *py= (mx + my - map.xsize), *px= (mx + mx - *py - (*py & 1))/2;
  else
    *py= my, *px= mx;

  return TRUE;
}

/**************************************************************************
Convert from compact native to standard map coordinates
Note: explicitly handle odd x loss in the compression
**************************************************************************/
#undef native_to_map
int native_to_map(int *pmx, int *pmy, int x, int y)
{
  if (map_type & MAP_TYPE_ISO) {
    *pmx= (y + (y & 1))/2 + x;
    *pmy= y - *pmx + map.xsize;
  }
  else
    *pmy= y, *pmx= x;

  return TRUE;
}


And here is the fully general normalize_map_pos() that uses them to
keep things looking pretty much like the original freeciv code. The
versions using "%" are faster and just as good, but this is the
function version that used more lines of code so was simpler for
most to accept.

Note this is general to any system where the equivalence relations
between points involve 2-D wrapping vectors. Seriously, the axes
need to be orthogonal, or the operations are multi-valued and in
most cases anything will wrap into anything else leaving you with
a 1 tile map.

/**************************************************************************
Normalizes the map position. Returns TRUE if it is real, FALSE otherwise.
**************************************************************************/
#undef normalize_map_pos
int normalize_map_pos(int *x, int *y)
{
  if( !is_real_tile(*x, *y) )
    return FALSE;

  /* normalization is best determined in native coordinates */
  map_to_native_pos(x, y, *x, *y);
  if( has_mapwrap(MAP_TYPE_WRAPX) && !RANGE_CHECK_0(map.xsize,*x) ) {
    /* In the normal case the while body doesn't execute, and on border
     * tiles this should happen only once, and occasionally twice.
     * Worry about (rare) multiple loops for safety, not performance. */
    while (*x < 0)
      *x += map.xsize;
    while (*x >= map.xsize)
      *x -= map.xsize;
  }

  if( has_mapwrap(MAP_TYPE_WRAPY) && !RANGE_CHECK_0(map.ysize,*y) ) {
    /* In the normal case the while body doesn't execute, and on border
     * tiles this should happen only once, and occasionally twice.
     * Worry about (rare) multiple loops for safety, not performance. */
    while (*y < 0)
      *y += map.ysize;
    while (*y >= map.ysize)
      *y -= map.ysize;
  }

  /* Now map things back to standard map coordinates */
  native_to_map_pos(x, y, *x, *y);
  return TRUE;
}                                                                             


This is the SAVE_MAP macro without the regular hacks. In most
cases I change the variable names to xn - native or xm - map
where the functionality split occurs and both are required.

In this case it is an explicit whole_map_iterate loop that is
hardcoded to preserve the order. But whole_map_iterate is just
the three lines that would replace this.

  for (WMI_y_itr = 0; WMI_y_itr < map.ysize; WMI_y_itr++)   
    for (WMI_x_itr = 0; WMI_x_itr < map.xsize; WMI_x_itr++) 
      if (regular_map_pos_is_normal(WMI_x_itr, WMI_y_itr)) {

(map.xsize,map.ysize) would be (50,80) in native and (130,130)
in the regular versions for a true isometric rectangle.

The real problem with this is the dependency on user code 
through the get_xy_char element which "understands" that
map coordinates are looping in x and y. You need to run the
normalize check before entering the if-clause where they might
be used. It also catches the unreal positions from filtered
realness. is_real_tile() is really a valid replacement here
because no normalization should ever be required by definition.
But in this case normalize_map_pos() is just as efficient.
Paranoia says use it in case someone does something stupid or
the logic hasn't covered all cases here. 

/*
 * This loops over the entire map to save data. It collects all the
 * data of a line using get_xy_char and then executes the
 * secfile_insert_line code. The macro provides the variables x and y
 * and line. Parameter:
 * - get_xy_char: code that returns the character for each (x, y)
 * coordinate.
 *  - secfile_insert_line: code which is executed every time a line is
 *  processed
 */

#define SAVE_MAP_DATA(get_xy_char, secfile_insert_line) \
{                                                       \
  char *line = fc_malloc(map.xsize + 1);                \
  int x, y, xn, yn;                                     \
                                                        \
  for (yn = 0; yn < map.ysize; yn++) {                  \
    for (xn = 0; xn < map.xsize; xn++) {                \
      native_to_map_pos(&x, &y, xn, yn);                \
      if (normalize_map_pos(&x, &y)) {                  \
        line[xn] = get_xy_char;                         \
        if(!isprint(line[xn] & 0x7f)) {                 \
          freelog(LOG_FATAL, "Trying to write invalid"  \
                  " map data: '%c' %d",                 \
                  line[xn], line[xn]);                  \
          exit(1);                                      \
        }                                               \
      } else {                                          \
        /* skipped over in loading */                   \
        line[xn] = '#';                                 \
      }                                                 \
    }                                                   \
    line[map.xsize] = '\0';                             \
    secfile_insert_line;                                \
  }                                                     \
  free(line);                                           \
}



         

>jason

Cheers,
RossW
=====