Posted: 10/08/12 A way of representing game progress to ensure a game is winnable.

This entry is newly written, but covers material published in multiple
Blind Mapmaker articles from August 2010.

Fig 158.1 - A Puzzle Tree From Grim Fandango.

Back in the early day of gaming, it was not uncommon for adventure games to have unwinnable situations. Maybe an item you need has become inaccessible. Or maybe you accidentally broke the sequence of puzzles. Or perhaps the designer just didn't design for a specific situation. If only there were some way that a designer could represent the puzzle dependencies in their game such that dead ends and broken progression were obvious and avoidable...

Much like how [#004 - Environment Tree] solves the basic problem of creating winnable lock-key solutions, a puzzle tree provides a mechanism by which to represent a sequence of puzzles to ensure a winnable solution.

I did not invent the concept of puzzle trees. It is the natural existence of any game with a sequence of dependent events. You can create a tree (or flowchart) out of any adventure game or RPG. However, there is little in the way of formalization or discussion of how it affects design. By formalizing this structure, one can take note of patterns and how they affect the overall work.

There's even less discussion on how puzzle trees could be the single most important innovation in procedural game generation. If you want to procedurally generate an RPG, the puzzle tree is going to be the backbone of the entire game. Period. Understanding it and knowing how to create one is fundamental to game design.

A puzzle tree is mathematical tree structure where each node represents a single puzzle, and each edge representing the dependencies between them. For instance, to win you need to get a car. There is a mechanic which has a an old beat up junker that he will sell you for $3,000. It doesn't work, as it has no gas and needs new tires. You can get the gasoline by syphoning it from the gas generator and you can steal a set of tires from an abandoned car. The $3,000? Well, you just need to grind that out the old fashioned way. If you were to make this into a puzzle tree, it would look like this:

Fig 158.2 - What I Just Said, But In Boxes With Lines and Junk.

The root node is basically a final goal, usually something like winning the game or the end of a quest chain. Due to the fact that we tend to start at the top and finish at the bottom, puzzle trees tend to be presented upside down, with the root nodes at the bottom, and the arrows pointing from child to parent. If we read it this way, top to bottom, it reads like a sequence of events. A then B then C.

It is possible to have multiple root nodes, as in cases where there are multiple endings or for goals that are optional to victory. For instance, an RPG might have a side quest where you collect dragon eggs. If you collect all of them, you will earn a super dragon sword. Gaining that sword would be the root node to the dragon egg subquest. As the dragon sword is not required for victory, it would be its own tree that may share puzzle nodes (you need to finish the dragon dungeon to win the game and get the dragon sword).

Leaf nodes are puzzles which have no dependencies. For instance, you may find a crowbar on the floor. You do not need to have solved any puzzles in order to pick it up. Another example might be if the crowbar was behind a door that required you to solve a sliding block puzzle to get in. As you can solve sliding block puzzles without requiring any items, you can solve this puzzle the moment you encounter it. If a puzzle has no dependencies, it is a leaf node.

The edges between each node represent the dependencies that one puzzle has for another. In most cases, this is an item. Solve a puzzle, get an item. Use item to solve next puzzle. Adventure games tend to be primarily item-based puzzles (use crowbar on hamster), possibly because they allow puzzles to be indirectly related over a large geographical area.

Less frequently, you'll see puzzles dependent on learning new information. For instance, you may find a piece of paper which has the safe's combination on it. If that combination doesn't change, you can open the safe in subsequent play-throughs (or using a FAQ) without doing the prior puzzles in the sequence. If you learn that mixing the blue potion with the green potion creates a necessary poison, it's the same thing. These dependencies are based on learning something about the game world to be utilized later - and you have to assume that repeat players, cheaters, and FAQ users will be able to break the sequence by gaining that knowledge some other way. Maybe these edges should be represented with dotted lines?

Games like Zelda and Metroid - not sure what you call that genre... exploration games? - tend to be based around abilities. You can use bombs now, so bomb this wall to reveal the next dungeon. There is a block in your path and you need to have the bracelet of strength to move it. There's a really high ledge that you must double jump to. It's the same thing as item-based puzzles as far as puzzle trees are concerned.

Role playing games, however, tend to be based on world state changes. Once you talk to the hermit, the girl in town will join your party. Killing the evil goblin will cause a cutscene to happen next time you go into town. Zelda dungeons also rely on world state changes: completing this box pushing puzzle will unlock the door to the boss. Occasionally, RPGs will use item puzzles (you need to give the dynamite to the dwarves) or ability-based puzzles (you need to be level 37 to defeat the boss). JRPGs, especially, tend to stick to a linear path of events that must be experienced in sequence.

These all sound like very different things to the players, but they serve the exact same purpose in a puzzle tree. One puzzle depends on something, be an item, knowledge, or state change, that you get by completing a different puzzle.

Fig 158.3 - Common Situation.

A very common situation in many games is that the result of solving a puzzle or completing an event will be the unlocking of a new area. For instance, you find a key and it unlocks the bedroom in the mysterious mansion. Now you have a new area to explore with a bunch of items you can collect just sitting around. Under normal circumstances, these would be considered leaf nodes, but because they are behind a locked door, you end up with a node (unlocked bedroom) being the dependency for many nodes. This makes the tree more difficult to understand visually.

Fig 158.4 - Dependency Zone.

My solution is that the nodes themselves are inside of a dependency "zone", None of the nodes in that zone can be accessed before that zone is unlocked first. This makes the "unlocked bedroom" puzzle into the root of its own puzzle tree, while the main story puzzle tree will run between multiple zones.

Largely, it is a way of simplifying a puzzle tree to be more useful to humans. Both of the above puzzle trees are equivalent. It's just that one makes it more obvious that unlocking a zone causes a bunch of leaf nodes to become accessible.

Fig 158.5 - Zones Can Use Nodes From Previous Zones.

One special property of dependency zones is that in situations where you can guarantee that one zone will be unlocked before another, the second zone can contain nodes that take place physically in the first zone and still have a winnable outcome.

Example: You are in the kitchen (gray area) and unlock the door to the dining room (purple area). In the dining room, you find a small key under a plate. Back in the kitchen, you use the small key to unlock the bread box.

The reason this works is because puzzle trees are not based on the physical location of the puzzles. Once you've entered a zone, every puzzle within that zone, and every puzzle within the previous zone should be accessible. You may see the locked bread box in the kitchen, but the puzzle to unlock it is dependent on the dining room. The zones themselves are a metaphorical representation of access.

Honestly, I haven't scratched the surface of dependency zones. There are a lot of things you can do with it. For instance, you can have two zones run parallel to each other (you can find keys to the bedroom and garden at the same level, allowing you access to either or both), or a zone wholly contained within another one (like a dungeon inside the ice region). Heck, you can have zones that are metaphorical rather than based on physical areas (these puzzles become available when you are transformed into a werewolf).

It should also be stated that dependency zones are the linchpin in the procedural technique I created to generate a Desktop Adventures/Zelda-like exploration game. But that will have to be a different entry.

Like I said, I didn't invent puzzle trees. Here are some other places on the internet which have decided to similarly map adventure game puzzles to a tree format.

Grim Fandango Design Document

This is the design document to Grim Fandango (spoilers!!). Of note is that it is broken into three parts: the puzzle tree, a map, and detailed puzzle descriptions. I think that this approach, with a little effort, can be the foundation to procedural game design.

The Making of "Bronze"

Here is an article on the creation of the puzzle tree by Emily Short, using her interactive-fiction game "Bronze" (spoilers!!). Well worth the read.

Monkey Island Flowchart

Some industrious fan has decided to chart out the puzzle tree for Monkey Island (spoilers!!). Though intended to be a sort of walkthrough, it is probably the closest I've seen to the charts than Ron Gilbert makes for his games.

Metroid Zero Mission Sequence Map

Puzzle trees don't just deal with puzzles. Here is a chart for Metroid Zero Mission that keeps track of the order in which you can obtain the different special abilities in the game. Special attention has been given to "sequence breaking" - trying to obtain abilities before you would normally be able to using glitches, tricks, and ingenuity.

The Puzzle Structure of Ocarina of Time

This examination of Zelda:OoT starts out with a dependency tree for the items you get (not unlike the Metroid chart above), and then it tries to compare puzzle trees with their physical locations in the dungeons, primarily to describe in scientific terms why the Water Temple is such an annoying dungeon.