26 January 2014

I recently entered the 2013 GitHub Game Off with a team of colleagues from Softwire. You can see our project, including all of the code discussed below, in our GitHub repository.

The theme for the game off was ‘change’. After brainstorming a few ideas, we decided to build a game based around the idea of dealing with climate change. We split up development of the game amongst the team, and my main focus was on the GUI.

Our first prototype (an extremely minimal viable product) used some real world data to illustrate rising sea levels on a world map. This was interesting in concept, however we decided it would be more appealing and better support our game mechanic if the interface was a more cartoonish fictional mini-planet instead.

I set out with an image in mind of a hex grid on a spinning globe. One important point was that our game would require interaction with the map, so I needed to be able to access and manipulate individual cells on the grid.

Getting started

I thought this was a fairly common model so started looking for libraries that might help. I spent some time playing around with d3js, which I’d already been using for the interface based on the real world, and which has some great features such as orthographic projection of co-ordinates. I also stumbled across a d3js plugin for generating a geodesic sphere, which was very close to what I wanted.

You can construct a geodesic sphere by starting with a regular icosahedron (i.e. a D20), dividing its faces into smaller triangles, and then projecting those triangles out onto a sphere. If each edge is subdivided into n edges, then each face is subdivided into triangles. For n=3 this results in the following shape:

From triangles to hexagons (and a few pentagons)

It is, of course, impossible to tile a sphere using only hexagons, but you can get close by using 12 pentagons and a number of hexagons (which depends on the scale of the grid but can be arbitrarily large). You can construct such a grid by starting with the pattern of triangles described above and then constructing its dual by placing a vertex in the centre of each triangle. The next image shows the corresponding dual for the n=3 geodesic sphere above.
While dual polyhedra are easy to describe in principal, actually constructing them turned out to be a bit tricky in practice. Each triangle in the initial grid would correspond to a vertex shared by three hexagons (or possibly a pentagon and two hexagons) in the dual. To construct each hexagon (or pentagon) in my grid, I would need to find the six (or five) corresponding triangles that would determine the vertices. These would involve determining neighbouring triangles.

A flawed attempt

My first approach relied on the fact that the grid of triangles was constructed in a predictable way. This meant I could just assign all of the triangles a numerical index and work out the patterns of indices that describe neighbouring triangles, which is actually possible generalise in terms of the parameter n mentioned above. The fact that the pattern of indices repeats for each face (modulo the number of triangles in a face) simplifies this a bit, although accounting for triangles that meet along the edges or at the vertices of the original icosahedron was messier. While I did get this approach to work, it resulted in some fairly ugly code that was also very difficult to test in any meaningful way.

Keeping it simple

I decided to go for another approach that would involve less clever code, but a bit more hard work for the computer. I found neighbours by brute force, taking each triangle in turn and searching through all the other triangles to find those that shared an edge. This resulted in much more understandable code that was also more general, which actually made it a little easier to test (by considering simpler cases). The cost of this generality was that the new code was definitely slower to run. However with some judicious choices about search order and a few easy optimisations I got it under a few seconds for the size of grid that I needed. At this point I was able to render my hex grid on a sphere, as in the following image.

Update: I had a suspicion that the brute force part of this approach wasn’t necessary, but couldn’t quite see a way around it myself. However, I managed to get help with this particular problem in a discussion of this article on reddit.

Terrain generation

Once I had a hex grid I wanted to turn it into a little world, and that meant dividing it into continents and lakes, oceans and islands. Part of the mechanic of our game involved dealing with rising sea levels. This meant that I also needed each cell in the grid to have an altitude, so I could redraw the map if necessary as sea levels changed.

While writing the geodesic grid code had been a bit arduous, it yielded an extremely useful byproduct for this process: My algorithm for generating the hex grid made it very easy to store against each hexagon an array of its neighbours.

The algorithm I used for generating the land was as follows:
  • Decide what the total number of land cells should be (e.g. 40% of the grid)
  • Set the starting altitude to the maximum desired
  • Keep choosing land cells completely at random until you reach a tenth of this number
  • Then choose land cells at random from the set of neighbours of existing land cells
  • Each time you pick a cell, set its altitude to the current altitude, and decrement the altitude

This was just the first and simplest approach that came to mind, but it turned out to work quite well, producing pleasingly clumpy land masses with sufficiently interesting features. You can see the end result in the following image, and play around with it in our prototype game (use left/right arrow keys to spin the globe).

A word on testing

Unit testing in general and TDD in particular do not seem to be such mainstream practices in game development as they are in other parts of the software industry, possibly partly because they can be harder to apply. I was attempting to follow TDD on this project, but did find it quite challenging to write meaningful tests for the dual generation code. The second approach I took did enable me to write tests that covered all of the code, although I’m not convinced about how thoroughly my tests probe the output of the code for correctness, and I didn’t TDD it.

For the terrain generation on the other hand, I was pleasantly surprised. I expected procedural generation to be very difficult to test, but I actually ended up with a set of tests that nicely described the desired behaviour, and I was also able to stick to TDD, making one code change at a time to make the current test pass. The following tests (in order) drove the development of the whole algorithm:

it('should mark the correct proportion of cells as land', function() {...});

it('should mark the remaining cells as sea', function() {...});

it('should clump together land locally', function() {...});

it('should spread out land globally', function() {...});

One word of caution though: My procedural generation code does of course rely on a pseudo-random number generator in order to provide different terrain each time, and I initially accidentally wrote some non-deterministic unit tests, much to the consternation of the rest of the team! This was of course easily fixed by setting up a pRNG with a fixed seed value for the tests.

Source code

As mentioned at the top of the article, all of the source code is available on github. The most relevant parts for this article are: