Modelling a sphere

[demipomme]

Before I begin, I realise the controversial nature of this post and understand that this will never be implemented. I do however want to post it, just so its out there.

One of my biggest annoyances with civ 2 was the cylindrical world, so I have alway been a fan of a spherical world. It was not till recently however that I realised that squares don't fit on a sphere. So I set out on a quest to find a polygon that would enable a map spherical map:

- every polygon is of the same type (this excludes the hexagon-pentagon mix of soccer balls)
- every polygon is adjacent to the same number of polygons (this excludes cubes the corner squares of which are adjacent to seven rather than eight squares)
-the polygons are regular

The only answer I can find is to use equilateral triangles. I didn't like the idea at first, but it doesn't look too bad...

[Mark_Everson]

Hi demipomme:

This has been discussed several times. Actually once we go to a continuous coordinate system (if we ever get there) then a sphere would be relatively easy. You should be able to find some of the earlier discussions by searching. I did one on "spher" but on got a Really old 1999 thread. There have been much more recent ones that I'm sure you can find if you're interested.

[Lord God Jinnai]

What are the likelihoods of a CCS being implimented then?

[LDiCesare]

I still have a document on icosahedra somewhere on my files (there's something to do with pentagons when you're trying to pave a spgere correctly, but I don't remember all of it - it's somewhere on these forums).
The CCS is Gary's dream, so it very much depends on him having time to do it.

[Max Sinister]

I always thought the problem with a CCs would be the question how you represent streets - it's easy for a unit to go from (x1, y1) to (x2, y2), but how do you get the fastest way from here to there? It's hard enough with tiles. Maybe it would help if you represented the roads not as one-dimensional lines, but as long-stretched areas, but I still don't know a working pathfinding algorithm. And that's what you'd need, right?

[shimmin]

Before you give yourself a headache with the geometry, be aware that while there are several ways to tile a sphere with like polygons, none of them scale up to using a large number of tiles.

If you want a tile-based system with spherical geometry, you must accept that there will be a few corners, and then adapt your game mechanics so that they will not be terribly distorted at these corners.

[demipomme]

Originally posted by shimmin
there are several ways to tile a sphere with like polygons, none of them scale up to using a large number of tiles.

As far as I can see, triangles do scale up. Four (or more) equilateral triangles fit in each equilateral triangle. See picture below.

There are really two separate issues in modelling a sphere:
1. dividing the surface into evenly sized units
2. presenting the sphere on a 2D screen (i.e. the use of projections)

Number 1 is solved by using triangles.

Number 2 can be ignored if the player only ever sees the world in 3D as a sphere. Zoomed in, it would look slightly flatter.

N.B. apologies for a mistake I made in the first post of this thread, even using triangles not every polygon is adjacent to the same number of polygons

[demipomme]

Also, could someone explain CCS or point me in the direction of an explanation?

[shimmin]

N.B. apologies for a mistake I made in the first post of this thread, even using triangles not every polygon is adjacent to the same number of polygons

That's part of what I was referring to: on the example you provide, most of the triangles have 12 neighbors, but some have only 11.

If this is acceptable, then you can also use squares: most of the squares have eight neighbors, but some will have 7.

[Lord God Jinnai]

In order to make a perfect sphere using anything but CCS some compromises will haveto be made.

FE: You could use hexigons, but you'd haveto accept that there would be exactly 5 pentagons, no matter what size.

Or triganles being the smallest unit, other than a pixel, to represent the map best would have exactly 5 areas where there would be 11 triangles vs. 12 as neigbors.

Compared to using squares, those disortions pale into signifgance.

There is no way around anything except with CCS.

[alms66]

Or if you're willing to accept a spherical world and not a true sphere.

[demipomme]

What would a CCS map look like?
If it is something like latitute and longitude, how do you counter for the increased resolution at high latitude?

I had a think about a sphere of squares and found this picture on the web. I can't visualise it, but couldn't you smooth it out into a sphere of squares?

[alms66]

Originally posted by demipomme
Also, could someone explain CCS or point me in the direction of an explanation?

CCS = Continuous Coordinate System

This is the type of movement system used in RTS games. Units don't rely on squares, they just move to a certain point in space (x & y coordinate). Presumably, cities and borders would work the same way for Clash.

[mrmielke]

is anybody still considering the spherical map idea? if so, please raise your hands. especially if any programmers are among you.
I am a total fan of spherical maps (I want to play on a real planet! not a cylinder, not a donut, a planet!), and the icosahedron-based approach with hexagonal tiling (including the necessary twelve pentagons) should be comparatively easy. if it won't be done in this game, we might just want to start our own project...
the internal representation of the grid would probably use nodes, with each node being the center of a tile and the middle between two nodes being the border of the tile.
the graphics would need to be all 3d to avoid weird stretching of the tiles. I have some renderings of 3d models if anyone wants to take a look.

