[Freeciv-Dev] Re: e: suggestion/idea - the world is round

[Reinier Post <rp@xxxxxxxxxx>]

On Fri, Jul 21, 2000 at 12:04:13PM +0200, Marc Strous wrote:

[sorry I'm a little late in replying, it got a little out of hand]

> Well, seems like you have given this idea some thought already. The ultimate 
> 'gridless' civ is attractive and allows for great flexibility. It does seem 
> far away from the current, griddy situation. A step by step strategy would 
> be required to get there without rewriting the complete code - a strategy 
> that would also lead to game benefits in the earlier steps.

OK, let me just input my crazy idea here.

The first step is to make a clean separation between underlying map
and projected view.  In order to allow generalization to maps on non-flat
surfaces such as a sphere, it cannot be assumed that all map view are
cut-outs from one (possibly infinite) big map view.  Instead, a map view
would be an object to represent the surroundings of a given center tile
as a set of tiles in a rectangular view window.  Recentering the map
would select a different map view.  The underlying map would just be an
adjacency graph on the underlying tiles; cities, terrain properties and
units become properties of the nodes of this graph.  Most map operations
such as 'goto' would be rewritten to operate on the graph.

The second step is to generalise the projection function that creates
map views from the underlying map.

A projection function, given the map graph and a node, generates a map
view around that node.  A map view is a 2D display of the surroundings
of that node.  The projection is now divided into two steps.  The first
step generates a particular map view for use at runtime.  It selects
the nodes to display, positions them onto the 2D surface, and
determines the shape mask for each tile (a node's tile is the set of
pixels nearer to the node's projected position than to any other node's
projected position).  This is the costly step, so the results must be
cached.  A map view can look like this:

  + for each tile in the view, the node it represents
  + for each node, the list of tiles representing it in this view
  + for each tile, a list of its adjacent tiles in clockwise order
  + for each tile, the tile shape mask
  + an array of all tiles for the purpose of iteration
  + for each tile, a mapping of the 8 move directions
    to adjacent tiles or nodes

Once a map view exists, operations on the the underlying map must be
translated to operations on the view and vice versa.  This must be
fast.  For instance, when tile properties change or units move, tiles
must be redrawn through their computed shape masks.  When a user moves
a unit, the move operation must be interpreted as a move within the
underlying node adjacency graph.  The 'center' interface operation now
becomes the 'select a map view' operation.  It's a good idea to limit
it to a selected set of nodes to limit the number of cached map views.

> For example, the idea of projections could be implemented independently from 
> any other steps. To begin with, for a simple "sphere", the complete map 
> could be subdivided into 6 projections (all square maps and still with 
> square tiles), that are layed out as a 6-sided dice, and all overlapping 
> each-other so that part of the area is covered by three projections. When 
> scrolling over the map, the client moves from one projection to the next. 
> Once this is done other shapes could be imlemented by adding more 
> projections and aligning them differently.

I think this is too limiting.  In fact T think it's possible to go
completely crazy here and use a generic graph display algorithm that
is capable of mapping fragments of arbitrary undirected graphs into a
2D rectangle.  We need a variant that takes one of the nodes as a
parameter, does its best to represent its surrounding nodes faithfully,
and omits every node that causes the adjacency graph to 'fold' on the
2D surface.  This avoids the use of underlying shapes and
shape-specific projection algorithms.  But we still expect the
projection algorithm to produce 'natural' results on adjacency
graphs derived from such underlying shapes.  For example, on graphs
derived from a sphere, the projection would need to approximate some
 kind of geometric projection of spheres onto the 2D surface.
On graphs that aren't 'locally planar', the algorithm will still work
but it probably won't produce any useful results.

For strongly 'curved' adjacency graphs, it may not suffice to have a
single map view at a time, because the map views cannot show enough of
the map; but it is easy to modify the Freeciv clients to support
multiple map views.

I think it will be necessary, for performance reasons, to fix
the (rotation) orientation of every map view.  There is no natural
'north' and 'south' in arbitrary graphs, and the method I can think
of to determine them is quite expensive, but it can be done.

What I like about this whole idea is the fact that it properly
generalises from the existing situation: the existing Freeciv map is a
special case.  Also, it isn't too expensive.  Computing views becomes
more expensive, but it needs to be done only once; displaying tiles and
executing user operations on the map become more expensive, but not by
much; expensive map operations such as goto and autosettle aren't
really be affected in performance when rewritten to operate on
adjacency graphs; so overall performance shouldn't suffer much.
However, the multiple cached views with their shape masks require a lot
of memory.

It's an overgeneralization, few people would actually like to play
Freeciv on a Klein bottle with holes.  But it make the inclusion of
all kinds of realistic map shapes trivial.

What it doesn't encompass is an isometric view.  The map topology
implied by an isometric view is no problem at all, but a special
graph display would need to be used in order to create the tilted
view on the map.

As part of the second step, the projection function must be
implemented at least for the standard Freeciv maps.  THe third
step is to add support for  different kinds of maps.

The question is how to input a map graph.  Clearly it is possible
to allow an arbitrary connected graph to be read in from a specification
file, but the present parameter-based generation would need to be
supported, too.  It would make sense to support a specific set of
underlying shapes.  Some ideas:

  - cylinder, with xsize, ysize, pattern (rectangular/triangular/hexagonal)
    ('rectangular' produces the existing map)
  - rectangle, with xsize, ysize, pattern
    (doesn't wrap horizontally)
  - 'bicylinder', with xsize, ysize, pattern
    (wraps both horizontally and vertically)
  - block, with xsize, ysize, zsize, pattern
  - sphere, with radius, pattern (the pattern is approximated)
  - donut, with xradius, yradius
  - Moebius strip, with xsize, ysize, hole size, hole distance
    (the holes connect to the other side of the strip)
  - symmetric Klein bottle, with radius, hole size, hole distance
    (the 3D equivalent of a Moebius strip)

Any function can be used here that takes a couple of parameters and
produces an adjacency graph.

The second stage of map generation is placing terrain types, specials and
initial positions onto the generated adjacency graph.  It would be nice if
the algorithms used to do this support the existing ones as a special case.
But can the existing algorithm be generalised?

The continent generation algorithms don't depend on the fact that the
Freeciv map is a cylinder, as far as I know.  They can easily be made
to work on arbitrary adjacency graphs.

Terrain types are distributed  based on latitude.  If 'north' and 'south'
are determined to fix the orientation of map views, latitude can be derived
from that.

The only remaining cylinder-specific property is the special treatment
of the outermost three rows.  The outermost row is always land in both
Civ I and II; the third row is always sea in Civ I.  These properties
can be applied to arbitrary graphs, if poles are defined to be the tiles
at extreme latitude.

So it is possible to generalise the existing map generation mechanism
to work on maps specified as arbitrary undirected graphs.

The result would be a pretty crazy map system whose power would hardly
be used in practice, but it would be genuinely new, as far as I'm aware.

I haven't looked at xconq yet - what kind of variety in maps does
it support?  xbattle allows a large range, but they're all flat.

-- 
Reinier