FANDOM


A Different Approach Edit

Intro Edit

It is not possible to cover a spherical surface in regular tiles apart from spherified platonic bodies (Tetrahedron, Hexahedron or Cube, Octahedron, Dodecahedron and Icosahedron - Picture of Platonic Solids ). All of those simply don't have enough tiles to allow decent playing on it. :)

While it is possible to cover a sphere in (almost-)identical tiles, there will always be a certain number of regions on the sphere where there will be tiles with a different number of neighbours. The number of these regions depends on the platonic body the tiling is based on.

Pathfinding and navigation on non-planar surfaces does not depend on the layout of the map since the map can internally be stored as a non-directed, cyclic graph and as such can be analysed using Dijkstra's Algorithm in approximately O(n ln n) time, where n is the total number of tiles. The advantage of doing things this way is that differently-timed paths, such as polar vs. grass land, can be taken into account as a part of the weight of traversal. Rather than giving each unit or improvement a co-ordinate location, it would be associated with a tile-node object. In turn, each tile node object can have an internal co-ordinate location on the map in say longitude and latitude. To build the 2-D display, one simply chooses a central node from the closes longitude / latitude match and then keeps adding nodes adjacent to the starting node successively onto a polar or other type projection mapping.

Proposal Edit

I propose the following approach: Instead of trying to bend a planar surface into a spherical one, we redefine the basic principles of location and movement:

1) The possible unit positions are defined as nodes. These nodes are simply points in space (Vertices).

2) The nodes are connected by pointers representing possible movement paths. Movement is possible only along these pointer links. Pointers are not directional and can be travelled in either direction.

3) Each node will have a movement cost associated with it that is incurred when entering that cell but not when exiting; the cost of exiting is defined by the subsequent destination cell.

A map consists of a network made up of nodes and pointers. Usually, pointers come in pairs with each node having a pointer to the other through adjacency - where movement in one direction is possible, movement in the opposite direction is also possible, but not necessarily at the same cost.

The network is created at map generation. A standard civ-style map is a cylindrical structure of vertically and horizontally aligned nodes in an isometric grid, connected by bidirectional geometric vectors in eight directions (N,NE,E,SE,S,SW,W,NW), with southern and northern "border" nodes only connected in five directions.

A spherical map would be created as a geodesic sphere. each vertex is a node, and each edge is a pair of pointers. That's it.

Major Differences Edit

If this method is used, shape, size and arrangement of tiles becomes irrelevant in terms of programming. As long as there is a pointer between a node A and a node B, you can move from A to B. This adds even more versatility than is apparent at first glance: since a pointer has a direction, you need two pointers between A and B (A-->B and B-->A) to be able to move freely between them.

This allows unidirectional paths (swiftly flowing rivers, for example, where upstream movement is impossible) as well as unidirectional teleporters connecting non-adjacent nodes (i.e. airports). If a pointer has an additional movement cost associated directly with it, in addition to the intrinsic cost associated with a given node, it is possible to make uphill movement slower than downhill movement, to implement ocean currents and persistent strong winds. With another value associated with tile nodes might add a unit restriction: the differentiation between land and sea units is handled by this, and it also becomes possible to disallow tanks travelling through swamps or implement "mountaineer" units that can cross high mountains.

Backwards Compatibility & Advances Edit

With this method it is still possible to play on flat, "standard" maps, with or without wraparound effects. At the same time it becomes entirely possible to create spherical maps (true planets) as well as multi-submap systems (several planets, moons, asteroids... travel between the submaps becoming possible with space flight). Another possible extra is allowing multiple-level oceans - allowing seafloor installations with ships passing overhead.

Graphics Edit

For display purposes, the nodes should be "expanded" into tiles - the middle points between adjacent nodes and the center of each enclosed triangle are calculated and connected to form the border between neighboring tiles. This is, of course, the same as creating the geometric dual (turning "corners" into "sides" and vice versa).

Another nice thing is that any computer-generated 3d object can be played on - they all consist of nodes (vertices) connected to other nodes to form triangular faces. The actual visual representation of the playing field would, of course, be the geometric dual of the original object.

The camera could for simplicity's sake be always directed at the center of gravity of the map. For "closed" convex maps (spheres etc.), it can be calculated - for other types, it can be defined by the user. In the standard civ-style map, the center of gravity would be linear - the center line of the cylinder.

