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

[orthoceros]

Hello Kyarao. Thanks for your suggestion. What you are heading to is the real Great Circle Distance on a sphere (the link shows a derivation and the correct formula).
However, this is not what we are looking for right now: We need the exact (and minimal) number of tiles between two given tiles (which could be specified in the above 2D coordinate system as (tileTheta1, tilePhi1) and (tileTheta2, tilePhi2)).
Because of the tile area equalization process, you may be able to approximate this via numberOfTiles =ca= GreatCircleDistance/4*n, but this is only an approximate solution because of the octahedron base geometry and the overlapping tiles at the poles.

 

[PieceOfMind]

Interesting thread. Thanks orthoceros.
I will enjoy sitting down to read this more carefully.

 

[Semmel]

I just want to add that it is a very common problem to have a difference between near-distance calculation and far-distance calculation on a sphere surface. For example in air traffic movements, the distance is calculated with polar coordinates using trigonometry on far distances. But this method is numercially unstable if applied on close distances like near one airport.. lets say around 20 miles or roughly 45km. At this distances, a cartesian coordinate system is used which of course prodices some arrors. Its the question qhich errors you exapt and which you can get around.

Of course, the earth is not tiled in hexes or squares, so it does not directly apply to the Civ-Eath problem. What I want to say is, that you have to accept certain inconsistancies when dealing with a sphere surface. The largest problem of the overlapping tiles is the k-distance as stated above. It would, taking into account far distances, a difference if traveling around one of the overlapping points. If you travel over the point, the distance is slighly shorter than it should be. Lets say you travel on the equator (of the real world) around the globe. And than you travel parallel to the equator, a few km north. The second travel will be slightly shorter than the equator travel. On the hex map, these changes in distance are 'compressed' in the areas of overlapping tiles. In other words, if you travel around the globe on the equator, you travel exactly the same amount of tiles as you travel one layer north.

With increasing distance from the equator however, you dont find parallel rows of hexes any more and the problem solvs on its own. However, I find that a little odd. But as stated above, its a question which problems you want to accept and which not. Anyway, thanks orthoceros for your work, it is really interesting and I like your idea alot because it is the first alternative to the pentagon solution.

 

[orthoceros]

Hello all. I automized my approach and can now relatively quickly generate pure-hexagonal tesselations of the sphere for arbitrary (not too large) n.
I had to reinvent my tile positioning formula because I changed the application. It tries to roughly euqilize the tile area and to place all tiles with the following aim: Around every pole, the tiles are locally arranged such that you can move on circles around the respective pole. This ansatz is mathematically symmetric, i.e. no pole is favored over another.
One could certainly tweak this formula more to further reduce the remaining tile area and shape variations, especially to increase the size of the overlapping tiles a bit as I did for the original images at the start of this thread... but I do not have an infinite amount of time and for the proof of concept it is enough.
The following images show the results for n=55 The color has the following meaning: Every path from the same start color to the same end color, moving parallel to the color gradient and without crossing the same color twice, has roughly the same amount of tiles.

• Front view:
  
  
• North Pole view:
  
  

@PieceOfMind: Thank you very much, enjoy reading.

@Semmel: Thanks for your insight from an air traffic point of view; I didn't know they were using cartesian coordinates near air ports...interesting.
About "parallel rows of hexes": I know what you mean. You could place the tiles in a way to get parallel rings of tiles (perpendicular to the North/South axis), but by doing so you favor one polar axis over the two others. I.e. you will break symmetry and will no longer be able to travel in circles around the equatorial poles. Also, the tile area/shape would vary more noticeably and not all poles would look alike.
Nevertheless, I will try to create an image with this alternative approach of tile area equalization, because I agree that the non-existance of these parallel rings is somehow odd. (Well, "odd" because we are used to the usual spherical coordinate system, which shows these rings; from a mathematical perspevtive the "oddness" is reversed, because of symmetry. )

 

[Semmel]

Very nice visualization, orthoceros. I like your way of presenting your thought. Well, you are right, the horizontal parallel lines are not really relevant for the real world. Locally, no body cares or walks parallel to the equatorial level. Maybe it would also be nice to see a distance coloring where the poles are not center of origin for the color. So one could see which effect the centers have on the distance if you want to go from one point to an other which crosses near a pole.

I dont know if it is much work for you (if so please ignore this request) but i would like to see a similar distance-color picture for the pentagon-approach. I think this shows very nicely how distance would work on a sphere map.

one question though.. how do you measure the amount of disturbance? Just by looking at it? Or is there a mathematical way to measure the "local" or "global" deformation of the hexes or tiles in general.

 

[orthoceros]

Here is the alternate tile arrangement with parallel rings (perpendicular to the North/South axis for n=127), which were sought-after by Semmel:

• z-cylindrical positioning, front view:
  
  
• z-cylindrical positioning, North Pole:
  
  
• z-cylindrical positioning, an equatorial pole (zoomed):
  
  

  
  

  

(I could upload higher res images, if needed by someone.)

It follows the comparison between the new cylindrical positioning (parallel lines) and the circularly symmetric positioning we had before, both for n=127:

• z-cylindrical positioning (note the asymmetry of the North/South Pole and the equatorial poles):
  
  
• circular symmetric positioning (With the same lines highlighted, although a unit would usually not follow them, but prevent apexes near the 90° arcs by changing direction earlier at no additional tile/movement cost. Also note, that here you could highlight circular tile paths also around all equatorial poles, not only for the North and South Pole):
  
  

Both solutions have their artifacts; which one do you favor?

 

[orthoceros]

@Semmel: Thank you. Answers to your questions:
"Distance coloring": First of all, for such a distance coloring you will have to (arbitrarily!) select a start tile, to which the shortest tile distance of all other tiles will be measured and then colored. I will do that, but probably not before next week, because to create this plot, I first need the neighbourhood graph for all tiles and implement an algorithm, which calculates the shortest path between any two tiles...
"Pentagon solution": No, I would need to start from scratch with a different base geometry (icosahedron)... Also, for the pentagon solution there are probably already such images on the web somewhere.
"Measure the amount of disturbance and optimization procedure": Typically I just imagine what a good formula could be and try it out by looking at the result. I also look at the amount of disturbance left in the form of the tile area distribution: Here they are for the above n=127 solutions; as expected, the distribution is a bit worse/broader for the solution with parallel rings compared to the cicularly symmetric one. (The few tiles with area ca=1.2e-4 are the overlapping tiles.):

• z-cylindrical positioning:
  
  
• circular symmetric positioning:
  
  

Of course, I could also use this distribution and minimize e.g. its maximum extent (max(tileArea)-min(tileArea)) in a space of premodeled functions for the tile positioning, in order to obtain an optimal positioning in mathematical sense, but then... its just a hobby and my time resources are limited.

 

[Semmel]

Well, as a programmer my self i know what you mean. I dont know what your algorithm looks like so i thought it might be just one little method to find a tile. And i imagined your distance algorithm was more general. So please, dont do anything that is not in your own interest. I just found it interesting.

But quite frankly, I must say that the z-cylindrical solution does not really look nice. The disturbance is a little counter intuitive because it changes direction on the meridian lines from the north/south poles to the equatorial poles. But thanks anyway for trying it out.

Thank you very much for the nice work. I just keep my mouth shut next time I want to ask for something ;-)

 

[snipperrabbit!!]

Orthoceros, are you working a pathfinding method along the line of azimuth approximation ?

Also, I'm amazed you already automated the n-world creation.

Hexe rows parallel-ing (is that a word) the equator : that is just silly to me ! I mean, when I want to travel to Bordeaux I don't care to follow a meridian or a latitude.

How much is your maximum arbitrary n before your comp collapse ? Or, can you give an idea on construction time for the upper end of the window I mentioned earlier ?

 

[Semmel]

Well, I also did not expect to see a globe that has z-parallel hexes. What I actually wanted to remark is, that if you travel around the globe, parallel to the equator, you should travel less hexes than you do on the equator. That was not the case in the original version. But hence orthoceros created sucha nice responds, I just got away with it because I reallized it was too hard to make an algorithm that takes care of such strange requests.

What might be most important though may be that the area of each tile is roughly the same as well as the inner angle of the lines of each hex is roughly 120°. This second condition was very bad with the z-parallel version.

As third conditiot it might be interesting to achieve, that local changes in area and angle might be minimized. That means that the global range of angles might be a relativly large factor, lets say T. But that adjacent tiles are much more similar, or in other words, differ only a small portion of T. The idea behind this third condition is, that at close proximity, the structure of the hexes do not change noticably.

I dont know if this third condition is really good implementable, but well.. its just an idea and might as well be going into the bin ;-)

 

[Blkbird]

