Note: This is a work in progress. Currently 18 of 63 puzzles have been broken down. Follow me on twitter (@brickshot) for updates. 

Welcome to the third and final part of this series on The Day of the Tentacle. By this point you have hopefully read the introduction to Puzzle Dependency Graphs and seen them used in Part two to breakdown the framework of the game. This final post is a puzzle by puzzle wrap-up in which we’ll take a critical look at the game and apply some of Ron Gilbert’s rules for game design along the way.

Note that this is not a walk-through. There are plenty of those available (an excellent one is here). This is an attempt to analyze the game as a creative work in the way a film or novel might be. I will attempt to determine the quality of each puzzle (via a standard set of criteria) and see what part it plays in the game as a whole. My desire is to create a resource game developers seeking to learn from the game or just for fans who want to delve deeply into a classic game to see what makes it tick.

The Puzzles

By my count there are 63 puzzles in Day of the Tentacle. That does not include a few things which are not technically puzzles according to my definition but which will still feel like a puzzle to the player. Like realizing you can shut the door to the Sleeping Conventioneer’s room and get the keys out of it. I didn’t include it as a puzzle in my graph because it has no dependencies other than starting the game. You could certainly make an argument for including it in which case it would have an edge directly from the ‘Begin Game’ node.

Intro Segment

Let’s Get Cracking!

The linear introductory segment of the game has four puzzles if you include the not-really-a-puzzle of Boot Up the Game. While the player is not required to complete them all before moving on (see Highlight below) they are heavily encouraged to do so. These puzzles reveal critical story elements which almost all other puzzles rely on.

While providing back-story and plot these early puzzles also have the side effect of handing the player some early successes to boost their confidence.

The Meta-Game

At the beginning of the game the player is also engaging in a kind of meta-puzzle which goes on when playing any adventure game for the first time. This is the “What kind of game is this?” puzzle (for lack of a better name). Adventure games as a whole subscribe to a lot of similar conventions: focus on story, puzzle solving, inventory management, etc. But outside of genre conventions (and outside of the stories themselves) each individual adventure game has a very specific set of characteristics which inform the style of play. Some games allow your character to die (Beneath a Steel Sky, Kings Quest), while others don’t (Day Of The Tentacle). Some games reward exploration (The Secret of Monkey Island), while other games punish even the slightest risky move (Adventure). Some games require constant saves to protect against dead-ends (Zork Zero). Some have realtime action sequences (Space Quest) while many don’t. Knowing what kind of game is being played factors into how the game is played. Discovering these game-specific quirks is a real part of the player experience which I feel many designers don’t acknowledge or account for but which is critically important.

Day of the Tentacle does seem to take this opportunity to get the player acclimated to the type of game they are playing. So in these initial few sections of the game the player learns that dialogue is a big part of this game and exploring dialogue trees is as important as physical room exploration. While it’s not conclusive it appears that this is not the kind of game where arbitrary death is lurking around the corner and as such pre-emptive game saving is probably not necessary. While no difficult puzzles have come up yet it does feel like the puzzles are tied tightly in to the story.

This nascent trust-building time is very important in any game but especially in adventure games where the player needs to decide what “might” work in this world. The more consistently the game sticks to it’s own internal logic and rules the happier the player will be. Conversely when the game crosses its own implied boundaries and “throws a curve” the player more than often will feel betrayed.

 Puzzle: Boot up the game (not really a puzzle)

Our Heros?

Dependencies: None
New Rooms: Present-Day Lobby and Office
New items Available: Textbook, Dime, Bankbook, BooBoo-B-Gone, Flier
Other Rewards: Intro cutscene
Downstream Puzzles: Find the Secret Lab

Puzzle: Find Dr. Fred’s Secret Lab

Bernard you a damn genius.

Dependencies: Boot up the Game
New Rooms: Entire Present-Day Mansion
New items Available: Disappearing Ink, Videotape, Hamster, Crank, Coffee, Decaf Coffee, Fork, Funnel
Downstream Puzzles: Find Super Battery Plans, The Chattering Teeth, The Crowbar, The Fake Barf, The Stamp
Other Rewards: Big cut-scene, lots of plot and the whole present day mansion to explore.

