Constraint Based Procedural Content Generation With ML

Introduction

I have been reading this book on Procedural Content Generation and its integration with ML. As I go through this book, I will try my best to implement the concepts we go over in small, easily implementable examples. In this chapter, we will implement some algorithms to allow our model to learn rules from example levels and layouts rather than us having to manually input that information.

The Notebooks used in this article can be found in the below repository.

PCGML/constraint-based-pgml at master · mattmacf98/PCGML

Generating Levels

Our first task is a a classic Procedural Games task — we want to generate lots of levels automatically, but we don’t want nonsensical layouts we want our levels to follow a shared set of guidelines.

We are given our level in the form of columns labeled A-H.

Below is a sequence that follows: [‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’, ‘A’, ‘C’, ‘H’]

and together generates the below level

We could manually describe the rules in code, saying A must be followed by B or C and F always comes after E etc… This would work and then we would just generate our level by following our rules. This rule creation is tedious work and is rather inflexible, perhaps the rules are something we can actually learn from our input data.

Extracting Rules

The first thing we must do is extract our rules given some example levels.

col_labels = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'A', 'C', 'H']
col_to_segment = {
    'A': 0,
    'B': 1,
    'C': 2,
    'D': 3,
    'E': 4,
    'F': 5,
    'G': 6,
    'H': 9
}

forward_adjacency_rules = {
    'A': set(),
    'B': set(),
    'C': set(),
    'D': set(),
    'E': set(),
    'F': set(),
    'G': set(),
    'H': set(),
}

backwards_adjacency_rules = {
    'A': set(),
    'B': set(),
    'C': set(),
    'D': set(),
    'E': set(),
    'F': set(),
    'G': set(),
    'H': set(),
}
for i in range(len(col_labels)):
    forward_adjacency_rules[col_labels[i]].add(col_labels[(i+1) % len(col_labels)])

for i in range(len(col_labels)):
    backwards_adjacency_rules[col_labels[i]].add(col_labels[(i-1)])

print(f"Forward Adjacency Rules {forward_adjacency_rules}")
print(f"Backwards Adjacency Rules {backwards_adjacency_rules}")

Since this is a level, the type of rule we are extracting is adjacencies. We read through the data and see what adjacencies are present and possible.

Forward Adjacency Rules {'A': {'C', 'B'}, 'B': {'C'}, 'C': {'H', 'D'}, 'D': {'E'}, 'E': {'F'}, 'F': {'G'}, 'G': {'A'}, 'H': {'A'}}
Backwards Adjacency Rules {'A': {'H', 'G'}, 'B': {'A'}, 'C': {'A', 'B'}, 'D': {'C'}, 'E': {'D'}, 'F': {'E'}, 'G': {'F'}, 'H': {'C'}}

The Algorithm

We will input how many columns our level should be and we will start out with an array of that length where each entry contains a list of the possible values that entry could be.

We will then make an observation and collapse a column to one choice and propagate the results of that choice until all columns are collapsed.

Observe

def get_most_constrained_index(level):
    option_lengths = [len(column) for column in new_level]
    min_index = -1
    min_num_options = math.inf
    for i in range(len(option_lengths)):
        if 1 < option_lengths[i] < min_num_options:
            min_index = i
            min_num_options = option_lengths[i]

    return min_index

We simply pick the non-collapsed index that has the least number of options left. This is the one we will collapse.

Propagate

def select_and_propagate(level, index):
    selected_option = np.random.choice(level[index])
    level[index] = [str(selected_option)]
    propagate(level, index, 'both')
    return level

We collapse our given index by randomly choosing from its options, and then we will propagate that decision to the rest of our columns.

def propagate(level, index, direction):
    column_options = level[index]
    if index > 0 and direction != 'forwards':
        enforced_constraint_options = set()
        for option in column_options:
            for back in backwards_adjacency_rules[option]:
                enforced_constraint_options.add(back)

        prev_col_options = set(level[index - 1])
        level[index - 1] = list(prev_col_options.intersection(enforced_constraint_options))
        if len(level[index - 1]) == 0:
            raise RuntimeError("No Valid Solutions")
        propagate(level, index - 1, 'backwards')
    elif index < len(level) - 1 and direction != 'backwards':
        enforced_constraint_options = set()
        for option in column_options:
            for forward in forward_adjacency_rules[option]:
                enforced_constraint_options.add(forward)

        next_col_options = set(level[index + 1])
        level[index + 1] = list(next_col_options.intersection(enforced_constraint_options))
        if len(level[index + 1]) == 0:
            raise RuntimeError("No Valid Solutions")
        propagate(level, index + 1, 'forwards')

Since we are building a 2D platformer using a sequence of columns, our generation is 1-dimensional so our propagation logic only needs to go forwards or backwards.

We use our extracted rules to determine what the viable neighbors could be for the remaining options of our columns. We take the intersection of those options and the neighbor’s current options to then set to the neighbor’s new options (which will be more restrictive).

