[Freeciv-Dev] Re: to wrap or not to wrap?

[Jason Dorje Short <vze2zq63@xxxxxxxxxxx>]

"Ross W. Wetmore" wrote:
> 
> At 01:01 AM 01/10/13 -0400, Jason Dorje Short wrote:
> >"Ross W. Wetmore" wrote:
> >>
> >> At 11:39 AM 01/10/10 -0400, Jason Dorje Short wrote:
> >> >Raimar Falke wrote:
> >> >wrap_map_pos(&x, &y) takes the vector (x, y) and physically wraps it
> >> >into its proper position.  It is independent of (x, y) being real, so it
>                                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> >> >will only work for topologies that wrap "regularly".  However, the fact
>    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> >> >that it'll work on any position or vector makes usage much simpler.
> >> >
> >> >For a real position, it will have identical effect to
> >> >normalize_map_pos.  For an unreal position, it will wrap the coordinate
> >>                                                      ^^^^^^^^^^^^^^^^^^^
> >> >normally just as if it were real (which is only possible under a limited
> >>  ^^^^^^^^  i.e. do bogus transformations of gaming coordinates.
> >
> >The transormation is not "bogus" if we define topologies as Gaute has
> >proposed; i.e. such that equivalence classes of coordinates are defined
> >as differing by a linear combination of given vectors.  It's a bit of a
> >tautology, but if we are willing to limit our topologies in this way we
> >can make the conversion a lot easier.
> 
> Unfortunately this does not work for the standard cylinder map. And it
> does not allow you to decouple the wrapping in x and y to handle the
> rectangular 4 set trivially.

Yes, it does.

For a theoretical argument, see:
http://arch.freeciv.org/freeciv-dev-200110/msg00385.html.  I'll also
explain it (hopefully) more understandably below.

For a practical example, check out this code:

void wrap_map_pos(int *x, int *y)
{
  if (wrap_in_x_direction) {
    while (x < 0) x += map.xsize;
    while (x >= map.xsize) x -= map.xsize;
  }

  if (wrap_in_y_direction) {
    while (y < 0) y += map.ysize;
    while (y >= map.ysize) y -= map.ysize;
  }
}

> You *cannot* wrap to a "normal" position first, then start thinking about
> what restrictions you might want to put on. That is the reason why Gaute
> is wrong, and why the initial Freeciv hacks to deal with unscrambling
> things after the eggs were turned into omelet were so endemic and
> un-generalizable.

One problem, and the reason why this code (with the extra assumption) is
helpful is that the eggs are already in an omelet.  Unscrambling the GUI
code will be a major undertaking.

> And all the wonderful algebraic noise is not particularly useful since
> it is not applicable to the problem that needs to be dealt with here.
> It clearly is just obscurring that.

No, you just don't understand the algebra (Gaute's not very good at
explaining it, for one thing).  It's quite applicable, I assure you.

> >Personally, I now believe the use of wrap_map_pos (with the added
> >restriction to topologies) is a good intermediate step; at least it will
> >allow us to convert the code to entirely use one set of constructs
> >(wrap_map_pos) before we set about a full cleanup.  The "full cleanup"
> >will be very difficult.
> 
> You are wrong ... on all counts, as has Gaute been since the summer.

Gaute's problem was that he took an assumption (that wrapping will be
done in a linear-algebra way) as a given.  This assumption is not
needed, but if we make it then the wrap_map_pos() function is quite
valid.

> Think it through all the way first before you start implementing.
> Especially when you have 1) someone telling you that this is bad,
> 2) a working practical implementation that handles everything fine
> at levels beyond where you are currently limiting yours to.

Actually, the current implementation is almost exactly a special-case of
this assumption.  Calling x=map_adjust(x), which is done practically
everywhere, is the equivalent of calling wrap_map_pos(&x, &y).  The
problem with the current code is that it fixes the direction of
wrapping.

> Just concentrate on fixing things using normalize_map_pos() which
> internally deals with any topology issues like wrap conditions for
> coordinates separately. Get Flat-earth through torus working cleanly
> and then the true isometric flavour in all these modes. This is the
> real set of problems of the moment.

Well, that's what I am doing at the moment.  Unfortunately, we're about
to hit a big wall in the GUI code which cannot be fixed in this way
without major restructuring.

> After that weird diamonds and such with all kinds of limitations may
> be easier to deal with because the code will be consistent and
> work through a well defined interface as a starting point.

This interface is well-defined, it's just more restrictive.

> >> >set of topologies).
> >> >
> >> >Like I said, it is confusing and will probably lead to misuse.
> >>
> >> I don't see any real use for this. Perhaps you could give the example
> >> (again if I missed it). I think it is more than confusing, I think it
> >> is fundamentally wrong to think of a topology unaware 2-D wrap.
> >
> >Again, so long as you define the topology as always wrapping in the same
> >way it is acceptable.  To use vague mathematical terms, we're taking
> >advantage of linear algebra here instead of just plain set theory.
> 
> Always wrapping 2D topologies == torus. None of the other current
> flavours of rectangular coordinates including standard CIV are supported
> by this so it isn't of much real use.

No, you misunderstand.

What follows is a somewhat mathematical explanation (although you don't
appear to put much stock in such explanations).

My basic idea of a topology, as described in my RFC post, is that we
define different coordinate sets to be equivalent (that is, we define an
equivalence relation on the plane ZxZ).  For instance, under the current
wrapping system (x, y) is equivalent to (x+map.xsize, y), in fact it's
equivalent to (x+n*map.xsize, y) for any integer n.  For each set of
equivalent positions (equivalence class), we set one position to be the
"normal" or "proper" position.  For unreal positions, this doesn't apply
- you can't wrap an unreal position (see my previous post with an
example topology); in fact you might as well consider all unreal
coordinates to be equivalent.  Under this mathematical system, the
wrap_map_pos() function has no validity.

Gaute's idea of a topology is slightly different.  He assumes a linear
algebra approach; in this system two coordinates are equivalent if they
differ by a linear combination of some given set of vectors.  For
instance, under the current topology there is just one element to this
set of vectors: (map.xsize, 0).  This means that two points (x, y) and
(x1, y1) are equivalent if x=x1+n*map.xsize and y=y1 (for any integer
n).  The same system can apply to a torus: now the set of vectors is
{(map.xsize, 0), (0, map.ysize)} since the torus wraps in both x and y
directions.  Now (x, y) and (x1, y1) are equivalent if x=x1+n*map.xsize
and y=y1+m*map.ysize (for any integers m and n).  It will likewise apply
to a non-wrapping map (the set of vectors is the empty set {}) or to an
isometric rectangle, cylinder, or torus.  It will NOT apply to a mobius
strip, klein bottle, or any of the "approximations of a sphere" that
have been proposed; these are all impossible under Gaute's system.

The main advantage of Gaute's system is that it allows use to separate
wrapping from realness.  Even an unreal tile can have a "proper"
position that is the wrapped version of the coordinate.  For instance
under the current system the coordinate (-1, -1) can be said to be
equivalent to (map.xsize-1, -1).  Both are unreal, of course, so from a
mathematical perspective this doesn't do you any good.

From a practical perspective, though, the wrap_map_pos() function is
extremely useful.  Since things are already implemented in this sort of
way, it makes converting the client code to the new system much easier. 
Code that would require major restructuring to work with juse
normalize_map_pos() and the like can be fixed much more easily with
wrap_map_pos().  For instance, the following code

static int get_canvas_xy(int map_x, int map_y, int *canvas_x, int
*canvas_y)
{
  if (map_view_x0+map_canvas_store_twidth <= map.xsize)
    *canvas_x = map_x-map_view_x0;
  else if(map_x >= map_view_x0)
    *canvas_x = map_x-map_view_x0;
  else if(map_x < map_adjust_x(map_view_x0+map_canvas_store_twidth))
    *canvas_x = map_x+map.xsize-map_view_x0;
  else *canvas_x = -1;

  *canvas_y = map_y - map_view_y0;

  *canvas_x *= NORMAL_TILE_WIDTH;
  *canvas_y *= NORMAL_TILE_HEIGHT;

  return *canvas_x >= 0
      && *canvas_x < map_canvas_store_twidth * NORMAL_TILE_WIDTH
      && *canvas_y >= 0
      && *canvas_y < map_canvas_store_theight * NORMAL_TILE_HEIGHT;
}

cannot be written in terms of normalize_map_pos().  However, it can
easily be written in terms of wrap_map_pos:

static int get_canvas(xy(int map_x, int map_y, int *canvas_x, int
*canvas_y)
{
  map_x -= map_view_x0;
  map_y -= map_view_y0;
  wrap_map_pos(&map_x, &map_y);
  *canvas_x = map_x * NORMAL_TILE_WIDTH;
  *canvas_y = map_y * NORMAL_TILE_WIDTH;
  return map_x >= 0
         && map_x < map_canvas_store_twidth
         && map_y >= 0
         && map_y < map_canvas_store_theight;
}

The reason wrap_map_pos works while normalize_map_pos doesn't is that
the "position" that's being wrapped isn't really a position at all; it's
just a random vector expressing the difference between (map_x, map_y)
and (map_view_x0, map_view_y0).  But wrap_map_pos will handle it just
fine by wrapping it in only the correct (valid) directions.

> Vague mathematical terms just means it is a great theory, but has no
> immediate practical applicability. I have refereed enough papers for
> scientific journals to recognize the argument and discussion technique :-).

