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

[hunterai]

WOAH!!! This would be really nice to have for Civ V!!!

 

[Blkbird]

Considerations for vertex cities
military
-?

Since units can move more than one tile at a time, less k-neighbors mean less point of attack, but also less room to fan out.

Generally, since it's impossible to achieve constant balance (as opposed to statistical balance), we must be very conservative and make sure that settling on a vertex tile is almost never beneficial overall, because otherwise the location would become a hyper-valuable resource that only exists six times in the whole world, most of which are unavailable as ice / ocean tiles.

 

[orthoceros]

Answers:
@snipperrabbit!!, Blkbird: You are probably correct: No special bonus system for vertex cities, because overall they are already statistically balanced and currently are neither "hyper-valuable" nor "hyper-bad" places to settle down.
@Atrebates: Thanks for the links; interesting.
@hunterai: Thank you.

Bad news:
I have finally managed to programmatically create the tile neighbourhood graph for all n. I also implemented the A* pathfinding algorithm on top of it. I even reduced the tile area deviations to less than +-10%, but then I faced the following:
While studying the shortest tile paths based on the A* algorithm, I saw some artifacts in the form of deviations from the great circle path (which is the mathematically shortest path) between the start and end tile.
I first thought it was some coding error, but it turned out to be an intrinsic fact of any tesselation of the sphere (also the pentagon solution): Since your tiles only have a limited number of "preferred directions" (6 in case of hexagonal tiles), the map requires your unit to go zig-zag, if you want to travel along any other direction. This results in the direct great circle tile-path having more tiles than another non-direct path. I find this very unattractive and unintuitive. Below is an image, which shows one of the worst cases (look inside the red ellipse and compare the tiles of the zig-zag great circle arc with the outer non-zig-zag shortest tile path):

Of course, as shown previously, you also have this zig-zag problem in 2D, but it is much more obvious on a sphere:

What do you think about this "new" problem? Any ideas how to solve it or at least reduce it?

 

[snipperrabbit!!]

I concur it's a serious problem ! Can you calculate the movement point budget limit where the short path need one more move than the smooth path ?

 

[PieceOfMind]

With the type of hex grid employed here, I'm not surprised to see that often the shortest path between two points if it's a straight line (in terms of unit movement) is not part of a great circle and that the great circle is sometimes 1 move or more slower.

I don't see it as a big deal IMO. But looking at the picture, I see the octagon at the pole as being kinda like a massive gravitational body. The path that goes nearby it is pulled in a bit and hence is not as direct. This is because there is more curvature of "space" as you get nearer that pole.

Well done on getting the A* algorithm done by the way. I'm guessing it was far from trivial. Are you willing to share how you did it? I'm doing a course at the moment where literally today we had a lecture on shortest-path algorithms.

 

[orthoceros]

@snipperrabbit!!: The answer to your question is four-dimensional: Both, the number of tiles on the shortest path and the number of tiles following the great circle path, are dependent on the start tile (2 dims) and the end tile (2 dims), or equivalently on the start tile and the desired movement direction. In order to answer your question approximately, I chose three representative start tiles and colored the tile distance to all other tiles, i.e. tiles with the same color have the same shortest tile distance from the start tile.
The deviation of this color gradient from circles centered at the start tile is your answer, i.e. circles are the ideal shape, because then the tile-shortest path meets the shortest path on a real sphere. If you want to compare with the situation for a 2D hexagonal map, the comparison shape is simply a large hexagon instead of a circle.
For start tiles near a pole my map behaves approximately ideal, i.e. the local tile distance gradient has roughly circular shape. The farther away the start tile is from the poles the more my map behaves locally like a 2D hexagonal map, i.e. the local tile distance gradient is shaped like a large hexagon.
But see for yourself:

• minimal tile distance, starting from a polar tile (the right one of the four in the center):
  
  
• minimal tile distance, if you start from a tile between two poles:
  
  
• minimal tile distance, if you start from a tile somewhere between three poles (not the symmetric center to make deviations visible):
  
  

@PieceOfMind: Thank you. On the A* implementation, you have a PM.

I don't see it as a big deal IMO.