About the k-neighborhood problem at the poles: The 4 tiles at each poles are not the only one having reduced number of neighbors. The 8 tiles surrounding them all have 11 instead of 12 2-neighbors, and the 12 tiles surrounding those all have 17 instead of 18 3-neighbors. Since the city radios in Civ5 is up to 3, at least 24 tiles have to discarded as non-settleable at each of the 6 poles in order to maintain minimum equality among settleable tiles. That is a lot of tiles to be discarded!

And now for something completely different: Given it's impossible to map a sphere with n-gons except triangles, and how full of problems even approximation solutions are (yours being probably one of the best), why don't we just follow the obvious path: Use triangle tiles! Consider this: Instead of the interior, we can use the vertices of the triangles as tiles, and a triangle vertex map is equivalent to a hexagon interior map, in that each vertex has six neighbors. Defining the vertices as point of real estate may seem radical at first, but it's the common characteristic of traditional Eastern board games like Go, Chinese chess and Chinese checkers -- the last which is played exactly on a triangle vertices map. Since most people who play game have played Chinese checkers, it's not a totally alien concept.

 

[orthoceros]

@snipperrabbit!!: Thanks.
"pathfinding method": I will work on a pathfinding algorithm later (I first need the tile neighbourhood graph). There will be no need for any approximation then, because I will already work tile-based, i.e. with discrete distances.
"construction time": Since I work with The MathWorks MATLAB, which has an interpreted programming language, loops and such are relatively slow to execute; you cannot compare this with natively compiling languages like C++. I guess the complexity will be O(n^2), if you also create the neighbourhood graph (which is needed by the game engine for path finding and the like.) However, it is importeant to note that you will not need to do this construction everytime you start a new game!: Simply save the tile net for player-selectable map sizes (small to huge), including the tile neighbourhood graph. Then the engine would just have to load the proper map from a file, which can be done in a fraction of a second. This loaded base map will then be populated by the terrain first and the units second...

@Semmel:
"distance algorithm was more general": At the moment there is no distance(tile1,tile2) algorithm, yet. The tile placement formula is a global ansatz (the positions of all tiles are determined the same way everywhere on the sphere, without any need to know their neighbours by some kind of indexing). So, actually, the generality of this ansatz prevents me to give tile-individual statements at this time. (And the distance from one tile to another is such an individal info.) The pseudo coloring of the above plots also does not need any neighbourhood info: it just uses the tileTheta-coordinates from the 2D coordinate system, which I discussed earlier in this thread. More on tile distance this next week.
local conditions on tile shape: I agree with all three conditions (area, angle, local difference). All can be measured and maybe one could implement an iterative postprocessing of the vertex positions, which tries to minimize: a) tile area deviation from 4pi*R/#tiles, b) angle deviation from 2pi/3 and c) the difference of area and angles between neighbours. This will, of course, increase the computational costs for the map construction considerably, but since we save the final result and then just load it as soon as a player starts a game, it would be worth a try.
"So please, dont do anything that is not in your own interest.": Thanks for the remainder.

@Semmel, snipperrabbit!!: Its agreed then: Do not give up symmetry to force tiles in z-perpendicular parallel rings any more.

@BlkBird:
"use the ertices of a triangle-based mesh": Your idea is the dual of the pentagon solution: Look at this image (it shows a triangle-meshed sphere):

As you can see, not all triangle vertices have six neighbours, some only have five. To make it symmetric, you would have to use the triangles themselves as tiles. Actually, I thought about this for myself a few month ago, but I came to the conclusion that it would not be very Civ-friendly to only have three neighbouring tiles everywhere (from a unit/strategic perspective).
About the k>=2 problem for tiles near the poles: I disagree that these tiles are "non-settleable". First of all, the percentage of fewer tiles even within the three-radius is rather small. You could compare it with a city with some mountains in its radius. Also, if you want to make it perfecty fair again, simply use this percentage as a correction factor: Say a city somewhere only has e.g. x percent of tiles in its radius it would usually have, then simply apply a city-global bonus factor of 1/x to all tile income (production, commerce, food). This should solve the problem completely from a gameplay perspective!

 

[Atrebates]

Say a city somewhere only has e.g. x percent of tiles in its radius it would usually have, then simply apply a city-global bonus factor of 1/x to all tile income (production, commerce, food). This should solve the problem completely from a gameplay perspective!