I hope I have given a valid practical reason as well.

> >The "use" for it is that it makes cleanup of the GUI code much, much
> >easier (see my previous overlong patch that allowed map wrapping in the
> >opposite direction).
> 
> The GUI code is a separate issue. It deals with a very specific flat-earth
> type window object that can be thought of as floating over a game map.
> And in this case the GUI coordinates are both clipped equivalently.
> 
> Note that while the game coordinates may wrap to give you the effect
> of continuous scrolling in a given direction, the GUI ones never do.
> 
> The issue of transforming one set of coordinates to the other is not a
> "generalized coordinate system" problem. But it is the GUI problem.

The problem is exactly that the GUI does not behave in this manner. 
It's not just a flat window sitting over a wrapping world; the
coordinates in the window itself are being wrapped (as above).  If it
were otherwise, then we'd just take our window coordinates (window_x,
window_y), adjust them to map coordinates (map_x, map_y), and call
normalize_map_pos() to see what we had at that position.  This would be
the better solution, but unfortunately (1) it will require a significant
overhaul to achieve this and (2) we will need to do some additional
tricks to make sure we don't draw a tile more than once (since the
flat-earth window knows nothing of the underlying topology) [2].

If you don't believe me, please prove me wrong by fixing the GUI to work
with your system.  You may use only existing topology functions
(normalize_map_pos, is_real_tile, nearest_real_pos, and
is_normal_map_pos).

> The game map coordinates are something one would like a general system
> for, but it is very unlikely that the GUI and game systems will ever
> be one and the same, so there are always going to be transformations
> using techniques like clipping and wrapping for the specialized
> transformation code.
> 
> And until you and Raimar, really internalize the concept that the GUI
> coordinates and the game coordinates are two separate systems dealing
> with two fundamentally different objects, you are going to continue to
> confuse and amalgamate the two into a very broken Freeciv omelet.

Like I said before, the omelete is there.  We can either deal with it as
it is or unscramble it.  But right now, the GUI coordinates are NOT
separate the way you claim they are; they are quite intertwined with the
map coordinates.

> >> Put another way, I can see the corresponding clip_map_pos(&x,&y) being
> >> used in certain kinds of GUI operations that draw into a fixed window
> >> object. This is because GUI window pixel coordinates are non-wrapped
> >> in both directions. But one would never wrap such coordinates in the
> >> same way.
> >
> >I don't understand.
> 
> Then think on it some more ...

I don't understand what clip_map_pos() does.  Surely you can explain
this much?

> >> Or, yet another flavour, I can see independently wrapping or clipping
> >> individual coordinates as suboperations in certain specialized code that
> >> knows exactly what it is doing, but I don't see use for a generalized two
> >> coordinate function.
> >
> >Huh?  You cannot wrap coordinates individually.
> 
> Sorry, the current code does this all over the place. Which has been
> part of the current problem. And a cylinder needs to wrap in only one
> of its 2 coordinates, so clearly this is also a required part of the
> current Freeciv system.
>
> But, I'll let you take this impromptu comment back ... :-)

Touche [1].

But, we both agree the current system is broken as far as general
topologies go.

> >And any such
> >"specialized code", no matter how little it is used, must go into
> >map.[ch] so that it can be easily adjusted to handle alternate
> >topologies (case in point: nearest_real_pos).
> 
> Specialized code goes where specialized code needs to go. By definition
> it is not general and so your concern for trying to make it fit
> general topologies is admirable but misplaced.
> 
> To make this easier for you to swallow, specialized code might be a
> "subclass" that handled a particular specific topology. Only the class
> interface needs to be in map.h.

This would make the job much, much harder.  There is so much GUI code
that changing it for every topology is not practical.  Additionally, I
believe it is fundamentally very, very flawed.

> You are getting there. I don't mean to dampen your enthusiasm, but you
> aren't there yet. And I am sure you will in a couple more iterations.

Right now we are making straightforward changes.  But as I said before,
we will soon hit a point with the GUI code where we will have to decide
what to do.


[1] This word looks really ugly without the accent!

jason