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

[Jason Dorje Short <vze2zq63@xxxxxxxxxxx>]

For those who don't want to read all of this, at least skip down to the
part on unnormalize_map_pos and N(x,y) sets.

"Ross W. Wetmore" wrote:
> 
> At 03:31 PM 01/10/29 -0500, Jason Dorje Short wrote:
> >"Ross W. Wetmore" wrote:

[...]

> Right, ditch "proper", leave "normal" to mean the N(0,0) set which
> coincides with the current code usage, and then do a better definition
> of what you called normal above before you hunt for a name for it.

I propose the name "representative set" to mean any set of class
representatives.

normal set = THE normal set of coordinates.  It is a representative set
(I would call it the canonical/proper one, but really it has no special
significance outside of topology code).

representative set = any complete set of class representatives.

> >Regular is not being confused with normal, except in the code (at least,
> >I don't think it has been...).  I think you may have been confusing
> >them, though, since you were arguing a check for normalcy was not needed
> >in whole_map_iterate and elsewhere.
> 
> whole_map_iterate() iterates over the "whole map" which is the N(0,0)
> set. I suspect it is you that are confusing this with some other
> iterator that has to date not been required just because the form of
> whole map iterate implementation is currently a rectangular iteration
> over the xsize x ysize set. The implementation should change not the
> interface if new capabilities are introduced.

whole_map_iterate iterates over the normal set.  Currently this is the
same as the regular set, but in the future it will not be.  My change
leaves the interface the same while changing the backend.

I don't understand where we're getting crossed up here.  I suspect it is
because there are many places in the code that cannot use
whole_map_iterate, and thus use an explicit loop.  Here we must change
the explicit loop.  Again, there is no change to the interface.

From the map_iterate patch (cvs diff -u5):

@@ -470,13 +475,15 @@
 /* iterating y, x for cache efficiency */
 #define whole_map_iterate(WMI_x_itr,
WMI_y_itr)                               \

{                                                                            
\
   int WMI_x_itr,
WMI_y_itr;                                                   \
   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++)
+    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)) {

Note again regular_map_pos_is_normal is the functional equivalent of
is_normal_map_pos, but it's faster.

> If you are having problems with xsize x ysize needing to be changed
> to width x height because you relabelled them as regualr and now need
> new normal variables, then maybe you should backoff and consider adding
> the regualr stuff as new code and leave the normal alone.

They were always regular.  The normal cannot be left alone because the
definition of normal is being changed.

> It is a lot simpler if you don't keep constantly doing cosmetic name
> changes to basic elements.

Can you give me an example?

> >Just like normalize_map_pos, [the normalize_map_pos_rect] function 
> >does several different steps at once.  This makes it very easy to use.
> 
> Actually normalize_map_pos does one thing, and returns a status that
> says whether it did it.
> 
> You aren't making a lot of sense.

Similarly, normalize_map_pos_rect does one thing, and returns a status
that says whether it did it.

If you want to debunk normalize_map_pos_rect, you're going to have to
give real arguments. :-)

> Why would you want to "wrap" after this? the whole point was to
> "unwrap" the initial (x,y) value to another cannonical set, say
> the one lying under the floating GUI window so you can compute
> the correct offset to display it.

Unwrapping and wrapping are the same.  normalize_map_pos(x, y) wraps (x,
y) to be (x0, y0).  normalize_map_pos_rect(x0, y0, ...) wraps (x0, y0)
to be (x2, y2).  There is no way to recover the original (x, y) pair at
this point.

> Are you adding further complexities by trying to fold in iso
> coordinates in addition to gui and map coordinates here? That would
> certainly leave me confused and inarticulate too.

Nope.  normalize_map_pos_rect is a *pure topological function*.

> >With normalize_map_pos_[rect|iso], we give a whole range of values into
> >which the position can be wrapped.  This range may contain no
> >representatives of the position we are wrapping (in which case we return
> >0 and be done with it), it may contain one representative (in which case
> >all is well), or it may contain multiple representatives.  For the
> >latter case, the function must clearly define which representative will
> >be used.
> 
> Very interesting, but why would you want to do such a thing?
> Transforming a coordinate into a multivalued coordinate doesn't seem
> too useful. Even you seem to think you need to fix this up if it
> happens. So why even do it?

It will work, whereas other methods will not.  The simple fact is that
when we wrap one coordinate into a given region (which, make no mistake,
is exactly what is needed), there may be several different
representatives within that region.  What, then, are we to do?  The best
solution may be to return several positions and let the calling code
(most likely the GUI) determine which is useful.  An easier solution is
to have a convention about what position is returned in this case.  The
GUI can then match this convention.  You may say that this confuses the
layers (a valid argument), but until a better solution is found I don't
see what else to do.

> > There are infinitely many
> >(perhaps uncountably infinitely many) possible sets,
> 
> As you say, there are now infinitely many sets (sigh) ...
> 
> >and trying to
> >represent such a set by a single coordinate will not work.
> 
> But labelling (we are back to) one set with a single index can't be
> done ... right. Now tell me why?

See, here we are again...I stated something without explaining. :-(

The simple explanation is for that any topology that wraps, each
coordinate (x,y) is a part of infinitely many representative sets.  For
a topology that wraps in weird ways (like an iso-rectangular one),
there's no particular reason to choose any particular one of them.

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:
  N(0, 0) = {(x, y) | 0<=x<map.xsize, 0<=y<map.ysize}
So N(0, 0) contains the point (0, 0).  In fact, if we keep everything
rectangular then we can imagine that the definition becomes:
  N(x0, y0) = {(x, y) | x0<=x<x0+map.xsize,
                        y0<=y<y0+map.ysize}
So far we're okay.  Note that if the topology wraps in the x direction,
y0 must always be 0 and if it wraps in the y direction, x0 must always
be 0.  This means the calling code must already know what it's doing to
make sure of this (or, if we change the definition above, then it will
no longer work in torus maps...we'll need separate definitions).  Things
start to look ugly.

For a circular topology it would be different:
  N(0, 0) = {(x, y) | (x-r)^2 + (y-r)^2 < r^2}
  xsize = ysize = 2*r
where the circle has radius r (an elliptical topology is similar, but
the math is a little uglier).  Note first that this set doesn't even
include the point (0, 0), so already we have gone wrong.  Shouldn't this
set be called N(r, r)?  How about N(5, 30) (assuming (5, 30) is within
the circle)?  Aren't all of these valid names, even though they refer to
the same set?  Do we, then, mean that N(x,y) is a representative set
lying within (x..x+xsize-1,y..y+ysize-1)?  Well, it's okay...an ellipse
doesn't wrap, so there is only one representative set (the normal set),
and we can shuffle off these problems.

Now consider an iso-rectangular topology with dimensions (u_size,
v_size):
  N(0, 0) = {(x, y) | x+y<(u_size-1)/2,
                      x-y<(-u_size-1)/2,
                      x+y>(u_size-1)/2+v_size-1,
                      x-y>-(u_size-1)/2+u_size-1}
  xsize = (u_size+v_size)/2
  ysize = (u_size-1)/2 + (v_size-1)/2 + 1
If this topology does not wrap, then again we have the same situation as
with the elliptical topology: N(x,y) all refers to the same
representative set so long as (x,y) is normal.  But, suppose for a
minute that it wraps in both directions.  We now have something like:
- - - - - - - - 
|   # #       | 
| # # # #     | 
|   # # # #   | 
|     # # # # | 
|       # #   | 
- - - - - - - - 

But this is equivalent to the flat-rectangular topology
- - - - - - 
| # # # # | 
| # # # # | 
| # # # # | 
| # # # # | 
- - - - - - 
that also wraps in both directions (both are simple torus shapes).  So
when we say N(0, 0), do we mean the first set or the second one?  What
about N(5, 5) or N(x, y) in general?  If some piece of code calls
unnormalize_map_pos, what is it supposed to do with the output?

Now consider if the iso-rectangular topology wraps in one direction. 
Again N(0, 0) doesn't include the point (0, 0) so we have to come up
with yet another definition:
  N(x0,y0) = {(x, y) | x+y<(u_size-1)/2+x0+y0,
                       x-y<(-u_size-1)/2+x0-y0,
                       x+y>(u_size-1)/2+v_size-1+x0+y0,
                       x-y>-(u_size-1)/2+u_size-1+x0-y0}
In fact, none of these sets N(x0, y0) includes the point (x0, y0).  If
the topology wraps in the u direction (bottom-left to top-right), then
we are restricted to x0+y0=0; anything else throws off the math entirely
and is almost impossible to figure out.  (Consider N(5, 3).  Now we have
a position that is at least real.  But what set is this?  Is it the same
as N(0, 0)?  Is it the same as N(2, -2)?  There's no good way to supply
a unique definition.).  And all of these sets are iso-rectangles, the
exact opposite of what the calling code might expect based upon the
flat-rectangle scenario above.  The calling code will not be able to do
anything useful with the output, and needs to know something about the
topology to even give valid input to the unnormalize_map_pos function.

A clever FreeCiv might decide to simplify the above topology
(iso-rectangular, wraps in u direction) to the following normal set (it
wraps vertically but isn't lined up):
---------------
|      # # # #|
|    # # # #  |
|  # # # #    |
|# # # #      |
---------------
How does this change our definitions?  With each new topology, we'll be
forced to pick a new definition of N(x,y) for that topology, and embed
this information within the calling code.  And the output of the
unnormalize_map_pos function still won't be in any useful form.

As a final example, consider the following topology:

         ^ ^ ^
         | | |
<- X X X X X X
<- X X X X X X
<- X X X X X X

There are lots of problems with this topology, but they may eventually
be surmounted.  How do you define N(3, -1) for this set?

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). 
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.

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.  It will
certainly not be useful to GUI code, which needs to wrap a map position
into the GUI's "floating window" that hovers over the map.

Whew.


> 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.  But this is a topology operation, and needs to be extracted
from get_map_xy/get_canvas_xy and placed in the topology backend code. 
If you are unhappy with it, a collection of diff_map_pos topology
operators can be used to do the same thing - the code is uglier but
avoids the pitfalls that normalize_map_pos_rect has (by clearly defining
where the new coordinate will be).

> >> I think that width, height in the above are bad for these reasons and
> >> duplicate the information content in xsize,ysize.
> >
> >No, you have it backwards.  xsize, ysize duplicate information content
> >in width, height (or usize, vsize).  It is not necessary to record them
> >in the savegame.  However different topologies may have the same
> >xsize/ysize - look at the thread on iso-rectangular maps a little while
> >back.
> 
> Since xsize,ysize were there first, and I still use them in their
> original context, I think that the new kids width,height are the
> unnecessary ones.
> 
> You should probably come up with something to justify them and explain
> what they are doing for you.

Read back over the previous discussion of iso-rectangular maps.  I think
we are all agreed that (xsize,ysize) determines the bounding rectangle
of the set of normal coordinates.  Since this is used everywhere within
the code, they should be kept.  u_size and v_size determine the
dimensions of the iso-rectangle.  It is impossible to do any topological
operations without them, and it is impossible to determine them from
(xsize,ysize).  Therefore they must be kept.

> >Because they are all necessary.  map.xsize and map.ysize are the least
> >necessary since they can be recomputed from usize/vsize on demand, but
> >it's much easier to compute them once and store them.
> 
> This I think says we really don't need them, though, except as transients.

Yes.  But it would be a major pain to remove them and would provide no
benefit.

> It is actually easiest to not have a collection of odd properties, but
> a single identifier. That is why "flat-earth" is better than "cartesian
> rectangular, standard, no_wrap_x, no_wrap_y". People will even remember
> "0". Only geeks thrive on long complex strings of weird symbols that
> they somehow find self-defining or something.

If you say so.  Personally, I find it easier to set up a topology by
changing each individual property rather than picking a number in the
0-8 range.  But then, I'm a geek.

jason