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

[Jason Dorje Short <vze2zq63@xxxxxxxxxxx>]

There are three practical examples down below.  If you get bogged down,
skip on down to them.

"Ross W. Wetmore" wrote:
> 
> At 04:25 AM 01/10/30 -0500, Jason Dorje Short wrote:

> >Now for a full explanation...
> >
> >You have labeled N(0, 0) to mean the "normal" set.  Currently this is
> >the same as the regular set:
> 
> Let's just stick with normal for now and ignore this newfangled
> regular invention :-).

Without understanding the distinction, you cannot understand the
problems the code now faces.

> The twin problems are how to "normalize" coordinates to THE normal set.
> And how to reverse this process to find their value in some other set.
> While there are lots of arbitrary sets to the theoretical mind, for
> practical purposes we will always want one that gives us useful offsets
> from particular point, e.g. the point corresponding to the origin of a
> floating GUI wiondow for instance.

The "process" cannot be reversed as easily as you claim.  A "floating
GUI window" will require a set that corresponds to its layout: a
rectangular set for an overhead view, an iso-rectangular set for an
isometric view.  These are different from each other, and may both be
different from "the" normal set of coordinates.

So, we may ignore the general case of representative sets, but we can't
just label a representative set as "the set we want" and be done with
it.  We have to define its properties.  This is exactly what
normalize_map_pos_rect and normalize_map_pos_iso are intended to do.

See below.

> >Again N(0, 0) doesn't include the point (0, 0) so we have to come up
> >with yet another definition:
> 
> Who cares if it contains the point 0,0? If this is what you are
> spending all your time fighting, or think that defeating this strawman
> wins some other argument, you are arguing with yourself.

To quote you from before: "unnormalize_map_pos(&x, &y, x0, y0)
unnormalizes the coordinates to the particular N(*,*) that includes the
point (x0, y0)".

Since this is how you defined N(*, *), I have used it to help explain
that N(*, *) cannot be clearly defined.

> N(0,0) is a label that identifies a particular 2-D set. If it helps
> think of the two values as indices. The key concepts of one of these
> sets are that all unique coordinates are represented exactly once
> in such a set, and that equivalent coordinates are separated by a
> multiple of some constant like map.xsize.

Note: equivalent coordinates need not be separated by a multiple of some
given vector.  This is exactly the assumption we have tried to avoid by
not using wrap_map_pos.  (However, in all topologies realistically
considered so far this is the case.)

> >So, in summary there are two reasons why the N(x,y)/unnormalize_map_pos
> >system will not work:
> >
> >1.  It is impossible to uniquely and intelligently define a set N(x,y).
> 
> I don't have any problems with this, I just pick one and ignore the rest :-)

So how do you pick one?  How does the GUI overhead view use it?  How
does the GUI isometric view use it?

> >In the absence of a general definition, we have to choose specific (not
> >particularly unique) definitions for each topology, and the calling code
> >must be aware of them.
> 
> Actually choosing something that is useful, does sort of get the job
> done. And there is no reason why the calling code can't indicate
> some preferential form of the set by setting a "context" value if
> there are different choices available for different jobs.

Choosing one set that is useful will not work, because there are a large
number of sets that might be useful, and no way to know which is desired
without extra information.

There are exactly two forms that the representative set must take:
rectangular (for the overhead view) and isometric (for the isometric
view).  Both must be bounded by given parameters (width and height); if
necessary they will stretch in one direction rather than overflow in the
other.

If we use a "context" value (i.e. a parameter to the function) to
indicate this data, that accomplishes the same thing.  What matter if we
use:

int normalize_map_pos_rect(int *x, int *y, 
        int x0, int y0, int width, int height);
int normalize_map_pos_iso(int *x, int *y,
        int x0, int y0, int width, int height);

or

struct map_context {
  int x0, int y0;
  int width, int height;
  int iso;
}

int find_representative_set(int *x, int *y
        struct map_context map_context);

?

You may pick one over the other - I don't have a preference.  (And note
the naming is not an issue here; we can also rename the functions as
desired.  normalize_map_pos_[rect|iso] was named before we completely
agreed on the nomenclature, so a renaming would be appropriate.)

> >2.  The position returned by unnormalize_map_pos will lie within a set
> >N(x0, y0).  This set will have a shape that is unique to the underlying
> >topology, and has no special significance outside of it.
> 
> Unless you ignore this theoretical conundrum, hold your nose, and just
> pick something that works.

