Category Archives: Day of the Tentacle Three Part Series

Day of the Tentacle Puzzle Dependency Graph Analysis

The Day of The Tentacle: Puzzle by Puzzle

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.

Ron Gilbert’s Rules of Game Design

In addition to the puzzles it will be interesting to refer to Ron Gilbert’s rules for game design as laid out in his article Why Adventure Games Suck. He wrote that while designing Monkey Island (after Day of the Tentacle). There are 6 affirmative and 6 negative. We will look at instances of the affirmative in DOTT and note any cases where the negative rules were not followed.

Affirmative Rules:
  • End objective needs to be clear
  • Sub-goals need to be obvious
  • Puzzles should advance the story
  • Incremental reward
  • Reward Intent
  • Give the player options
Negative Rules:
  • Live and learn (no dying)
  • (No) Backwards Puzzles
  • I forgot to pick it up (backward puzzle type)
  • Real time is bad drama
  • (No) Arbitrary puzzles
  • (No) Unconnected events

Most of these are followed in Day of the Tentacle although not all.

Intro Segment

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)

puzzle0

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

The story begins. We learn that Purple Tentacle drank toxic sludge and has become fixated on taking over the world. In response Dr. Fred has captured both Purple and his harmless brother Green tentacle and plans to kill them both. Green tentacle sends a hamster to Bernard asking for help and Bernard determines to rescue him. He takes along his two roommates – Laverne and Hoagie. The game begins in the foyer of the Mansion with each of the three adventurers being assigned to an area of the house. Bernard takes the main floor and in case you skipped the intro he clearly states what needs to happen next: “We’ve got to find where Dr. Fred is holding the Tentacles.” If that wasn’t obvious enough he continues with “If I know Dr. Fred… He’s got the tentacles tied up in his secret lab. Question is, where is the secret lab?” Immediately we see Ron Gilbert following his own advice by making the current sub-goal very clear: Find the Secret Lab!

Right off the bat we’ve been rewarded with a huge entertaining animated cutscene just for booting the game. We’ve been cued in to the scenario and been pointed in the right direction by a very explicit line of dialogue.Bernard at this point has access to 2 rooms and 5 items. There is one real puzzle available at the moment: Where is Doctor Fred’s Secret Lab? Three other minor mysteries are also available if the player happens to notice them:

  • What’s up with the dime and gum on the floor of the lobby?
  • What’s up with the fake barf on the ceiling of the lobby?
  • How do you open the safe? (Only if the picture in the office is opened)

The player’s emotional state at this point is one of enthusiasm brought on by the intro cut-scene and the clear goal they are being faced with. Their efforts are even more focused by the lack of mobility. There must be something in these two rooms which will help them get to the secret lab.

Puzzle: Find Dr. Fred’s Secret Lab

puzzle1-findTheSecretLab

Bernard you a damn genius.

1-findDrFredsSecretLab

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.

Once Bernard opens the door to the Grandfather clock he solves the first puzzle of the game and finds Dr. Fred’s Secret Lab. The reward is a large cutscene which gives us the main plot of the game: Keep purple tentacle from drinking the toxic sludge and taking over the world by turning off the Sludge-o-Matic yesterday via the time machine. This “simple” action is however immediately stymied when the time machine breaks and the three characters are strewn across the chronosphere.

Once Bernard is dropped off in the present day Dr Fred lays out explicitly the first subgoal (following the rule “Sub-goals need to be obvious”): Find the Super Battery Plans. We get a slew of new rooms to explore (all 16 rooms of the present day mansion) many new items to pick up and 5 new characters to interrogate.

At this point the next subgoal is very clear (Find The Super Battery Plans) but it is interesting to note that in this essentially linear portion of the game four other puzzles are already available as well: The Chattering Teeth, The Crowbar, The Fake Barf, The Stamp.

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

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!

Give Plans To Red Edison

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

Again a very simple puzzle. You are free to explore the whole of the Mansion in the Past before solving this one but given the very direct instructions by Dr. Fred it’s pretty clear that you should try opening the grandfather clock and find out if Red Edison is down there. He is! What an amazing adventurer you are! Once we give the Patent Application to Red we are rewarded with a small advancement of the story. The Super Battery can be built from “Oil, Vinegar and Gold. Let me know if you come across any.”

The reward for solving this puzzle is really minor compared to the previous ones so it’s a good time to start talking about pace. The game up to this point has had a blazing pace. Each little puzzle resulted in large cutscenes explaining a lot of the story. We got a huge increase in the amount of available territory we could explore, new characters, items and dialogue. But now… what? A little tiny one line of dialogue. It seems like this should have killed the pace but in reality this is the first time we’ve had a moment to actually get down to the business of adventuring. We still have a very clear goal (Oil, Vinegar and Gold) and the world is our oyster.

 

