[Freeciv-Dev] Re: topology RFC (again)

[Jason Dorje Short <vze2zq63@xxxxxxxxxxx>]

"Ross W. Wetmore" wrote:
> 
> Jason, the only fallacies are the ones you keep dreaming up. You
> can't keep redefining things so the world is theoretically broken, or
> misinterpreting them in twisted ways just to try and show something
> is wrong that needs your solution, or expect that that carries back
> as proof that reality is out of sync with you.

Since you probably won't be able to respond for a week, I won't be too
argumentative.  But I strongly disagree. :-)

> To quickly summarize the key points ...
> 
> The unnormalize example used a rectangular shape. And if you work
> your way through it you will see it does exactly what is needed.
> You clearly haven't understood it because you get the wrong results
> in your examples. The shape it uses is a map-sized rectangle. Both
> the GUI and the map/memory use the same basic context.
> 
> As you say there is a second "shape" that may be needed to handle
> isometric - if you choose to work in an isometric coordinate space
> that skews things relative to the target memory or GUI. You should
> work out the wrapping conditions for this shape and what it looks
> like in iso coordinates and plug them into an iso algorithm similar to
> the unnormalize one. The shape will be a map-sized isometric rhomboid
> or paralleogram which is what GUI rectangular coordinates project to
> in iso.

Look over my examples again.

The first one showed that unnormalize_map_pos must use a rectangular
representative set, not one corresponding to the "normal" representative
set.  So we agree on this.

The second one showed that we need a different set - an isometric one -
for an isometric-view GUI to be able to use it.  This could be handled
either with an extra parameter to the function or with a new function
("unnormalize_map_pos_iso", I guess you'd call it).  So we agree on
this.  2 out of 3 ain't bad!

The third example showed that without giving dimensions to the set, it
will sometimes fail to find to find a position that you are looking
for.  Or, as I said before: "we don't just want a subset of a
representative set, we want a different representative set".  Here's a
simple example: suppose we have an overhead-view GUI.  It calls
unnormalize_map_pos to wrap positions into a representative set with the
following shape:

# # # # #
# # # # #
# # # # #
# # # # #
# # # # #

But, suppose the GUI window has the following shape:

# # # # # # # #
# # # # # # # #
# # # # # # # #

In this case, it is quite possible that an position along one of the
bottom two rows of the representative set would actually have wrapped to
be in one of the right three columns of the GUI window.  But if we only
use clipping, we'll never know this.  The full example I gave showed a
case where this happens using an iso-rectangular torus map; it can also
happen using a flat-rectangular torus map and isometric view.

> The "shapes" are of fixed size defined by the fact that they
> include a complete set of unique coordinates which is useful to
> think of as a N(*,*) set. Don't confuse yourself by trying  to
> figure out what the *,* means - it is just a label, not geek bits.

Nit: The sets can't be of *fixed* size, because the wrapping of the
topology will work in different ways.  We can try to fit them to a
rectangle (or iso-rectangle); certainly they will all fit within an
rectangle of size xsize x ysize but will often fit into a smaller
rectangle (as in an iso-rectangular torus).  In this case, we'd want to
choose a shape as close to as a square as possible (IMO).

More importantly, I'm very dissatisfied with these names.  N(*, *) is a
complete misnomer since it implies some relationship to the "normal" set
where none is there.  The normal may not every be any of the N(*, *)
sets.  How about we call it a "representative set P".  If you don't like
this, please suggest some other name.

Also, the naming of functions is no good.  normalize_map_pos_[rect|iso]
implies a normalization, which is not what's happening. 
unnormalize_map_pos_[rect|iso] implies an "unnormalization", which isn't
what's happening (normalization isn't 1-1 so it can't be inverted). 
What we're really doing is wrapping (x, y) to be within a representative
set that we specify.  If we were willing to change all existing
terminology, we could call this "normalization" and just stick to
"proper" for the other direction, but as you say this is to difficult
:-).  So I am out of naming ideas.  If it really comes down to it, I
suppose "unnormalize" is better than "normalize".

> You may have to be clever to figure out just how you need to represent
> this wrapping or unwrapping algorithm. It is actually the same thing.
> If you feed in (0,0) for (x0,y0) for the rectangular case this should
> be clear, as it reduces cleanly to the simple normalize we have become
> accustomed to. When you work out the (un)normalize_iso_pos() they
> should have similar relationships that you can use to check.

