Procedural Generation for Simple Puzzles

Puzzles are an integral part of gameplay for many genres. Whether simple or complex, developing puzzles manually can quickly become cumbersome. This tutorial aims to ease that burden and pave the way for other, more fun, aspects of design.

Procedural Generation for Simple Puzzles

Procedural Generation for Simple Puzzles
Together we are going to create a generator for composing simple procedural “nested” puzzles. The type of puzzle that we will focus on is the traditional “lock and key” most often iterated as: get x item to unlock y area. These types of puzzles can become tedious for teams working on certain types of games, especially dungeon crawlers, sandboxes, and role-playing where puzzles are more often relied upon for content and exploration.

By using procedural generation, our goal is to create a function that takes a few parameters and returns a more complex asset for our game. Applying this method will provide an exponential return on developer time without sacrificing gameplay quality. Developer consternation may also decline as a happy side effect.

What Do I Need to Know?

To follow along, you will need to be familiar with a programming language of your choice. Since most of what we are discussing is data only and generalized into pseudocode, any object-oriented programming language will suffice.

In fact, some drag-and-drop editors will also work. If you would like to create a playable demo of the generator mentioned here, you will also need some familiarity with your preferred gaming library.

Creating the Generator

Let’s begin with a look at some pseudocode. The most basic building blocks of our system are going to be keys and rooms. In this system, a player is barred from entering a room’s door unless they possess its key. Here’s what those two objects would look like as classes:

class Key {

Var playerHas;
Var location;

Function init (setLocation) {
    Location = setLocation;
	PlayerHas = false;
}

Function pickUp() {
	this.playerHas = true;
}
}

class Room {

	Var isLocked;
	Var assocKey;

	Function init () {
		isLocked = true;
		assocKey = new Key (this);
	}

	Function unlock() {
		this.isLocked = false;
	}

	Function canUnlock {
		If (this.key.PlayerHas) {
			Return true;
		}
		Else {
			Return false;
		}
	}
}

Our key class only holds two pieces of information right now: the location of the key, and if the player has that key in his or her inventory. Its two functions are initialization and pickup. Initialization determines the basics of a new key, while pickup is for when a player interacts with the key.

In turn, our room class also contains two variables: isLocked, which holds the current state of the room’s lock, and assocKey, which holds the Key object that unlocks this specific room. It contains a function for initialization as well—one to call to unlock the door, and another to check whether the door can currently be opened.

A single door and key are fun, but we can always spice it up with nesting. Implementing this function will allow us to create doors within doors while serving as our primary generator. To maintain nesting, we will need to add some additional variables to our door as well:

class Room {
    Var isLocked;
	Var assocKey;
	Var parentRoom;
	Var depth;

Function init (setParentRoom,setDepth) {
	If (setParentRoom) {
		parentRoom = setParentRoom;
	}
	Else {
		parentRoom = none;
	}
	Depth = setDepth;
		isLocked = true;
		assocKey = new Key (this);
	}

	Function unlock() {
		this.isLocked = false;
	}

	Function canUnlock {
		If (this.key.playerHas) {
			Return true;
		}
		Else {
			Return false;
		}
	}
}

 Function roomGenerator (depthMax)
{
	Array roomsToCheck;
	Array finishedRooms;

	Room initialRoom.init(none,0);
	roomsToCheck.add(initialRoom);

	While (roomsToCheck != empty) {
		If (currentRoom.depth == depthMax) {
			finishedRooms.add(currentRoom);
			roomsToCheck.remove(currentRoom);
		}
		Else {
			Room newRoom.init(currentRoom,currentRoom.depth+1);
			roomsToCheck.add(newRoom);
			finishedRooms.add(currentRoom);
			roomsToCheck.remove(currentRoom);
		}
}
}

This generator code is doing the following:

  1. Taking in the parameter for our generated puzzle (specifically how many layers deep a nested room should go).
  2. Creating two arrays: one for rooms that are being checked for potential nesting, and another for registering rooms that are already nested.
  3. Creating an initial room to contain the entire scene and then add it to the array for us to check later.
  4. Taking the room at the front of the array to put through the loop.
  5. Checking the depth of the current room against the maximum depth provided (this decides if we create a further child room or if we complete the process).
  6. Establishing a new room and populating it with the necessary information from the parent room.
  7. Adding the new room to the roomsToCheck array and moving the previous room to the finished array.
  8. Repeating this process until each room in the array is complete.

Now we can have as many rooms as our machine can handle, but we still need keys. Key placement has one major challenge: solvability. Wherever we place the key, we need to make sure that a player can access it! No matter how excellent the hidden key cache seems, if the player cannot reach it, he or she is effectively trapped. In order for the player to continue through the puzzle, the keys must be obtainable.

The simplest method to ensure solvability in our puzzle is to use the hierarchical system of parent-child object relationships. Since each room resides within another, we expect that a player must have access to the parent of each room to reach it. So, as long as the key is above the room on the hierarchical chain, we guarantee our player is able to gain access.

To add key generation to our procedural generation, we will put the following code into our main function:

 Function roomGenerator (depthMax)
{
    Array roomsToCheck;
	Array finishedRooms;

	Room initialRoom.init(none,0);
	roomsToCheck.add(initialRoom);

	While (roomsToCheck != empty) {
		If (currentRoom.depth == depthMax) {
			finishedRooms.add(currentRoom);
			roomsToCheck.remove(currentRoom);
		}
		Else {
			Room newRoom.init(currentRoom,currentRoom.depth+1);
			roomsToCheck.add(newRoom);
			finishedRooms.add(currentRoom);
			roomsToCheck.remove(currentRoom);

			Array allParentRooms;
			roomCheck = newRoom;

			While (roomCheck.parent)
			{
				allParentRooms.add(roomCheck.parent);
				roomCheck = roomCheck.parent;

			}
			Key newKey.init(Random (allParentRooms));
			newRoom.Key = newKey;

Return finishedRooms;

	}
	Else {
		finishedRooms.add(currentRoom);
		roomsToCheck.remove(currentRoom);
	}
}

This extra code will now produce a list of all the rooms that are above your current room in the maps hierarchy. Then we choose one of those randomly, and set the key’s location to that room. After that, we assign the key to the room it unlocks.

When called, our generator function will now create and return a given number of rooms with keys, potentially saving hours of development time!

That wraps up the pseudocode part of our simple puzzle generator, so now let’s put it into action.

Procedural Puzzle Generation Demo

We built our demo using JavaScript and the Crafty.js library to keep it as light as possible, allowing us to keep our program under 150 lines of code. There are three main components of our demo as laid out below:

  1. The player can move throughout each level, pickup keys, and unlock doors.
  2. The generator which we will use to create a new map automatically every time the demo is run.
  3. An extension for our generator to integrate with Crafty.js, which allows us to store object, collision, and entity information.

The pseudocode above acts as a tool for explanation, so implementing the system in your own programming language will require some modification.

For our demo, a portion of the classes are simplified for more efficient use in JavaScript. This includes dropping certain functions related to the classes, as JavaScript allows for easier access to variables within classes.

To create the game part of our demo, we initialize Crafty.js, and then a player entity. Next we give our player entity the basic four direction controls and some minor collision detection to prevent entering locked rooms.

Rooms are now given a Crafty entity, storing information on their size, location, and color for visual representation. We will also add a draw function to allow us to create a room and draw it to the screen.

We will provide keys with similar additions, including storage of its Crafty entity, size, location, and color. Keys will also be color-coded to match the rooms they unlock. Finally, we can now place the keys and create their entities using a new draw function.

Last but not least, we’ll develop a small helper function that creates and returns a random hexadecimal color value to remove the burden of choosing colors. Unless you like swatching colors, of course.

What Do I Do Next?

Now that you have your own simple generator, here are a few ideas for extending our examples:

  1. Port the generator to enable use in your programming language of choice.
  2. Extend the generator to include creating branching rooms for further customization.
  3. Add the ability to handle multiple room entrances to our generator to allow for more complex puzzles.
  4. Extend the generator to allow for key placement in more complicated locations to enhance player problem solving. This is especially interesting when paired with multiple paths for players.

Wrapping Up

Now that we have created this puzzle generator together, use the concepts shown to simplify your own development cycle. What repetitive tasks do you find yourself doing? What bothers you most about creating your game?

Chances are, with a little planning and procedural generation, you can make the process significantly simpler. Hopefully, our generator will allow you to focus on the more appealing parts of game-making while cutting out the mundane.

Good luck, and I’ll see you in the comments!