The Chattering Teeth, The Crowbar, The Fake Barf, The Stamp

These four puzzles require special mention because although the game strongly encourages you to find the Super Battery Plans at this point there are actually four other puzzles which can be solved now as well (and in any order).

The Five Finger Fist

Making these puzzles available gives the player some options while they wander around the mansion looking for the Super Battery Plans. In the event they get really stuck and solve all four of these side-puzzles first there are even a few more puzzles which open up due to their dependencies being satisfied. The game won’t really get started until the Super Battery is found however.

Puzzle: Give the Plans To Red Edison

I made this!

Dependencies: Find the Super Battery Plans
Dependencies Provide: The Super Battery Plans
New Rooms: None
New items Available: None
Downstream Puzzles: Get the Super Battery
Other Rewards: Tiny plot advancement

Puzzle: Get the Dentures

Classy

Dependencies: Find the Super Battery Plans
Dependencies Provide: Access to Hoagie, Textbook to Hoagie via the Chron-o-John
New Rooms: None
New Items: The Dentures
Other Rewards: None
Downstream Puzzles: Mummy Fashion

Bernard’s Story: Get a Diamond

Puzzle: Find the Super Battery Plans

In retrospect it seems obvious.

Dependencies: Find The Secret Lab
Dependencies Provide: Access to Secret Lab (in the present)
New Rooms: Entire Past-Era Mansion
New items Available: Patent Application, Can Opener, Oil, Spaghetti, Bucket (Bucket Full of Water), Brush, Red Paint, Wine Bottle, Left Handed Hammer
Downstream Puzzles: Give plans to Red Edison, Get Laverne down from tree, Make Vinegar, Get into Dwayne’s room, Get the Super, Battery, Get Soap, Start Storm, Get lab coat, Get Dentures, Mummy Fashion, Get Skunk, Make Vacuum, Sleepwalk Fred, Switch Statue Handedness, Paint Ted Red
Other Rewards: Big cut-scene, access to Hoagie, information about the chron-o-johns

Puzzle: Get The Stamp

Worth it

Dependencies: Find The Secret Lab
Dependencies Provide: Disappearing Ink
New Rooms: None
New Items: The Stamp
Other Rewards: None
Downstream Puzzles: Mail Contract in the Past

Puzzle: Switch Statue Handedness

So fucking smooth.

Dependencies: Find Super Battery Plans
Dependencies Provide: Hoagie
New Rooms: None
New Items: None
Other Rewards: Left Handed Statue
Downstream Puzzles: Get Access To VCR

Puzzle: Sleepwalk Dr. Fred

Drink up Drinky

Dependencies: Find Super Battery Plans
Dependencies Provide: Dr. Fred Drinking His Coffee
New Rooms: None
New Items: None
Other Rewards: Dr. Fred Opening Safe
Downstream Puzzles: Record Safe Combo

Puzzle: Paint Ted Red

You need another coat.

Dependencies: Find Super Battery Plans
Dependencies Provide: Red Paint
New Rooms: None
New Items: None
Other Rewards: Red Ted
Downstream Puzzles: Rescue Dr. Fred

Puzzle: Get Access To VCR

Graceful as ever Bernard.

Dependencies: Switch Statue Handedness
Dependencies Provide: Left handed statue
New Rooms: None
New Items: None
Other Rewards: None
Downstream Puzzles: Record Safe Combo

Puzzle: Record Safe Combo

This one goes to 999.

Dependencies: Get Access to VCR, Sleepwalk Fred
Dependencies Provide: Access to VCR, Fred Opening Safe
New Rooms: None
New Items: None
Other Rewards: None
Downstream Puzzles: Get Rope, Get Contract

Puzzle: Get Rope

Crack that whip.

Dependencies: Record Safe Combo
Dependencies Provide: Fred Tied Up
New Rooms: None
New Items: Rope
Other Rewards: None
Downstream Puzzles: Get Ted in Attic

Puzzle: Get Contract

I said there would be spoilers.

Dependencies: Record Safe Combo
Dependencies Provide: Safe Combo
New Rooms: None
New Items: Rope
Other Rewards: None
Downstream Puzzles: Get Signed Contract

Puzzle: Rescue Dr. Fred

Physics inaction

Dependencies: Get Ted In Attic, Paint Ted Red
Dependencies Provide: Ted in Attic, Red Ted
New Rooms: None
New Items: Rope
Other Rewards: Dr. Fred
Downstream Puzzles: Get Signed Contract

Hoagie’s Story: Power Hoagie’s Chron-o-John

Puzzle: Get the Chattering Teeth

Logical

Dependencies: Find The Secret Lab
Dependencies Provide: Access to Living Room
New Rooms: None
New Items: The Chattering Teeth
Downstream Puzzles: Build a Fire
Other Rewards: None

Laverne’s Story: Power Laverne’s Chron-o-John

Puzzle: Get The Fake Barf

So welcoming

Dependencies: Find The Secret Lab
Dependencies Provide: Access to the Tentacles’ Room
New Rooms: None
New Items: The Fake Barf
Other Rewards: None
Downstream Puzzles: Get Rid of Harold

Puzzle: Get The Crowbar

Crow bar none

Dependencies: Find The Secret Lab
Dependencies Provide: Keys
New Rooms: None
New Items: The Crowbar
Other Rewards: None
Downstream Puzzles: Get Dime From Gum, Get The Quarters

Puzzle: Get The Quarters

A good year

Dependencies: Get the Crowbar
Dependencies Provide: Crowbar
New Rooms: None
New Items: The Quarters
Other Rewards: None
Downstream Puzzles: Get Tiny Sweater

To be continued…

Note: This is a work in progress. Currently 18 of 63 puzzles have been broken down. Follow me on twitter (@brickshot) for updates. 

The following is excerpted from a talk I gave at GDC 2016 on Puzzle Dependency Graphs. The full slides from that talk are available here. For a companion to this primer please see my analysis of the Day of the Tentacle which includes the full dependency graph for that game.

This is an introduction to an analytical technique which can be used to gain insights into the size, structure and complexity of a game. It helps visualize non-linear branching in the puzzle structure which can be key for tuning difficulty and pacing. It is of use in games with interrelated puzzles where solving one puzzle gets you something you need to solve other puzzles. Adventure games are a common example but many other genres and game types exhibit this design. I’ll discuss the theoretical background of the technique, what you can learn from using it and reference some free tools which can be used to make and analyze these graphs yourself.

The technique is called a Puzzle Dependency Graph. 

History and References

Ron Gilbert is credited with the first use of dependency graphs for puzzles in game design. His blog post on the subject has a wealth of information (including the full graph from Deathspank). Another fantastic resource is a talk by Noah Falstein from GDC 2013: The Arcane Art of Puzzle Dependency Diagrams.

Both Ron and Noah are legendary LucasArts designers and have over thirty years’ experience using this technique in game design. Because their resources are available I will not attempt to repeat what they have already said and this post will focus on the theory behind the technique, practical advice on how to create the graphs and some additional thoughts of my own on new ways to analyze a graph once it has been created. Again, for a wealth of practical advice and time-tested experience, please review the links above.

Formal Definition

Puzzle Dependency Graphs are also referred to as a “chart” or “diagram” but I prefer the term “graph” because it is an application of a dependency graph which is a well-known data-structure with a formal definition. A dependency graph is itself a form of a directed acyclic graph which is a class of a general graph. To make sense of all this I’ll give a brief description of each. 

Graph

At the most basic level a graph is a way to represent a collection of items and the relationships between them. Typically visualized as nodes connected by edges. Graphs can be ‘directed’ or ‘undirected’. A directed graph has arrows for edges which indicate that the relationship between the nodes is asymmetric.

Dependency Graph

A dependency graph is a graph in which the nodes represent things which are dependent on other things. Often this is a dependency over time and indicates that the later thing cannot occur until its dependencies are satisfied. An example of this is a college course curriculum. A prerequisite course which must be completed before another course is a dependency. That is to say that the later course is dependent on the earlier one. For a familiar example in gaming think of crafting in Minecraft. Creating a wooden axe requires wooden planks and sticks and those could be graphed as dependencies of the axe.

