Before we get into more world generation talk, just want to say that there will be some less technical posts in the future that cover game play, videos, music, sfx, etc. So, if you’re bored by technical discussion, we just need to get some proper art before we go too heavy into anything flashy.
This post is a more in-depth discussion of some of the specific algorithms we use for world generation. The previous post covered a more high level process description, while this post will get into some specific examples.
We've built several highly configurable systems to handle generation. The following sections are a deeper dive into some of the more heavily used pieces. There are many ways to accomplish what we're trying to do, but the following, after a lot of trial and error, ended up working well for us.
Biomes
As discussed in the last post, the main generation process’ entire goal is to define biome locations with a size and type. The biome types refer back to pre-configured biome definitions that include a specific algorithm to use and configuration for it.
We have a few different algorithms, but the most dungeon-like generation comes from one we call ‘overlaid rooms.’ The basic concept is to place some number of rectangle rooms of varying size around a biome’s area and then build a minimum spanning tree for connections.
We can vary the room width, height, number, and if overlap of rooms can occur. This allows us to reuse the same algorithm with different configuration and get unique layouts. It's very simple, and can create decent results.
The screenshot below is an example of a biome configuration from our game editor. Note how variables can can tweaked to achieve different results
Hallways
We mainly use 2 connection algorithms for room and biome connections. Also worth mentioning, halls are pretty boring. So, we try to maximize the size and density of biomes and reduce long connecting halls between the interesting content. This was the main reason for injecting biomes when possible during stage 3.
The first algorithm is a “square edge” hallway. To move from one tile to another, we move the entire horizontal distance and then the entire vertical distance in straight lines along the X and Y axis. Despite sounding terrible, this works well for very short distances. The axis to start with can be randomly chosen or based on which is shorter.
The 2nd is a “disjoint” hallway. This delegates the actual generation to another algorithm, usually the square edge, and just repeats the following steps
If the distance between start and end tiles is under some threshold (say 6 tiles), just generate with the delegate algorithm
If the distance is over some threshold, offset the midpoint by some small amount, and then repeat hall generation for both sub segments.
Using the square edge algorithm as a delegate, this results in a jaggy randomized hall between 2 tiles.
Rooms
Our room generation is fairly simplistic, and mostly explained in the previous post.
Each biome generates a set of room outlines and the connections between the rooms. The room size, room connection count, containing biome, etc determine what pre-configured room definitions are applicable.
The room definition contains what types things can be generated within the room and how many of each thing should be added. This is just a few lists of possible decorators, npcs, etc with min and max counts. After a definition is chosen, a random number of items within the min and max counts are selected and added within the room bounds.
Each item to be placed defines its own rules for when it is applicable to be placed. This can be as simple as a torch can only be placed on a wall tile or as complicated as an npc can only be placed in an open tile with 3 surrounding wall tiles and a treasure chest in the right adjacent tile. Keeping restrictions on the items themselves kept room definitions much simpler and allows decorators or npcs to be designed in generic ways.
Our initial version randomly chose tiles within a room and then tried to find an applicable item to add. This ended up not really populating the room well, especially with highly restrictive items. Instead, we now select an item to add and then randomly pick room tiles until a match is found.
Below is an example of our Room Set Editor which allows us to configure the probability of any one room type spawning in the biome.
Rooms can be built using our Room Editor
