[Freeciv-Dev] Re: [PATCH] Formatting cleanup.

[Gaute B Strokkenes <gs234@xxxxxxxxx>]

On Sun, 07 Oct 2001, vze2zq63@xxxxxxxxxxx wrote:
> Gaute B Strokkenes wrote:
> 
>> The current underlying assumption is that two coordinate pairs are
>> considered to be the same if and only if their difference (as
>> vectors of the Z-module ZxZ) can be expressed as a linear
>> combination of a given set of vectors.
> 
> Assumption?  Where?  I know you are assuming this, but can you
> please point out where the code uses this?

In most places where map_adjust_x() or normalize_map_pos() is being
called.  Just look at the implementation.  If you don't know what a
module is, in this case it is just like a R^n but with integers
instead of real numbers.

Search the archives and have a look at the places where people changed
map_adjust_x() so that it would give correct results even for negative
integer multiples of map.xsize.

The basic idea is that you can add any pair of offsets (dx, dy) to a
coordinate pair, call normalize_map_pos() or map_adjust_x(), and then
end up with a canonical coordinate pair that refers to the tile you
expect it to.  There are numerous places in the source where this is
assumed, either directly or indirectly.  In other words, when you
decide which coordinate pairs do and do not refer to the same tile,
you need to do so in a way which preserves the additive structure.
The only way to do so is in the way indicated (to prove that we
observe that the kernel of a module homomorphism is itself a module.
Again, if you're not familiar with that concept I'm afraid you will
just have to stare at it until you have convinced yourself that it is
true.)

In a layman's terms, the result is that two coordinate pairs (x1, y1)
and (x2, y2) are considered to refer to the same tile if and only if
their difference (x1 - x2, y1 - y2) can be expressed as a Z-linear
(i.e. a linear combination with integer coefficients) of a certain set
of coordinate pairs.

> I know we do make assumptions about the continuity of the map; for
> instance I think a goto from (x1,y1) to (x2,y2) will just set up a
> direct path and assume everything in between it is valid.  This is
> hardly a fundamental assumption.

That's not "continuous", but "convex".  It is also unrelated to the
above.

