Skip to content

Procedural dungeon generation

Jump to bottom
Mattias Päivärinta edited this page Sep 24, 2021 · 3 revisions

1. Introduction

In this document we describe an algorithm for generating dungeons for an adventure style game. It is an improved version of what's implemented in Tunics! 0.3.

In section 2 we describe an abstract core algorithm that performs most of the heavy lifting while being oblivious to the specifics of any particular game. In section 3 we discuss how to fill in the blanks with game specific details. In seciton 4 we give a concrete example of game specifics to generate dungeons.

2. Core algorithm

The core algorithm is divided into several phases. Each phase outputs a piece of data that is used as input for the next phase.

2.1. Build plan

The objective of the build plan phase is to define a general structure for a set of dungeons.

The inputs of this phase are entirely implementation specific.

The output of this phase is a directed acyclic graph called a build plan. The datatype of the vertices is implementation specific and opaque to this phase.

The vertices represent the steps to be taken when constructing a feature plan. The arcs represent the ordering constarints on the steps.

2.2. Build sequence

The objective of the build sequence phase is to concretize the build plan into a specific sequence of steps. The build sequence basically describes how to construct the feature plan from scratch.

This phase takes two inputs:

  • A build plan
  • A "traversal-selector" function

The output of this phase is a sequence of steps called a build sequence. The datatype of the steps is implementation specific and opaque to this phase.

The "traversal-selector" function takes a list of vertex indices and returns one of those indices.

The build sequence is constructed by creating a topological sorting of the build plan. When there are multiple candidates for the next vertex in the output the "traversal-selector" function is consulted for the choice.

2.3. Feature plan

The objective of the feature plan phase is to decide the logical structure of the dungeon in terms of "features".

This phase takes two inputs:

  • A build sequence.
  • A "join-selector" function.
  • A "prepend-selector" function.

The datatype of the elements is a tagged union of the following variants:

  • New("feature")
  • PrependGrouped("feature")
  • PrependEach("feature")
  • PrependOne("feature")

The datatype of a "feature" is implementation specific and opaque to this phase.

The datatype of a "join-selector" is a function that takes a list of at least two feature plan nodes and returns either a pair or indices into the list or nothing.

The datatype of a "prepend-selector" is a function that takes a "feature" and a non-empty list of nodes and returns an index into the list.

The output of this phase is a tree called a feature plan. There are two kinds of nodes in the tree:

  • A branch node - has a list of child nodes.
  • A feature node - has a single "feature" and a single child node.
  1. Let the root node be a new branch node without children.
  2. For each command in the build sequence:
    • New(feature):
      1. Add a new feature node child to the root.
      2. If the root node has at least two children:
        1. Let "join-selector" choose two of the root children.
        2. If children are chosen.
          1. Remove the two children from the root node.
          2. Create a new branch node with the two removed nodes as children.
          3. Add the new branch node as a child to the root.
    • PrependGrouped(feature):
      1. Prepend the root node with a new feature node.
    • PrependEach(feature):
      1. Prepend each root child with a new featuer node.
    • PrependOne(feature):
      1. If the root has no children: Add a new branch node child to the root.
      2. Let "prepend-selector" choose a child of the root and prepend it with a new feature node.

2.4. Floor plan

2.5. Furnishing plans

3. Game design considerations

By using the same general template every time we generate a build plan, but parametrizing it with a few basic parameters we can construct a dungeon of the desired complexity.

We can compensate a lack of variability in the build plan by choosing a "traversal-selector" function that chooses randomly among the possible nodes while favouring depth first traversal over breadth first.

In order to only generate valid feature plans we define and enforce a set of constraints on the sequence of generators we use to construct our feature plans. We express these constraints in a build plan. A build plan is valid iff all its [topological sortings][topological sort] result in valid feature plans.

A feature plan is either valid or invalid. A valid feature plan is one that can never dead-lock because of the order in which the player acts upon its features. An invalid feature plan is one where you can get dead-locked.

There is a trivial feature plan with no features. Starting from the trivial feature plan we generate a more interesting feature plan by applying a sequence of generators.

4. Example game implementation

This section describes how to roughly reimplement the algorithm in Tunics! 0.3 using the core algorithm described in section 2.

This is the template for the build plan:

  • The following vertices always exist:
    • One Boss vertex (This represents placing of the boss room
    • One Treasure("bigkey") vertex
    • One Treasure("map") vertex
    • One HideTreasures vertex (This represents marking of a subset of the previously placed treasures as hidden behind a puzzle.)
    • One Compass vertex
    • num-keys LockedDoor vertices (Each representing the placing of a single locked door
    • num-keys SmalleKey vertices
    • num-fairies Fairy vertices (This represents the placing of `num-
    • num-cul-de-sacs CulDeSac vertices
    • For each element in the treasures list:
      • One BigChest vertex (Represents the big chest for this item.)
      • One Obstacles vertex (Represents the placing of obstacles for this item.)
  • The Bigkey vertex depends on the Boss vertex.
  • The Compass vertex depends on the HideTreasures vertex. (This ensures that the compass is never hidden behind a puzzle.)
  • Each Obstacles vertex depends on the Boss vertex.
  • Each BigChest vertex depends on its corresponding Obstacles vertex.
  • If the treasure "bombscounter" is in the treasures list:
    • The Obstacle(VeryWeakWall) vertex depends on the Obstacle(WeakWall) vertex. (This ensures that no very weak walls are placed behind weak walls.)
    • The Treasure("map") vertex depends on the Obstacle(VeryWeakWall) vertex. (This ensures that the map is never placed behind a bomb-door.)
  • All LockedDoor vertices depend on each other in a chain.
  • The first LockedDoor vertex in the chain depends on the Treasure("bigkey") vertex. TODO: say something about this.
  • All SmallKey vertices depend on each other in a chain.
  • The first SmallKey vertex in the chain depends on the last LockedDoor vertex. (This ensures that you can never deadlock yourself by having the last small key together with the big key behind the last locked door. In fact all small keys are accessible without opening any locked doors at all.)

In each node in the build plan we include a count of the number of its children plus one (for itself). We call this the weight of the node.

We define the "traversal-selector" function such that chooses a node at random according to their weights.

4.1. List of treasures

Treasures are items that you get in big chests. For each item there is a set of obstacle types that are unlocked by this item and this item alone.

TODO: List all available treasures

TODO: For each treasure, list its set of obstacle types

Clone this wiki locally