Yes and no: For a high resolution map and versatile terrain there are nearly no game situations, where a player would notice the deviation from the great circle path as something obscure: Because to notice it, one would have to send a unit at least n tiles far away and all tiles in the region between the start and the end tile would have to be the same terrain or, more precisely, cost the same movement points. However, there are some important exceptions: Ships on oceans, helicopters (what are their movement points in comparison to n?), and the tiles you choose to build long roads through your empire...

 

[Atrebates]

Them's some nasty movement problems... 21 vs 26 in post #83?

The problem (in post 83) is somewhat reduced by having an algorithm that can autoroute along the shortest distance. That way players wouldn't have to suffer artificially long journeys from a to b. Annoying visually but doesn't effect gameplay**

Your later posts with blue-green distance maps don't have an obvious solution that I can see... As you say, it's an artifact of having 6 "primary" directions.

The only way to alleviate the symptoms would seem to be having some impassable terrain chaotically distributed, so that the movement impact of the terrain dominates over that imposed by the map vertices etc.


** Well, doesn't effect travel from a to b. The problem of building a road network between a,b&c (or any group larger than 2) becomes rather fiddly because the most efficient road layout a la "travelling salesman" might look mighty bizaare

 

[Semmel]

I had a feeling something like your thired picture would come out. But I didnt expect it to be that bad. Ohh dear, that looks quite ugly..

Is it possible to make the Tiles around the poles slightly smaller woithout changing their geometry too much? I know, I posted before that the tile form, acale, and arc-difference should be minimal. But obviously its a tradeof. So you cant have everything optimal.. Maybe its possible to make the distance lines at least convex? I mean, ok, thats a lot to ask but how else could you overcome such problem? I don't really have any good idea.

 

[Last_Evolution]

Please can you post math algorithms that generate this hex grid?

Thank you

 

[MrHan]

I was planning on starting work on a dymaxion-kavrayskiy vii hybrid for a hex earth map until I found this...

Orthoceros, you are a genius. Your solution to the spherical map problem is the best I've seen to date. I sincerely hope you (or the devs) create a working model for Civ V. One thing that worries me, though, is the severity of the deformation of the tiles as they approach the poles and the shortest-distance problems as demonstrated by your diagrams in post #86. Tesselating a sphere, to me, feels just too problematic in nature to be done without the annoying kinks.

Btw, I was wondering... Would it be possible to create a map by interpolating between six longitudes created by two hexagons at the poles?

 

[orthoceros]

Hello guys. Sorry for being not so responsive, but I am short on time; and this will probably not become better in the next few months...

I have decided to publish the Matlab source code, which constructs my map, but be warned: It works, but is messy and far from usual publishable structure and quality, but then... its only a hobby. You should read the usage example info in the header of the m file to start:
View attachment (Matlab code) Civilization hexagonal Earth map.zip

@Semmel, Atrebates: I have tried a few more changes to the projection formulas. The distance pattern is more convex now in the latest version of my code, but this is a tradeoff with the circle-based distribution of the tiles around the poles. So this is an open problem, effectively. An ideal solution while keeping a 100% hexagonal tesselation is probably impossible by virtue of the nature of the sphere (hexagons have 6 "primary" directions and the global distance artifacts show the octahedron base geometry, which "shines through" here, since it defines the tile neighbourhood).

@MrHan: Thank you.

Would it be possible to create a map by interpolating between six longitudes created by two hexagons at the poles?

Hmm. At the moment there are 6 poles with 4 overlapping hexagons each and 2 tile-based straight great circles crossing at each pole. This gives in total 8 270°-triangles, which are filled with hexagons. I do not understand what you mean with "interpolating between six longitudes"; if you join 6 straight hexagonal tile paths, you end up with a single hexagon in the center (compare the 8 dual poles, i.e. the centers of the 8 270°-triangles in the maps above); but this is probably not what you meant...?

 

[MrHan]

yeah.. what i meant was.. uh..
there would be a hexagon at the north and south pole, and 6 straight hexagonal tile paths would radiate out from one hexagon, go around the circle, then converge at the other hexagon. It's like slicing an orange into 6 equal pieces - the tile paths would be the cuts, and the area to fill in would be the orange (another way to see it are 3 circles around the globe that intersect at the poles). I was wondering if there would be a way to fill up the remaining area without too many artifacts. My gut told me no (still does), but I was curious if it could somehow work.

Btw, I'd like to know if there was a way to reduce the deformation on the hexes some more. Is it possible at all to tessellate a sphere without any deformation of the tiles?

 