(I'm going to call cities in such situations near the vertices "vertex cities")
For a given value of fixed... The twist is that such a system would give an notable advantage to such cities if they had large production bonus luxuries (like gems or gold) in their economic radius - because a 10% bonus on such a luxury gives a disproportionately large bonus (which would be magnified by subsequent production boosts like markets&banks).

This is not a criticism, it certainly sounds like a fair deal to me** (and the chances of having 3 gold/gem near a vertex city must be rather small anyway). In conclusion, a nice solution.


**Also, 'tis always better to offer bonuses than penalties. A player much prefers to take advantage of an opportunity the game code offers rather than feel that his cities are crippled through nasty coding.

 

[civ_king]

(I'm going to call cities in such situations near the vertices "vertex cities")
For a given value of fixed... The twist is that such a system would give an notable advantage to such cities if they had large production bonus luxuries (like gems or gold) in their economic radius - because a 10% bonus on such a luxury gives a disproportionately large bonus (which would be magnified by subsequent production boosts like markets&banks).

This is not a criticism, it certainly sounds like a fair deal to me** (and the chances of having 3 gold/gem near a vertex city must be rather small anyway). In conclusion, a nice solution.


**Also, 'tis always better to offer bonuses than penalties. A player much prefers to take advantage of an opportunity the game code offers rather than feel that his cities are crippled through nasty coding.

yields could be boosted to normal levels but on fewer tiles?

 

[orthoceros]

usual hexagonal map: 1-radius: 6 tiles, 2-radius: 12 tiles, 3-radius: 18 tiles.
worst case location (city founded on an overlapping polar tile): 1-radius: 6 tiles, 2-radius: 10 tiles, 3-radius: 14 tiles.

• For small cities (only the 1-radius has workable tiles due to low culture) there is no percentual difference, thus no advantage or disadvantage. This is especially important if a Civ founds their first city at/near a pole, because the initial growth speed can have quite in impact on the later game, as you all know.
• For medium-sized cities (1- and 2-tile radii are workable) and in the worst case (i.e. city placed on a polar hexagon), you would have only (6+10)/(6+12) of maximal workable tiles, i.e. x=88%.
• For large cities (1,2 and 3-tile radii are workable) and in the same worst case situation you would have only (6+10+14)/(6+12+18) of maximal workable tiles, i.e. x=83%.

@Atrebates: Having calculated the concrete percentages, I now also think that a flat bonus factor of 1/x might be a bit unbalanced, especially in your case of bonus ressources.

So what can we do? I think we must also consider the actually worked tiles: As long as the population limit on workable tiles is lower than the map limit, the only disadvantage for this city is less terrain diversity to choose the worked tiles from, isn't it? I.e. its identical to the situation of a city at an usual map location, where the additional tiles have mountain terrain. Correct?
So, the question is: How to compensate for the "invisible mountain tiles"? How to make it fair? ...considering things like:

• map limit on the count of workable tiles
• current population limit for the city on the count of workable tiles
• current culture limit on the count of workable tiles
• current amount of actually selected and worked tiles
• current mean terrain and infrastructure quality of workable tiles

@civ_king: I am not sure, if I understand you correctly. What is your boost factor and do you want to apply it on the map directly or only in the context of a city?.

What do you think of the following approach?: Calculate the mean production, food and commerce of all currently workable tiles of a city =:meanTerrainAndInfrastructureIncome. Count the "invisible mountain tiles" =: nMissingTiles. Count the excess population units, i.e. how many specialists would the city have, if all workable tiles were assigned? =: nMinAvailableSpecialists. Now grant the city min(nMissingTiles,nMinAvailableSpecialists) many slots of "intensive agriculturer specialists", which, if assigned a citizen unit, would provide meanTerrainAndInfrastructureIncome. This would use a familiar Civ concept (specialist citizens) to neutralize the disadvantages of missing tiles without giving unbalanced advantages, I think.

 

[Semmel]

Cities with less tiles than normal: I do not see any gameplay issue here. If you settle a city in an area where the city has less tiles to work on, than its your choice to do so. In fact, most of my cities during the game share tiles with other cities, have mountains in it or are settled near enemy culture. If you are gaming below immortal, i guess the negative impact on your economy is neglectable. On games like immortal or diety, players are that much into the game that they know about the tile problem and settle their cities accordingly. I honestly do not think that is an issue.

Tactical importance: The argument to not have pentagons in the game was, that the tactical situation should be identical for all tiles. Since the tactical situation involes at least the 2-distance for range units, the overlapping approach unfortunatelly does not grand the desired solution. Also, if for the path finding algorithm an adjacence graph is constructed, the pentagons are no problem for the algorithm to deal with. Its just a matter of implementation and code complexity if you expect 6 neighbours for all tiles or if you use a dynamic number for neighbourhood tiles. The interesting part is really how well a globe can be constructed given the above conditions, using different strategies. But the tactical game situation is less an issue in my opinion.

 

[Atrebates]

Considerations for vertex cities
economic
- Are they "balanced" at all times? eg. Not giving a 12/18% bonus for 'missing tiles' when the city doesn't have the labour to work such tiles.
military
-?
general
- Does the solution allow exploits and are they reasonable?
- Can the solution proposed be implemented in code?

IMO your new solution is generally reasonable.

I think the only possible exploit could be for when you had multicity overlap around the vertex, and assign all the crap/okay tiles to one city and the fantastic tiles to another. Depending on how "MeanTerrainandInfrastructure" is calculated you might end up with the the agriculture specialists in the good city churning out incredible levels of resources. And potentially similar tricks with how many specialists you are allowed to assign.

That said, I wouldn't put too much effort into any single solution as of yet, because we don't know how is implementing its economic system (Do we have individual citizens working individual tiles? specialists?). It is very likely that the gist of the system will be the same (more population = more resources gathered), but until we know the exact nature of the system the level of nitpicking that I do in the prior paragraph is probably futile.


PS. There might be a military exploit in that you can get less bombarding artillery at 2,3 tiles distant for a vertex city. But surrounding a city with artillery is a complete overkill situation AND rumour has it that city sieges are not the focus of the military fighting any more, so I'm not too worried about that.

 

[orthoceros]

@Semmel: Both of your points are correct and both are issues in my opinion: You may be right that this only affects seldom game situations, but we should try to solve/balance them as good as possible without causing trouble or higher complexity for the player. Of course, the minimization of tile area and vertex angle differences (locally and globally) is also very important, but more from an aesthetic point of view, not from a gameplay point of view.
I cannot do much about the tactical issue that you can only use 10 (in the worst case) instead of 12 ranged units to fire onto a polar tile with the new CiV ranged bombardmend. Its like having 2 impassable mountains in the 2-radius, i.e. a city on a polar field would have a slight tactical defense advantage in "all sides attack/siege scenarios". (Btw, the 2-radius in the pentagon solution around a "pentagon pole" also has only 10 tiles.) What I have done in comparison to the pentagon solution, is to prevent tiles, which can only be attacked by 5 instead of 6 front units (which is important in CiV, because there won't be unit stacks any longer as far as I know).

@Atrebates: Right, nearby cities must also be considered; you could decrease nMissingTiles (which can be at maximum 6 in the worst case) by the percentage of inaccessible fields (used by other cities or blocked by enemy units etc.). I still think that map based differences for cities can be neutralized/balanced nearly perfectly; I see more problems for the "ranged bombardment all sides attack" military scenario; I do not know what one could do to compensate for the "invisible mountains" in this case.
Also correct: To delve too far into details before CiV is out, is probably a waste of time (except we will all have a great surprise and the initial release of CiV comes out with a real planet map; then the whole thread would have been a waste of time...)
"rumour has it that city sieges are not the focus of the military fighting any more, so I'm not too worried about that": Interesting. Link?

 

[snipperrabbit!!]

I'm fine with no balancing at all for the vertex cities :

1 - it must take about 5/6 of game length to reach size 31
2 - the 2 polar vertex cities (PVC ) are expected to be surrounded by ice so practically impossible to even reach size 31
3 - the fewer tiles means a reduced city garrison health bar but also less tile to attack from
4 - the 4 equatorial vertex cities are expected to be surrounded by jungle or water (Earth map) and, thus, slower to grow (jungle chopping time or sea growth)
5 - the oecumene do not comprise the higher latitudes

So, all in all, I estimated the overall disadvantage of vertex cities at about 3% at most.

 

[Atrebates]

Links: http://www.gamernode.com/previews/8948-civilization-v-preview/index.html (This is new and I haven't read it - but tis the new military info bit in the Sticky civV features thread)
http://uk.pc.ign.com/articles/107/1075587p1.html (Where I remember things from)

Basically the non-stacking applies to cities as well - so you can't have a huge garrison. Prior designer comments said they were trying to induce field battles rather than city seiges (AFAIK) which suggests to me that cities can't be made too hard to remove.