[Freeciv-Dev] Re: (PR#7287) Extended Topologies

["rwetmore@xxxxxxxxxxxx" <rwetmore@xxxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=7287 >

I think this may have been lost. My apologies if it is a repeat.

Cheers,
RossW
=====


 > This is the Postfix program at host glockenspiel.complete.org.
 > [...]
 > <rt@xxxxxxxxxxxxxxx>: connect to freeciv.freeciv.org[64.37.156.68]: 
 > Connection
 >     timed out
 > [..]
 > Reporting-MTA: dns; glockenspiel.complete.org
 > Arrival-Date: Mon,  1 Mar 2004 12:08:55 -0600 (CST)
 >
 > Final-Recipient: rfc822; rt@xxxxxxxxxxxxxxx
 > Action: failed
 > Status: 4.0.0
 > Diagnostic-Code: X-Postfix; connect to freeciv.freeciv.org[64.37.156.68]:
 >     Connection timed out


 > Subject: Re: [Freeciv-Dev] Re: (PR#7287) Extended Topologies
 > From: Ross Wetmore <rwetmore@xxxxxxxxxxxx>
 > Date: Mon, 01 Mar 2004 13:06:11 -0500
 > To: rt@xxxxxxxxxxx


Marcelo Burda wrote:

 > <URL: http://rt.freeciv.org/Ticket/Display.html?id=7287 >
 >
 > Hello,
 >
 > Ross i am thinking in your super-tile extended map. i am donne exact
 > this for my last overview code.


Super-tile concepts are extremely powerful and this is one of the
reasons I think they have a real part to play in a generalized topology
implementation.

The super-tile technique is in some sense what unnormalize_map_pos()
uses, though in this case the second step is not to handle "near-orbit"
situations, but to deal with coordinate axis rotation in the case of
normal and iso mixed choice in map vs view coordinates.

The ability to do these things and maintain common code is lost from
the virtual function technique you introduced in your patch which is
another reason why you need to revert back to the original Freeciv
coding style for this.

<ASIDE>
The final step here is a vector version of the original wrapping code
pre corecleanups that maps elements in a rotated frame to align in the
most compact way with the output axes. This is the step that Jason dropped
when he changed to a centered mapview with map_distance_vector algorithm,
and thus lost some coordiantes permanently from the view. Map_distance
also doesn't properly handle normal set issues and this too might be an
area of concern in extended topologies.

Also, unnormalize_map_pos() is the generalized normalize_map_pos() and
it would be a good thing to migrate to an implementation based on this one
single function. Splitting it as it is now for performance reasons is the
one big caveat. But in that case, developing the common code, measuring
its performance and then optimizing it and rechecking the benefit is the
correct way to go. This is out-of-scope for the current patch, but it
should be kept in mind when developing implementation code to make future
merges and migration easier.
</ASIDE>


Before making comments on the particular implementation technique below,
I think it is useful to step back and outline a framework in which to
discuss and compare techniques. Things like "why" are we doing this, and
what makes it "good", or what is the "minimal/necessary" element.

One can then try to figure out which steps within each prototype are
beneficial or cause problems, and thus try to come up with a generalized
solution that implements a number of the good parts, and avoids the bad.
Those topologies that can be developed from the good then can be added,
while the ones that have problems will need to wait until solutions are
found for handling the bad cases.


There are two elements that this is primarily used for, 1) the overview
and 2) the mapview/canvas.

The overview must show a complete normal set of tiles. It should allow
scrolling in wrapped coordinate directions so that the focus unit is
centered. The latter is not necessary as FlatEarth will not centre the
focus unit, and thus overviews do not need to do this. But it helps to
see the surrounding terrrain in scrolled cases, so should be a highly
desirable feature. The focus unit/tile need not be at the absolute
centre, as in cases where two hemispheres are shown, but should be
centred in a regional sense.

The mapview is a local view usually depicted by an outlined rectangular
region on the overview. It is rectangular (though possibly rotated)
because the GUI window is traditionally a rectangle. This view "floats"
over a tiled overview showing a compact representation of all surrounding
tiles and is the main window in which players interact with units and
moveable/changeable elements of the game.

It is very important that users see an uncomplicated consistent view of
the world, i.e. multiple equivalent locations cannot be shown, or at
least not without some indication of which locations are not in the
current normal set. Note fogging near-orbit locations as opposed to
completely black tile might work, but the implementation issues of
multiple updates are still not resolved by this and are a significant
part of the reason for Freeciv rules in this regard. In any event such
changes are out-of-scope for this patch and thus if this is a requirement,
then this patch or at least those parts will need to wait for those changes
to be incorporated before it can be included.

What makes all this scrollability across wrapping edges work well is
currently what the patch calls simple scrolling. If one tries to
analyze this a bit, it is the fact that scrolled tiles generally
appear as far away from their original location in every near-orbit
normal set. The requirement for a mapview is that they appear at
least as far away from any mapview location as the dimensions of the
mapview. In the case of the overview, smooth scrolling puts even more
of a constraint on this as only one normal set can appear and a shifted
view needs to fit in the same pixel space. But one can do periodic
resets of the overview to optimize centring of focus elements without
smooth scrolling that does it every time.

These then are the conditions that one must impose on the viability of
the different extended scrolling mechanisms. It looks like a full wrap
with or without a rotation or inversion of the wrapped edge, i.e.
simple, Jason strip and rotated flavours are all equally viable without
much change to existing supporting code. On the otherhand, there are some
problems with case that cause inversion in the wrapped coordinate in
near-orbit normal sets. This includes the prototype example below which
has a simple wrap in E-W and an inverted wrap in N-S. It is also a problem
with qunicuntial map projections. One can say it is *the* problem, as it
causes the multiple location in view problems. What is needed is a set of
techniques or practices to minimize or get rid of this effect in order to
allow those topologies to move forward.

It also means that an alternate prototype model for a torus-world mapping
of a spherical earth might be better served by choosing the normal set to
include the inverse wrap in y, and thus convert the E-W scrolling into a
Jason strip form while the N-S then becomes simple. This is probably a
doable update that will have minimal impact of current code or since it
violates almost no curent rules, will be virtually guaranteed to not raise
robustness issues.

The fact that one can make a basic topology work by looking at the unrolled
near-orbit normal sets and choosing a working normal set that has a different
origin and dimensions in this expanded space seems to be a very powerful
idea and approach to solving some very complex issues.

But identifying the wrapping mechanics and the associated techniques or
issues raised by them, is I think the first step. If there is a solution
to the inverted coordinate wrap by certain constraints or changes to the
overview and mapview, then that would seem to have a strong bearing on how
one should proceed with the full quincunx topologies.

[...]

 > The the twisted torus maps tiles this way
 >
 > ----+---+---+-
 >     |       |
 >     |       |
 > +---+---+---+-
 > |       |
 > |       |
 > +-------+----
 > i use a special function (near_orbit() ) to create a super-tile map.(the
 > overview store one) then i show only the needed part to make the
 > overview.
 > ----+---+---+-
 >     |  Far  |
 >     |  Orbit|
 > +---+---+---+-
 > |  Near |  N.O.
 > |  Orbit|
 > ----+---+---+-
 > N.O | Real  | N.O.
 >     |  Map  |
 > +---+---+---+-
 > |  N.O  | N.O
 > |       |
 > +-------+----


I'm not sure I like the near-orbit macros/functions. I like the term as
used here to mean all surrounding normal sets, and have used it above in
that sense.

But since I think the type of wrapping constraint that the function needs
to handle is different in the N-S vs E-W coordinate directions, I would
prefer to have sub-functions based on wrap type and not refer to everything
with the same general interface, at least in topologically aware code.

However, since the particular case in question is probably trivially
determined from the topology_id, that may mean that having to identify the
specific coordinate interfaces in hardwired code is not beneficial. There
can be specialized sub-macros or sub-functions that are indexed and called
from a generic interface hiding the details if detail hiding is good. That
is of course the same argument for a single normalize_map_pos() interface
with the specific topological details hidden from the casual programmer,and
thus the ability to change or combine elements of the implementation in the
future without impinging on non-topology code.

 > super-tile maps was (for the simplest topos only the  half most near
 > part of the orbit is needed, nearobit function only return the half part
 > of the orbit)
 > ::::::::::::::::::
 > :|  N.O. |   N.O :
 > :+---+---+---+---:
 > :N.  | Real  | N.:
 > :O.  |  Map  | O.:
 > :+---+---+---+---:
 > :|  N.O  | N.O   :
 > ::::::::::::::::::
 > This is a client side feature. Server not need it at all.


I don't understand this. In general I think the topological model should
be equivalent on client and server or you run into massive maintenance
issues. The server still prints out debug maps and handles savegames which
might benefit from knowing such things although those operations should be
handled purely by native coordinate ops. I'd like to flesh out the areas of
general/server/client topology before starting to spread code and interfaces
across a number of disjoint files.

 > For the server side the wraps topological extensions is ok as is. For
 > the client we can think to explore this idea for the tildables
 > topologies.
 > Best regards
 >      Marcelo


Cheers,
RossW
=====