Tomus Blogus Noteworthy coding techniques and discussion

30Jun/130

Procedural content generation framework

I've somehow become enthused about procedural content generation, and my enthusiasm isn't content to just pick an example case and figure out how to do it, it's gone and dreamed up a framework where procedural generation algorithms are composed out of small elements, and can be extended and modified by swapping out pieces of an existing algorithm or throwing new elements into the mix. Then it went and dreamed up an online repository, where existing elements could be downloaded and mixed together to create customised algorithms.

Usually this kind of airy fairy, nonspecific scope creep will quickly inflate a potential project into the land of fantasy, but I've decided to stick with it and see if I can boil it down to something useful.

The project has 2 layers:

  1. Create a general purpose framework for procedural content generation algorithms, composed out of smaller parts.
  2. Implement a specific working example using the framework.

The framework

The framework is quite general. It doesn't dictate what kind of content it generated (2D, 3D, haiku, ...), but rather focuses on how the pieces can advertise what they do, and discover each other.

Its main requirements are:

  1. You can introduce new code and assets into existing algorithms to extend them
  2. You do not have to explicitly change the existing algorithms. If the new code/assets are suitable it will automatically find and use them
  3. Larger algorithms can influence the behaviour of the sub-algorithms it uses.

For example, an algorithm to generate a house might have steps to layout the main area, insert hallways, subdivide into rooms, populate those rooms with items. We may want to introduce a new "chandelier" asset to use while populating the rooms, or a new algorithm for laying out hallways if the building happens to be a jail. The framework should be able to find the new asset/algorithm and use it in correct place in the appropriate context.

After a few iterations I've come up with the following concepts:

Content

Is what algorithms generate.

It can either be final content to be consumed by the application/game we are generating it for (height-maps, object placements, way-point graphs, etc). Or it can be intermediate content generated at a higher level, and used as parameters for lower level algorithms. For example, a generate house algorithm needs to know where it's allowed to put it.

The framework doesn't dictate what content actually is, so we store it as a dictionary of general purpose objects, keyed by a text ID.

Assets

Are general purpose assets, like textures etc, that can be used for generating content.

Again the framework doesn't care what the content actually is.

Generators

These are the algorithms that generate actual content.

Library

A library object to store the available assets and generators. Each is categorised and has optional "traits" (see below)

Categories

Categories are used to indicate where an asset or generator can be used.

For assets, the category is simply a text identifier, e.g. "Texture".

For generators, the category can also specify pre-requisite content that must be present before any algorithm can be run, as well as the content that each algorithm in the category must guarantee to generate. This is important for validating that a procedural generation program can actually execute properly.

Traits

Traits work together with categories to indicate when it is appropriate to use an asset or generator. The category indicates whether the program can use the object. The traits indicate whether the program should.

For example, a golden chandelier (asset) can be generated in the middle of a room. But if the room being generated is a run-down grass hovel, it probably wouldn't be appropriate. Likewise a room layout algorithm that creates regular sized rooms with space for a toilet and bunk-bed might be appropriate if generating a prison building, it probably shouldn't be selected when generating a residential home.

Traits are used to indicate to the framework when assets/algorithms are appropriate to use, so that larger algorithms can request suitable objects from the framework without knowing about them specifically. This is a crucial part of its extensibility, as we can introduce new assets/algorithms and have them used automatically.

Queries

Queries are used to fetch assets/generators from the library by category. Queries can also specify the required traits, to ensure relevant content is returned.

The query currently can specify "Must have trait: X", and the engine will randomly select from the set of matches. But I feel this area could grow out to include things like weighted random selection, or "fuzzy" query criteria "Prefer trait X over trait Y" etc.

For now I'm keeping it simple.

Filters

Filters are used by larger algorithms to control the behaviour of its generators. They are effectively trait-based criteria which must be added to any queries performed by the generators.

For example, a castle generation algorithm (itself a member of the "generate building" category), might define filter criteria for wall and floor textures, such as "floor type = stone", "wall type = stone".  Or a town layout algorithm may use traits to control the type of buildings generated in a particular area based on whether it is a rich or poor area.

Generator Graph

Finally this graph pull everything together into an executable program.

Each node can either be:

  • A reference to a generator
  • A generator category (referenced by ID)
  • Another graph

Generator categories are preferred to referencing a specific generator directly, as it allows the extensibility mechanism to be used. In fact I'm still tossing up whether to include direct references to specific generators at all.

The ability to reference another graph allows for grouping algorithms together. E.g. a "generate basic house" algorithm built from multiple generators can be registered itself as a "generator".

The specific example

My simple example I've called "ASCII dungeon", which you've probably guessed is a 2D map of ASCII characters containing a procedurally generated dungeon.

To start with I'm going to generate a building, and the algorithm I've come up with is:

  1. Place an initial rectangular area.
  2. Extrude it a handful of times
  3. Connect areas together using hallways (and split areas into rooms around them)
  4. Add hallway doors
  5. Add doors between rooms

So far I've implemented steps 1 & 2: