Posted: 10/10/12 Techniques for procedurally generating puzzle trees and creating interesting, winnable games.

This entry is based on material published as a
Blind Mapmaker article on March 18, 2011.

Indiana Jones and His Desktop Adventures.

At the risk of bloating this entry, I thought it prudent to describe the goal of building a puzzle tree. To do this, I'm going to briefly describe the two games in LucasArts' Desktop Adventures series, Yoda Stories and Indiana Jones and His Desktop Adventures.

At their heart, these games are randomly generation action-adventure games, somewhat of a cross between a Zelda game and a Roguelike, that was designed to create a "coffee-break" experience that could be completed in 30 minutes to an hour. A randomly generated world is created from a bunch of prefabricated rooms, with some of these rooms being dedicated to puzzles. Though the world was open and you could encounter the puzzles in any order, they were dependent on each other, such that you needed to solve them in a particular order.

Yoda's Stories.

Though the games were frustratingly shallow, the techniques used to build these games could be modified to create much more complex Zelda-like games with relatively little modification. A majority of my procedural generation ideas originated from reverse engineering, and then improving, the concepts used in the Desktop Adventures series.

In this entry, I'm going to discuss the basic method used to create a similar gaming experience, and in a future entry, I'll discuss more advanced concepts that take it to the next level.

Before moving forward, let me describe some of the assumptions that I'll be making in order to simplify the process:

Prefabricated rooms.

Rooms are not created or modified by this process. Instead, they are simply selected from a pool of candidates and dropped in, as is. The DA series did feature minor randomization of room elements (items would be hidden under a different random rock each time you played).

One puzzle = One room.

To simplify the process, each puzzle will only take up a single room. While not a difficult limitation to overcome, it will be easier to understand if one considers a puzzle node in the puzzle tree and a puzzle room on the map to be singular, related entities.

You may encounter puzzles before you can solve them.

There is no tier world progression. No locked doors. For a basic introduction to this method, I've decided to limit it to a single, continuous zone. You will be able to encounter every puzzle right from the start. The DA series did have multiple zones connected through gateways, and even multiple themed planets in Yoda's Stories, but that's a discussion better left to the advanced discussion.

Puzzles take only items, give only items.

To keep it simple, only one type of puzzle connection is used. Each puzzle is linked to each other puzzle through inventory items, like the Desktop Adventures. No puzzles are limited by player advancement, cutscenes, world state changes, or required physical abilities.

Any puzzle can accept/give any item.

Similarly, puzzles can use any items. It may seem weird for an archeologist to ask to trade a car engine for a rubber boot, but it keeps the process somewhat simpler. The advanced puzzle tree building entry will discuss theming the glue between the puzzles.

The rooms can connect at any edge.

To keep things simple, all rooms have open edges and can connect to any other room through any of the four sides. There's no shaped rooms, like horizontal rooms that only connect to the east and west. There are no walls preventing two touching rooms from connecting. Any room can be placed anywhere and it is connected and accessible to any adjacent neighbors.

Before the process can begin, you need to have the components you'll use to create the procedural room. Below is a description of each of the components and how they interact.

Fig 159.1.1 - Filler Room.

The majority of the rooms in the game world will not be puzzle rooms. Instead, they will largely be filler that exists to spread out the puzzles, give shape and size to the game world, and to provide a moderate challenge in between puzzles. These are not empty rooms, as they can be filled with monsters to fight, but there is nothing to solve in them and visiting them is entirely optional.

Fig 159.1.2 - Puzzle Room.

These rooms have a one to one correspondence with a node on the puzzle tree. They are rooms with some puzzle to solve. Leaf nodes may involve pushing blocks around to locate an item, while regular nodes will trade one item for another. For example, an NPC may offer to give you a shoebox if you give him a jet-ski.

Fig 159.1.3 - Start Room.

Both the final room and the start room are pre-selected and often related. The start room will give you the basic story of the mission ("oh no, the princess has been kidnapped") as well as function as a leaf node, giving you a starting item to get you on your way.

Fig 159.1.4 - Final Room.

The final room represents a small, prefabricated dungeon or story adventure area that is behind a single locked door. This locked door is considered the final puzzle in the game - the root node of the puzzle tree. While the prefab dungeon may have puzzles or whatever inside it, those are not generated, or if they are, are not generated as part of the core puzzle tree.

Fig 159.1.5 - Event Items.

Event items are items which are only used within the puzzle tree. There may be other gameplay items involved, such as health kits or equipment, but event items are not used outside of trading in the puzzle tree. If you collect a jet-ski item, it can only be given to the guy trading a shoebox for a jet-ski.

Fig 159.1.6 - Puzzle Nodes.

Puzzle nodes are what you are going to be building your puzzle tree out of. They represent a single puzzle, like "used dynamite on brick wall" or "solved block pushing puzzle". Each node has zero or more inputs (items you need to solve the puzzle) and a single output (item you get as a reward for solving the puzzle). Leaf puzzle nodes, such as the starting room's puzzle or block pushing puzzles, have no inputs. The root puzzle node (story dungeon) has only inputs, and no outputs.

Puzzles are "glued" together via a single, randomly selected event item. "Solved block pushing puzzle" will output an item, while "traded weird guy for item" has a single input item. A random event item is chosen to glue the two together. If the item was a pair of snowshoes, the block pushing puzzle would now reward the player with a pair of snowshoes, and the weird guy would now ask for a pair of snowshoes to trade.

Step 1.

You begin the process with a game world. The shape of the world is prebuilt (or at least, built in a prior, unrelated procedural process), but the contents of each room are empty. So the world is more like a shell, which we will fill in in the later steps.

Building the shape of the world should be separated from this process for one simple reason - it dictates the parameters. Because there is a direct one-to-one relationship between puzzle tree nodes and puzzle rooms, the number of rooms available dictate how large your puzzle tree will be. Similarly, if the world's shape is done ahead of time, you don't need to double check the placement of each room to make sure it is valid. Build the world, then fill it. Don't do it simultaneously.

Step 2.

You begin the puzzle tree by selecting a root node. You pick a random puzzle node associated with a final story dungeon and place its associated room somewhere in the world's skeleton.

Step 3.

Next you take a random puzzle node from the pool of puzzle nodes and you "glue" it to one of the inputs to the root node, as described above. After you've done this, take the room associated with that puzzle node and place it randomly somewhere in the world's skeleton.

Step 4.

Repeat the above step X times for various dangling inputs. There are 15 rooms in this skeleton, and I'm aiming for a 50% puzzle room rate. That means that there will be a total of 7 puzzle rooms, including the start room and the final room. Repeat the previous steps enough times that the number of nodes in the tree plus the number of dangling inputs is equal to 7.

Step 5.

Now we have just enough dangling inputs to fill in with leaf nodes. Make sure that at least one of these leaf puzzle nodes is the start room. Glue them to the tree using random event items until there are no dangling inputs left. At this point, you have a complete puzzle tree and each puzzle node's associated room has been placed into the map skeleton.

Step 6.

Finally, randomly choose from among the various filler rooms and place them in any of the empty room spaces in the map skeleton. This will fill the map with combat encounters and complete the process. You are done.

While this is an simplified version of the process, this should go a long way to being able to replicate the structure of the Desktop Adventures game. This process scales extremely well, as changing the size and/or shape the skeleton world will not affect the process at all. As long as you have a start and finish node, you are limited only in the number of puzzle nodes available to you.