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

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

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.

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. 

It doesn't look like we need any more shapes at the moment, so there
is no point in worrying about the intractable theoretical problem 
just yet :-).

But here you need to reset. You really don't want to map points into 
an arbitrary sized shape. This really is confusing two operations, the
unnormalizing or transformation, and the clipping that will determine
if after transforming, it is visible in the particular sized GUI
window, or lies outside of this in some other part of GUI space.

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.

Incidentally the fact that such sets include all coordinates just
once, means you don't have to worry about the multiple image problem
of having the same thing appear at multiple places simultaneously.

But what you really want to do is find the value of your point inside 
the shape that is offset from some useful point like a GUI window
origin. So apply the wrapping operation (don't worry about some 
impossible non-wrapped example till you need it) until you come up
with a point that "wraps" into the right shape.

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.

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.

Now be clever. Don't define some weird "regular" space that includes
all of reality, so you can loop over it hunting for the point you need.
Figure out how to work within the right space, and do your algorithms
there, transforming back to GUI or array coordinates when you are 
done if further things are needed like clipping.

Cheers,
RossW
=====

FYI:

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|
 -+--+-----+--+-

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?

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.

At 08:50 AM 01/10/31 -0500, Jason Dorje Short wrote:
>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
>
>