Puzzle Dependency Charts

Aug 10, 2014

In part 1 of 1 in my series of articles on games design, let’s delve into one of the (if not THE) most useful tool for designing adventure games: The Puzzle Dependency Chart. Don’t confuse it with a flow chart, it’s not a flow chart and the subtle distinctions will hopefully become clear, for they are the key to it’s usefulness and raw pulsing design power.

There is some dispute in Lucasfilm Games circles over whether they were called Puzzle Dependency Charts or Puzzle Dependency Graphs, and on any given day I'll swear with complete conviction that is was Chart, then the next day swear with complete conviction that it was Graph. For this article, I'm going to go with Chart. It's Sunday.

Gary and I didn’t have Puzzle Dependency Charts for Maniac Mansion, and in a lot of ways it really shows. The game is full of dead end puzzles and the flow is uneven and gets bottlenecked too much.

Puzzle Dependency Charts would have solve most of these problems. I can’t remember when I first came up with the concept, it was probably right before or during the development of The Last Crusade adventure game and both David Fox and Noah Falstein contributed heavy to what they would become. They reached their full potential during Monkey Island where I relied on them for every aspect of the puzzle design.

A Puzzle Dependency Chart is a list of all the puzzles and steps for solving a puzzle in an adventure game. They are presented in the form of a Graph with each node connecting to the puzzle or puzzle steps that are need to get there.  They do not generally include story beats unless they are critical to solving a puzzle.

Let’s build one!

I always work backwards when designing an adventure game, not from the very end of the game, but from the end of puzzle chains.  I usually start with “The player needs to get into the basement”, not “Where should I hide a key to get into some place I haven’t figured out yet.”

I also like to work from left to right, other people like going top to bottom. My rational for left to right is I like to put them up on my office wall, wrapping the room with the game design.

So... first, we’ll need figure out what you need to get into the basement...

And we then draw a line connecting the two, showing the dependency. “Unlocking the door” is dependent on “Finding the Key”.  Again, it’s not flow, it’s dependency.

Now let’s add a new step to the puzzle called “Oil Hinges” on the door and it can happen in parallel to the "Finding the Key" puzzle...

We add two new puzzle nodes, one for the action “Oil Hinges” and it’s dependency “Find Oil Can”.  “Unlocking” the door is not dependent on “Oiling” the hinges, so there is no connection. They do connect into “Opening” the basement door since they both need to be done.

At this point, the chart is starting to get interesting and is showing us something important: The non-linearity of the design. There are two puzzles the player can be working on while trying to get the basement door open.

There is nothing (NOTHING!) worse than linear adventure games and these charts are a quick visual way to see where the design gets too linear or too unwieldy with choice (also bad).

Let's build it back a little more...

When you step back and look at a finished Puzzle Dependency Chart, you should this kind of overall pattern with a lot of little sub-diamond shaped expansion and contraction of puzzles.  Solving one puzzle should open up 2 or 3 new ones, and then those collapses down (but not necessarily at the same rate) to a single solution that then opens up more non-linear puzzles.

The game starts out with a simple choice, then the puzzles begin to expand out with more and more for the player to be doing in parallel, then collapse back in.

I tend to design adventures games in “acts”, where each act ends with a bottle neck to the next act. I like doing this because it gives players a sense of completion, and they can also file a bunch of knowledge away and (if need) the inventory can be culled).

Monkey Island would have looked something like this...

I don’t have the Puzzle Dependency Chart for Monkey Island, or I’d post it. I’ve seen some online, but they are more “flowcharts” and not “dependency charts”. I’ve had countless arguments with people over the differences and how dependency charts are not flowcharts, bla bla bla. They’re not. I don’t completely know why, but they are different.

Flowcharts are great if you’re trying to solve a game, dependency charts are great if you’re trying to design a game. That’s the best I can come up with.

Here is a page from my MI design notebook that shows a puzzle in the process of being created using Puzzle Dependency Charts. It’s the only way I know how to design an adventure game. I’d be lost without them.

So, how do you make these charts?

You'll need some software that automatically rebuilds the charts as you connect nodes. If you try and make these using a flowchart program, you’ll spend forever reordering the boxes and making sure lines don’t cross. It’s a frustrating and time consuming process and it gets in the way of using these as a quick tool for design.