[orthoceros]

slicing an orange into 6 equal pieces

Imagine the three great circles, which slice your orange into 6 equal pieces: They will meet on the North and South Pole in a single hexagon each. So far, so well. Additionally imagine the equator. This results in six triangles on the sphere's surface on each hemisphere. The equator is also a great circle, i.e. it must have the same amount of tiles, say m. This results in each triangle being bordered by m/4 tiles on two sides and m/6 tiles on the third side. Now these triangles have to be filled with hexagons, but this would only be uniformly possible, if all three sides of the triangle were bordered by the same amount of tiles! (Compare this image to see why.)
Of course, you could actually fill all 12 triangles by introducing artifacts; probably it is enough to introduce a pentagon in each triangle, which should result in the well-known 12-pentagon tesselation.

Is it possible at all to tessellate a sphere without any deformation of the tiles?

Certainly not: The deeper reason can again be seen in 2D already (above image link): If you stick to uniform tiles without gaps between the tiles and choose an arbitrary starting tile, then the actual distance from this starting tile and the distance-in-tiles is direction-dependent, which is intrinsically incompatible with a sphere and can only be solved by deformations. This is the local reason, why deformation cannot be omitted. Additionally there is a topological/global reason for deformation: The base geometry, i.e. the defined neighbourhood net between the tiles and the placement of the artifacts, also require deformations. These topological deformations are not uniform (only 90°-periodic in my case), which can cause discrepancies between the real distance and the distance-in-tiles to accumulate(, which is again the unsolved problem depicted above).

 

[MrHan]

ah. that's a shame.. thanks for clearing things up though

Then here's another question: is there any way to further reduce deformations of hexagons from what is shown in your pictures?

 

[orthoceros]

Well, that's the big question. The source code I posted above is a bit more current than the last pictures. In it I have played a bit with the projection formulas again and actually reduced the global deformation a bit in the sense that the distance coloring now is more convex for non-polar starting tiles, but this was only possible at the price of giving up the circular tile positioning around the 6 poles (which I chose for optical reasons). If you want and have a working Matlab installation, you could download the source code and try your own projection formula, because at the moment I am out of ideas....
...well there is one more "brute fore idea", but I currently don't have the time to realize it: For every start tile and every end tile compute the number of tiles along the great circle arc (mathematically shortest path) and the number of tiles on the shortest tile path (via pathfinding). Then use this information to iteratively reposition all tiles in order to minimize the stress (spring model). If it converges, see what the result looks like.

 

[Ramesses]

Hey, orthoceros. I just wanted to say that this idea you've been developing is really impressive. The way I see it, you deserve to get paid by Firaxis to use your system for Civ VI. I'm just wondering, have you made any progress getting pathfinding optimized yet?

 

[orthoceros]

Thank you! Well, getting paid for a hobby project would certainly be welcome and also particularly useful for my real-science projects.
The pathfinding algorithm itself is finished (cf. my source code posted above): It finds the shortest tile-path between any two tiles and also supports arbitrary movement costs for every (tile, neighbouring tile)-pair.
What still needs optimization is the tile placement in order to get an at least convex k-neighbourhood (for every starting tile and not only for small k, but also k>~n). No progress has been made on this problem since May, because I still don't have a good and realizable new idea here (the "brute force idea" from above would take weeks to implement and properly simulate; time which I simply cannot afford in the forseeable future...sorry.)

 

[gazius]

Is there another tile shape you could use besides the hex to get around the issue of having 'poles'?

 

[Ramesses]

Is there another tile shape you could use besides the hex to get around the issue of having 'poles'?

Long answer: To do this requires that the globe use only a single shape for its tiles. The only convex, regular polyhedrons (the only kind that the surface of a planet could use) that can be constructed using no more than one shape for each of its sides are the Platonic Solids, of which there are only five, and they are far too small to create a Civ map on. By extruding the sides to get a spherical shape in which you can allow more tiles, you will get exactly what you've seen in this thread.

Short answer: No.

 

[Robo-Star]

The only convex, regular polyhedrons (the only kind that the surface of a planet could use)...

Couldn't it be something like a pentagonal hexecontahedron?

P.S. I am absolutely awed by the work you've put into this, orthoceros (the pictures look fantastic!), and consider your solution to be more suitable than the "12 pentagons" solution.