[Freeciv-Dev] Re: Suggestion: Growning cities

[Steve Hodge <shodge@xxxxxxxxxxxxxx>]

ccrayne@xxxxxxxxxxx wrote:
> In <39A855FB.1BE6ADB7@xxxxxxxxxxxxxx>, on 08/27/00
>    at 09:42 AM, Steve Hodge <shodge@xxxxxxxxxxxxxx> said:
> 
> :Being able to handle an arbitrarily connected network of
> :cells wouldn't be a bad thing for FreeCiv.
> 
> To me, the key design point in modifying Freeciv to allow playing on a
> globe is that the implementation can be, and should be, divided into three
> independent tasks:  a coordinate system which will uniquely identify any
> point in the game space; a rendering algorithm for the detailed map in the
> main window; and a rendering algorithm for the world view map.

The "coordinate system", which is really cell identification, is needed
in both the server and the client, the other two are needed only in the
client.

> I. Coordinate system
> 
> The current coordinate system is based on the concept of a point in a
> plane (x,y) and the height above the plane (z) in which z is assumed to be
> zero for all purposes except the map generator. 

z is actually an attribute of each cell, not a aspect of the coordinate
system. For example you can't have two cells at the same (x,y) position
with different z values.

> Although it is possible
> to describe the surface of a sphere in such a system, it greatly increases
> the computational cost of movement along the surface.
> 
> Instead, the existing x and y coordinates should be interpreted as angular
> movement along lines of latitude and longitude, with z retaining its
> current meaning as height above the surface.  The strength of this method
> is that it preserves most of the simplicity of the current method.  In
> fact, the current cylindrical map becomes just a special case of the
> spherical one.

This isn't really going to help in the case of a (mostly) hexagonal
sphere. The problem is that the hexagons don't match up a convieniently
corresponding latitudes or longitudes (see attached screenshot). While
you could use latitude and longitude it doesn't get you anything -
there's still no fast way of calculating adjacencies or anything. That's
why I think the map handling (the coordinate system and accessing of
individual cells) should be encapsulated seperately and all the bulk of
the code knows about is cell references. For a square grid the map
encapsulation may well use (x,y) coordinates, for a hexagon based sphere
it might use face numbers or spherical coordinates or anything. For the
server that should be fairly straightforward, although it might be a bit
tricky to adapt the AI and map generating code. Obviously the client
needs to be able display and navigate which is more difficult because
each different map "shape" will need it's own renderer.

> II.  Detailed Map
> 
> Although there are some known advantages to using something other than
> squares to tile a physical game board, the assumption that this is also
> true of a scrollable window does not automatically follow.  The game logic
> deals with points, not areas.  Since all regular polygons have a clearly
> defined center, how the areas surrounding each point are rendered is
> solely an aesthetic issue. 

Yep, display is not really an issue for any specific case. Navigation
is. In particular key bindings. I'm still thinking about that part.

> And, as this window is not intended to show
> the entire world at once, there are no closure problems (i.e.  the
> pentagons are always on the dark side).

Well there are 12 of them. The two at the poles are not such an issue
but the other 10 will be hard to avoid. I don't think it'll be a
problem.

> III.  World Map
> 
> Since this map is designed to show the entire world at a single glance, I
> do not feel that a 3D view which the user had to rotate would be
> acceptable.  Therefore, some means of unrolling a sphere is required.  The
> easiest method would to use the same method as today, except that there
> would be a different number of columns in each adjacent row, thus changing
> the current rectangle to a diamond. Alternatively, the rectangular shape
> could be preserved by padding the width of the elements in each row as
> necessary.

That'll work for a square mapping onto a sphere but not a hexagonal one.
Plenty of work has been done on map projections in the last few hundred
years though, so something should be appropriate. Have a look at
http://mathworld.wolfram.com/topics/MapProjections.html for some
examples.

> IV.  Programming Considerations
> 
> Because N/S movement is always along a great circle route, the
> y-coordinate handling remains unchanged, except for the special cases of
> the poles themselves.  However, because the farther away a unit is from
> the equator the fewer the number of equally spaced points there are on a
> given line of latitude, the x-coordinates of these points are no longer
> consecutive.  Thus, any routines which handle movement, or test for
> adjacency, must look up the x increment for the corresponding y value in a
> table built by the map generator.

Again, sounds reasonable for a square mapping but it won't work for a
hexagonal (or arbitrary) one. I think if we're going to change it we'd
be better going for a more powerful solution unless it's really too
difficult.

Regards,
Steve Hodge