Puzzle: Get the Dentures

24-getDentures

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

OK why is a horse living in the Mansion? More importantly: Why do I still insist on looking for logic in this game when there clearly is none? Nowhere does a single other character mention this horse. And the horse itself just casually gives Hoagie shit about talking to horses. The real question is: Why does this feel totally normal and acceptable in this game? They clearly just take things so far that you give up trying to fit any logic to it. It works! I don’t know why or how but it works.

To look at the puzzle itself however we have to consider the hints. Hoagie repeatedly mentions the horse’s teeth so it’s pretty obvious we want them. But that suggests that we try to use the chattering teeth which quickly are denied. Mucking about with the glass of water gets you nothing. What on earth would point you to Bernard’s book? Not much I’m afraid. If Hoagie looks at the book he mentions that “it would work better than a sleeping pill” but that gets us thinking about the sleepwalking Dr Fred, not the horse. The only thing to suggest the horse might like a book read to it is that it is quite intelligent (and arrogant). Other than that thin clue this puzzle is sadly one of the try-everything-everywhere variety.

Bernard’s Story: Get a Diamond

 

Puzzle: Find the Super Battery Plans

In retrospect it seems obvious.

3-getSuperBatteryPlans

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

Is this even a puzzle? If I’m strict with my own definition then no. You don’t need to do anything but pick the plans up. It is a bit different however because the game has pretty clearly tried to steer the player away from finding them (at least immediately). Dr. Fred says that they are in the attic and wanders off that way. When followed up the stairs into the lobby he is seen wandering upstairs and if you follow him upstairs he goes off to the attic where you lose him. I feel this was done deliberately to get the player to explore the present-day mansion a bit before launching into another game-expanding cut-scene and opening up even more territory.

This is where the plot-heavy linear intro gives way to full-blown non-linear craziness. Looking at the Puzzle Dependency Graph you can see that there are 15 puzzles which are directly opened up by solving Find the Super Battery Plans. That being said the game heavily encourages you to take one more linear step: Give the Plans to Red Edison. This is encouraged by Doctor Fred’s direct instructions:

“I want you to pick up those plans you see in the Chron-O-John, Hoagie. Bring them to RED Edison. He’s my great, great, great, great, great, great, great, great, great, great grandfather. He’ll know what to do.”

If Doctor Fred wasn’t clear enough there are two more hints on how to proceed:

  • The Dialogue Tree for the Sleeping Conventioneer includes Bernard musing about the Super Battery Plans: “I wonder where Dr. Fred could have put them? I’ll bet they’re someplace obvious.”
  • Talking to Green Tentacle reveals this not-so-subtle hint: “Any of Fred’s plans would probably be in his office or the lab.” How much clearer can I say, “There’s always money in the banana stand!”

Side note – what about the croutons and lettuce needed for the Super Battery? The plans clearly show they are required! Does Red already have these ingredients lying around and so doesn’t need you to find them? Or did the puzzle originally include them and Lucas Arts forgot to change the graphic after removing it? Add this to the list of burning questions you will never have answered.

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

Weird Ed is, well, weird. This guy has calmed down a bit from Maniac Mansion but he certainly can be touchy. He does mention that those stamps are his whole life. Luckily Bernard is so socially inept that subtle social cues like that escape him and he’s more than willing to whip out his invisible ink for the lulz.

This is a good puzzle – nicely set up with two subtle hints in the dialogue and a big explosive payoff. I actually felt sorry for Weird Ed the first time. I mean he’s trying so hard to be good. The stamp isn’t used until much later in the game so it just kind of bounces around your inventory for a while depending on when you solve this. The one criticism I can make about this puzzle is that the invisible ink feels just arbitrarily thrown into Dwayne’s room. I mean he is a novelty item inventor but it’s just kind of there with no dialogue referencing it or anything.

As a side note… how did that hamster in Weird Ed’s room beat the kids back to the Mansion? They drove a car for fuck’s sake.

 

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

OK so here’s the problem with this puzzle: There’s about a 50/50 chance you are going to encounter the solution before the problem. And if you “solve” the puzzle which you didn’t even realize exists you see a brief cut-scene of a room you may never have even visited before! This isn’t the worst example of this happening in Day of the Tentacle (see the Vacuum Puzzle) but it is rather glaring.

Here’s one way things could go: After finding the Secret Lab Bernard follows Dr. Fred up the stairs seeking the Super Battery Plans and going room to room exploring. When he happens upon Nurse Edna and being curious about the VCR and being stymied in all other things to do in the room and noting the awfully tempting rolly chair she’s sitting on he shoves Nurse Edna and she catches herself by the arm of the statue. Having no other way to get to the VCR Bernard just continues on his way thus setting up the puzzle as… well… a puzzle. Great! This is the “Lock before the Key” scenario.

