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

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

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


Jason Short wrote:
> <URL: http://rt.freeciv.org/Ticket/Display.html?id=7287 >
> 
> rwetmore@xxxxxxxxxxxx wrote:
> 
> 
>>I still think there are solutions to minimize or make clear non-intuitive
>>problems with the quincunx topology, and classes of similar topologies.
> 
> 
> Don't keep us in suspense.  What are they?
> 
> jason

Marcelo Burda wrote:

 > I introduce a lot of nice work making freecev best:
 > generalise mapgenerator to make poles in all topologies and best climat
 > generation in  hold and new topos.
 > extend init prosess to make it more easy. alow extention to more
 > simplest and complex topos as, Torus, twisted torus, "quincuntial" and
 > your proposal too!!!
[...]
 > NOT INTERESTED TO MAKE MORE WORK!!!!!
 > I am workin in it from 6 monts. all of my free time. and you think i no
 > make engout work? And your best proposal is to WAST ALL.
 >
 > ...i go stop writin now. the next word is not to be writed....
 >

I don't think Marcelo is much interested in fixing up his prototype, as he
thinks this is the greatest stuff ever written for Freeciv and wants to just
checkin a broken version and run off leaving lots of code that is really not
compatible with Freeciv rules and coding elements or a true generalized
topology model. So the continued discussion *is* probably moot.

But on the off chance someone else wants to try and rework the compatibility
and generalized elements properly, I've listed some  possibilities below.
They are by no means complete or intended as a list of fixes to be added,
but more as a list of the broken elements of the patch with some indication
as to why such things are broken as far as Freeciv is concerned. This is
also by no means a complete set of the problems. The discussion of these
has not even really begun.

Also, one has not even started on implemetation issues of the code in the
patch. Marcelo's prototype is really very good as a prototype with lots of
things at least partially present. But it is clearly nowhere near a final
version, and there will be a lot of work needed to pull apart things and
put them back in a way that builds on the current codebase model so as to
make future topology development extensions of his work rather than a set
of one-offs with lots of previous gotchas to work around until the system
falls over from its own weight :-). There is enough good stuff in his patch
that not finishing it properly would be a shame. But checking it in without
cleaning it up, would be far worse.


Cheers,
RossW
=====


As a means to highlight the problems with qunicunx topologies and perhaps
approach them from a different viewpoint that helps crystallize the wedge
issues and thus clarify things that need to be fixed, let me try to show
how one might convert to a quincunx map from the standard Mercator 2-D one
used by Freeciv. I've attached the 4-fold quincunx bitmap for reference.

I'll also throw out a couple off-the-wall ideas on how one might fix these
problems, not so much because I think they are great ideas, but rather as
something to start people thinking. If you don't want to think or offer any
improvements or alternatives, that's fine. But if no one has any new ideas
it does mean the process won't move along very fast :-).


Ok, let's start with a standard Freeciv map of Earth. The first thing to do
is collapse the North Pole back into a point from a line across the top of
the map. To do this we grab the NW and NE corners and wrap it around a straw
shrinking the north edge and extending the south one until we have a cross
section of a donut. Collapsing the straw gives us a circular map with a point
pole.

<ASIDE>
This circular map is actually a very common point for building many topologies.
The issue from here is generally how to make such an overview map tilable so a
rectangular canvas window can keep scrolling in any direction and get a
consistent view of all parts at all times. A Quincunx way is just one of them.
</ASIDE>

We can't collapse the south edge that forms the edge of the circle to a
single point now and still remain in the 2-D plane. But what we can do is
pin down four corner points on the circle, make cuts along the longitudinal
lines from the edge inwards halfway between each corner, and let the corners
of each of these cuts collapse back into the corner points. We have a choice
as to how far up we make the cuts, but somewhere between 0 and 20 degress
south latitude is probably going to look the best. After this we have 4
quarter south poles. If we rotate the corners +/-90 degrees and pin a point
say 20 degrees up the longitudinal line from the south pole along the new edge
of the map joining its two adjacent south corners, then each south pole corner
really will be a quarter of a south pole map.

Note, because of the opposing 90 degree rotations, tiling this map means
reflecting it through the midpoint between any two south pole corners. If
you keep doing this, you can build up a complete south pole as a single
point with more or less minimal distortion around it. Also somewhere along
a longitudinal line between the cut point latitude line and the circle of
the pin latitude any longitude line will bend up to 90 degrees turning in
towards the corner (aka south pole). All the extra lines on the bitmap
show some of the longitudinal warping, the shape of the equator or separation
between southern and northern polar regions to give a hint at what the
above is trying to describe.

At this point depending on how we allowed each cut to stretch from the cut
point near the equator to the edge pin point, we have something from a square
to a four point star hole between each of the original south corners.

Note that while the bend in longitude is weird, as long as it is not possible
to cross the star hole, you will be deflected at some point to head towards
one of the Antarctic corners. Note also that if you follow along the star hole
edge, then when you reach the pin point near Antarctica, you must turn at least
90 degrees to head back up the other side, i.e. move away from Antarctica. The
point to be made here is that even though the turns are probably not as much
as one would expect to reverse direction, there is a need to change course and
some indication that normal linear map mechanics are not normal in this region.
It is not really so strange then that one can move from India to India by way
of Antarctica, making various changes of direction at key points.


The final step that map makers usually take at this point is to try and hide
the star hole - afterall it is in the middle of the ocean where all directions
look alike. To do this, they pull on the midpoints between pin and near equator
cut, and draw them down to meet at the center of the line between the poles.
This is the step that I think completely invalidates the tiling operation in a
2-D Freeciv environment since in so doing one removes any indication of the cut
and sew operation along the pin to centre to near-equator points, and of the
direction change that takes place as one moves across such a boundary. In this
case one heads off south from India and with no indication of any change in
direction ends back at India, or heads west from N. America and finds S. America
dead ahead.

<ASIDE>
Note, such things are not unusual on 3-D surfaces, afterall that is what a
great circle does. But these are not the properties of 2-D maps. In a 2-D
map Newtonian physics applies - one continues in a straight direction unless
acted on by some external force, and there are no magic portals that cause
you to invert your motion like light in a miror. Freeciv maps are 2-D and
thus the above weirdness is a fatal violation of the map mechanics and core
game rules/code. No patch should be checked in that doesn't fix this in some
way.
</ASIDE>


So how does one fix these problems?


At a minimum, if you break 2-D map mecahnics, there must be some indication of
points where 2-D map mechanics are being broken. This could be different 
coloured
sea tiles coupled with some corrective map mechanics and/or a user message.

As an example, every time one crosses the border between northern and southern
tile domains, one could have the canvas view rotate 90 degrees and a message
say something like "nasty gales cause course disorientation". In the range of
any south pole the prime meridian runs EW, while in the northern region it
runs NS. This has the interesting effect that if one keeps hitting the down
key from India, then at some point one is actually moving at 90 degrees from
the original motion.

This doesn't fix the problems of adjacent tile mechanics, i.e. core game rules,
breaking down near such singularities and the inability to build cities near
such locations, though. That one is tough so I'll leave it for others at the
moment. Needless to say, the broken mechanics causes a lot of such problems that
have not completely come to light yet, but will need to be identidfied and 
fixed.

The simplest fix may actually define "black tiles" as tiles which can never be
entered, and leave the original star holes in the map. Note this actually works
for a number of topologies, and filter ruless that introduce and handle black 
tiles
within normal sets as opposed to at borders, are a topo TODO. It does not
require any other changes to map mechanics per se, since unreal tiles are 
already
excluded from such processing. Cities near star holes have fewer tiles, just
like ones in flatearth maps. The unreal tiles and need to move around them is
maybe sufficient to indicate 2-D mechanics are strange near the singularities.


There are some other minor tweaks that could be done to make a few things more
like reality. If you look at the attached bitmap, New Zealand is halfway across
the Pacific from Australia, and has been remarked, the Pacific is huge.

One should offset the cuts 5-10 degrees more to the east, pushing S. America
a little more into the Pacific and bringing New Zealand back into Australia's
corner. One could even stretch everything a little bit to shrink the Pacific
half of the map while expanding outwards from Africa in both directions.

Because of the warping of the Southern hemisphere and the general E-W expansion
of landmasses as one moves further from any pole, S. America is bigger than
N. America, Africa as big as Europe and Asia combined. This can be changed by
scaling the latitude lines so they are 10% or whatever further apart at the 
poles
than near the equator or into the Southern Hemisphere to compensate for the
increase in E-W dimensions of a flat circle over a spherical surface as one 
moves
outwards.


These sort of tweaks also bring up another point. The Quincunx map is really
only designed for viewing Earth. There are no map generators that build maps
with nice oceans every quarter circumference in which to hide singularities.

How many of these tweaks and hacks are generalizable in ways to automatically
map an arbitrary map to a quincunx model? And thus is the work to do this
part of an extended generalized topology, or just a one-off hack. Some ideas
and discussion about how one might build an arbitrary quincunx map and what
sorts of problems one runs into in generating it also needs to be part of the
preliminary prototype before the patch is ready for CVS consideration.


Some of the questions to be asked are whether one wants to spend a lot of
effort to only get a one-off Earth scenario with some unusual features, or do
something else that gives a spherical representation in a general fashion with
different distortions but none of the oddities or restrictions in the case of
general random maps.


Anyway, some more issues and ideas for further thought and discussion.

Enjoy!