Curse you, Riven, for the brain worm you left me with.
So… I’ve been working on Battledroid for quite some time now (and it’s just got a whole lot harder as I am now effectively a full-time housewife thanks to Mrs. Prince suddenly getting a full time job leaving me to wrangle the kids). Whilst Chaz is totally tied up making Basingstoke I’ve been able to slowly trundle away doing long-undone jobs in our game framework in some sort of attempt to make it all a bit more easy to make games etc. etc. blah blah refactor refactor.
A couple of weeks ago I finally had the full metagame in Battledroid implemented, which is the bit where you take over territory on a giant world atlas of the actual Earth, and win the resources contained therein. There was (is) a screen in Battledroid which you can zoom and scroll around the atlas and see who’s got what, and overlay various sorts of data over it such as the size of the armies or the value of the resources or the time since territory was last attacked. There are something like 7m territories in the atlas of which 2m are actually conquerable (the rest of course being ocean). They’re tinted blue if they’re your territories, red if they’re enemy territories, and purple if they’re friends’ territories (Steam friends); the brightness of the territory described the overlaid data value. Plus a few decals such as the location of custom resources, home bases, and such. Yay! There’s a debug mode which lets you click all over the place and “annex” territories and I had a fun little “battle” with a friend the other day watching them turn red and blue.
But I am dissatisfied, thanks to Riven.
See, he said that a hex map would be much nicer. And he is of course right, as a hex map would indeed be much nicer, especially given the significance in this game of contiguous territory clusters. And there’s also the tiny niggling irritation of the fact that no 2D atlas projection manages to get the land area right without looking pretty distorted or being rather difficult to manage or render.
Now here I am building an entirely new world topology based on a geodesic sphere. I am really only just at the start of this particular endeavour but I’ll try and describe where I’m at and who knows, maybe some bright spark in here knows some shortcuts that they might be able to show me.
So, a geodesic sphere is a based on an icosahedron (d20). What you can do is subdivide each face of the icosahedron into many, many smaller equilateral triangles; and then when you’ve got enough, you “balloon” the whole thing out so each point is at a constant radius, which gives you sphere. Though at this stage I am not so concerned about the rendering of the globe which is another problem entirely. Right now, I am concerned simply about the topology of the sphere.
That’s yer basic sphere. I need a subtly tweaked version: I want hexes, not triangles. This means you can’t just naively subdivide the faces of the icosahedron by powers-of-two because hexes don’t quite fit right in that; each hex requires a clump of 9 triangles in which to fit. But this again is simply an issue for rendering the globe later on - I don’t need to worry about it right now.
In order to use my topology in the game, I need a data structure for which I can ask, “Given a hexagon at index n, what are the indices of its six neighbours?”
Firstly, I’ve arbitrarily numbered the vertices, edges, and faces of the icosahedron to give everything some sort of frame of reference, with vertex 0 being the North Pole and vertex 11 being the South Pole. The Greenwhich Meridien will be down edge 0, and Blighty will be split over faces 0 and 4. I am describing the sphere in terms of an “order” (its “size”), which is the number of wholly contained hexes along an edge. For order 0, there will be a single wholly contained hex in each face of the icosahedron. As each vertex of the icosahedron joins five edges, there is a pentagon at each vertex - a special territory which just 5 neighbours. Each edge has a number of hexes which are shared by the two faces on that edge (for a sphere of order n, there are n shared hexes on each edge, and an additional n + 1 edges touching that edge).
In theory I should be able to mathematically calculate the indicies of every hex / pentagon on the sphere, and their neighbours, using a whole bunch of formulae, but this might take me an exceedingly long time to work out being a bear of little brain, so instead I’m going to precalculate the whole lot and stash it in a simple data structure.
Precalculating the whole lot is almost as hard.
What I’m attempting to do is, for each “Face”, construct the appropriate number of “Hexagons”, then iterate along them, joining them together in a two-way graph. After I’ve done all the wholly contained faces I will need to do the “Edges”, stitching the faces together. Then finally the 12 pentagons hold the whole thing together. After that, I should be able to validate the topology with two tests. Firstly, all territories should have exactly 6 unique neighbours (except the pentagons which must have 5). Secondly, I can do a flood fill of the topology, the end result of which should be that I’ve touched every single territory.
Turns out it’s quite a complex problem to solve and might take me a week or two 
Cas