No.  unnormalize_map_pos(&x, &y, 0, 0) is not the same thing as
normalize_map_pos(0, 0).  Normalize map_pos wraps (x, y) into the normal
set, which need not correspond to any particular representative set that
unnormalize_map_pos wraps into.

Take a look at the normalize_map_pos_[iso|rect] from my "general
topology" patch.  (Aside from the width/height parameters, these are the
equivalent of your unnormalize_map_pos function.)  Although we're just
doing simple linear-algebra operations, the arithmetic is very, very
ugly.  And the implementation isn't even correct (it doesn't fit the
"wrap-to-a-square" criteria specified above).

So, you're right.  To implement unnormalize_map_pos you will have to be
clever and very good at arithmetic.

> If you used an iso shape for the simple rectangular case, then it
> wouldn't be useful for the sort of memory access things that the
> regular normalize gets used for or the rectangular GUI requirements.
> 
> But that is perfectly fine. You use the right shape for the end use
> you need at the moment. Using the wrong one doesn't say the idea is
> bad, just that you haven't correctly understood it or applied it.

Note: at no point does FreeCiv use "isometric" coordinates.  They are
used in internal calculations - converting an isometric-view (map_x,
map_y) position to a (canvas_x, canvas_y) canvas position and within the
topological functions in my general topology patch - but they are never
stored or bandied about.

So, this isn't a problem.  At some point it may become useful to do more
with the isometric coordinates, but for now we just determine them from
map coordinates every time we need them.


> Note, if I were trying to "wrap" a point into a shape defined by the
> parallelogram below, and wasn't quite clever enough figure out how to
> wrap in parallelogram coordinates, I might be just as happy to find
> the point in a pure rectangular set whose relationship to the final
> parallelogram shape was clearly understood. So if I came up with
> a point at "1" (somewhere in the triangular non-overlapping bit),
> after doing my simple unnormalize, I would know that I needed to do a
> final operation to come up with point 2 to complete the unnormalization.
> 
>       /        /
>     -+--------+-
>     /|       /|
>    /2|      /1|
>  -+--+-----+--+-

Fortunately, the calculations are actually quite easy when you think in
terms of isometric coordinates.  So this isn't necessary.

> One could just as easily choose the parallelogram form to store the
> map tile data. This would require the current normalize_map_pos() to
> use such an algorithm to return "normal" coordinates in this admittedly
> abnormal programming model.
> 
> Of course, this is half way to the iso case, right?

A parallelogram can be used to store an isometric map, but the wrapping
calculations become much harder.  It is only easy to wrap in one
direction, and it will not work for flat-world isometric maps (since the
map is the wrong shape).  (Note: when iso-rectangular maps were first
proposed, this is how Thue wanted to handle them.  I think he had only
considered the single-wrapping case.)

> Also note that the rectangular does *not* correspond to your "regular"
> coordinates for this system. Regular coordinates would have at least
> two extra triangles of data in the way you like to do things. The
> rectangle is a proper N space object and is useful because of this.
> Your regular shape here is not, and is correspondingly useless for
> any of these operations.

"The way I like to do thing"???

If you were to write a whole_map_iterate over this set, how would you do
it?  There are two possible ways that I see:

for (y=0; y<map.ysize; y++)
  for (x=map_min_x(y); x<=map_map_x(y); x++) {
    /* ... */
  }

or

for (y=0; y<map.ysize; y++) 
  for (x=0; x<map.xsisze; x++)
    if (is_normal_map_pos(x, y)) {
      /* ... */
    }

Note that there are some places in FreeCiv that *must* use the second
form because they must loop over rectangular regions (for instance the
debugging stuff in game.c; savegame code also uses this because it makes
the calculations easier).  The only advantage of the first form is that
it might be faster.  Places that use a whole_map_iterate shouldn't care
about this, though, so whole_map_iterate might as well use either one. 
But since map_min_x and map_max_x aren't written and is_normal_map_pos
is, i've stuck to the second form for now.

I'll say it again: I didn't invent the "regular" set.  I just invented
the idea that it's different from the "normal" set.  Outside of my
changes, all of FreeCiv just loops over the "regular" set and assumes
it's looping over the "normal" set (of course, it's right since
regular==normal for the current topology).

jason