Carving the Infinite Plane into Discrete Regions

By Keith Evans (Twitter)



Unlike Infamous or Daggerfall which utilised procedurally generated content (PGC) during development to build staggering amounts of content that would later be refined by traditional designers, games like Dwarf Fortress, RimWorld and Ultima Ratio Regum generate vast, persistent spaces for exploration at player request, each world generated from a single random seed at the start of a game.

A subset of these kinds of spaces are those that exist on an infinite plane. Rather than limit themselves to a fixed area, games like Minecraft potentially go on forever in every available explorable direction. Traditionally built by layering many Perlin or Simplex Noise algorithms of different scales atop each one another, the generator will continually feed a player an infinite horizon by observing the values returned from inputting a given pair of cartesian coordinates to the noise functions, and interpreting the returned values as new tiles (in Minecraft’s case blocks of tiles are built at the same time and stored as chunks).

There are limitations to using noise like this; chief amongst them is it can often appear nonsensical. Should a player take a bird’s-eye view of the world they will see a scattered, abstract pattern with no clear oceans, continents or identifiable features.

From a designer’s point of view it is also difficult to design a game’s mechanics that operate on properties of a map that are wholly random in nature. How often a specific feature of a landscape is generated can be at the mercy of luck, making for interesting terrain but can mean unpredictable gameplay length and pacing.

To address these issues, I have been working on an algorithm to carve an infinite plane into discrete elements. Rather than refer to multiple noise functions to develop individual tiles and chunks in isolation, my generator creates fractal regions on request at runtime. These regions are collections of chunks connected together and generated simultaneously; which know of each other during their generation steps and can build content in relation to each other and in the context of neighbouring regions.

These regions can be thought akin to Zones in an MMORPG such as World of Warcraft or Final Fantasy XIV; they are bounded discrete areas of a given size that know which other zones they are connected to. By carving sections of the infinite space into discrete regions, the problems inherent to infinite space are reduced but still allow for endless exploration.

Figure 1: Generating a region that starts with a 3x3 square of chunks. It then recursively extrudes a smaller square from a random point on each edge, and repeats until it is generating squares only a chunk in each direction. Finally, orphaned chunks are identified and added to the region as well.

The initial pass of the algorithm defines the shape of the area, generated in a variant of a Koch Snowflake. Starting with a large blocked out square of chunks, from a random point on each of the four edges, a smaller square of chunks is extruded outwards. This repeats recursively down to a single chunk (Figure 1). Since these areas are extruded outwards from a given point, rather than simply placed, the algorithm can account for already generated chunks, and can be cancelled at any point along it’s extrusion, generating areas that are wholly contiguous. This area becomes the base region. (Figure 2)

Figure 2: An example of generating a region (orange) that is a neighbour to the one generated from the previous example. The left extruded region intersects the other region and thus doesn’t extend further in that direction.

In the second pass, the generator runs a flood fill sweep from just outside the determined boundaries of this base region (and any of it’s detected neighbour regions), to find any potential chunks that have been orphaned by the process, i.e. those that are wholly enveloped by the base region and its neighbours (Figure 1). These orphaned chunks are added and this forms the region.

Once the physical dimensions of the region and it’s currently generated neighbours of are determined, other steps can proceed. These may include:

  • Climate Assignment, which can be influenced by neighbouring regions to prevent tropical desert zones emerging next to stretches of arctic tundra.

  • Constructing impassable mountains, coastlines and passes at the perimeters to control travel between the region and neighbours

  • Smart placement of gameplay elements; settlements, rivers, roadways and easily identifiable landmarks (“weenies”) can be sensibly assigned to this discrete space, allowing the region to have its own identity.

A region can be created at any point in the infinite plane, with the knowledge that they will connect seamlessly to other parts of the map once new adjacent regions have been generated. This allows for the placement of fixed, future or mandatory content, allowing control of the game’s pacing.

As with all PGC, there are trade-offs in algorithms selected. In this case the order that the regions are generated in changes and influences how regions will be generated in the future, influencing their geography, climate and contents. This makes it impossible to predict what properties any given hypothetical tile will have until the region containing it starts generation, unlike with deterministic noise functions which will always be able to identify what a tile’s content will be simply by passing the algorithm a pair of X,Y coordinates

Despite this complication, this region focused method of generation has potential, and could find a place in any number of games wishing to boast infinitely explorable worlds whilst allowing for context sensitive positioning of gameplay elements.