You contradict yourself.  If we pick something that works, then nothing
will be the same as the normal set since it, by definition, does not
always "work".  N(0,0) will then no longer even refer to the normal set,
even though N was defined as the normal set...

Here's an example: Say we have an isometric map (usize=80,vsize=40),
wrapping in both directions, that we are viewing with an overhead view. 
Our GUI origin is (0,0), width and height (in tiles) are 20x20.  We have
a map position (40,40) that the GUI wishes to convert to GUI
coordinates.  It therefore calls unnormalize_map_pos to wrap (40,40)
into N(0,0).  If unnormalize_map_pos does its job right, it wraps
(40,40) to be (0,0) (see below for an explanation of wrapping).  But
(0,0) isn't even a normal position!

My point?  That N(x,y) has nothing to do with the normal set.  N(0,0) is
not the same as the normal set even though that's what you've defined it
to be.

> >> If you want to choose the range in the relationship to be an arbitary
> >> rectangle, then you certainly will have the chance to do everything
> >> from missing it to hitting it multiple times. But this doesn't
> >> correspond to any unnormalizing operation, or any other useful
> >> operation that I can think of.
> >
> >To return to the normalize_map_pos_[rect|iso] functions:
> >
> >On the contrary, this is exactly the operation that is done now in the
> >GUI code.
> 
> No one says the current GUI code is particularly elegant. In fact fixing
> it is the current problem, right?

Actually, I now believe we may be able to do a quick-fix of the GUI code
to use arbitrary topologies without restructuring the GUI.  But, we can
still do the full fix if desired.

> If you want a smaller rectangular subset of this, as for a GUI window,
> then just apply a clip operation to the returned result (hopefully
> though after you have transformed it to rectangular GUI coordinates).

Here is another point where you are getting confused.  Clipping will not
do the job here.  We don't just want a subset of a representative set,
we want a _different_ representative set.

Here's a second example.

Consider the following situation: we have a flat-rectangular
horizontally-wrapping topology (the same as the current topology) with
xsize=80 and ysize=40.  Our GUI map origin (map_view_x0/map_view_y0, top
left corner) is at (40, 40).  Our GUI code has a position (x,y) that it
needs to find a GUI position for.  So, it calls
unnormalize_map_pos(&x,&y,40,40) to try to get this position.  You have
arbitrarily defined N(x0,y0) to mean all points (x,y) where
(x0<=x<x0+xsize).  Therefore, this unnormalize_map_pos call finds some
point (the new (x,y)) where 0<=y<40 and 40<=x<119.  The GUI code then
takes this position and translates it easily into a GUI position, clips,
and proceeds thenceforth.

Everything works out fine, right?  If you are using an overhead view,
everything will go smoothly - the representative set you've just wrapped
(x,y) into is rectangular, and you're looking for a rectangular set, so
you're happy.  But if you are using an isometric view, things will not
work.  If your original point was (x,y)=(40,0), then it gets wrapped to
become the position (40,0).  But that point isn't even within the GUI
window - the point you were looking for was (120,0).  The only way
around this is to pick a *different* representative set for (40,40) to
wrap into - an isometric one - that will not work for the rectangular
case of the overhead view.

My point?  There is *no unique way* to define N(x,y).  We are looking
for two different shapes of representative set - isometric and
rectangular ones.  (In the future, different shapes may be needed - who
knows?)

> The real problem with normalize_map_pos_rect() is the arbitrary "rect"
> that does not correspond to any N(*,*) set no matter how it is selected.
> Plus the fact that it is defined in "rectangular" coordinates, and in
> the general case, say for normalize_isomap_rect(), this is not the
> native coordinate system. So the function is a confused hybrid.

(I have no idea what you mean by normalize_isomap_rect, but everything
in the core code uses rectangular coordinates.  The GUI also uses
rectangular coordinates (both overhead and isometric view).  Rectangular
coordinates are what we want.)

It is true that there may be more than one position within the rectangle
that corresponds to the given position.  But this is unavoidable.  We
can't just say normalize_map_pos_rect(&x,&y,x0,y0) and count on
normalize_map_pos_rect to wrap the position (x,y) into the rectangular
representative set defined by (x0,y0).  We must sometimes use a
"stretched" representative set to find the right position.

Again, a practical example.  Consider the following situation: we have
an iso-rectangular topology that wraps in both directions.  Take
usize=80, vsize=40 (which gives us xsize=(80+40)/2=60 and
ysize=79/2+39/2+1=59).  Our "vectors of wrapping" are (40,-40) and
(20,20).  Now suppose that we have a GUI with overhead view and origin
(0,0).  So, we again have a map position (x,y) for which we want to find
a GUI position.  We call unnormalize_map_pos again, only this time we
tell it we want an rectangular set (we've learned from the last
example).

Again things do not work.  We have said that we want a rectangular
representative set, so the topology function at least knows this much. 
But what shape does this rectangle take?  If the dimensions of our GUI
window (in tiles) are 100x20, then the point (10,30) should be wrapped
to (70,10) (applying wrapping vectors (40, -40) and (20,20)).  However,
if the dimensions of the window are 20x100 then it should be wrapped to
simply (10,30).

My point?  It is not enough to define N(x0,y0,isometric) as a flat or
isometric representative set.  We must include the dimensions of this
representative set as well.  The GUI must pass in these dimensions to be
able to use whatever function we devise.

If you are not convinced, please re-read this argument and the
theoretical one made by my previous post.  Unless I have seriously
missed something, they should be irrefutable.  Feel free to prove me
wrong, but please give an example and an explanation.

> The sample unnormalize works for a hardcoded default context that
> includes all current (and forseeable) rectangular coordinate cases
> including the current bastard-iso flavours. When you produce something
> that defines the true-iso coordinate system, we can do a corresponding
> unnormalize_isomap_pos(), but probably choosing at least the default
> "shape" of the N set to be rectangular as opposed to skewed by whatever
> scheme you come up with for the coordinate numbering.

You're beginning to come around.  But you're not there yet.  Note that
the parameters to this wrapping function (or functions) depend on the
GUI system, not the type of map wrapping system as you seem to think. 
Once could imagine different angles at which the GUI would tilt; these
would require yet new parameters.

> The reason for the "default" is that practically, that is what one
> needs most of the time. If there are other needs, we can define the
> appropriate additional contexts and/or algorithms as required.

See above.

> Someday, maybe the impossibility of the general theoretical problem
> will vanish and a real solution will even be found :-).

Maybe today.  The problem is that the dimensions passed in to
normalize_map_pos_[rect|iso] (or unnormalize_map_pos_[rect|iso], or
whatever you want to call it) may not correspond to an actual
representative set - they may be larger or smaller than what is needed
to uniquely define such a set (this is unavoidable; there's no guarantee
that any parameters will uniquely define a representative set).  The
drawback of this is that the GUI has to rely on the topology code to
give it the coordinates it wants so that the map will be drawn
continuously (this is only a problem when the GUI window is larger than
the map and the alternative is drawing a tile twice).

I see three ways around this problem.

- Have a convention for which position normalize_map_pos_[iso|rect] will
return.  In the case of normalize_map_pos_rect, it will return the
coordinates with the smallest real map distance to the origin of the
wrapping rectangle.  In the case of normalize_map_pos_iso, it will
return the position with smallest (manhattan) map distance to the
origin.  (See real_map_distance() and map_distance() in map.c.) 
Combined with the above restraints, _this_ will uniquely [1] define a
representative set, and satisfy the GUI.

- Ditch the concept of wrapping/unnormalizing/normalizing to a different
representative set altogether, and implement map_distance and
real_map_distance as topological functions (similar to my described
diff_map_pos) to return the distance and vector to a point.  The GUI can
then take the map position of the center tile, and call the applicable
function (map_distance for iso, real_map_distance for overhead) to find
the unique [1] nearest map position corresponding to the normal map
position it is given.  This position will be the one it is looking for -
except again a convention will be needed to define what happens in
border cases (although this will only matter when the GUI window is
exactly the same size as the map).

- A topology function could return a complete set of "nearby" map
positions and let the calling (GUI) code choose which one it wants. 
This would give the GUI the most flexibility, but defining "nearby" is
slightly tricky (though not too hard), and the algorithm presents very
limited opportunities for optimization.

There may be more solutions, but I can't think of any.  In any case, the
unnormalize_map_pos function will not work without changing its
functionality to be the equivalent of one of the above, and the N(x,y)
concept will _never_ work.  You have considered the straightforward
cases, but without a mathematically sound approach you're just going to
keep running into pitfalls like the N(x,y) fallacy.  Please, think this
through fully.

[1] Well, it's not quite unique since representative positions with the
same [real] map distance may exist.  But that's okay.  Note this is the
same problem with the map distance solution as well.

jason