Procedural Cartography: The Bones

In this first dev diary post, I’m going to talk a bit about the generator that creates the underlying data behind a Spies & Soldiers map – the bare bones of information, before they’re overlaid with a nice stylish skin by the rendering systems.

An important decision when building the map generator was whether to place gameplay elements first and use them to drive terrain generation, or generate terrain first and then analyse it to find good locations for gameplay elements. The things that interest me most about procedural generation are the process of simulating interesting systems and the sense of creating new worlds to explore. This meant I ended up going with the terrain-first approach, as I felt that there was more potential for interesting surprises if the gameplay emerged from the terrain rather than having terrain just be a cosmetic layer over a more predictable gameplay setup. While quite rudimentary at the moment, there are also elements of simulation in the analysis phase, modelling a population as it builds settlements and sets up shipping routes. The terrain generation is also quite simple, but I’m hoping to add more simulation elements to it in the future.

Another principle I have tried to follow when developing the map generator is to create algorithms that always keep the map geometry valid, rather than generating invalid (e.g. overlapping) geometry and cleaning it up later. This seems to have worked pretty well so far, without imposing too many limitations.

The maps in Spies & Soldiers are built on top of a Voronoi diagram, which is a fairly commonly used tool in the world of procedural content generation. Simply put, a Voronoi diagram is based on a set of seed points on a plane and divides the plane up into a corresponding set of cells, where each cell contains the part of the plane that is closer to its seed than to any other seed. This is a useful way to generate a set of interesting shapes that fills the plane completely without any overlaps.

I was initially planning to use one of the freely available Voronoi diagram implementations, but because we’re using the Moai game engine I needed a Lua implementation, which I was unable to find. Hence, I decided to write my own implementation of Fortune’s algorithm. This involves maintaining a set of parabolas (the “beach line”) whose intersections trace out the edges of the Voronoi diagram, and a list of upcoming events based on the movement of a “sweep line” (which can add or remove parabolas to/from the beach line). I implemented a number of debugging visualisations to help with the implementation, which produced some cool sequences like this:

The resulting Voronoi diagram can easily contain cells that extend beyond the desired area of the map. In addition, there will always be cells that are unbounded on one or more sides. This means the diagram needs to be clipped to fit within the desired map area:

The generation function produces a half-edge mesh representation of the Voronoi diagram, which makes it simple to traverse and modify further. In hindsight I think it was beneficial to implement my own Voronoi diagram generator, as it gave me a deeper understanding of the algorithm and more capability to tweak it according to my needs.

Once the Voronoi diagram has been generated, the map generator marks all cells within one step of the map border as ocean to define the main land mass of the map. Then it marks out up to four islands. My first thought for this step was to start at the coast and follow a semi-random path through the land cells (carving out a channel as it went) until it arrived at the coast again. However, I couldn’t come up with a satisfying way to make sure this approach would produce nice island shapes. Instead, I implemented an algorithm that works as follows:

1. Choose a random coastal cell as the seed cell of the island
2. Grow the island a random number of times (possibly none) by adding all adjacent land cells to the island
3. Mark all land cells within a threshold distance of the island (measured along the mesh edges) as ocean; this creates a channel that cuts the island off from the mainland, leaving enough space for clear visual separation
   

At this point the land masses have been set up. The next step is to define the map gameplay regions, which are the locations that tokens can occupy and move between. Each of these regions is made up of a number of Voronoi cells, which produces more interesting shapes than just using one cell per region. The region creation algorithm groups adjacent Voronoi cells until the area of each group is greater than a threshold value. When choosing a neighbour to merge with, I originally made it use the smallest neighbour, but this produced some quite confusing region shapes and tended to make regions grow too large. It now uses the neighbour with the longest shared edge, which gives nicer region shapes and more consistent sizes.

Once the islands and regions have been defined, the generator tags the edges in the mesh as coast (if they run between an ocean cell and a land cell) or border (if they run between two different regions). These tags are used in the feature extraction step, which extracts region borders and island coastlines, places ports and sea routes, creates a neighbour table, and places settlements.

The generator determines the border of each region by finding one of its border edges and then following the border from that point around in a loop. Islands are extracted by picking an unvisited coastal edge, following coastal edges from that point around in a loop, and storing the loop as the coastline of a new island; this process is repeated until all coastal edges have been visited. I tried making the land mass marking step remember the islands as it marked them out, but ran into a problem where creating later islands could break up earlier islands (or the mainland), producing additional islands that would not be detected. Extracting islands in a separate pass after they’re all marked out avoids this problem.

Once the islands have been extracted, the next step is to place ports and sea routes. Ports are placed by choosing locations around each island’s coast where the ocean is the most “sheltered” (surrounded by land). The algorithm tries to space ports evenly around each island, but allows some deviation from this so that more sheltered locations can be used. It then creates sea routes by using a pathfinding algorithm to connect each port to all ports within a maximum path length, and then connecting more distant ports together if necessary to ensure all islands are reachable from anywhere on the map.

Now that all the connectivity of the map is set up, the generator creates a neighbour table for each region recording which other regions can be reached in a single step (either by land or by sea route).

The next step is settlement placement, which begins by placing the player start positions. Using the information from the neighbour table, these are placed as far apart as possible to allow for some room to manoeuvre before battle is joined. Then the generator places a set number of neutral castles and cities, putting some in isolated regions that have few neighbours and scattering the rest randomly while ensuring none are placed immediately adjacent to the player start positions.

At this point the underlying data is complete, and the map is ready for detail generation and rendering.