The other just as likely scenario is this: After finding the Secret Lab Bernard follows Dr. Fred up the stairs seeking the Super Battery Plans. After getting one of the hints as to the whereabouts of the Super Battery Plans (see hints under Find The Super Battery Plans) he marches down there and picks them up leading to cut-scenes, Hoagie, etc. Now at any point Hoagie can grab the hammer and wander into the sculpting room. All it takes is some curiosity about that other hammer and BAM puzzle solved. Cut-scene to prove it as the statue in Nurse Edna’s room gets switched… but wait… we’ve never even been in Nurse Edna’s room! Dang and Blast this puzzle got all flipped around like a left handed hammer in the hands of a right handed sculptor. Egh sorry. It’s late.

The point is – a better puzzle would not let us solve it before we realize it even exists. I must say the humor of a left-handed hammer is points in this puzzle’s favor though – in general this game gets by on personality in times of crisis and so it is here.

Puzzle: Sleepwalk Dr. Fred

46-sleepwalkDrFred

Bottoms up Buttercup

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

By talking to Dr. Fred Bernard can discover the hilarious story behind the family’s failed finances. This dialogue tree includes one of the best lines of the game (and one of the best lampshades ever):

BERNARD
Let’s go get the contract out of the safe and sign it!

DR FRED
I forgot the combination!

BERNARD
But that’s … that’s so STUPID, Doctor Fred!

Once clued in to the fact that Dr. Fred drinks coffee to stay awake it’s pretty clear what needs to be done. Even without this hint the coffee mug is blazingly obvious as a target for messing with – once you realize you can’t pick it up you’ll certainly try putting various types of coffee in it. If you do manage to solve the puzzle without hearing the back-story first you’ll end up with some unexplained dialogue later on (Bernard makes reference to “Dr. Fred’s contract” for example) but this is fairly unlikely since Nurse Edna also explains the whole story as well as a backup. In any event no matter how you get there the payoff for the puzzle is quite satisfying as it turns Dr. Fred into a sleepwalking zombie who opens and closes the safe in the office. Now you can just go in there and grab the contract while it’s open! Wait you can’t do that because… reasons. See Record Safe Combo for some notes on this state of affairs. Spoiler alert: It’s annoying.

There are some red-herrings around the coffee which may have been added to try to make this puzzle more difficult. For example both regular and decaf coffee comes up in Hoagie’s conversation with John Hancock and when Hoagie looks at the Kite Plans in the mirror he sees a coffee stain on there as well. Obviously exploring using the coffee in the past is stymied by the fact that you can’t get it through the Chron-o-John so ultimately this puzzle remains quite easy.

Puzzle: Paint Ted Red

You need another coat.

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

One of two puzzles in the game which are solved with the red paint, this one is hinted at visually by the fact that once Dr. Fred gets tied up in red tape he does look an awful lot like Ted the Mummy. While it’s possible to paint Ted Red very early in the game (immediately after finding the Super Battery Plans) there is really no reason you would try it until you see Dr. Fred tied up after being snatched by the IRS agents. This puzzle is the easiest part of the Rescue Dr. Fred puzzle sequence.

Puzzle: Get Access To VCR

48-getAccessToVCR

Graceful as ever Bernard.

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

Creepy-ass Nurse Edna! Trying to put the moves on teen-aged boys and generally being a freak gives the player no remorse when they kick her down the steps. Of course it’s mostly those tempting wheels on that rolly chair which hint that pushing her might be a good idea…

As mentioned in Switch Statue Handedness it’s pretty easy to stumble on the solution to that puzzle without really understanding how you did it (via switching the statues before trying to push Edna). This part of the puzzle is really well done however. The player is dying to get their hands on all that… technology. And Edna’s constant admonition to “Get away from that.” makes you just want to shove that crazy old bat out the door! The fact that she actually ends up completely disappearing from the mansion is a bit odd. There’s not even an Edna shaped hole in the front door. This puzzle and the Enter Human Show puzzle both involve shoving someone down the steps so whichever one you solve first acts as a hint for the other. Clever! And quite satisfying.

Note: Bernard’s quote about pushing old-ladies down the steps is probably one of the most quoted from the game.

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

Maybe it’s because I love technology but this is one of my favorite puzzles in the game. It’s quite simple to solve once you have the prerequisites but the fact that you can load up the VCR with a tape and then record, rewind, playback and fiddle with the speed settings is very satisfying. Does anyone have a degree in VCR repair? Can you please tell me it’s actually possible to playback a tape recorded at SP in EP and it will be in slow motion. My brain says no but I want to believe.

To step back a minute though… this scenario doesn’t make a lot of sense to me. Dr. Fred has forgotten the combination to the safe but he knows that the contract is in there and he also knows that it doesn’t matter anyway because he didn’t sign it in time to get the royalty money. This is all explained to Bernard by Dr. Fred. So what is he freaking out about when he opens the safe? Nurse Edna says “something about what’s in there really scares him”… but what? Maybe I’m missing something obvious here but it seems like he already knows exactly what’s in there and it shouldn’t surprise or scare him at all. I guess we can chalk it up to sleepwalking craziness but it does feel like they backed the plot into this one after deciding how you would solve it first.

Puzzle: Get Rope

getRope

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

Fuck me how did this get in here. This isn’t a puzzle! Once you find Fred in the attic you can just pick the rope up. Well shit. I already included it in a raft of graphs and charts and I have no interest in going back to fix it so I guess it makes the cut. Luckily I’m just analyzing a video game, not doing rocket science. Although in the words of my genius rocket-scientist friend Wayne: “Even rocket science isn’t rocket science”. Wise words.

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

This is the last phase of the excellent group of puzzles needed to open the safe. Outside of some confusing character motivation (see Sleepwalk Fred) this whole story-line is really entertaining. I like how once you have recorded the combination on the VCR you aren’t expected to write it down and then manually enter it via some clumsy user interface. Having Bernard just take over because he knows the combo now is much more pleasing and cuts right to the chase.

Interesting note: If you try to open the safe during the end-game (which is the day before the main game) you get this cautionary bit of dialogue:

BERNARD

We need to leave the contract in there so I can get it tomorrow and send it to Hoagie two hundred years ago.

They thought of everything! Too bad they didn’t… see You can pick up the help wanted sign.

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

You have to use ted with dr fred. As confusing as the puzzle with the mattress. Also when Bernard is on the roof and you use rope he says he’s not going to make that mistake again and he moves to the other side. But what mistake is he talking about? I guess when he fell off the roof.

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

Puzzle: Get the Chattering Teeth

Chattering Teeth

Logical

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

How to pick up the Chattering Teeth? This counts as a puzzle because you can’t just pick them up – you must take a different set of actions which results in getting the teeth. The solution is available in the same room – open the grate and chase the teeth in there. Doing so nets you the reward you might expect: the teeth and nothing else. This is unremarkable except that it’s an example of a Backward Puzzle which Ron Gilbert has admonished us against.

In fact there are many examples in DOTT of this kind of thing – inventory items with no current applicability. After finding Dr. Fred’s Secret Lab the player has access to the whole present-day mansion. Exploring it methodically and picking up every possible thing will net 13 items in their inventory and each one is a “key before the lock”.

Whether this negatively impacts the gameplay is debatable. The inventory in this game is not capped and so it seems there is no harm in just making lots of items available for easy pickup. It makes the player feel like they are making progress and doing well. “Boy I’m finding all kinds of useful(?) stuff!” On the other hand for each new item in their inventory the player may (at least mentally) start trying to apply it to every available situation. “I wonder if Edna would like a pair of Chattering Teeth? No? Maybe Weird Ed?” After a while the exponential growth of potential items and uses and places for them to go grows out of hand and the player may get a sinking feeling that they will never figure it all out.

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

Puzzle: Get The Fake Barf

27-getFakeBarf

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

Ah the fake barf. So tantalizing. So elusive. So… insane. Why is it up there? Apparently the novelty salesman bash from the night before got a little out of hand. I’ll accept it. How to get it down? Well luckily this puzzle introduces the Day of the Tentacle patented quick-cutaway cut-scene which gives you a nice hint while you’re putting your grubby hands all over everything in the tentacle’s bedroom. Turning on the stereo cuts to a brief view of downstairs and you see the barf aaaaaaalmost fall off the ceiling. What a tease. But this does two things: First it lets you know that something in another room has changed. This is the “No Unconnected Events” rule in action. In some games (*cough* Zork *cough*) your actions have unseen consequences all around the world. This feels totally arbitrary and sometimes when you solve a puzzle you might not even realize that you’ve solved it (or get the satisfaction of doing so). Now Day of the Tentacle isn’t totally innocent of this crime even while using this quick-cutaway device (see Switch Statue Handedness) but it does solve the problem in almost every case. Second (bet you thought I forgot) this cut-away gives you a much needed hint on how to actually get the barf down. You now know that you’re right on top of it (which is not apparent from the room layout) and that loud noises can affect it. This turns what would otherwise be a pixel-hunting/try-everything-once kind of puzzle into something that feels motivated and fair.

Puzzle: Get The Crowbar

37-getCrowbar

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

This puzzle could arguably be broken into two parts, the first being: Get the Keys. I left that out since the keys are technically just hanging on that door with the puzzle being that you have to realize you can close doors once you go into rooms. Once you have the keys you go hand them to the car thief and get his crowbar.

This puzzle always struck me as a little bizarre. The car thief is totally outside the plot and just happens to spend his entire night working on the only car outside the mansion. And why is he trying to break into the trunk of the car? They have a line of dialogue attempting to lampshade this but it makes no sense. Wouldn’t he just break a window instead of perpetually trying to wiggle his crowbar into the trunk? (There’s a dirty joke in here somewhere). Obviously it’s because then he wouldn’t be there to trade you the crowbar but it feels a bit random. Once you get the crowbar you can get the dime from the gum in the lobby or attack the vending machine for quarters.

Puzzle: Get The Quarters

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 Day of The Tentacle: Dependency Graph Analysis

The Day of the Tentacle is a classic LucasArts adventure game released in 1993. Starring an irrepressible nerd, an evil tentacle and three generations of the same mad scientist it quickly captured the hearts of the adventure going public of the day. It’s a light-hearted game with a focus on exploration, narrative and humor. The creative team included Dave Grossman, Tim Schafer, Ron Gilbert and Gary Winnick.

While cartoonish on the surface this game is highly polished with an elaborate design and complex puzzle structure. This post will focus on the puzzle dependency graph and the way in which the puzzles are integrated into the narrative.

Puzzle Dependency Graph

For the purpose of analyzing the game I have re-constructed the Puzzle Dependency Graph as described in Part 1: Puzzle Dependency Graph Primer. I used yEd to build the graph and CAM for the GANTT chart. The graph is laid out vertically from top to bottom with nodes colored to show which game character is required to solve the puzzle. The colors are assigned as follows:

Bernard: Blue Laverne: Green Hoagie: Orange Start / End

Nodes were created for all player actions which satisfy downstream dependencies. I did not create nodes for the act of just picking up an item which is lying around or for walking into new areas. While those actions technically fit the criteria it is usually an earlier puzzle which has actually allowed the player to take that action and so the dependencies are assigned to those upstream puzzles.

As recommended in Part 1 I have used a layout which places puzzles in the highest layer possible while still keeping all dependencies flowing downwards. Note that the three graphs shown in this post all represent the same dependency graph data but with different layouts. The initial graph with no grouping of nodes is shown here.

Dependency Graph displayed using a compact layout. The non-linear mid-game is kicked off dramatically by the “Find Super Battery Plans” puzzle with its 15 downstream puzzles.

Features of the Graph

In this graph there is a single initial starting node with no input edges (the starting condition) and one destination node which has no outbound edges (the victory condition). The horizontal layers give an indication of the amount of non-linear branching happening at a given point in the game. When all the puzzles of a layer are completed then all the puzzles in the next layer down are guaranteed to have their dependencies satisfied and are available for solving. Of course the player need not solve all puzzles layer-by-layer and so the number of puzzles available at a given time could be more or less than the number in a particular branch. The size of the layer just gives us general idea of the degree of non-linear branching at each phase of the game.

A valid order in which the player may solve the puzzles is known as a Topological Order. Due to the high degree of non-linear branching this game has a vast number of valid topological orders. The exact number is not known to me but a lower bound can be determined by looking at the number of permutations possible in the largest layer. With 13 puzzles in the fourth layer there are over 6.2 billion possible orders in which the player might solve them.

The GANTT chart is a nice way to look at the size of the layers visually. It shows the number of puzzles available in each layer as green boxes in vertical columns. From this we can see that this game has a short linear introductory segment followed by a very non-linear middle-game with all kinds of puzzles available for solving at once. The degree of non-linear branching is reduced slowly as the game winds down and finishes with a completely linear segment of 4 puzzles at the end.

GANTT Chart for The Day of the Tentacle Puzzles

GANTT Chart for The Day of the Tentacle Puzzles

Other games could have dependency graphs with different features. A game with multiple starting conditions would have more than one initial node in the first layer. A game with multiple victory conditions or optional puzzles which do not contribute to the final victory would have more than one leaf node.

The shapes of the dependency graph and the GANTT chart are also instructive. A game which was purely linear would have a straight line of nodes from start to finish, each with one dependency. If there was an even higher degree of non-linear branching the result would be a wider graph with more puzzles in each individual layer. This game follows the advice of Noah Falstein when he said “Make it Bushy“. By this he is advocating for a graph which balances linear and non-linear branching into a shape that resembles a bush. This shape is also mentioned by Ron Gilbert when talking about the graph for his current game “Thimbleweed Park”.

Considering these other possible types of graphs allows us to think about how The Day of the Tentacle was constructed. Choices were clearly made by the designers to incorporate every puzzle into the narrative and to have no “alternate” endings or even optional “easter-egg” puzzles. The focus on non-linearity gives the player plenty of available puzzles in the mid-game. This has the benefit of giving plenty of things to do at any time and avoids holding up the game because the player is stuck on a single puzzle. This choice had to be carefully crafted into the game however. Many games begin to feel aimless and random when there are too many possibilities with no clear goal. Day of the Tentacle manages to retain the benefits of non-linearity while avoiding the pitfalls and this is in large part due to the puzzle structure.

Character Cooperation

A key game device of The Day of the Tentacle is the ability to switch between characters. This is somewhat unusual in adventure games and very unusual in that it actually works from a gameplay and story perspective. Most games which require the player to juggle multiple characters don’t work nearly as well (including Maniac Mansion). One reason I think it succeeds is the combination of the time-travel as a narrative device and the restriction of the setting to different versions of the same Mansion. These two elements combine to enable many cooperative puzzles where one character’s actions contribute to a puzzle for another. This is done by passing items via the Chron-o-Johns and by taking actions in the past which affect the future. It’s a testament to the high caliber design of this game that these two basic actions are used over and over but they never seem to lose their charm or magic.

Swimlanes

We can tell exactly how many puzzles involve this kind of inter-character cooperation by looking at the Dependency Graph grouped into lanes. Each lane groups the puzzles solved by an individual character. If we look at the edges between nodes which cross from one lane into another we can easily see which puzzles have dependencies on other characters’ puzzles. There are 32 of these types of inter-dependent puzzles. Half of the gameplay therefore relies on either cooperating directly between characters via the Chron-o-Johns or taking some action with one character with enables a puzzle for another character (usually crossing time). The Dependency Graph is shown here separated into lanes:

Dependency Graph grouped into “swimlanes” by character. Puzzles which require cooperation between characters can be seen by the edges which cross between lanes.

Expanding and Contracting

There is more that we can discover by analyzing the graph. Looking at the in and out degrees on each node we can see which puzzles open up or close down the branching and by what degree. It is clear that the puzzles which open up the branching in this game really open it up. Find the Super Battery Plans opens up 15 downstream puzzles. The player spends the rest of the game finding and closing down all those branches. The puzzles which close it down generally reduce the branching by only 1 or 2 (meaning their in-degree is only 1 or 2 more than their out-degree). This is certainly a design choice and it would be interesting to know if other approaches were tried and discarded.

It’s clear just from looking at these tables the way this game plays out. A small number of puzzles dramatically opens up the non-linear branching. The game expands very quickly and then takes a long time to close back down.

Expanding: These puzzles have higher out-degree than in-degree meaning that they “open up” the non-linear branching and expand the number of puzzles available to be solved.

Puzzle In Degree Out Degree
Find Super Battery Plans 1 15
Disguise Laverne 2 6
Find Dr. Fred’s secret lab 1 6
Laverne Access Outside 1 3
Get Laverne down from tree 1 2
Enter Human Show 1 2
Get Crowbar 1 2

Contracting: These puzzles have higher in-degree than out-degree meaning that they “close down” the non-linear branching and reduce the number of puzzles available to be solved.

Puzzle In Degree Out Degree
Get the Super Battery 4 1
Mummy Fashion 4 1
Get tiny sweater 3 1
Get Dusty Warm Hamster 3 1
Back to the Present 3 1
Get Vinegar 2 1
Build a fire 2 1
Start Storm 2 1
Get lab coat 2 1
Get Kite 2 1
Charge Battery 2 1
Dentures to Laverne 2 1
Get Rid of Harold 2 1
Win Human Show 2 1
Get Skunk 2 1
Plug in Laverne’s Chron-o-John 2 1
Get Toasty Warm Hamster 2 1
Power Laverne’s Chron-o-John 2 1
Rescue Dr. Fred 2 1
Get Signed Contract 2 1
Mail Contract In Past 2 1

Narrative Structure

As discussed in the Puzzle Dependency Graph Primer, non-linear branching in the puzzle structure poses complications for narrative. This is because of the factorial expansion of the orders in which the player may solve the puzzles. The Day of the Tentacle addresses this problem by isolating the narrative sub-plots into almost totally distinct puzzle trees. We can see this very clearly by organizing the puzzle dependency graph into groups based on the downstream goal. This graph shows this.

The non-linear branching of puzzles in The Day of the Tentacle aligns closely with the major sub-plots of the game. Only a single cross dependency exists between groups.

 

It is clear from the graph that there are essentially three totally separate games here which map directly to the primary sub-plots. We can see that it is possible to play through the entire sub-tree to ‘Power Laverne’s Chron-o-John’ without ever doing any of the puzzles in either of the other two sub-trees. Likewise we can ‘Get the Diamond’ without doing a single puzzle outside of that sub-tree. There is only one puzzle which has a dependency outside its group. That is “Get Vinegar” which requires “Access to the History Room” from the “Dentures to Laverne” puzzle. This acts like a gate which requires the player to at least get Laverne down from the tree and disguised before Hoagie can continues on to the end of his story. There are more of these gates internal to each story tree which we will explore below.