Back at Lucasfilm Games, we used some software meant for project scheduling. I don’t remember the name of it, and I’m sure it’s long gone.

I’ve only modern program that does this well is OmniGraffle, but it only runs on the Mac. I’m sure there are others, but since OmniGraffle does exactly what I need, I haven’t look much deeper. I'm sure there are others.

OmniGraffle is built on top of the unix tool called graphviz. Graphviz is great, but you have to feed everything in as a text file. It’s a nerd level 8 program, but it’s what I used for DeathSpank.

You can take a look at the DeathSpank Puzzle Dependency Chart here, but I warn you, it's a big image, so get ready to zoom-n-scroll™. You can also see the graphviz file that produced it.

Hopefully this was interesting. I could spend all day long talking about Puzzle Dependency Charts. Yea, I'm a lot of fun on a first date.



Noah Falstein
I covered a bit of this lore at GDC a couple years ago:
http://www.gamasutra.com/view/news/189266/The_technique_LucasArts_used_to_design_its_classic_adventure_games.php

BTW I find that Visio is a pretty good tool for making them.

Rum Rogers
This is VERY interesting.
I was trying to do some reverse engineering on the puzzle structure in Monkey Island 1, in order to test the expressivity power of the engine I'm programming.
I don't know if the pros agree, but I found myself more comfortable using "hierarchies" of Puzzle Charts, going from the most high level down to the details.
For example, this is the Puzzle Chart describing Part1 of MI1, in the most generic way possible, I think: http://i60.tinypic.com/2ns2z2t.jpg
Then, at a lower level, I came up with this middle-level Puzzle Chart: http://i58.tinypic.com/1z4iiyd.jpg
High level charts just WAIT for events to be fired by low level ones, while low level charts specify the chains of verb-action combinations that FIRE the events waited for by the higher.
Arrows define sequencies, while lines describe parallel dependencies.
I'd like some feedback from Ron, but I know time is gold, so these are just my two cents.

Rum Rogers
P.S. I just read my previous post and noticed I wrote "most high". This is obviously due to a sleepless programming night, sorry for that horrific expression.

Joel Mayer
I recommend XMind. It comes with a free version that has everything you need to build things like this.

Craig
I really like those bite-sized escape-the-room puzzles where the game dumps your inventory (or sometimes not) and traps you in a scene.  You have to find all the interactive objects and figure out how to use them to escape.  My favorite example is when Guybrush is arrested in MI2.  There's also the pit of acid scene, and the scene in SoMI where you're under water.  And of course the cannibal hut.  It's a nice break from the game.  When you're on the Sea Monkey trying to find Monkey Island, the scope of the puzzles is a bit larger than being stuck in a room, but it still had that feel.

As for non-linear, finding the map pieces in MI2 has to be the best puzzle design I've ever seen in a game.  That entire game is amazing.  There's so much to explore and do.  I actually miss getting stumped.  It took me a month to figure out some of those puzzles.  I completed both stories in Broken Age in an afternoon.

Something you don't see a lot but I always appreciated is when things come full circle and you arrive back where the story began.  When Guybrush makes it back to Melee island with his root beer potion, he absolutely dominates everyone in his path.  You feel like he's finally become a pirate and his arc is complete.  And he gets the girl in the end.

And as a game developer, you can reuse a location of the game.  A necessity when disk space and budgets are/were limited.

Pablo
I also thought the same about linear structures and I was surprise of hearing this critique since MI uses a few of them quite well. Nowadays they´re used too much, and there´s no game that lucks a jail part.
I think the rule is that if the puzzle is linear, the inventory and space should be small.

Pascal
It's a Java program, but one of the few I find usefull enough to install the JRE: yEd (see http://www.yworks.com/en/products_yed_about.html)

I like it because I can use the same program on OSX, Linux and Windows

Sean Howard
My preferred data structure is a tree with the root node being "win game", and each child being a puzzle that condition is dependent on. You traverse it in reverse, clearing leaf nodes first, then nodes that depend on those lead nodes, and up the tree until you have taken many puzzles and reduced it to a single one.