A dependency graph is a common class of graph known as a Directed Acyclic Graph or “DAG”. This type of graph has directed edges and no cycles. A cycle in a graph would let you to loop back to a starting node by following edges out of it. This is not allowed in a dependency graph because you would never be able to satisfy any of the dependencies in the cycle. In a game this would be the equivalent of having a key to unlock a box actually locked inside the box itself.

Puzzle Dependency Graph

Simple Puzzle Dependency Graph

This, finally, is the application of a dependency graph to the domain of puzzles in a game. The nodes in the graph represent puzzles that the player can solve. The edges represent the dependencies between puzzles and can be labeled with the “thing” which is received from the first puzzle that is required to solve the second puzzle. For example if you did need a key to unlock a box there could be a “Find the Key” puzzle which would provide that key and allow the player to then complete the “Open the Box” puzzle.

Note that this definition does not actually specify what a puzzle is. A puzzle can in fact be anything you can possible program into a game. For the purposes of this discussion we will just say that a puzzle is anything a player can do in a game which produces or consumes dependencies. Likewise we won’t define what a dependency is. We will just pick a practical definition and say that a dependency is anything you need to solve a puzzle. Often this will be an inventory item (the key in the above example), access to a room or an area in the game world or certain behavior from other in-game characters. These are informal definitions (and self-referential!) but they codify the insight that as a player, solving puzzles gives you what you need to solve more puzzles.

Multiple Dependencies

Puzzles can of course have more than one dependency. Say our locked box needs both a key and some oil to un-stick a rusty hinge before it will open. This situation is modeled by having two dependencies: “Find the Key” and “Get the Oil Can”. Both of those nodes have arrows pointing down to “Open the Box” which means they both must be completed before the box can be opened. Those two puzzles can be solved in any order as long as they are both solved prior to “Open the Box”. This situation where multiple puzzles are available for solving at the same time is known as Non-Linear Branching and will be discussed in depth below.

In Degree and Out Degree

Node A has an In-Degree of 2 and an Out-Degree of 3

Two metrics which come up when analyzing a graph are in-degree and out-degree. These represent the count of upstream and downstream dependencies for a node. In-degree is the number of incoming edges (upstream dependencies) and out-degree is the number of out-going edges (downstream dependencies).

Puzzles with a higher out-degree than in-degree open up the branching and leave more puzzles available for solving. The reverse situation where a puzzle has a higher in-degree than out-degree means that solving the puzzle closes down the branching and consumes more dependencies than it creates. The size of the difference between the in and out degree can be indicative of the role a puzzle plays in the game. A puzzle with higher out-degree means the non-linear branching increases and the player has more options for downstream puzzles to solve. Often in this situation the narrative either branches along with the puzzle structure or there is no narrative connection between these downstream puzzles at all. When the branches are collapsing and coming together in a puzzle with a high in-degree this can indicate a narrative plot line is being resolved. For more on how non-linear branching affects narrative see below.

Graph Layout

To properly visualize the puzzle dependency graph I suggest you use a top-down hierarchical layout with puzzles grouped into horizontal layers as shown in the diagram below. Edges in this type of layout are only drawn going down, not up or horizontally. Nodes are then placed in the highest layer possible which does not violate that restriction. This means that all nodes will have at least one dependency in the previous layer or they are a root node (on the first layer). By using this type of layout we ensure that the shape of our graph is consistent and can be compared with graphs of other games. The layers also give an indication of the amount of non-linear branching which can occur at any point in the game.

Five layers from The Day of the Tentacle

This type of layout can be automatically generated by some of the software packages referenced below.

Topological Orders

In most applications of a dependency graph it is desirable to find an order that the nodes could be visited such that the dependencies are satisfied by the time we get there. This would give us the order in which we could take courses in our courseware example. In the Puzzle Dependency Graph it will give us a valid order in which the player could solve the puzzles in the game. This order is known as a Topological Order and can be found by applying a Topological Sort algorithm.

Typically when designing a game “by hand” there is no need to actually implement or run a Topological Sort as it is clear from the graph if there is a way to win the game or not. If your game is programmatically generating puzzles and dependencies between them then you might want to generate a dependency graph in memory and run a topological sort on it. In any case the important thing to note is that there can be more than one valid topological order for a given graph. In fact there may be very many valid orders in which the player may solve the puzzles in a game.

Non-Linear Branching

Three puzzles are available

Non-Linear Branching in a puzzle dependency graph is defined as a point in the game at which more than one puzzle is available to be solved. This means that multiple puzzles have their dependencies satisfied and the player is free to solve them in any order. The diagram here shows this situation where after solving an initial puzzle the player can then solve A, B or C in any order.

Note we are not talking about a branching narrative structure in which a player can experience one of many stories depending on their choices. What we are concerned with here is a branching puzzle framework in which multiple puzzles are available at a single time and the player can choose the order to solve them in.

Non-linear branching of this type can provide many benefits for a game. It gives the player multiple options for what puzzles to solve at a particular time and helps avoid the situation where the game grinds to a halt because the player is stuck on a single puzzle. On the downside, however, Non-Linear Branching can complicate narrative and plot development. The reason has to do with the number of orders the player may solve the puzzles in.

To make this more concrete: If a layer has three puzzles in it, that indicates that it is possible for all three puzzles to be “open” at the same time. If the puzzles are labeled ‘A’, ‘B’ and ‘C’ then it is possible for the player to solve them in any of the following orders:

So 6 orders are possible. This number can also be arrived at by taking the factorial of the number of puzzles in the layer (see Permutation). In this case 3 * 2 * 1 = 6. This number will grow very rapidly when adding more puzzles to the layer. With 4 puzzles the count is 24. With 5: 120. In the game The Day of the Tentacle there is a layer with 13 puzzles which results in over 6.2 billion possible orders.

The number of permutations of a set grows very quickly as the number of elements in the set increases.

Non-Linear Branching and Narrative

So the player can solve puzzles in many different orders but what does this have to do with narrative? Good game design encourages you to tie puzzle completion into the narrative. This allows the player to move the plot forward with their actions. The complications arise when writing dialogue and descriptive text around puzzles in a non-linear segment which may occur in any order. You can’t make assumptions about what narrative information the player has since there are likely too many possibilities. 

The ancestor graph can be found by reversing the dependency graph above a puzzle.

As an example, take the diagram above from The Day of the Tentacle. “Get Vinegar” and “Get the Gold” have disconnected graphs above them meaning that they have no ancestor nodes in common. When writing the narrative around “Get Vinegar” the designer must be careful not to reference any plot points or information which is revealed outside of that puzzle hierarchy. It might be tempting to mention giving the plans to Red Edison in the dialogue around the Vinegar puzzle but there is no guarantee that the player has done that yet. The only puzzles which definitely have been solved at this point are in the ancestor graph above “Get the Vinegar”. Therefore, when integrating puzzles and narrative, pay attention to the ancestors in the inverted dependency graph above the puzzle in question. The puzzles in that collection are guaranteed to have been solved and you can safely reference any narrative event which was revealed in them.

Tools

While it is possible to draw dependency graphs by hand or with general graphics software you will get many benefits from using a tool which understands something about the data structure you are creating. Graphing packages like Visio or Omnigraffle have the useful ability to maintain connections between nodes when moving them around and some edge routing capabilities but they are lacking in layout algorithms. I encourage you to explore the following packages which are better suited to creating and rendering Dependency Graphs:

• yEd: Full featured graphing tool with useful layout and edge-routing algorithms with many options. Support for swim lanes and grouping. Highly recommended for this type of graph. I used yEd to generate the graphs in this blog and in my Day of the Tentacle analysis. Download yEd. The specific configuration settings I recommend for the layout in yEd.
• Tulip: Somewhat difficult user interface but has support for advanced features such as manipulating nodes programmatically via a built-in python interpreter. Includes the Sugiyama layout algorithm which is specifically designed for dependency graph data. Download Tulip.
• Graphviz/GVEdit: Basic graphing with programmatic support. Uses the DOT graph description file format which may be useful if converting graph data from other tools. Download Graphviz/GVEdit.

Business Process Analysis Tools

One final area which deserves mention is the potential for the use of Business Process Analysis software to analyze puzzle dependency graph data. This type of tool is typically used to optimize production processes in which multiple tasks may be undertaken in parallel. It can be adapted to our purposes by treating each puzzle as a task which must be completed in the process. One such tool is the Cambridge Advanced Modeler (CAM) which I used to create the diagrams in this section.

GANTT Chart for The Day of the Tentacle Puzzles

Two common types of diagrams which can be generated by this approach are the GANTT chart and the Dependency Structure Matrix (DSM). Both represent the same dependency information but provide different insights. The GANTT chart displays puzzles in rows with the layers as columns. The green boxes indicate when a puzzle has its dependencies satisfied. The number of green boxes in a vertical column are the number of puzzles which could potentially be performed simultaneously as they have no inter-dependencies. This count is the degree of non-linear branching and is the same as the number of puzzles in the corresponding layer in our dependency graph. The benefit of this chart is that it makes the shape of the graph very clear. In this example from The Day of the Tentacle we can see that the game starts off with a few linear puzzles which are used to set up the plot. By the fourth column we see the non-linear segment of the game open up dramatically where 13 puzzles are all available at once. Then as the player closes down the branches of the graph by solving puzzles we return to a more linear and narrative driven format to close out the game.

Dependency Structure Matrix for The Day of the Tentacle Puzzles

The DSM shows us a highly compacted version of the same information. Puzzles are listed on both rows and columns with marks in the grid to indicate dependencies between puzzles. Reading down a column reveals the children of a particular node, i.e. the downstream puzzles which are dependent on it. Reading across a row reveals the parents of a node, i.e. the upstream puzzles which it is dependent on.

The puzzles are ordered using a topological sort or other sequencing algorithm which leaves no marks above the diagonal (which would indicate either a dependency cycle or a puzzle being solved before one of its dependencies). By glancing at the DSM we can see the non-linear segments of the game as columns with many marks vertically and the linear segments of the game having single marks trending along the diagonal.

More Fun With Business Process Analysis

In closing I would like to suggest one more analytical approach which I have not explored extensively but which might lead to interesting results.

A tool like CAM will allow you to perform other types of analysis on your dependency graph. The software allows you to assign a time range to each node which is intended to model the time it would take an individual to complete a task in a production workflow which is then executed in parallel by multiple workers. This is not a good analog to a single-player game where the actions are taken serially by one player. However often the player does “work on” multiple puzzles simultaneously just by wandering around and trying different things with different inventory items. With that in mind we could potentially adapt the time-range to our purposes by treating it as a range of difficulty which we estimate (or observe) for each puzzle.

Histogram generated from 1000 random “play-throughs” of a simple puzzle dependency graph with estimated time assignments for each puzzle.

With a range assigned to each node in the graph, CAM is able to apply a statistical modeling algorithm using a Monte Carlo method to forecast the result of many thousands of play-throughs of the entire game. The result is a histogram and accumulated effort curve as seen in this diagram.

This analysis could give you an idea of the difficulty and estimated time to completion for the game in the current configuration. By manipulating the dependency graph or the time estimates on individual nodes and then re-running the simulation you could compare the histograms against each other to predict effects of making changes. This type of analysis is common when working to improve a manufacturing or business process and is potentially valuable in game design.

Closing

I hope this information has been enlightening. To review:

• Learn from the masters:
  • Ron Gilbert: Puzzle Dependency Charts
  • Noah Falstein: The Arcane Art of Puzzle Dependency Diagrams
• Puzzle Dependency Graphs are Dependency Graphs which are DAGs. Plenty of resources are available to learn about these data structures.
• Non-Linear Branching can be good for game design but can lead to a huge number of orders in which the player may solve the puzzles. This leads to complications when telling stories around the puzzles. So…
• Integrate puzzles with narrative by looking at the inverted dependency trees above a puzzle to see which events can safely be referenced.
• Use tools:
  • yEd: Download here. (Configuration hints for Hierarchical Layout)
  • Tulip: Download here.
  • Graphviz/GVEdit:  Download here
  • CAM (Business Process Analysis):  Download here
• Thank you. Stay in touch!
  • @brickshot
  • thewebsiteisdown.com

For a fully worked example of this technique and further analysis please see the companion to this post: The Day of the Tentacle Puzzle Analysis.