Troubles & Troubleshootings Edit

As explained in the introduction, pathfinding is one of the most trivial of problems to solve and so is not an issue except in so far as it grows at O( n ln n ) and therefore may be an issue with really large maps. Where the standard grid map only needs to store two co-ordinates per tile (x and y) and simply adds or subtracts whole numbers to calculate the next position in movement, the node-net needs to store at least 2 spherical co-ordinates (longitude and latitude) and use the Dijkstra algorithm to calculate paths. The bigger issue is that this potentially requires a complete re-design of the game system since it means that the entire game must be built using object-oriented principles. This does not mean it would have to be re-written in C++ or Java, since structs in C can be used to represent the node objects, but it does mean that a new tile node object needs to be created and build, complete with place-holders for the up to 8 pointers that it may have connecting it to other nodes.

Node identification could be done using their Cartesian spatial co-ordinates (x, y, z) or through longitude and latitude, but it might be better to instead give each node a unique identifier. This allows for in-game modification of co-ordinates (sea level changes, tectonics, large-scale bombardment effects) without breaking the incoming pointer connections. The easiest way of creating this unique identifier would probably be to number them in ascending order at the moment of creation. However, this creates two additional problems: It could be quite confusing for humans looking at saved games files, and we have to be careful about allowing very large numbers of nodes so that we don't later run into a wall of overflow errors.

It might also be possible to short-circuit the Dijkstra algorithm to make it quicker with large maps given very large maps. For instance, we might also just disallow long-distance travel, instead implementing a waypoint-system. Instead of having to calculate one long path, the game then only has to deal with several short paths, probably decreasing the total possible paths greatly. This could be configurable since obviously shorter maps could be dealt with directly with Dijkstra.

Keyboard movement commands are a problem... on a geodesic sphere-based node-net, we can superimpose the w-e-a-d-y-x movement keys on the adjacent tiles. If multiple levels and the like are involved, we need to find more creative solutions. Also, using the keyboard keys would interfere with action hot keys such as e for build air base or a for automatic or x for explore. As such, it may be better to consider both making use of the arrow keys and secondly letting the setting be configurable. For instance, as the page up and page down keys are not yet used, we could assign them for instance: left is left, up is up-left, down is down-left, right is right and page up is up-right and page down is down-right. Also, see the discussion about turning hexagons into squares (TBD).

Conclusion Edit

If we are not scared by an increase in resource usage, we believe this is the way to go. Of course, this will probably mean starting from scratch given the new object-oriented approach. I don't know enough about the code used in freeciv, but I guess it is different from this. or is it?

--moriarty 09:31, 26 Jun 2006 (PDT)

--TimeHorse 13:09, January 5, 2010 (UTC)

"different approach" - possible or not? Edit

let me open this discussion page with a simple question for the programmers: is it possible to create a game system that uses the mechanics I proposed? If no, why not? --moriarty 10:52, 26 Jun 2006 (PDT)

I have a difficulty visualising what you are suggesting. Per 14:35, 26 Jun 2006 (PDT)
That's probably because I have difficulties expressing what I am visualizing :)
I'll try to put it another way. The "node-net" would look like a simple mesh model (for example a "geosphere", or for simpler things, a flat plane of regularly arranged vertices like
 +-+-+-+
