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

[Jason Dorje Short <vze2zq63@xxxxxxxxxxx>]

Reinier Post wrote:
> 
> On Sun, Oct 07, 2001 at 09:52:19PM -0400, Jason Dorje Short wrote:
> 
> [among many other things]
> 
> > > > I say again: any time you are wrapping an unreal coordinate, or
> > > > doing anything at all to it for that matter outside of converting it
> > > > to a real coordinate, you are doing something fundamentally,
> > > > theoretically wrong.
> > >
> > > I'm afraid that it is your reasoning that is fundamentally,
> > > theoretically wrong.
> >
> > Naturally, I disagree.
> 
> As a bystander I would like to say that it is still unclear to me
> what an 'unreal' coordinate is supposed to be, and yes I do try to
> follow the whole thread.  Also for many postings it is unclear
> which exact set of topologies they discuss. The whole notion of
> normalization doesn't apply to some of the example maps.
> 
> As long as all of you are clear on this it doesn't matter, but from
> remarks such as these I get the idea that this isn't the case.
> 
> Perhaps it would be better to provide some clear mathematical definitions.
> Defining these things in terms of patches to the code base doesn't seem to
> work very well.

OK.  These mathematical definitions should go into comments in the code.

> > I mean nearest_real_pos().  This conversion is sometimes necessary, and
> > it's okay for it to be a bit fuzzy.  For instance, the client uses it to
> > convert out-of-bounds clicks to clicks on real tiles.
> 
> I know it's none of my business, but remarks like this don't give
> me any confidence that the map view code will be bug-free again this year.
> "Sometimes we throw in some partly-understood conversion function
> there to make it work", that's what it seems to say.  There just
> don't seem to be any decent definitions of concepts here, only a bunch
> of conversion algorithms.  The data model is missing.

The conversion is well-understood; the problem is that it's fuzzy. 
There may be several nearest values.  It needs (or should have already)
a comment to this effect.  The situations in which it should be used are
those in which a specific behavior is not needed.

> > My underlying assumption is that every topology we implement will map
> > cleanly onto a plane.
> 
> What exactly is a "topology" here, an adjacency graph?  And what does
> "map cleanly onto a plane" mean exactly, does it merely have to be
> planear, or does it have to map onto a rectangular grid of adjacent tiles?
> Is the grid allowed to have holes?  Can nodes in the graph be mapped
> onto multiple tiles?  Please provide some actual definitions!

See below.

> > Given that, there will always be at least one
> > nearest_real_pos.  There may be more than one (as in my example from the
> > previous post).
> 
> Again, what on earth is a "real" position?

One that is "valid" :-).  the check for is_real_tile() returns true if
the coordinate pair is legal at all.  If not, that means it's can never
be reached and is not a part of the world/topology at all.  For
instance, our current topology wraps in east and west directions, if you
try to move off of the world to the north or south you'll come to unreal
coordinates.  (20, -1) is an unreal coordinate in this regard, whereas
(-1, 20) is not because of the wrap-around.

> > > 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.
> 
> OK, well, then add that information to your postings, define the Freeciv
> data structures you need and the conversion routines, and you can prove
> whether or not any piece of map manipulation code is correct or not.

The problem in working the problem from that angle is that the biggest
problem is in the code itself.  We can come up with a mathematical
definition of what's desired, but if the code won't support it without
drastic changes we'll probably end up changing it.  I think I have a
good enough handle on what's possible to start on it, though.

> As a user I'd like to have a torus, it would make it easier to have
> a fair start when player density is high.

Fair enough.

> > > 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.
> 
> Well, hexagonal maps and approximations of spheres would be interesting.

A hexagonal map would be easy enough.  An "approximation of a sphere"
needs to be more well-defined.

> > 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.
> 
> First you need a good *definition* of the data structures,
> then you can specify the conversion routines.

The data structures themselves aren't much the issue.  It's the topology
assumptions and transformations that need to be defined.

The following is an extension of what Raimar said.

- Definitions:
  - Let Z be the set of all integers.
  - A "position" is the same as a "coordinate set".
  - A "tile" is the same as a "position" but should not be used.

- S=ZxZ is the set of all possible positions, both real and unreal.

- R<S is the set of all "real" or "valid" positions.  (< means subset
here).  Any position that is real has at least the following properties:
(1) units can move there (2) the client can draw a tile for that
positions.  An unreal (not real) position does not have these
properties.

- Coordinate pairs may be considered equivalent.  This means that if a
unit on position (x, y) which is equivalent to position (x2, y2) that
unit could just as easily be considered to be on position (x2, y2). 
This property is an equivalence relation [1] - it is reflexive,
transitive, and symmetric.  I'll call this relation "wrapping".

- N<R is the set of all equivalence classes of the wrapping relation.  N
is represented as a set of equivalence class representatives [1].  More
simply put, N is represented as the set of all "normal" positions;
exactly one position from each equivalency class is in N.  A position in
N will have at least the following properties: (1) it will have a lot of
data stored about it, (2) it will be used as an index to map_inx and
map_get_tile.  A non-normal position will not have these properties.

- (map.xsize, map.ysize) is the dimensions of the smallest possible
bounding rectangle for N.  In general, N should be chosen to fit inside
as small a rectangle as possible (this also makes calculations easier). 
The data structures will store map information as a map.xsize x
map.ysize array.  Nice conversion routines will make this easy -
currently map_inx() does this but I expect it will be expanded to
map_pos_to_index(), index_to_map_pos(), and map_index_size() or
something like that so that everyone is happy. [3]

- is_real_tile(x, y) returns TRUE iff (x, y) is an element of S.  This
should be renamed is_real_map_pos for clarity.

- is_normal_map_pos(x, y) returns TRUE iff (x, y) is an element of N.

- normalize_map_pos(&x, &y) returns FALSE if (x, y) are unreal (x and y
become undefined) and TRUE if (x, y) is real (x and y are adjusted so
that they are the class representative of the (x, y) equivalency class;
the new (x, y) will be equivalent to the old one and contained in N).

- nearest_real_pos(&x, &y) adjusts x and y to be one of the nearest
positions to (x, y) that is contained in N.  (NOTE that it is misnamed,
it should be nearest_normal_pos.)  Since distance is poorly defined and
there may be more than one position with equal distance, the new set of
coordinates is not well-defined.  Thus you should not assume anything
about this function [2].  It is definitely needed to keep the same
behavior in the user interface, unfortunately; in fact right now it is
the same as x=map_adjust_x(x),y=map_adjust_y(y) which is still used in
many places (mostly incorrectly).

- map_pos_difference(x1, y1, x2, y2, &dx, &dy) will determine the
minimum difference between (x1, y1) and (x2, y2).  The (dx, dy) are the
x and y differentials of the two positions; "minimum distance" is
defined as having a minimum (max(dx, dy)).  If more than one position
has equal minimum difference, the result may be any of the equivalent
differences.

- Etc.  No doubt more is needed.

[1] http://www.math.csusb.edu/notes/rel/node3.html

[2] Therefore Raimar was entirely correct that I should avoid using it
in smooth_map().

[3] Currently there are two flavors of data storage.  One stores things
as an array of size (map.xsize x map.ysize).  For these, it's just a
matter of introducing the macros.  Others store things as an array of
map.xsize arrays of map.ysize (or vice versa, perhaps).  These need to
be converted and fixed.

jason