Electronic Thesis and Dissertation Repository

Thesis Format

Monograph

Degree

Master of Science

Program

Computer Science

Collaborative Specialization

Artificial Intelligence

Supervisor

Dr. Michael Katchabaw

Abstract

This thesis presents a novel approach to the Procedural Content Generation (PCG) of both maze and dungeon environments. The solution we propose in this thesis borrows techniques from both Procedural Content Generation via Machine Learning as well as Constructive PCG methods. The approach we take involves decomposing the problem of level generation into a series of stages which begins with the production of macro-level functional structures and ends with micro-level aesthetic details; specifically, we train a Deep Convolutional Neural Network to produce high-quality mazes, which in turn, are transformed into the rooms of larger dungeon levels using a constructive algorithm. For our dungeon’s micro-level details, we use a context-free grammar for the instantiation of interactable puzzle elements, and an n-gram model for decorating our dungeon's entrance rooms. This unique combination of methods successfully generates a large number of visually impressive game levels without compromising on any desirable PCG metrics such as speed, reliability, controllability, expressivity, or believability.

Summary for Lay Audience

This work presents a method for generating video game maze and dungeon levels. We refer to the production of any video game music, graphics, levels, or rules by a computer algorithm as Procedural Content Generation (PCG). Many popular video games today rely on PCG in order to reduce development costs through a reduction in the number of artists and level designers needed for projects as well as increase player satisfaction through vastly more substantial replay value. In terms of the system presented in this work, we use a novel combination of PCG methods found within academic literature such as machine learning models as well as human-controllable algorithms inspired by games found in the commercial games industry. The advantage to using a blend of various PCG strategies is that it allows us to carefully select when and where each method is used in order to leverage their respective strengths while simultaneously circumventing their inherent weaknesses; In particular, our aim was to develop a system which can ensure the playability of each newly created game level, as well as maximize how fast the generator can produce levels, how much control the developers have over the generator’s final output, how many different levels the generator can produce, and how well the final product can fool a player into believing that it was designed by a fellow human as opposed to a computer. A system which possesses all of these desirable traits is extremely important if we wish to have commercial game developers adopt the approaches we are providing, as they are the ones driving the video game industries’ ever-increasing relevance. We view this work as a step towards expanding the possible set of practical methods both game developers and PCG practitioners have at their disposal by demonstrating a novel PCG system which is capable of generating a nearly infinite number of distinct 3D game levels.

Download

Share

COinS