Solution: The Globe in Civ V, a really spherical map with only hexagonal tiles!

[orthoceros]

Thank you. We need to distinguish two different things:

First the easy one: If the "camera is close enough" at the sphere (like when you zoom in in Civ IV), the impression of the tiles you see becomes planar, but you do not see all tiles any more. This is the same effect, if you look out of the window: You may think the environment is flat, but the Earth is actually still spherical. Nothing needs to be unbend here.

Now the more difficult one: Unbending the spherical map to get a 2D planar map, where you can see all tiles, and all tiles having exactly the same shape again: This is also possible, but don't expect the result to be intuitive. If you start with the images from above, the following steps are necessary to achieve this:

• undo the deformation, which gives all tiles roughly the same area on the surface of the sphere
• undo the spherical projection
• You are now back at an octahedron shape. (Well, not exactly, but this is not relevant here...) Like the sphere, the octahedron is still borderless. The 2D representation will necessarily have borders. So:
• Slice the octahedron at some lines from vertex to vertex (the 6 vertices of the octahedron correspond to the locations, where the four overlapping hexagons meet).
• Now you can unbend the resulting polygon net easily to become two-dimensional. Actually, there are 11 ways to choose the slice lines and get a 2D net of the octahedron. One possibility is shown in the Wikipedia article linked above.

Some more hints to understand the result:

• Also note that always four triangle faces meet at each vertex of the net; this corresponds to the four overlapping hexagons.
• Of course, each triangle face of the octahedron net consists only of hexagons, the very same hexagons you see in each 270°-triangle on the sphere spanned by three locations with overlapping hexagons.
• Try to fold the 2D octahedron net pictured in Wikipedia to a 3D octahedron in your head. Then you will know, which borders of the 2D net correspond to each other (if a unit on the 2D map would move over such a border, it would be "beamed" to the corresponding border; this is what I meant with "unintuitive result").

The point of feasability: For an efficient implementation you would not follow the steps explained above, of course. Instead you would choose one octahedron net at the beginning and give all tiles a pair of coordinates. So you can always switch from 3D view to 2D map without additional calculation by your CPU.
However, if you have a kind of a minimap feature in your head, I would strongly suggest not to use the octahedron net for it. Instead do it like Google Earth: a usual 2D projection of the whole Earth and if you click in it, the camera flys to the corresponding location over the sphere.

 

[Qxkcvdf]

I wasn't thinking of using that "unbending" as a minimap, I was thinking it would be a better way of rendering the world at close-range.

Assuming that when the world is flat, we can only see a small part of its surface, would it be possible to render that net, with the "gaps", and at the edges, draw the "neighbour" hexagons where they "should be"? And effectively "teleport" the camera to the other edge of the net if it goes too far. And, if possible, would this eliminate the overlapping hexagons (in close-up view)? Because if so, this is a damn perfect solution.

 

[orthoceros]

I think you are asking: Is there a continuous deformation, which I can link to my camera zoom so that I do only see a perfect 2D hexagonal grid, if I only zoom in enough?

If this is the question, the answer is no. The best you can get is the following: I explained above, how to transform the map to an octahedron 2D net. If your camera is close enough, you could always make this net to appear borderless (by copying the tiles from the corresponding triangle face and thus eleminating 2D beam lines). However, to my knowledge it is impossible to get rid of all artifacts: If I imagine it correctly in my head, this procedure would result in a small square shaped hole between the once overlapping four hexagons. The movement semantics at this hole would be to jump over it, i.e. it connects the two left/right hexagons and the two top/bottom hexagons.

Even if this was possible, I however would not recommend it for the following reasons:

• from a coding perspective it is much easier to just tell your camera to zoom in than to simultaneously apply a deformation not only on the grid tiles, but also on the terrain within
• all units will probably render at a constant size in Euclidean space anyway. So, they just have to be centered at the corresponding tile, i.e. their display method is already independent of the remaining area differences of the tiles.
• if your objective is to make the grid easier-to-grasp for the player, you could hide it and instead display the wireframe of a perfect "Sevengroup" (center hexagon and its six neigbours without any overlap) at the location of the selected unit like in the following image for the North Pole, where the deviation from the ideal map is the strongest. (The player would only see the cyan lines.) As soon as the unit has moved to the real center of the target tile, the cyan grid would be realigned and again be displayed at the new unit location. Admittedly, this only works locally, i.e. for the 1-neighbours of the center field.
  
  

 

[sampo]

After seeing this I really want spherical maps in Civ 5! Those images of Earth look so beautiful. Great work orthoceros!

 

[orthoceros]

Thank you very much.
I also still hope for "the planet" in CiV, but my hope decreases: Too many players (buyers from Firaxis' perspective) just do not accept or understand the necessity of the artifacts in the tesselation...

 

[snipperrabbit!!]

You are really a !

It's something I wondered if it was possible and I find your solution elegant. I don't care about the ovelapping artefacts because it does no significant damage to both area and distance.

Thank you for your hard work !

 

[orthoceros]

You're welcome and thank you . Let's just hope that some people at Firaxis also want to finally play on a real planet and have the possibility to realize the corresponding development effort...

 

[Atrebates]

Very, very nice.

My thoughts:
- I suspect the issues with the game engine may be more severe than suggested. Following from Eireksten's point, I think the game might cry if you placed a city on one of these vertices (because of the gathering system for 1,2,3 radius hexagons). Depending of how the coding for gathering around the city works this might be a very large problem.

I presume there's no solution possible for tessellating hexagons for any closed surface without vertices? (cos then the solution would be a sphere).

Out of interest, what's your research area?

 

[orthoceros]

Thanks. For the 1-radius everything should be 1:1 compared with flat 2D hexagonal maps, but you (and Eireksten) are correct for the >=2 tile radii. Still, since the city radius is a parameter, I suspect that it works distance based, i.e. internally selecting all fields that are k-near to the city. If this is the case, the only algo in need of generalization ist the distance(tile1, tile2) algo. This one and the pathfinding algo should be the only non-local algorithms wrt. the tiles. At least I do not see why other game engine algorithms, for which tiles are relevant, cannot be based on these two...?
@my research area: I am working as theoretical physicist in the complex systems group with my current main focus on nonlinear dynamics (Navier Stokes, analytical perspective). The sphere tesselation thing is more or less a hobby (and I only did it because of CiV).
@"no solution possible for tessellating hexagons for any closed surface without vertices?": You mean a smooth convex base geometry without apexes / edges? This would be a sphere from a topological perspective, right. So I think yes: it would be impossible to tessalate such a base geometry with only hexagons (and free of holes/overlaps). Not sure though, if there might be a solution of a pole-free hexagonal tesselation via "everywhere-local mini-overlaps"...? I don't think so, but I cannot prove it.

 

[Atrebates]

Not sure though, if there might be a solution of a pole-free hexagonal tesselation via "everywhere-local mini-overlaps"...? I don't think so, but I cannot prove it.

I suspect not? My intuition is mini overlap won't make a difference unless the overlap is eventually sufficient to remove a tile somewhere, where we create an effective vertex again.

On algorithms etc... damned if I know. There's lots of AI programming and the like where we don't know how it "thinks" and makes tactical decisions about city placement, resource optimisation and troop production. It could be possible that some shortcut has been made in the code (to make it more processor efficient) that is only valid for the case of projection onto a cylinder.

However, CiV is a huge programming task so hopefully the entire thing is modular, and you're correct that fixing a few algorithms will sort the entire code (ie. all aspects of the program reference the same "pathfinder" algorithm when they want to think about distance, fix "pathfinder" and you're sorted).

 

[orthoceros]

I suspect not? My intuition is mini overlap won't make a difference unless the overlap is eventually sufficient to remove a tile somewhere, where we create an effective vertex again.