The reason I prefer a tree is because it becomes trivial to procedurally generate (and also because Puzzle Tree is snazzier than Puzzle Dependency Chart - search your heart, you know this to be true). I also think trees create better graphs, allowing you to spot patterns and potential flaws more easily (the DeathSpank graph gets very confusing in that last section).

Of course, trees don't work when puzzles expand instead of contract. In practice, however, puzzles rarely expand. Much of the time, they simply unlock new "zones" of puzzles, with the entire zone being dependent. Getting to the WWII zone unlocks a bunch of new puzzles - but within the WWII zone, those puzzles should be considered leaf nodes since they have no dependencies other than being in a newly available area ( this is a beneficial way to think of it for procedural generation: http://www.squidi.net/three/entry.php?id=160 ). Puzzle zones becomes an excellent way to break Puzzle Trees up, providing a visually appealing structure to the whole thing.

In the few cases where puzzles expand legitimately, it is usually bad design. You opened the locked box and inside found three random items you needed for three other puzzles that were suspiciously unsolvable until this box was unlocked. There are cases when new goals are given to the player (new puzzles, not new solutions), but that either opens a new puzzle zone or isn't actually a dependency (being told the goals is not the thing which unlocks their ability to be solved, thus it doesn't belong in the tree).

Davide
It's interesting that once, thinking of a possible model to describe game's objectives,
I drew a similar chart (with circles and arcs, and a similar semantic!).

I like much the way you can easily draw puzzles that you could solve indipendently and switch
from one to another if you get stuck at one of these.

The only thing that I dislike of such approach is the mixing of "figuring out" and "acting",
since usually discovering objectives and achieving them follows opposite directions in the game logic (e.g
"Take the magnet -> Use the magnet on the grate and take the key -> Open the door with the key" vs
"I should open the door -> I should take the key that I saw inside the grate -> I should find something to use to grab the key inside the grate").

Probably I would draw another chart that I would call "Objective Dependency Chart":
- to model just "why" you act and not "what" you do, and exclude from the chart what is merely "acting" (e.g. get the shovel from the sign)
and leaving only what makes you "figure out". For this I would concentrate only on question/problems more than answers/solutions
("Find a shovel" would represent the player's question "where I can find a shovel?");
I would write "acting" steps in a separate chart.
- I would draw it in the reverse order ("Open Basement door" would be the first on the left) and swap the arrows' directions.
The arrow would mean "goal completion depends on the completion of this other goal", but, above all,
"Ok, I would like to achieve this goal... and to do this I just discovered that I should achieve this other goal before").
The chart would describe the new goals that the user would know that has to achieve while playing the game and discovering new informations,
places and characters while trying to figure out to solve more long-term objectives.
Maybe it would help avoiding the creation of "backwards puzzles"? I don't know..
What I'd like is that the chart should help the designer to make long-term and short-term
objectives clear to player in each part of the game.

Hori
That approach of thinking in terms of "goals" and the prerequisits / conditions needed to achieve them is used in the field of engineering dealing with complex systems, e.g. in the proverbial rocket science.

There are two excellent episodes of the "Omega Tau Podcast" on the topic:
http://omegataupodcast.net/2012/08/100-system-health-mgt/
http://omegataupodcast.net/2011/03/58-komplexe-systeme-4/
(the latter one is in German)

They´ve got it all!
Dependencies! Common causes! Zoning! (Fault) tree analysis...

Perhaps one could mis-use some of their tools... :-)

Davide
We may conclude that many adventure games suck because many people think that Adventure Games Design it's not Rocket Science? :D

flesk
I imagine that any kind of UML diagramming tool might do the job. There's a big list of them on Wikipedia: http://en.wikipedia.org/wiki/List_of_UML_tools.

I've used Dia for some larger programming projects in the past and thought it was pretty good.

denzquix
Very interesting! Thank you.

Do you do anything to indicate when a puzzle has two alternative prerequisites (i.e. you only need to do one, not all, of the preceding actions), or is that outside the scope of these charts? (Or do you recommend against doing this anyway?)

YpSiLoN
This is a great share Ron, thank you. I’m trying to develop an adventure game with a friend, and I told him the other day about these charts (I think I read it in one of your older posts), but I didn’t know how it’s actually done. Now I know and we can use it!

ElChapucero
Thank you for that!

Daniel
The "software that automatically rebuilds the charts as you connect nodes" is performing a topological sorting for you, see http://en.wikipedia.org/wiki/Topological_sorting. Such a sorting exists if and only if the dependencies form a directed acyclic graph.  Of course the actually interesting part is then drawing the graph: http://en.wikipedia.org/wiki/Layered_graph_drawing.

Pablo
By making an analisys of most games I realized that along with puzzles there are what you´d call a "stopper": Something that is not logical and is there to slow the player down v.gr when Wally is taken, there´s nothing logical that tells you that there´s a cage in the swamp... you just need to walk everywhere and you just find it. Funny, but not logical.
The puzzle where you get Largo´s [Lord Jack´s LMAO!] loundry ticket after closing the door of his room is interesting beause is like a blend of a real puzzle and a "stopper". There´s a logical reason for the ticket to be there, but is only a posibility in a thousand. I think it´s also one of this puzzles that couldn´t be done without a verb tab, and it´s clever because nobody closes a door. It´s also interesting that a variation of this puzzle is seen in DotT where you need to close the door in order to get the car keys.
In the graph you posted, this loundry ticket thing doesn´t appear. Well, that make sense since clearly you fill the graph later with the actual puzzles, that´s why I was wondering if along this you had a list of free ideas to fit there.
Clearly the stan-nailed-into-a-coffin is a fantatic idea, it´s also dependent of another good one: sawing the pirate peg leg to get the nails, yet some other puzzle are not really puzzles: Turning down the gas of Ralph Scallion´s kitchen is funny but is no puzzle (and the fact that you have to search for the house without clue makes it a "stopper"). The library puzzle (the one about the books) is a pretty mean "stopper".
So I wonder how many good ideas you try to get to make a really good game like MI or MI2 and if this is the first thing you do.

Rum Rogers
I disagree.
Most puzzles in Monkey 2 are logical, which doesn't mean easy at all.
When Wally gets kidnapped, you feel like you need help from the voodoo lady and that's the reason why you go to the swamp.
At least, this is how I always felt it.
Monkey 2 is one of the few adventure games with very hard puzzles that feel logical once you solved'em.
What a masterpiece.

oneofm4ny
Just realized that the puzzle charts have another nice property: player actions are put into a cause and effect relationship. You have to unlock the door first to open it. To unlock it you need to find the key etc.

That way there are no nonsensical relationships. Doing random stuff triggering an unrelated event e.g. you need to push the monkey, start the car and refill the chainsaw for the UFO to arrive. That way the player won't be confused what to do next.

Great share Ron. Thanks!

P.S. YED is a great editor for diagrams. It allows sorting of nodes in various ways. I have used it for dependency charts at work. Puzzle charts should be easy to do.

Tobin Harris
So I whacked this whopping bad boy into my yUML site. It uses Graphviz but also presents as an API with simple text.

http://yuml.me/c110f8bf

http://yuml.me/edit/c110f8bf

It's a whopper.

Crowvyn
Thanks for sharing this! Helps me a lot, especially your hate for linear puzzles :)

dinososs etc
Seems like a flow chart is different in that it's usually structured in a way that leads you to a certain action, or it categorizes something for you. Also the mechanic of following a flowchart is by answering yes or no questions. So a flowchart is like a divination tool that helps you interpret a certain situation, and depending on what "flow" you follow, the interpretation varies.

On the other hand, a dependency chart is static. It's only open to interpretation as it's being designed, and its use is as a tool for situating oneself within a definite location in the game as either a designer or a player.

So you can just look at a dependency chart and know something, whereas with a flowchart you don't know anything until you finish the flow. One's a map or list of instructions, the other is a troubleshooting manual.

Pavel
There is an online diagram editor for game designers:
http://joy.pavel-insight.com

Example of Puzzle diagram (in Russian):
http://joy.pavel-insight.com/diagram/1-110222-a36d6e798655624000318f4d0be76147/

Puzzle Diagrams are inspired by articles of Daniel Schuller about puzzle classification:
http://www.godpatterns.com/2006/04/adventure-game-design-patterns.html
what is two + one?