Procedural Level Generation – Block Building part 1

Fight at the gates

Random dungeon in Wizards’ Duel

For Wizards’ Duel the main Dungeon Building algorithm will be based on building Blocks, or rooms. The core of the system is taking these construction Blocks and place them on a grid in a deliberate way, a bit like a Lego construction set. The same concept is used to generate level in Spelunky, you can read more about it here.

Using what i call the Block Building Algorithm has some bid advantages over other algorithms, principally:

  1. The designers have a measure of control over the generation process that allows them to more easily guarantee a certain kind of experience in each level;
  2. A single algorithm can generate all kind of levels by just changing the construction Blocks instead of having to use a different method for each type of layout (dungeons, mines, caves, mazes, building interiors…).

Of course there is a tradeoff, namely:

  1. The generated levels are less random and may contain repetitive patterns that can be recognized by the player, thus breaking the immersion of exploration.

Later on this article I will propose a way to address this issue, but for now let’s take a look at the basic concepts required to run the algorithm.

Tiles Blueprints

Before defining Blocks it is necessary to define the Tiles that will be used to represent them. A Tile Blueprint defines how a certain cell will be filled when generating a level: will it be a wall, a pit, a section of floor, or maybe a window? Will it offer cover, will it block Line of Sight, will it have special scripts attached?

Tiles are defined by several properties:

  1. Their Representation, that will be used inside Blocks definition (it also doubles as ID),
  2. If it blocks Line of Sight (BlocksLoS flag),
  3. If it blocks movement (BlocksMovement flag),
  4. A script that should be run when an Object enters it (OnEnter script).
EXAMPLE - Tiles Blueprints
[
    {
        description: 'Floor'
        representation: '.',
        blocksLoS: false,
        blocksMovement: false,
        onEnter: null
    },
    {
        description: 'Wall'
        representation: '#',
        blocksLoS: true,
        blocksMovement: true,
        onEnter: null
    }
]

Of course, several other properties may be conceived, for example an OnExit script or a BlocksMagic flag etc.

Conditional Tiles

Some tiles can act as a “stand-in” for others. In the case of Conditional Tiles, the blueprint contains a list of references to other Tiles, each with its own probability (actually its Occurrences).

When the generators encounter these kind of Tiles it randomly chooses one of the references to replace the Conditional Tile.

Conditional Tiles are a very powerful way to add variation to the Block Building Algorithm while keeping the control in the hands of the designer.

EXAMPLE - Conditional Tiles
{
    description: 'When an ? Is encountered change it in # (33%) or . (66%)'
    representation: '?',
    references: {
        '#': 1,
        '.': 2
    }
}

Tile Inheritance

While it is not used in WD, it can be useful to define a simple Inheritance mechanism for Tile Blueprints. This means that every Tile also has a Parent reference property. Having a parent means that the Tile property is the same as the Parent if not defined otherwise, just like Inheritance in Object Oriented programming languages.

Blocks

A Block is defined by its 2D appearance, a matrix of Tiles with some meaning, but also other metadata that are useful for constructing the level. These metadata can be defined by the designer of the Block, like I do in Wizards’ Duel, or generated automatically.

These metadata are:

  1. The ID of the Block,
  2. The Width and Height of the Block,
  3. The probability that the Block has to appear in the form of Occurrences (how many times relative to the total number of blocks it has a chance to be selected),
  4. The Exits from this Block, which are further defined by their Position and Direction,
  5. Any number of Objects that may be placed inside the Block when generated, with their own Position, Probability and of course Reference to its Blueprint.

Block can also have Transformations that can be automatically generated when loading. For example we may define a room with an Exit on the bottom (South), then we can instruct the building algorithm to also rotate it 90°, 180° and 270° degrees, to cover all the directions (see picture).

A Block and its rotations

A Block and its rotations

EXAMPLE - Block
{
    id: 'bl_room3x3'
    description: 'A square room with a single exit and central dynamic 
                  lighting, half of the time contains a monster, sometimes
                  a treasure chest',
    width: 5,
    height: 5,
    representation: 
        '#####
         #...#
         #...#
         #...#
         ##.##',
    exits: [
        { position: [2,4], direction: 'South' }
    ],
    objects: [
        { position: [2,2], probability: 1.0, reference: 'bp_light_small' },
        { position: [2,2], probability: 0.5, reference: 'bp_generic_enemy' },
        { position: [2,1], probability: 0.25, reference: 'bp_treasure' }
    ],
    transformations: ['R90', 'R180', 'R270']
}

Note that Blocks do not have to be square or rectangular to work, they just have to tell the generator if a certain cell is used or not: you may define a special Tile for empty space, list the empty spaces etc.

EXAMPLE - Non-rectangular Blocks
{
    id: 'bl_dcorridor'
    description: 'A diagonal corridor, X are empty cells',
    width: 5,
    height: 6,
    representation: 
        'XX###
         X##..
         ##..#
         #..##
         ..##X
         ###XX',
    exits: [
        { position: [4,1], direction: 'East' },
        { position: [0,4], direction: 'West' }
    ],
    transformations: ['MIRROR']
}

Chains of Blocks

Exits can have two additional properties to them: allowedBlocks and forbiddenBlocks. These two arrays of IDs acts as exclusive (you only have one of them) white-list or black-list. They instruct the generator, when searching for the next block, to only use specific blocks.

Using this technique give the designer a measure of control on the generation process. By defining the Starting Block it builds something akin to a Markov Chain of blocks for the generator to use.

Fixed Sized Blocks

If the blocks are of fixed size the procedure for generating the levels can be simplified a bit, while keeping most of the benefits from the Block Building Algorithm.
During generation the level will be subdivided in a grid and each cell of the grid will contain exactly a single block. At this point the only check that needs to be done is to guarantee that the exits match up when placing a block and keeping track on what cells are already used.

 

Having defined these basin construction blocks, next time I will describe in detail the Dungeon Generation Algorithm.

Thanks for reading.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s