Learn by making things

Global Game Jam 2016 - Writing a Procedural Maze Generator

This year I participated in the Global Game Jam at Volta Labs.

The theme of the game jam was ritual. In our group brainstorm we thought of rituals as referring to repetitive behaviors and routines, which got us thinking about robots designed to perform specific functions, which ultimately led to an elaborate and whimsical game idea about amnesiac robots trying to rediscover their purpose.

Directile Dysfunction: A Search For Meaning

Procedurally generated levels were part of the design of the game, and my role in the team was to write the level generator. It later became apparent that our idea was over-ambitious (it wouldn’t be a game jam without a crash course in scope creep!) My new mission was to take the code I had written so far and make a game out of it, trying to fit in as many elements of the original idea as possible. The end result, just barely finished before the deadline, was a simple find-the-exit maze game starring a robot with an existential crisis. You can download the game and Unity project here.

What follows is a post-mortem of the things that worked, the things that didn’t work, and the lessons I learned from my game jam experience.

The Challenge

Being mindful of the always-looming deadline, I chose a simple concept for the procedural level generator. The game world would be a network of individual rooms connected by doors, and only one room would be shown on the screen at any given time, like the dungeons in the first Zelda games.

The algorithm I wrote stored the game world in a two dimensional array. Each element of that array was an instance of a Room class which contained, among many other things, information about which other rooms it was connected to. For every room in the array a compass direction was chosen at random and a connection was made to the neighboring room in that direction. I thought that since every room had at least one connection, a path would therefore exist between any two rooms. After that was done I wrote an ASCII display so I could see the worlds my algorithm was generating…

The Problem

Whoops.

My hypothesis was wrong. Rather than a single network of rooms, I got multiple isolated islands.

level generator problem level generator problem

I realized now that what I was trying to write was, in essence, a maze generator. I started reading about different ways of creating mazes and learned about Kruskal’s algorithm, Prim’s algorithm, and recursive backtracking. (lots of great information and code examples here if anybody is interested!) Many browser tabs later I realized that I had fallen into a Nerd Vortex, that I wasn’t really working on my code anymore, and that it was very late.

I decided to sleep on it.

The Solution

My first plan was simply to create a connection linking each of the islands. To do that I wrote a depth first search algorithm. It worked recursively, calling itself on each neighbor of a starting room and finally returning a list of every room it found. Now that I could identify each island, I could search for connections which would merge two islands together, and repeat that process until only one superisland remained.

The problem was time. I had already spent too much time generating and manipulating graphs of rooms, and there was still an entire game to build! So I decided to use the code I already had for a quick and simple solution: use the largest island as the game world and discard the other islands.

As a bonus, I also got the solution to another problem almost for free! By making a small modification to the depth first search algorithm I could keep track of the recursion depth and attach that data to each room searched. This meant I could pick the two rooms with the least and greatest depth to be the start and end points of the level, so you would never start the game right next to the goal.

What I Learned

Nobody loves the stress of having deadlines, but time constraints are ultimately good for creativity. I have a tendency to be a perfectionist, which can bring my productivity to a standstill if I get lost in small details. Given unlimited time, I probably would’ve started from scratch and tried to implement one of the maze algorithms I had learned about. The deadline forced me to think differently and to keep moving. Instead of seeing my algorithm as wrong and rewriting it, I saw opportunities to make creative use of what I already had.

The lesson I learned is summed up nicely by a poster on the wall at Volta: “done is better than perfect.”