| | | |
+-+-+-+
| | | |
+-+-+-+
the nodes / vertices (or "points") are possible unit positions, and the pointers (or "lines") are possible movement paths. if a unit wants to move from one node to another, the system checks for a pointer that connects the two nodes, and if it exists, changes the unit position to the new node, subtracting the node's movement cost from the unit's movement points. It's as simple as that. Since the new position does not need to be exactly "one tile length" away from the previous position in this model, the arrangement, shape, size and everything of the tile is completely irrelevant. -- moriarty 22:22, 26 Jun 2006 (PDT)
I am not a very experienced programmer, but i can surely say something about this: making boards for computer games based on nets is harder than arrays, and it would probably be consuming so much energy, that it would be senseless to use it. The next problem is that it will be unintuitive for a player to play on it. It's better find good (for this game) system of positioning on sphere with 2 or 3 variables. Kshinji 05:24, 27 Jun 2006 (PDT)
I suspect that the type of programming needs to be a whole lot more clever in order to avoid needing too much computer power; true.
I think this might be done by confining AI operations to small parts of the actual net. I think it might be possible to program it so that instead of trying to parse the whole net for movement paths or strategies, the AI looks at the immediate surroundings of the unit and then decides on an action, perhaps "influenced" by a global tactic that is calculated without looking at every detail. This might even make the AI more "human", sometimes overlooking small details.--moriarty 08:23, 27 Jun 2006 (PDT)
And, as I said, we could build a short-circuit into Dijkstra, such as do not follow any path greater than, say, 99 movement cost. -- TimeHorse 15:09, January 5, 2010 (UTC)
I disagree about the energy costs. The Dijkstra algorithm has been used in computer programmes for decades and is a very well understood and powerful algorithm. As far as projected the game into a flat screen from a source sphere, we could learn a bit from how polar and other projections are made and I'm sure we could come up with some quick solutions to drawing the map. -- TimeHorse 15:09, January 5, 2010 (UTC)
I do not see how the "different approach" model solves any problems. Instead, I see other problems that have to be solved, which is how to calculate which nodes are adjacent, and how to draw polygons the way the player would expect them for movement. Consider a grid which would yield a map of square tiles (numbers are nodes):
 1 2 3
 4 5 6
 7 8 9
Movement in a square world, like in civ1, would be in 8 directions, but only 4 of those are strictly adjacent. Such a square has 4 edge neighbours and 4 additional vertex neighbours. This is simple for hex maps, and also combined hex/pentagon maps, where there are no vertex neighbours who are not also edge neighbours, but for a generalized topology system like what you suggest we do not know beforehand how this should play out. Notice how, if we only identified closest nodes as adjacent for polygon drawing and movement purposes, following the suggested drawing method, we would get a tilted square in the above example, drawn with vertices between (2,5), (4,5), (5,6) and (5,8), but movement would be expected to go across the tile's edges, not across its vertices. Notice, also, for spheres, you would still get some tiles as hexagons and some (12) as pentagons. A big problem for the basic sphere idea is that we have tiles in two variants. However, for the nodes idea, many more variants are needed, as we may not always get only hexagons or pentagons. Per 05:53, 30 Jun 2006 (PDT)
Actually, I don't think adjacency should be an issue at all. The question whether a tile is connected to another is only defined by the pointers(s) connecting the two tiles. whether there _is_ a pointer is a problem of map creation. For that, there should be different possibilities, allowing eight-way connected tiles like in civ, or six-way connected tiles like in freeciv with hex grid, or any other kind of connection, really. And there is no problem with having different kinds of tiles in one map. Of course, map creation should be done reasonably, unless we want to have utterly confusing and unplayable maps. That's why I think the map editor should start out by creating a "net" of nodes and pointers in the form of a convex 3d mesh, the kind we know from CAD programs. --moriarty 07:42, 4 Jul 2006 (PDT)
And specifically as in the Geodesic Dome. The thing with the geodesic dome is that it is either composed completely of triangles or hexagons with 12 pentagons. A description of how a geodesic is constructed can be found here. As you can see, in the triangle form, it has:
 20 f**2 Triangles
 30 f**2 Edges
 10 f**2 + 2 Vertices
Where f is the amount of subdivision of the original icosahedron, 1 being the icosahedron itself. The dual of this is composed of replacing every face (triangle) with a vertex and every vertex with either a hexagon or in 12 cases a pentagon face, yielding
 10 f**2 + 2 Faces [ 10 f**2 - 10 Hexagons and 12 Pentagons]
 30 f**2 Edges
 20 f**2 Vertices
Each edge connects one face with another directly. Each vertex connects a triangle with 2 to 3 other triangles but no additional polygons when using hexagons and pentagons. This means that with triangles, you can move in up to 12 different directions if edge movement is allowed. This could be reduced to 6 if you allow only the opposing edge of the given triangle and not allow movement to the triangles to the left and right of the opposing not already connected by the edge. However, I believe we both feel that the Hexagon / Pentagon solution is best. -- TimeHorse 15:09, January 5, 2010 (UTC)
Planes can only be tessellated by a handful of polygons. The square and isometric (rhomboid) grid are 2 examples now theoretically available in the freeciv 2.2 beta. Freeciv 2.2 beta also includes a setting for hexagonal tiling (though I've not seen this work when selected). The biggest problem is with the 12 pentagonal nodes in a geodesic projection like the one proposed. Also, it should be noted that a hexagonal pattern can be converted into a series of repeating trapezoids which in turn can be stretching into squares or rhombuses. More discussion to follow below. -- TimeHorse 15:09, January 5, 2010 (UTC)
What you initially proposed was feasible but as a classically trained software engineer, I think my edits make it easier to implement as they look it it from an implementation point of view. --TimeHorse 13:17, January 5, 2010 (UTC)

Coordinate system - Icosahedron Edit

To avoid the complexity of a spherical coordinate system, I propose using icosahedron coordinates on bucky-ball tillings. The icosahedron coordinates would be flatten into an icosahedral net then mapped to an x-y coordinate. The coordinate of a bucky-ball-1 (dodecahedron) tiling is exactly an icosahedron. The coordinate of a bucky-ball-2 (truncated icosahedron) tiling is a pentakis dodecahedron which can easily fit into an icosahedron coordinates. The bucky-ball-16 would be the standard size map. The coordinate of a tile is the center of the tile, so the tiles on the edge of the icosahedral face are split in following graphs.

bucky-ball-4 - 162 tiles Edit

   \/      \/      \/      \/      \/ --- the five slices of the North Pole pentagon tile
   ][      ][      ][      ][      ][
  ][][    ][][    ][][    ][][    ][][ --- each [] pair is a hexagon tile
 ][][][  ][][][  ][][][  ][][][  ][][][
)[][][]()[][][]()[][][]()[][][]()[][][]( --- each () pair is a pentagon tile
 ][][][][][][][][][][][][][][][][][][][][
  ][][][][][][][][][][][][][][][][][][][][
   ][][][][][][][][][][][][][][][][][][][][
    )[][][]()[][][]()[][][]()[][][]()[][][](
     ][][][  ][][][  ][][][  ][][][  ][][][
      ][][    ][][    ][][    ][][    ][][
       ][      ][      ][      ][      ][
       /\      /\      /\      /\      /\ --- the five slices of the South Pole pentagon tile

bucky-ball-1 - 12 tiles Edit

\/\/\/\/\/
)()()()()(
 )()()()()(
 /\/\/\/\/\

bucky-ball-2 - 42 tiles Edit

 \/  \/  \/  \/  \/
 ][  ][  ][  ][  ][
)[]()[]()[]()[]()[](
 ][][][][][][][][][][
  )[]()[]()[]()[]()[](
   ][  ][  ][  ][  ][
   /\  /\  /\  /\  /\

bucky-ball-8 - 642 tiles Edit

       \/              \/              \/              \/              \/       
       ][              ][              ][              ][              ][       
      ][][            ][][            ][][            ][][            ][][      
     ][][][          ][][][          ][][][          ][][][          ][][][     
    ][][][][        ][][][][        ][][][][        ][][][][        ][][][][    
   ][][][][][      ][][][][][      ][][][][][      ][][][][][      ][][][][][    
  ][][][][][][    ][][][][][][    ][][][][][][    ][][][][][][    ][][][][][][   
 ][][][][][][][  ][][][][][][][  ][][][][][][][  ][][][][][][][  ][][][][][][][  
)[][][][][][][]()[][][][][][][]()[][][][][][][]()[][][][][][][]()[][][][][][][](
 ][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][
  ][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][
   ][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][
    ][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][
     ][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][
      ][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][
       ][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][
        )[][][][][][][]()[][][][][][][]()[][][][][][][]()[][][][][][][]()[][][][][][][](
         ][][][][][][][  ][][][][][][][  ][][][][][][][  ][][][][][][][  ][][][][][][][  
          ][][][][][][    ][][][][][][    ][][][][][][    ][][][][][][    ][][][][][][   
           ][][][][][      ][][][][][      ][][][][][      ][][][][][      ][][][][][    
            ][][][][        ][][][][        ][][][][        ][][][][        ][][][][    
             ][][][          ][][][          ][][][          ][][][          ][][][     
              ][][            ][][            ][][            ][][            ][][      
               ][              ][              ][              ][              ][       
               /\              /\              /\              /\              /\       

bucky-ball-16 - 2562 tiles Edit

               \/                              \/                              \/                              \/                              \/               
               ][                              ][                              ][                              ][                              ][               
              ][][                            ][][                            ][][                            ][][                            ][][              
             ][][][                          ][][][                          ][][][                          ][][][                          ][][][             
            ][][][][                        ][][][][                        ][][][][                        ][][][][                        ][][][][            
           ][][][][][                      ][][][][][                      ][][][][][                      ][][][][][                      ][][][][][           
          ][][][][][][                    ][][][][][][                    ][][][][][][                    ][][][][][][                    ][][][][][][          
         ][][][][][][][                  ][][][][][][][                  ][][][][][][][                  ][][][][][][][                  ][][][][][][][         
        ][][][][][][][][                ][][][][][][][][                ][][][][][][][][                ][][][][][][][][                ][][][][][][][][        
       ][][][][][][][][][              ][][][][][][][][][              ][][][][][][][][][              ][][][][][][][][][              ][][][][][][][][][       
      ][][][][][][][][][][            ][][][][][][][][][][            ][][][][][][][][][][            ][][][][][][][][][][            ][][][][][][][][][][       
     ][][][][][][][][][][][          ][][][][][][][][][][][          ][][][][][][][][][][][          ][][][][][][][][][][][          ][][][][][][][][][][][      
    ][][][][][][][][][][][][        ][][][][][][][][][][][][        ][][][][][][][][][][][][        ][][][][][][][][][][][][        ][][][][][][][][][][][][     
   ][][][][][][][][][][][][][      ][][][][][][][][][][][][][      ][][][][][][][][][][][][][      ][][][][][][][][][][][][][      ][][][][][][][][][][][][][    
  ][][][][][][][][][][][][][][    ][][][][][][][][][][][][][][    ][][][][][][][][][][][][][][    ][][][][][][][][][][][][][][    ][][][][][][][][][][][][][][   
 ][][][][][][][][][][][][][][][  ][][][][][][][][][][][][][][][  ][][][][][][][][][][][][][][][  ][][][][][][][][][][][][][][][  ][][][][][][][][][][][][][][][  
)[][][][][][][][][][][][][][][]()[][][][][][][][][][][][][][][]()[][][][][][][][][][][][][][][]()[][][][][][][][][][][][][][][]()[][][][][][][][][][][][][][][](
 ][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][
  ][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][
   ][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][
    ][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][
     ][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][
      ][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][
       ][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][
        ][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][
         ][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][
          ][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][
           ][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][
            ][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][
             ][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][
              ][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][
               ][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][
                )[][][][][][][][][][][][][][][]()[][][][][][][][][][][][][][][]()[][][][][][][][][][][][][][][]()[][][][][][][][][][][][][][][]()[][][][][][][][][][][][][][][](
                 ][][][][][][][][][][][][][][][  ][][][][][][][][][][][][][][][  ][][][][][][][][][][][][][][][  ][][][][][][][][][][][][][][][  ][][][][][][][][][][][][][][][  
                  ][][][][][][][][][][][][][][    ][][][][][][][][][][][][][][    ][][][][][][][][][][][][][][    ][][][][][][][][][][][][][][    ][][][][][][][][][][][][][][   
                   ][][][][][][][][][][][][][      ][][][][][][][][][][][][][      ][][][][][][][][][][][][][      ][][][][][][][][][][][][][      ][][][][][][][][][][][][][    
                    ][][][][][][][][][][][][        ][][][][][][][][][][][][        ][][][][][][][][][][][][        ][][][][][][][][][][][][        ][][][][][][][][][][][][     
                     ][][][][][][][][][][][          ][][][][][][][][][][][          ][][][][][][][][][][][          ][][][][][][][][][][][          ][][][][][][][][][][][      
                      ][][][][][][][][][][            ][][][][][][][][][][            ][][][][][][][][][][            ][][][][][][][][][][            ][][][][][][][][][][       
                       ][][][][][][][][][              ][][][][][][][][][              ][][][][][][][][][              ][][][][][][][][][              ][][][][][][][][][       
                        ][][][][][][][][                ][][][][][][][][                ][][][][][][][][                ][][][][][][][][                ][][][][][][][][        
                         ][][][][][][][                  ][][][][][][][                  ][][][][][][][                  ][][][][][][][                  ][][][][][][][  
                          ][][][][][][                    ][][][][][][                    ][][][][][][                    ][][][][][][                    ][][][][][][   
                           ][][][][][                      ][][][][][                      ][][][][][                      ][][][][][                      ][][][][][    
                            ][][][][                        ][][][][                        ][][][][                        ][][][][                        ][][][][    
                             ][][][                          ][][][                          ][][][                          ][][][                          ][][][     
                              ][][                            ][][                            ][][                            ][][                            ][][      
                               ][                              ][                              ][                              ][                              ][       
                               /\                              /\                              /\                              /\                              /\

Martian Successor 22:52, 27 August 2009 (UTC)

Nicely done! -- TimeHorse 15:21, January 5, 2010 (UTC)

Sample Image Edit

Bucky-earth-20 Martian Successor 01:08, August 29, 2010 (UTC)

2D Backward Compatibility Edit

The Icosahedral Coordinate System with Bucky-ball Tiling is fully backward compatible with the old 2D view. As someone who is still using an old year 2000 machine, I know some players will have machine limitation.

Terrain and Unit Stack Edit

Some tiles at the edge of the icosahedron is broken into two half-tiles in the 2D view. For those with programing experience, you'll realize that it's two pointers referencing the same address. The same terrain and the same unit stack would "exist" in two places on each of the half-tiles. The polar tiles are each broken into five fifth-tiles in the 2D view. It's would just be five pointers referencing the same address.

Good idea, but it would be cumbersome to have players jump from here to there because the screen displays the same tile in multiple views. In other words, if I'm standing on the north pole, what do I see? Do I see the 5 points below me or just 1; and if 1, how do I get to my other adjacent tiles? -- TimeHorse 15:21, January 5, 2010 (UTC)

Movement Edit

Movement is very easy to calculate in the 2D map of the Icosahedral Coordinate System with Bucky-ball Tiling with little change in the code. Just imagine that the units can move at 0 movement point from one half-tile to the other half-tile. In fact, all broken tile are linked horizontally by invalid tiles! No change is needed in the path finding code.

From a programming stand point, we just need a new type of tile that allow horizontal movement and only horizontal movement at 0 movement point. It'll link the half-tiles together and it'll also link the polar tile together.

Fair enough, but I think to do it right, we should go for object-oriented as it would give us more flexibility and as I said, the 'horizontal jump' wouldn't look all that smooth on the play screen. Not that I don't like it, I just think we could improve upon it. -- TimeHorse 15:21, January 5, 2010 (UTC)

Earth Edit

See: Icosahedral Projection

See: Fuller Projection

For players who want the Earth map, use the Fuller Projection instead of the regular Icosahedral Projection. Fuller is slightly off pole, but all pentagon tile is now ocean.

Martian Successor 19:07, September 4, 2009 (UTC)

Some edits that make this more feasible Edit

As I've thought a bit on how this might work and some of the back-end implementation issues and this is basically an abandoned project, I've updating it for how I might achieve this since it seems I'm the only one still interested.

--TimeHorse 12:46, January 5, 2010 (UTC)

I had the same idea (of playing on an arbitrary graph) a long time ago. There's also been a lot of discussion on freeciv-dev on this issue, between Jason Short and Russ Wetmore to be precise. The main thing I'm missing is the observation that we want a map, hence, the adjacency graph you play on must be planar with some additional properties, so as to allow every neighborhood of every "tile" (node) to be displayd on a 2D surface in a way that still allows intuitive decision on possible paths units can follow and intuitive movement with e.g. the arrow keys. Rp 23:12, January 5, 2010 (UTC)

The beginning steps to a 2-D map Edit

I have been working on the math for how the 2-D map would be laid out and I know that the pentagons are our worst enemy. Hexagons can tessellate just as well as squares and rhombuses but pentagons not even close!

For example, here is what a projection around a one of our 12 cardinal pentagons might look like:

Pentagon-level-4

Projection of a buckyball around one of the pentagons (Buckyball level >4)

Here, there is 1 regular pentagon and 2 types of bilaterally symmetric hexagons. The wide hexagons emanate from the 5 sides of the central pentagon and form great circles connecting each with another pentagon. The tall hexagons fill in the rest of the space between the type 1 hexagonal arcs.

Now, each hexagon can be split in 2 creating 2 quadrilaterals and the pentagon as well by splitting it in 2. However, splitting the hexagons and pentagons in a way that would create a proper grid or isometric projection is not trivial. For instance, observe the image to the right:

Buckyball 2D-long-split

Split the cells along their symmetric axis

Here, all hexagons have been split along their symmetric axis and the pentagon arbitrarily down it's centre which effectively creates a series of quadrilaterals. In some cases, such as the regular same-type hexagon areas, where all the cells are actually trapezoids, (Ask former President of the U.S. James A. Garfield -- for whom the famous cartoon cat is named -- how one computes the area of a trapezoid) one can clearly imagine just stretching the non-parallel edges of each trapezoid so that it becomes a square and thus forms a normal grid. The problems arise in the discontinuity between type 1 and type 2 hexagons and the way we divided the pentagon. Although the pentagon now forms 2 quadrilaterals, those quadrilaterals share an edge with the same half-hexagon which makes it impossible to render with a conventional grid.

Buckyball 2D-diagonal-split

Buckyball projection along the short diagonals in a spiral pattern

As can be seen in in the image to the left, dividing along an arbitrary choice of shorter edge in a pattern that resembles a spiral has more consistency between adjacent cells but still has continuity issues along the 5 radial axes which have 2 cells connected by vertex in some places and none connected at others.

In any case, the nice thing here is that even with any of these divisions, you only have 3 cell types: Pentagon (or half-Pentagon), Hexagon 1 (or half) and Hexagon 2 (or half). Thus, you don't need to do any complex bit-bliting or other image transforms to fill the space: simply have 3 version of every image, one for each cell type.

The problem remains though that as you approach other pentagons on the globe, you end up with discontinuities. For instance, take the first sample I give you: imagine that we selected an order 5 buckyball, which has, from our previous formula, 240 hexagons and the usual 12 pentagons (f = 5). (Note: the level 1 buckyball is the dodecahedron and the level 0 is essentially a flat-Earth with 2 pentagons (or whatever polygon we choose), one for the "top" of the planet, and one for the "bottom".) If using the level 5 buckyball, the image above correspond to about 21% of the full level 5 map. The problem in this configuration is that the cells immediately surrounding the image above would not fit into the image evenly. Specifically, what you should see is 5 pentagons, each attached to one of the type-1 hexagons, and then 4 type-1 hexagons surrounding the rest of the image. The problem is that the type-1 hexagon will not fit on top of the type-2 hexagons evenly. Thus, you can't easily construct a surface containing 2 or more pentagons.

The situation is most profound when using Buckyball level 1, which is the dodecahedron. Many mathematicians have tried to come up with consistent mappings of the Dodecahedron onto the plane. Check out Mathworld's page on the Dodecahedral Graphs for more information on this. In my humble opinion, the Stereographic Projection looks the best, followed by the Orthographic Projection.

The Orthographic Projection does not preserve exact angles or areas though and this may be an issue but IMHO we should not worry too much as we should emphasize exact rendering for the centre of the screen and allow foreshortening around the periphery. The biggest drawback to this type of projection seems to be the advanced trigonometry required which could be calculation intensive.

On the other hand, if we give each cell a set of points that constitute vertices in 3-dimensional (x, y, z) co-ordinates (say with the origin being the centre of the Earth with all points satisfying $ x^2 + y^2 + z^2 \approx R^2 $, where R is the radius of the Earth. Given this, it should be easy to project the vertices of the Buckyball faces onto the screen-plane and connect them with edges. The problem, of course, is that the resulting hexagons and pentagons will not be regular and will come in myriad different shapes and sizes. Thus, we would still need to stretch our images a bit, but hopefully with some clever shortcuts we can make this simpler.

At last someone came to the idea to do the spherical map!

I have done some research myself just to prove my suspition it will be rather difficult. Evenly distributed random Voronoi diagram is one of the solutions. And about the buckyball, the following two could be interesting:

http://webpages.sou.edu/~sahrk/dgg/pubs/gdggs03.pdf

http://www.pyxisinnovation.com/pyxwiki/index.php?title=How_PYXIS_Works

I have not checked if this is copyrighted.

Boryupo 20:39, November 9, 2010 (UTC)

Community content is available under CC-BY-SA unless otherwise noted.