so please, if any of you are interested: speak up!

[alms66]

Originally posted by mrmielke
is anybody still considering the spherical map idea? if so, please raise your hands. especially if any programmers are among you.
I am a total fan of spherical maps (I want to play on a real planet! not a cylinder, not a donut, a planet!), and the icosahedron-based approach with hexagonal tiling (including the necessary twelve pentagons) should be comparatively easy. if it won't be done in this game, we might just want to start our own project...
the internal representation of the grid would probably use nodes, with each node being the center of a tile and the middle between two nodes being the border of the tile.
the graphics would need to be all 3d to avoid weird stretching of the tiles. I have some renderings of 3d models if anyone wants to take a look.

so please, if any of you are interested: speak up!

I can't speak for anyone else, but IMO, a tiled sphere would be the best possible map style for a strategic game of Clash's scope, level of detail and desired level of realism. I would be interested in seeing anything you've got in this regard.

[TimeTraveler]

Two weeks ago, I sought a new means of distributing tiles on a sphere, specifically for future games like Civilization (insert roman numerals here). I've looked at a myriad of patterns that failed to appeal to me for various reasons. The geodesic domes of 5-3-2 symmetry are the only ones that were even decent, and those still failed to appeal to me because of there being too few options for numbers of tiles.

I found an online program where the user chooses a number of points, then how they would be evenly distributed around a sphere or torus (I'm mainly looking at the sphere). Before the points rearrange themselves to what seem to look like failed attempts at perfection, there's the option to have the program arrange them into a spiral formation. It reminded me of points where each point slightly further from a center would be the golden angle around that center from the last.

I figured that making something that looked like this would still probably produce well-distributed points if the points were on a sphere. ...and I was right. I expanded the points into tiles and here are my creations.

One globe of tiles and one simple latitude-longitude map. I'd make ones with more detail, but I don't know how to make a program to do it for me, and making it by hand can be really tedious and time-consuming. Anyway, my methods of creating the globe is here.

Pros: It'll work for ANY whole number of tiles greater than 3, unless the number is so high that one's computer would crash from data overload (depends on the graphical detail and the computer's abilities. Raising it to 100000 or more generally shouldn't be too hard.) For common sizes, nearly all the tiles should be hexagons, with a few pentagons and fewer heptagons. Of similar sizes.

Cons: Since the tiles are arranged differently from each other, there may have to be some new rules involving city radii, or even movement (not that I don't think those need to be done anyway, though). Using a keyboard to move about won't be easy, either. Also, most people won't be able to easily plot the maps on paper.

Anyway, I figured it'd be worth some thought. So... any comments?

[mrmielke]

the program you linked to is actually kind of cool, and it uses an important concept that I think will have to be used for spherical tiling: evenly distributing points and expanding them into tiles. that's what I meant by "nodes": the points later represent possible unit (or city) positions, and each connection to a neighboring node is a possible pathway for movement. if it is programmed this way, the tiles can be any shape. but my favorite is still the icosa/dodeca-based model (the same that Buckminster-Fuller used in his original patent paper).

here's a picture I made yesterday, using 3d modeling... the red columns mark the pentagons at the corners of the original icosahedron
click the image to go to a higher resolution version, size approximately 230 kB



[EDIT] oh, btw, the image is of a grid with a multiplier of 16, by which I mean that each of the triangular faces of the original icosahedron is divided so that it holds 16*16 smaller triangles, which then each hold one "node". the resulting grid has 2550 hexagonal tiles plus 12 pentagonal tiles, which is approximately the amount of tiles found in a "standard" size civIII map. [/EDIT]

the movement control by keyboard could be using the w-a-s-d keys plus e, z and x, making a nice little hexagonal motion pad:

 w e 
a s d
 z x

if the player is on one of the pentagons, one of the keys simply has no function. preferably, since the whole display might not have a constant "north", the keys for movement should be superimposed on the surrounding tiles.

city radii are absolutely no problem, since they are defined with the node system: any tile that can be reached in two movement steps is "within the radius" - usually that would be the city tile itself, the six tiles surrounding it and the twelve tiles around that, for a total of 18+1 tiles. in the vicinity of a pentagonal tile it will be a little bit less, but if that really bothers too much, the pentagonal tiles could get some marginal boost in "shields" (="hammers") and/or "gold".

[mrmielke]

for those willing to help, there might be something starting to happen over at freeciv ... maybe.

[demipomme]

mrmielke and TimeTraveler:

Good work! Although I'm now a CSS convert, both your methods are a step in the right direction. It's amazing that despite numerous iterations of the civilisation formula, none of the companies have managed to conquer this problem. Hopefully the independent/open source community can get there first!

[mrmielke]

anyone here who is still interested in this please have a look at http://www.freeciv.org/index.php/Sph...erent_Approach and tell me what you think. especially the programmers. I really need a programmer to think through it and tell me whether it is possible.

[alms66]

See the following site(s), there are some interesting concepts that can be applied to modelling a sphere in Civ:

http://kiwi.atmos.colostate.edu/

In particular (for images)

http://kiwi.atmos.colostate.edu:16080/BUGS/geodesic/

[TimeHorse]

And then nothing in the last 2 1/2 years? >sigh< Well, folks, let's get cracking. I have been desperate to have a globe-like version of a game like Civilization since I was a wee shaver and Comp Sci under-grad when, like, the first, very first version of Sid Meyer's Civizilization came out as in the first first first the original you might say! Yes, I've been waiting almost 2 decades for this so here I am to say YES!

The buckmister-fuller approach of expanding on the icosahedron and then forming its dual is ideal. Someone suggested splitting the hexagons into triangle and I think we're better off with hexagons and the occasional pentagon. This is because when the grid is tessellated with hexagons, each edge has a hexagon but each vertex has nothing more than the previously counted hexagons. With triangles, you have 3 neighbours to be sure but when you consider things like vertex coverage, you add another 3 triangle each for a total of 9 vertex-adjacent cells. Remember in freeciv, for example, you the ability to travel diagonally and it seems unreasonable to restrict motion to just 3 directions or complicate it by 12. Thus, Hexagons are ideal and do indeed tessellate well!

Now, it's easy to render a screen full of hexagons and for those game artists, you can pick up hex paper in any old hobby shop where ex-DnD'r might dwell, or visit a site like http://incompetech.com/graphpaper/ and print some yourself.

It worries me, though, how you represent the pentagonal nodes on such a graph. Once could, for instance, construct the pentagon geometrically but build "snub" hexagons around it and just build the grid around it.

Listen, Populus III at least could put play on a sphere, there's no reason than we, in 2010, can't have a sphere for the little map and project a 2-D hex-grid for the play area!

Now, unfortunately, graphing the geodesic dome onto paper isn't as trivial as downloading a PDF. Take, for instance, the special case of the Dodecahedron; it would look something like this: http://en.wikipedia.org/wiki/File:Do...projection.png
where the outer 5 pentagons form the 5 edges of the opposing pentagon to the one in the centre. Of course, we wouldn't use that exact projection and would probably just arbitrarily choose one of the 5 outer pentagons to be adjacent to the missing one so you could see all of them on screen at the same time (one assumes ones screen is capable of showing at least 12 squares at a time). Focusing on regular repeat patterns however may be over-complicated. Instead, we can take the dual of our geodesic dome and project the centres of each of the resulting polygons onto a flat surface using a polar projection. In other words, each of those points in the projection are the vertices between polygons of our original model and thus form the scaffolding from which we build our grid.

As for how each cell is rendered, a layered approach like mentioned in the Wiki seems reasonable. With the stretched grid resulting from a polar projection where there is foreshortening and compression at the periphery mean a lot of computation would be needed to render each cell but hopefully machines are fast enough now since I'm no longer using that 386 or 486! But visually I think it's just the approach we need, where the centre of the screen is the least distorted and it gets more distorted as you move away. Of course, with more cells you have a smaller portion of the globe projected so it look more regular as you add more hexagons. It's the equivalent of zooming in; as a result of this work, it may be easy to add a zoom feature to the 2-D display as well!

So that's how I see it working on the front-end. As for game play, I think using the letter keys should be avoided since these are already reserved for action keywords. Rather, I think we should stick with arrows + Page Up and Page Down. This projects nicely onto the number pad (well, not perfectly but home and end seem better served elsewhere). So Up/6 is up-left; Left/4 is left; Down/2 is down-left, PgDn/3 is down-right, Right/6 is right and PgUp/9 is up-right. Alternatively, you could have 789 for up-left, up, up-right and 456 for down-left, down, down-right or even Insert/Home/Page Up and Delete/End/Page Down for your controls. I think in the end, we just need to allow the user to choose controls but choose logical defaults. It'd be nice to use the arrow keys and Page Up and Page Down are unlikely to be used for anything else so I suggest we use the permutation I spelled out initially.

Now, the nice thing about the game concept is that we could easily represent each cell as an object and have each object hold it's intrinsic properties: links to adjacent cells, terrain type, special type if any, road, rail, river, irrigation, farming, etc. as we as links to a resident city, if any, and a vector/array of links to each of the objects located on that square. There would still be a list of cities and a list of units and all kinds of other lists stored in memory and some grid manager to keep the whole thing contained since such a graph is both highly cyclic and without root. If we consider the path to each adjacent cell as the distance given by its terrain type and improvements as weight in its traversal, we can use the well-known Dijkstra Algorithm (http://en.wikipedia.org/wiki/Dijkstra's_algorithm) to compute shortest paths for goto and connect commands. This is the part that I understand best. It's a pretty neat algorithm and with that, and the unit rules et al. should pretty much stay the same except for the limits on movement as stated above. Sounds simple, eh? Well, a good algorithm for polar projection would be of use, but I'm sure we can find that. As for Dijkstra, we do need to take into account that it runs in |E| + |V| ln |V| time which since |E| is proportional to |V| so this reduces to |V| ln |V| which is not that bad for large sets -- about as quick as sorting the nodes -- but will get worse with a larger grid.

All in all, I think we have a winner here! Let's try and make this happen! I'll lend as much help as I can, especially to the back end and I think 2010 will be the year of the Sphervilition!

Disclaimer: My father probably oversees the funding of the CMMAP (http://www.cmmap.org/index.html) which is where kiwi.atmos.colostate.edu now redirects.
Disclaimer: I used to live in Montréal so have a thing for Geodesic Domes thanks to ça: http://en.wikipedia.org/wiki/File:Mt...Sept._2004.jpg

[TimeHorse]

Actually, a Hexagon can also be converted to a trapezoid and then nudged into the shape of a square by bisecting each hexagon from vertex to opposing vertex either horizontally, vertically or diagonally for a Cartesian or Isometric grid layout.

The problem, as I see it, is when you reach the 12 pentagons. The pentagon can be made into 2 quadrilateral by bisecting it with one point traveling through a vertex and the other through the mid-point of the opposing edge. Unfortunately, this means that along that now bifurcated opposing edge, you have a single hexagon which means 2 cells border the same cell on an edge, not a corner, which is weird. There are various solutions. One would be to split the pentagon into 3 triangle rather than 2 quadrilaterals. Another would be to insert a false edge that wedges the 2 quadrilaterals such that the opposing hexagon shared by 2 cells is connected by a corner vertex of each of the 2 quadrilaterals and yet you can pass directly between each of the 2 quadrilaterals by 'jumping' over the wedge.

Weird, I know, but it is a thought. Freeciv is working on a hex mode but it's not yet working in the latest beta AFAICT. But those 12 pentagons are a real pain and the secret to turning a flat grid into a spherical approximation.

Anyone want to work with me on this?

[alms66]

I know I'd love to have spherical maps for Clash. The one thing I don't think I'd want to lose is it's tile-based nature though.

Here's someone who's actually done something with a geodesic grid in a game prototype here

...and these are my old standby's of what I'd like to see for a spherical map:
and here
and also here

Figure 1 in the "and here" link is about right for a tiny Clash map, don't you think? I'm sure contacting some of these people in these links would provide some help in getting this off the ground. So, are you volunteering to implement this or what?

[LDiCesare]

The 'and here' representation is nice in that it just gets pentagons on the poles.

[alms66]

Actually, they get very hard to see as they get smaller in those images, but according to the text, you've got the standard 12 pentagons in all of the ones shown. I think I can barely make out the pentagon near the western tip of Africa, but out in the Atlantic ocean.

[LDiCesare]

Yes, the vertices in the middle of the stripes in Figure 6 are pentagons, but they drew them as hexagons in Fig. b in order to make it harder to spot. Still, knowing that 2 hexes are always in the poles is nice. The other ones are still a liability in terms of movement though. One could always trick a map generator into putting impassable terrain there, but it's going to create weird artfacts unless the map is very big.

[alms66]

I'd rather not take the impassible terrain route, it makes the tile seem like a waste of space. I didn't care for that in civ4 either.
I certainly hope to have very large maps, but there's only one way to find out how big we can make them.

[subversion]

hi everyone...

i'm a former Clash team member from many years ago, did some experimental Map AI coding for the path intensity stuff (my user name was JimC)

anyway, this idea (geodesic/hexagonal grid over sphere) intrigued me so much that i knocked something together quickly to try it out, and it looks promising... got the 10242 vertex version running at a good FPS

i have an existing code library with tile/graph based map system which works with an A* searcher etc... i'm now quite curious to see how easy it is to tie this spherical map into my existing framework

bad news is its in c#/XNA (i'm a total convert these days)

anyway, let me know if you want source code etc, i'll be happy to share if you can handle c#... for the non-graphical stuff its a pretty easy conversion between c# and java

[alms66]

Sounds good, you can just email it to me if that's ok. Thanks, subversion.