The fact that the game is broken up into these three siloed sub-plots is completely masked by the character switching dynamic. Since all of the sub-plots require extensive cooperation between characters it never feels like you are working on an isolated puzzle group. Also, given the vast number of orders in which the puzzles can be solved, the player is very unlikely to resolve one plot completely before even starting another one anyway. This is great for the player experience as they are free to make progress on all three sub-goals at any time. So if it is not noticeable to the player what is the point of keeping these puzzles all in their own sub-graphs?

From a narrative standpoint keeping the sub-plots isolated seems to be the key to maintaining a coherent story regardless of the order the puzzles are solved. With 13 puzzles in the fourth layer there are over 6 billion possible orders in which the player may solve them. To attempt to turn each order into a coherent story is obviously impossible. The solution The Day of the Tentacle takes is to isolate the subplots and then even further divide them into very small sub-trees which are able to be solved essentially linearly.

Sub-dividing the puzzles is only part of the equation, however. It is interesting to note that the dialogue and NPC actions which go along with the puzzles in each subplot do not reference any of the other subplots. The puzzles and plot points which together make up a sub-plot are completely self-contained and coherent regardless of what other units the player has or has not also experienced.

So we can see that two design choices were made. First: breaking up the puzzles and narrative into distinct units and second: refrain from making any narrative references to information outside of the unit. These both seem to be fundamental to the way Day of the Tentacle can provide a high degree of non-linear branching without introducing lots of logical narrative “bugs” or an impossible maze of dialogue trees to account for the different orders the player may visit the stories in.

Hoagie

Brap

A Detailed Example: Hoagie’s Journey

To demonstrate this design feature of narrative isolation I will walk through Hoagie’s narrative from the beginning of the game through to the point he plugs in his Chron-o-John. Then we can review how the narrative is broken into isolated sub-plots and compare the relevant sub-trees in the dependency graph to see how they relate.

The Story Begins

Purple tentacle drinks toxic sludge, turns mutant and decides to take over the world. So Dr. Fred ties up the tentacles in his secret lab and is planning to kill them both. The hamster goes to Bernard’s house to warn Bernard who decides to rescue the tentacles, bringing his two friends Hoagie and Laverne along.

After arriving at the house the kids split up. Bernard discovers the secret lab and releases the tentacles at which point Dr. Fred shows up and reminds Bernard that Purple Tentacle is incredibly evil and is planning on taking over the world. The only hope is to turn off the sludge-o-matic yesterday by using the time machine. So Bernard, Hoagie and Laverne travel through time in the chron-o-johns but due to an immitation Diamond the machine malfunctions. Bernard ends up back in the present, Hoagie goes 200 years in the past and Laverne is 200 years in the future. Now the goal shifts to rescuing the two friends.

With instructions from Dr. Fred Bernard realizes he must get a real diamond to use in the time machine and figure out a way for Hoagie and Laverne to plug in their Chron-o-Johns. Since Hoagie is 200 years in the past the only way for him to do that is to use Dr. Fred’s patented super battery. Dr. Fred flushes the plans for the battery down the Chron-o-John which sends them through time to Hoagie. Dr. Fred instructs him to take the plans to his long distant ancestor Red Edison.

The Floundering Founding Fathers
Super Battery Plans

This battery is going to be super.

Red Edison tells Hoagie he can make the super battery if he has Oil, Vinegar and Gold. The oil is found in the kitchen but the other items need more work. Hoagie discovers that the Founding Fathers are holed up in the mansion trying to write the Constitution but they have writer’s block and aren’t making much progress. There is a gold quill on the table but they won’t let Hoagie grab it. Jefferson does have a time capsule though – Hoagie puts a bottle of wine in the time capsule in order to send it to the future to make vinegar. By giving George Washington an exploding cigar, Hoagie knocks out his teeth which he replaces with the chattering teeth from the present day mansion. This makes George look cold and so Jefferson starts a fire in the fireplace. Hoagie puts the blanket Hancock was wearing on the top of the chimney, filling the room with smoke and setting off the fire alarm. The founding fathers all jump out the window which gives Hoagie a chance to snag the gold quill.

Once Laverne gets access to the history room in the future she is able to get the vinegar and send it back to Hoagie. Then, with oil, vinegar and gold he returns to Red Edison’s basement lab and hands them over to Red Edison who constructs a Super Battery out of them. However the super battery needs to be charged before it can power his chron-o-john.

The Ben Franklin Experience