We then recursively propagate, since we have altered our immediate neighbor’s options which in turn would affect their other neighbor’s options.

This propagation can sometimes have no solution, in which case we will just throw an error so we can start over.

The Loop

columns_to_create = 15
new_level = []
max_tries = 10000

cur_try = 0
while True:
    try:
        new_level = [['A','B','C', 'D', 'E', 'F', 'G']] * columns_to_create
        while np.any([len(column) != 1 for column in new_level]):
            index_to_collapse = get_most_constrained_index(new_level)
            if index_to_collapse == -1:
                break
            new_level = select_and_propagate(new_level, index_to_collapse)
        break
    except:
        print("Retrying...")
        cur_try += 1
        if cur_try >= max_tries:
            break
        continue
    
print(f"Final level {new_level}")

We initialize the level and loop while there is some column which is not collapsed.

Running the code spits out a sequence of columns like

Final level [['B'], ['C'], ['D'], ['E'], ['F'], ['G'], ['A'], ['B'], ['C'], ['D'], ['E'], ['F'], ['G'], ['A'], ['B']]

Which we can visualize

final_columns = []
for col in new_level:
    img_seg_index = col_to_segment[col[0]]
    final_columns.append(segmented_images[img_seg_index])

total_width = sum(img.width for img in final_columns)
max_height = max(img.height for img in final_columns)

concatenated_image = Image.new('RGB', (total_width, max_height))

# Paste each image into the new image, one after the other
x_offset = 0
for img in final_columns:
    concatenated_image.paste(img, (x_offset, 0))
    x_offset += img.width

plt.figure()
plt.imshow(concatenated_image)
plt.show()

Summary

• We can extract rules from example content
• We can create a new piece of content by initializing all entries to be anything
• We whittle down the options by collapsing entires and propagating the consequences of that collapse using our extracted rules

Wave Function Collapse

Wave Function Collapse is another method which uses example content in order to synthesize new content. Wave Function Collapse is quite cool because it can work based on pixel color so you don’t even need to have example content which was built using standardized tiles.

In our demo, we will base our generation on the patterns encoded in the above image.

Extract

Our first step is to extract the data rules from our example. Wave Function Collapse builds its own tile set and adjacency rules by running a convolution over our image. Creating overlap blocks which act as the connectors between tiles.

overlap_images = []
overlap_blocks = []
overlap_image_dim = image.size[0]
for block_row in range(len(blocks)):
    for block_col in range(len(blocks[0])):
        overlap_block = [
            [blocks[block_row][block_col], blocks[block_row][(block_col + 1) % len(blocks[0])]],
            [blocks[(block_row + 1) % len(blocks)][block_col], blocks[(block_row + 1) % len(blocks)][(block_col + 1) % len(blocks[0])]]
        ]
        overlap_blocks.append(overlap_block)

        overlap_image = Image.new("RGB", (overlap_image_dim,overlap_image_dim))
        for x in range(overlap_image_dim):
            for y in range(overlap_image_dim):
                tile = base_tiles[overlap_block[y // 32][x // 32]]
                color = tile.getpixel((x * (base_tile_dim // overlap_image_dim), y * (base_tile_dim // overlap_image_dim)))
                overlap_image.putpixel((x, y), color)
        overlap_images.append(overlap_image)

We are doing a 2x2 convolution over our 4x4 image block, at the end we will have 16 tiles where each tile is a zoomed out block of a 2x2 section of our original image.

Observe

Like our platformer, Wave Function Collapse uses a series of observing and propagating steps to generate the final output.

def observe(grid):
    entropies = [len(arr) for row in grid for arr in row if len(arr) > 1]
    if len(entropies) == 0:
        return -1, -1
    min_entropy = min(entropies)

    collapsable_indices = []
    for row in range(len(grid)):
        for col in range(len(grid[0])):
            if len(grid[row][col]) == min_entropy:
                collapsable_indices.append((row, col))

    cell_index = np.random.choice([i for i in range(len(collapsable_indices))])
    row_to_collapse, col_to_collapse = collapsable_indices[cell_index]

    option_index = np.random.choice([i for i in range(len(grid[row_to_collapse][col_to_collapse]))])
    grid[row_to_collapse][col_to_collapse] = [grid[row_to_collapse][col_to_collapse][option_index]]
    return row_to_collapse, col_to_collapse

We get a cell in our NxN grid with the least options, collapse it to one of its options and return the row and column indices for it.

Propagate

def propagate(grid, overlap_blocks, collapsed_row, collapsed_col, direction):
    row = 0
    col = 0
    if direction == "up":
        row = collapsed_row - 1
        col = collapsed_col
    elif direction == "right":
        row = collapsed_row
        col = collapsed_col + 1
    if direction == "down":
        row = collapsed_row + 1
        col = collapsed_col
    elif direction == "left":
        row = collapsed_row
        col = collapsed_col - 1

    if row < 0 or col < 0 or row >= len(grid) or col >= len(grid):
        return

    current_options = grid[row][col]
    new_adjacency_options = get_adjacency_rules(grid[collapsed_row][collapsed_col], overlap_blocks, direction)

    new_options = list(set(current_options) & set(new_adjacency_options))
    if len(new_options) == 0:
        raise RuntimeError("No Solution Available")
    if len(new_options) != len(current_options):
        grid[row][col] = new_options
        propagate(grid, overlap_blocks, row, col, "up")
        propagate(grid, overlap_blocks, row, col, "right")
        propagate(grid, overlap_blocks, row, col, "down")
        propagate(grid, overlap_blocks, row, col, "left")

Since we our working in a 2D setup, we need to propagate in 4 directions. The logic is very very similar to our 1D example: get the options for neighbors based on adjacency rules, set our neighbor’s new options as the intersect of their current options and the adjacency derived ones, recurse on our neighbors.

def get_adjacency_rules(options, overlap_blocks, direction):
    self_pixels_to_test = [(0,0), (0,0)]
    other_pixels_to_test = [(0,0), (0,0)]

    if direction == "up":
        self_pixels_to_test = [(0,0), (0,1)]
        other_pixels_to_test = [(1,0), (1,1)]
    elif direction == "right":
        self_pixels_to_test = [(0,1), (1,1)]
        other_pixels_to_test = [(0,0), (1,0)]
    if direction == "down":
        self_pixels_to_test = [(1,1), (1,0)]
        other_pixels_to_test = [(0,1), (0,0)]
    elif direction == "left":
        self_pixels_to_test = [(1,0), (0,0)]
        other_pixels_to_test = [(1,1), (0,1)]

    adjacency_options = set([])
    for option in options:
        pattern = [overlap_blocks[option][self_pixels_to_test[0][0]][self_pixels_to_test[0][1]], overlap_blocks[option][self_pixels_to_test[1][0]][self_pixels_to_test[1][1]]]
        for block_index in range(len(overlap_blocks)):
           check_pattern = [overlap_blocks[block_index][other_pixels_to_test[0][0]][other_pixels_to_test[0][1]], overlap_blocks[block_index][other_pixels_to_test[1][0]][other_pixels_to_test[1][1]]]
           if pattern[0] == check_pattern[0] and pattern[1] == check_pattern[1]:
               adjacency_options.add(block_index)

    return list(adjacency_options)

Our adjacency rules look at the overlap blocks of the current cell’s options and the candidate overlap blocks to determine if the candidate block could border the current cell, if so it is added to the options list.

The Loop

max_attempts = 10
attempt = 0
while True:
    size = 20
    grid = []
    for i in range(size):
        grid.append([[i for i in range(len(overlap_images))]] * size)
    try:
        collapsed_row, collapsed_col = observe(grid)
        while collapsed_row != -1:
            propagate(grid, overlap_blocks, collapsed_row, collapsed_col, "up")
            propagate(grid, overlap_blocks, collapsed_row, collapsed_col, "right")
            propagate(grid, overlap_blocks, collapsed_row, collapsed_col, "down")
            propagate(grid, overlap_blocks, collapsed_row, collapsed_col, "left")

            collapsed_row, collapsed_col = observe(grid)
        break
    except:
        if attempt < max_attempts:
            print("No Solution, Retrying...")
            attempt += 1
        else:
            break

We set up our grid with all possible options, and then loop through our collapse propagate logic.

At the end, we will have a grid where each entry is an overlap block index.

def visualize(grid, size):
    image = Image.new("RGB", (16 * size, 16 * size))
    for row in range(size):
        for col in range(size):
            if len(grid[row][col]) == 1:
                overlap_block_index = grid[row][col][0]
                tile = base_tiles[overlap_blocks[overlap_block_index][0][0]]
                for x in range(16):
                    for y in range(16):
                        color = tile.getpixel((x * (base_tile_dim // 16), y * (base_tile_dim // 16)))
                        image.putpixel((col * 16 + x, row * 16 + y), color)
            else:
                color = (255,255,255)
                for x in range(16):
                    for y in range(16):
                        image.putpixel((col * 16 + x, row * 16 + y), color)
    plt.imshow(image)
    plt.axis('off')
    plt.show()

To visualize our result, we grab the tile at [0][0] of our overlap block and paint the grid cell with that tile.

Summary

• Wave function collapse is a PCG method which can learn adjacency rules without strict tile sets
• WFC generates its own tile sets and rules by overlapping adjacent sections of the input image

Conclusion

In this article, we applied a form of ML for rule extraction in two different algorithms. Extracting rules from exemplary content is easier and more dynamic than hard coding the rules. Both approaches followed a loop of collapsing entires to singular values and then enforcing the rules based on that collapsed value to neighboring cells.

One thing you might have noticed is that these approaches did not take frequency of occurrence into account, anything that occurs in the example content appears with equal weighting in the generated content. Also, our generated content will never produce a pattern which is unseen in the example content — this may be good or bad depending on your goals. We will see how to address both of these issues in the next article where we add probability to our generation process.