I agree with your intuition, but I was wondering the following: Is there a way to systematically distribute points over the surface of the sphere such that every point has nearly or exactly the same distance to its nearest neighbours. If yes: What would the overlap look like, if you tangentially attached a hexagon to each of these points? The point distribution algorithm could start with the six points at the poles of my map. Then place a point in the middle of each of the eight 3*90°-triangles, then in the middle of the resulting smallest polygons and so on. What point pattern would result and are their nearest-distances roughly equal everywhere?... these are all very raw ideas; I did'nt really think them through.

 

[Atrebates]

Well, there'll be extra vertices the more we do that, which won't be helpful until there's the special case of every hexagon is on a vertex.

That case corresponds to the closest approximation of a sphere you can make with that many hexagons, which WOULD work easily because you remove the special consideration of each vertex. BUT this can't happen, the only way to develop a vertex pattern with one hexagon on each vertex (using the algorithm you suggest) is to have an original vertex pattern whereby each vertex has 6 equidistant neighbours... Which is only true for a solid made of hexagonal panels.

Which is a long-winded (and perhaps unclear) way of saying that the finite vertex issue can't be resolved IMO. Your original solution seems to be as good as possible, vertices will need to be incorporated to get a round earth map.

I think that the maths behind General Relativity metrics for a cylinder and a sphere could be of use if you wanted to think more deeply about this.

 

[playshogi]

It occurs to me that the greatest problem with a round map may actually be graphical. Civ 4 maps were small in the number tiles. This means that the curve of the map would be noticeable; looking at a few tiles together it would be possible to see that there is a curve to the world. The use of pentagons as described would require that there actually be a virtual model sphere.

The curve of such a model is proportional to the number of hexes on the map. So a small map would curve more than a large map. Even if you make the smallest map big enough so that a human can't see the curve at high zoom, you still have to have the curve in your model so that the pentagons fit right. This would all be fine if it weren't for one thing: units have to move and fight between hexes. Units are themselves 3d objects on the surface of this sphere and their movements would have to curve as well. But if the map can be different sizes, then the curve is different for the units. It would be necessary to have a separate movement animation for crossing a hex boundary for every map size. And no this cannot be approximated by non curved motion, even for very large maps because then if a unit walks far enough it will appear to walk off the earth!

This seems to me to be the biggest objection to why we won't see a spherical map in Civ5. Although I am hopeful for 1 size of spherical map.

 

[orthoceros]

@Atrebates: I Agree. Btw, what is your research area?

@playshogi/Souron:

It would be necessary to have a separate movement animation for crossing a hex boundary for every map size. And no this cannot be approximated by non curved motion, even for very large maps because then if a unit walks far enough it will appear to walk off the earth!

I disagree: As you can see in the images, neighbouring hexagons are effectively on the same plane. So the non-curved animation from center(tile1)->center(neighbouring tile) is okay. Since the unit has to follow tiles for longer movement paths, the animation could easily follow the piecewise straight path center(tile_1)->center(tile_2)->...->center(tile_n), where tile_i and tile_(i+1) are neighbours. I agree though that for very small maps this would lead to optical artifacts. However, you could simply prescribe a minimum amount of tiles for the spherical geometry; this would even make sense from a gameplay perspective: It is not very realistic, if you have so few tiles on the planet that the local curvature becomes a problem (because then a city would be as large as what - whole australia or at least half of it? ).
I even think that it would be possible without too much effort to define perfect animation paths (with curvature), since these are very easy to calculate: These are just arcs on a sphere, of which you know the radius. Then the say 50 frames of your animation would be displayed at 50 equidistant points on this arc instead at 50 points on a flat path. I don't think that this is a real issue from coding or performance perspective.

 

[Atrebates]

@Atrebates: I Agree. Btw, what is your research area?

Passing exams . I'm in my 3rd year (of 4) at Cambridge, doing physics. I can't be dealing with quantum and plan to stick with mechanical and vector based problems as soon as humanly possible.

@Sauron
If I understand your point, I think this will be fine. You are correct that unedited step animations would be slightly the wrong length/plane for the map, and if these errors were cumulative that could be an issue.
But (IMO) the game engine won't work like that; it will store data saying that your unit is at position (eg)A5. When you move the unit, the game will register the new position as (eg) A6 and show a suitable walking animation between those 2 points - AFTER the walking animation is finished the game will load the image of a stationary unit in the centre of tile A6. Therefore the concern is whether the walking animations will deviate strongly over the distance one tile, which I think they won't. And if they did, I'd be happy enough for my units to flicker a little bit between positions.

EDIT: Orthoceros, I also agree with what you've said. I'm just happy with the lazy coding option .

 

[frekk]

oops! Double post

 

[frekk]

This is an interesting concept, but, it sounds like alot of work for the game developers.

What do we get? Tiled poles that we probably wouldn't use.

For what price? Less time for developers to work on other aspects of the game.

Deal? No.

 

[orthoceros]

I disagree with both of your arguments:

• the development work needed: As I pointed out above, if you start from a game engine, which already works for 2D hexagonal maps, it is not too much work to realize it: All engine algos, which need tile distance information probably already refer to a central one-and-only distance(tile1,tile2) algorithm. In this case, this algo and the pathfinding algorithm are the only two in need of generalization. The rest is graphical coding only.
• Why would you not want to use the poles? I think the following is true independent of the actual concept of how to realize a real planet map in CiV: It would not only dramatically increase the game's realism, it also offers more strategical depth, more challenge, longer/nearer borders between civs, more tension, ... why would you not want this??

It would even bring more money for the developer, if properly marketed.... Deal? Yes!

 

[frekk]

The rest is graphical coding only.

Oh, just graphical coding. I see. Technically, Google Earth is just graphical coding and it doesn't even use discrete cells.

Any guess on the development time for that one?

Why would you not want to use the poles? I think the following is true independent of the actual concept of how to realize a real planet map in CiV: It would not only dramatically increase the game's realism, it also offers more strategical depth, more challenge, longer/nearer borders between civs, more tension, ... why would you not want this??

Well of course I would want it, just not at any price. I have to say I don't think it would "dramatically" do anything, and the level of "more" this and that would be rather slight.


Right off the bat, it would have zero strategic impact for 90% of the game. Even in the modern era, 90% of units will be unaffected; really, the only military aspect of crossing the poles is the possiblity of long-range heavy bombers flying over and subs flying under. I guess you could have an explorer wander around up there, fighting polar bears and whatnot, but no armies or fleets are going to be launching any invasions that way.

And even in terms of the 10% of units in the 10% of the game we're talking about, we're not talking anything earth-shaking really; no more profound than the difference between a flat map that wraps on just one axis (E-W) versus one that wraps on two axis (E-W and N-S). Less, really, because typically N-S/E-W wraps don't have poles and crossing is usually shorter and easier.

This can wait for civ, say, XII ... when the caps are gone and the poles are plastered with oil rigs and mining operations.

 

[Atrebates]

I have to say I don't think it would "dramatically" do anything, and the level of "more" this and that would be rather slight.


Right off the bat, it would have zero strategic impact for 90% of the game.

You're presupposing that the polar regions are useless, impassable piles of crap. A preconception drilled into the general population by years of Civ where polar ice was a convenient no-go area to allow cylindrical maps.

This presupposed idea is not true at all, for starters, you could design maps with no Arctic tundra/ice terrain at all (Carboniferous map ) so the N/S poles become as valid as land elsewhere.

Even if we are talking about icy poles, you can easily have land troops able to cross them or people building arctic cities to control these movement routes*. Both interesting strategies


*I don't know if you ever played the Giant real earth map in Civ3? I built cities on the 1tile land bridges to create my own panama and Suez and it was a massive strategic coup that allowed me to dominate the map and move my naval units between locations dozens of moves faster than anyone else.

It was great fun and an example of strategic planning paying off, an epitome of what (for me) Civ is all about