>> Currently, that set is {(map.xsize, 0)}.  If we implement a
>> rectangular topology that becomes the empty set.  For a torus it
>> would be {(map.xsize, 0), (0, map.ysize)}, and if we implment an
>> isometric-view cylinder it would be something like {(map.xsize,
>> map.ysize)} (I didn't check that, but you get the idea.)
> 
> Correct.  An isometric-view torus would have {(map.xsize,map.ysize),
> (map.xsize,-map.ysize)}.

Off course, this construction is of no use to neither man nor beast,
since the ordinary way to define a torus achives the same thing with
much less fuss.

> Again, I don't see that this is a fundamental assumption in the code
> (though I could be wrong) 

Yup.

> - but you are certainly trying to make it one.

No.  I am merely describing the current state of affairs; if you could
come up with a reasonably clean way to change things so that it is no
longer required then I would be happy to do so.  Off course, you would
have to justify the change with some sort of measurable gain.

>> Thus if (x, y) refers to a real tile, so must any other coordinate
>> pair that you arrive at by repeatedly adding or subtracting vectors
>> from that set.  Corrollary: if (x, y) does _not_ refer to a real
>> tile, neither does any other coordinate pair obtained by adding or
>> subtracting vectors from the appropriate set, since otherwise you
>> would be violating the above.
>> 
>> In short: under the current regime, you will never be able to break
>> anything by fiddling with unreal coordinates in this manner.
> 
> Please explain.

I'll try again; more slowly this time.  Remember: two given coordinate
pairs refer to the same (real) tile if and only if their difference
can be expressed as a Z-linear combination of elements in a given set
({map.xsize,0} and so on).  Since it is convenient to have a unique
"label" for each tile, we choose a particular coordinate pair, out of
all the possible ones, to be the canonical (or "blessed") coordinate
pair.  Although things would still work if you just picked the
canonical coordinates at random, in practise we make the choice by
e.g. insisting that the x-coordinate be in a particular range
( [0,map.xsize) ).  This is what we call "normalisation".

Now assume that a given coordinate pair (x, y) does not refer to real
tile.  It follows that adding any Z-linear combination of elements in
the aforementioned set (I'm tempted to come up with a name for it, but
I shan't be bothered) results in a coordinate pair which does not
refer to a real tile.  Because if it did, then the original assumption
states that it must refer to a real tile, so we have a contradiction.

Thus you will never be able to cause any damage by applying the
normalisation process to a coordinate pair that refers to an unreal
tile, in the sense that you will not accidentally end up with a
coordinate pair that refers to a real tile.  Moreover, because of the
way we choose our canonical coordinates, the normalised coordinate
pair always has a reasonable interpretation.

>> The topology that you have above does not satisfy these conditions.
>> That doesn't necessarily make it bad, but if you wish to implement
>> it you will need to change everything that depends on this
>> assumption.  Amongst other things, that means removing
>> normalize_map_pos() and all calls to it, so it is a bit backwards
>> to use this as an argument to use or change normalize_map_pos().
> 
> Huh?

My point is that if you have a topology where normalisation of unreal
coordinates does not work, then you must have broken the assumption
that we started with.  You can still make the topology work, but you
have to ditch the entire concept of normalisation, and replace it with
a system where you assign each tile a unique number of something and
then use accessor functions to manipulate them.  It is silly to use
such topologies as fuel for arguments about how to implement the
normalisation stuff.  It is more constructive to come up with
interfaces that avoid making the underlying assumption (but is still
compatible with it), like I did with MAPSTEP.

It is worth mentioning that the fundamental assumption is a sufficient
condition for normalisation in this manner to work, but it is by no
means necessary.  For instance, on a Möbius strip (where we flip the
y-coordinate when you cross the place where the x-coordinate wraps)
you can still define everything in (almost) the same manner.

> My underlying assumption is that every topology we implement will
> map cleanly onto a plane.

You need to be more precise.  Certainly a cylinder can not be realised
as a subset of the plane.  Also, a rectangle can not be made to cover
the entire plane, so the mapping can not be onto (surjective is a
slightly more modern word).

>> > Give me enough chances, and I'll find a topology that proves it.
>> 
>> I consider that unlikely, given my above proof.
> 
> Proof?

Yes; proof.  Just deal with it.

What you seem to be saying is that you intuit that there is no good
reason why this should work, and that if you just look hard enough
then you will find a counterexample.  I have presented you with hard
evidence that you will never find one.  It is up to you to find a flaw
in my argument.

I have already spent more time than I like on (from my perspective)
fruitless and uninteresting discussions about topology and
normalisation, and unless you can offer some earth-shattering new
insight I am reluctant to spend any more of the very limited time that
I have available to work on Freeciv to discuss this.  However, if
you're interested in the (relatively straightforward) mathematics I've
used in my arguments then I'm happy to provide references.

>> But really, I think all this talk about supporting arbitrarily
>> strange topologies really has that much value.  The only topologies
>> that I think we really want to support are the rectangular,
>> cylindrical and isometric-view cylindrical variants.  Additionally,
>> a torus might be so easy to do that there may well be no real
>> reason not to.  But everything else, including the stuff that I
>> have mentioned from time to time (Möbius strip, Klein bottle, RP^2
>> and so on) really strikes me as having little value beyond the
>> gee-whizz factor.
> 
> Correct, but I believe once we have a good implementation of the
> topology routines, these will fall into place - not that most of
> them ever need to make it into the real distribution.

I don't follow you.  It seems to me that the graphics code--which is
after all responsible for drawing a reasonable representation of the
map on screen--needs to know everything about how the map is laid out,
and that abstracting away all the reasonable assumptions that the
client code can make will only make the client more complicated since
it needs to deal with general cases rather than well-behaved specific
ones.

> One particular ugliness is that each client has separate code and I
> can't compile all of it.

Yes, we would like to share more of the client code.  Unfortunately,
anyone who wishes to do so needs to understand all of the clients, or
alternatively must cooperate very closely with people who in sum have
that knowledge.  That makes it tricky.

> On a side note, I think the client stuff will become less
> complicated since all of the "hard math" [1] will be moved into the
> topology routines (except for the isometric stuff which is much
> harder than the topology stuff...).

There is no "hard math" involved in this.  For the specific topologies
that anyone is ever going to implement, all of the conclusions that I
have gone to some trouble to make above follow trivially.  The only
reason I have bothered to produce this very long and boring message,
proving things in general, is that you insisted on having a general
discussion about arbitrary nightmare topologies, and because I am
hoping to put the issue to rest once and for all.  And remember that
if you wish to create another layer of abstraction to hide this stuff,
the "coders" are still the ones who have to maintain that layer.

-- 
Big Gaute                               http://www.srcf.ucam.org/~gs234/
I feel partially hydrogenated!