After finding Ben Franklin in a field trying to discover electricity Hoagie realizes that he might be able to power his Super Battery if Ben got his experiment to work. But it’s too sunny for a storm so he collects a brush, a bucket, soap and water and washes the buggy out in front of the house in order to make it rain. Unfortunately this just makes Franklin go back in the house because his kite won’t work if it gets wet. So he gives Red Edison the Help Wanted sign from the present day and gets hired as a “moronic drone”. This has the benefit of giving him access to a lab coat which Franklin then cuts up and makes an All-Season Frank-o-Copter which can fly in the rain. They both go back out to the field where Hoagie slips the Super Battery into the kite and when it gets hit by lightning the battery is charged.

Deconstructing Hoagie

A Hoagie's Journey

A Hoagie’s Journey

There are three main story threads involved in getting Hoagie back to the present:

  • Building and Charging The Super Battery
  • The Founding Fathers
  • Ben Franklin

These three stories branch out from the same incident – Hoagie traveling to the past – and they come back together with Hoagie getting the Super Battery, charging it and plugging it into his Chron-o-John. In between these two events the stories diverge into their own sub-plots. If we follow the inverted dependency trees back upwards from ‘Get the Super Battery’ we can see that the puzzles also exist in isolated sub-graphs. So it is possible to Get the Gold without making any progress down another tree. Likewise it is possible to Get the Kite or the Vinegar without having even given the plans to Red Edison.

The key thing to note here is that none of the dialogue in the narrative around these three stories makes any assumptions about what the player has done outside of the small sub-plot in question. Hoagie never mentions ‘Oh great I need this gold to get the Super Battery’, or ‘I bet I can charge the Super Battery with this Kite’. This is because the player may not even have given the plans to Red Edison before getting the Gold or getting the Kite. So they may not even know what ingredients are required or that the battery will need charging. By restricting any references in the dialogue and action to the puzzles and stories of each small sub-graph the game has avoided those kinds of “bugs” in the story.

Bernard’s Journey

Bernard’s Story Three linear sub-plots

Bernard’s Story Three linear sub-plots

Both Bernard and Laverne’s stories use a similar mechanism. Bernard’s is the simplest with two serial sub-plots and a maximum of three puzzles in a single layer. Bernard’s goals are to Get the Contract, Rescue Dr. Fred from the IRS and then Get the Diamond. Bernard’s story differs from Hoagie’s in that these parts are linear and must happen in sequence. This is enforced by two gated sections where you can’t get the rope until you have opened the safe and you can’t get the signed contract until you rescue Dr. Fred. So Bernard’s subplots essentially form a single serial narrative which have no possibility of having narrative information incorrectly referenced out of order.

Laverne The Great

Laverne’s story is much different. It is the longest and most complicated with four sub-plots and the biggest puzzle group of the game. Her subplots are:

  • Gain her freedom
  • Win the Human Show
  • Free the Edisons
  • Power the Chron-o-John using a Hamster

Before Laverne is disguised and can freely roam around the future mansion there are puzzles to be solved which eventually will play into her narrative but which are not motivated by anything. For example it is likely that the player will get the sweater out from under the sleeping conventioneer without knowing at the time what it will be used for. This is an example of a ‘key before the lock’ puzzle and can lead to player confusion (see reference to Ron Gilbert’s rules for adventure games in Part 3). In fact the need for the hamster (frozen, warm, dusty or otherwise) is not motivated at all until Laverne gets into the basement and finds the generator. So the number of puzzles which the player may solve “just because” is quite large.

Laverne's Story

Laverne is… complicated

Winning the Human Show on the other hand is well set up and has a number of clear guideposts in the narrative. This subplot is encapsulated and can be solved from start to finish with no outside dependencies. Once her two sub-plots are completed she can resolve her primary story and power her chron-o-john and get back to the present where the kids gang up and resolve the over-arching plot by saving the world from Purple Tentacle (and getting out of Dr. Fred’s house).

Summary

We have seen how the puzzles and narrative are broken down into three almost totally isolated groups and how each of those is broken further down into little sub-plots which are themselves well encapsulated with minimal external narrative references. By doing this the design of this game seems to have been greatly simplified. Instead of attempting to write dialogue and actions around a vast number of possible story scenarios based on the order the player might solve puzzle in the problem is reduced down to simple linear story-telling within the sub-plots. I believe this is the key to how The Day of the Tentacle benefits from a high degree of non-linear branching – effectively allowing the player to choose the order in which the story is told – while still avoiding mistakes where a reference is made to an event the player has not yet experienced.

For even yet more Day of the Tentacle analysis please see the last part of this series:  Puzzle by Puzzle.

Puzzle Dependency Graph Primer

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 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

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

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

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

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:

The permutations of a set with three elements: A, B, C.

1 ABC
2 ACB
3 BAC
4 BCA
5 CAB
6 CBA

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.

Factorial Growth

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.

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

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

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 a puzzle dependency graph with estimated time assignments 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:
  • 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:
  • 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.