Procedural Overworld Generation

I sometimes have conversations with others about various game ideas. A lot of these conversations involve procedural generation, a topic I find absolutely fascinating. Procedural generation in its simplest sense refers to when you have a program generating some form of content instead of having it manually designed by a human. A current mainstream example would be Minecraft where the game automatically generates a seemingly infinite unique world for each player.

The creation of worlds or levels is a common use of procedural generation, though many other things can be generated as well. This ranges from more tangible things like graphics or music to the more abstract. An example of the latter would be the AI Director from Left 4 Dead, a system that constantly changes how and when hordes of zombies will attack each time you play a level so as to increase suspense and uncertainty.

Given my personal interest in the topic, I’ve been in numerous discussions about how to generate various different aspects of various different sorts of games, some of which I hope to discuss on this blog in the future.

Today’s showcase is a proof-of-concept procedural generator for overworld maps in the style of games like Super Mario Bros. 3 (SMB3) or Shovel Knight, i.e. level icons connected by a non-linear mesh of orthogonal roads. In this prototype, I use graphics borrowed from SMB3 as a placeholder. Despite this appearance, the generator is not intended to generate actual SMB3 maps (though integrating something similar into an SMB3 randomizer would be cool), but rather maps for an unannounced game idea still in an extremely early “throwing ideas around” phase.

I intend to go into more detail about the actual algorithms behind this generator in a future post, but for now, I’ll show some screenshots and describe some of the things it can do.

A screenshot from a prototype map generation UI. Various settings can be tweaked on the fly to see how they impact the map generation.

As is commonplace in procedural generation, the input to the generator consists of a seed – from which pseudo-randomness is derived – and a set of settings that constrain the generated map in various ways. During gameplay, the seed would be randomly generated whereas the settings would be carefully chosen in advance by the developer. Presumably, a few different sets of settings would be carefully crafted to produce different sorts of maps. These have to balance desired outcome with generation speed as some types of maps are considerably more difficult – i.e. slower – to generate.

Another, slightly smaller, example of a map generated by this system.

The basic structure of the basic road network is controlled by two settings. The first one is called complexity which determines how many additional features – such as branches or small loops – should be added to the network. To illustrate, consider this comparison of a map with a complexity of one and another map generated using the same settings, but with a complexity of five:

Comparison between a low and a high complexity map with the same number of levels.

Of course, the second image looks a bit exaggerated since that amount of road segments for a map with a single level is ridiculous. For a map with numerous levels, the same network would make more sense.

The second road network setting is called connectivity and controls how interconnected the map is. The map that’s initially generated is relatively linear, modulo a few minor branches and cycles as controlled by the complexity. The purpose of connectivity is to then take this semi-linear map and tie it together into a larger loop. This effectively creates a map with a vaguely circular structure and, roughly speaking, two primary routes that one can take through the world. A higher connectivity value would repeat this process more times, although doing so rapidly decreases the chances being able to generate a map. This is due to the risk of the road network being non-planar (which is undesirable for this this type of map) skyrocketing as the interconnectivity increases.

To further illustrate how connectivity affects the map, consider this comparison of a map with a connectivity of zero and another map with a connectivity of one:

A zero-connectivity map showcasing a pseudo-linear network, and a one-connectivity map where the road network was joined into a larger loop.

Aside from the road network settings, one can also control the number of rivers to generate, whether or not to generate a port level on the river, how many shortcut caves to generate (which are here represented as the vaguely analogous SMB3 warp pipes) and lastly how many actual levels to place.

Another generated map where only the left half was joined into a loop, causing a choke point in the middle of the map and disconnected branching on the right.

While the main purpose of this generator is to generate the road network itself, it also has basic biome and decoration generation. For reasons specific to the unannounced game, the map is primarily a dry terrain (with palm trees), but with occasional patches of more lush terrain (bushes) and some other patches of badlands (mushrooms??), though the approach can be adapted for many other scenarios. An additional detail to note is that the rivers partially override the natural biome generation by increasing the probability of lush terrain near them. Likewise, the castle at the end of the world has the opposite effect, increasing the badlands probability near it.

The biomes may look a bit patchy in the images, though that’s partially an artifact of the medium. The biome for any given tile is actually on a spectrum from lush to badlands, but the current SMB3 assets I’m using – with three types of terrain – cause the edges between the biomes to appear aliased. It would be possible to do smoother transitions even with these assets, though putting time into making a system for interpolating the placeholder graphics (which would not necessarily carry over into whatever the final appearance might be) seems a bit unnecessary.

So, that’s what this generator is currently capable of. In a future post, I will go more in depth about how the generator actually works. (Spoiler: it’s actually a pipeline of several different generators to handle the various aspects of the map.)

Tags: , ,