This is something I already created a little more than a year ago, and only came around to publish now: a game dependency graph.
The Secret of Monkey Island is a computer game from 1990 which I loved to play back in the day. It is an adventure game, played with the mouse: You play as a character named Guybrush Threepwood (shown on the right), and can walk around many different areas, interaction with objects, people, and other things. This is not an action game; you don’t need to perform actions at subsecond precision to win, but instead you must find out how to proceed in the story by performing the correct actions, such as using objects with other objects, talking to people, pushing things around, etc. Essentially, the whole game can be seen as a set of actions that must be performed.
The actions in this game cannot be performed in any random order, but are interrelated. For instance, you need to pick up an object before you can use it. Thus, we can model the whole game as a directed graph, which the actions being the nodes of the graph, and the dependencies as directed edges. It is logically impossible for this dependency graph to have directed cycles, and thus this graph is a DAG, a directed acyclic graph. In fact, this type of graph has already been considered, in particular under the name puzzle dependency chart; see that article by the creator of Monkey Island himself, Ron Gilbert.
This graph has many additional features in addition to just being a DAG – see below for an explanation. The picture itself also includes a legend at the bottom.
SPOILER ALERT: This post contains spoilers for pretty much all puzzles in The Secret of Monkey Island.
NEW: PDF version of the graph (supports text search)
Special Graph Features
The graph has some extra features that put it beyond “just a DAG”, which I’ll list in the following.
First of all, a note about the direction of edges: The direction of edges is not indicated by little pointed arrows in the picture, but instead I follow the convention that all edges point down. This is possible because the graph is acyclic.
Multiple Types of Actions
There are different types of actions that can be performed: pick up, talk to, push, etc. Each of these is represented by a differently colored node.
- Rarely used commands are all shown in blue – remember that this is the first Monkey Island game, which had much more commands than later ones. Commands like “push” and “pull” are used only a few times in the game (but sometimes in a clever way, for instance to “rotate” the safe handle and the balanced stones.)
- Commands like “open” and “go to” are only shown if they have a game-relevant consequence. I don’t include all doors you have to open just to go through the game.
- I also don’t include all the people you can talk to. Almost all of these dialogues are optional, and would just be isolated nodes in the graph. I only make an exception for really, really important dialogues, such as with the Voodoo Lady.
- There is a single way to die in game, which is represented as a black node, and obviously cannot have any outgoing edges. It is located in the underwater scene in Part I. (Note that Monkey Island avoids death as a general rule – the inclusion of this is more of an easter egg, rather than actual gameplay, in particular because it will only happen if the player cannot exit the underwater scene in ten minutes, which isn’t too difficult to do.)
- There is also a way to get stuck in the game, by spending all pieces of eight on the broken grog machine. This too is indicated by a black node.
Some puzzles in this game have multiple solutions. This is reflected in the graph by dashed lines that converge on a little circle. This happens only a few times:
- In order to enter the forest in Part I, one of two things must be done: (1) buy the map, or (2) follow the storekeeper to the forest. Once the forest can be entered, both the treasure and the Sword Master can be found without further help, but one of those two actions must be performed, because otherwise Guybrush refuses to enter the forest.
- The option to ask the storekeeper to to the Sword Master (see previous point) can be unlocked in two ways: (1) By talking to the important-looking pirates, or (2) by buying the sword from the storekeeper.
- One of four different objects made out of cloth or paper can be used in the recipe puzzle in Part II: the business card, the map (which is optional), or one of the two T-shirts. The player can also put all of them into the pot in order to make the inventory shorter, since you don’t need them again.
- The dam in Part III can be burst in four different ways: (1) using the lens with the sun, (2) using the spyglass with the rock, (3) using the cannonball with the rock, and (4) using the magnetic compass with the rock. This also means that getting the spyglass from the fort is completely optional, even though it can be used in two different ways to burst the dam.
Some “action-like” puzzles in the game do not fit into the “dependency graph” approach, and are represented as a single node, even though the player must perform a little bit more than a single action. These cases are shown in red in the graph. These include: learning and applying swordfighting insults, navigating through the forest maze, following the store keeper to the swordmaster (which is optional), carrying the grog to the prison, haggling with Stan, and tricking the storekeeper in order to steal the note of credit.
(Since the graph doesn’t say how to solve these puzzles, they are the only part of the game not spoilered by this post.)
The game is divided into what I call areas, and which are separated by dashed lines in the graph. What I call an “area” is a set of rooms between which the player can navigate freely, and thus the player will always be in a single at a particular time, and will need to perform specific actions to enter another area. In the beginning of the game, areas correspond to individual parts of the game, e.g., when the player can finally leave Mélêe Island™, after which Part II starts, and the player is now on the ship. Each area can be seen as its own game with its own dependency graph. There are also what I call “subareas” in the game, which happens when you enter an area (usally a single room), which, when exited, leads you back to the previous areas – these subareas are shown as dashed rectangles. There are two of them: the seafloor scene in Part I, and being captured by the cannibals in Part III. The ending of the game can be seen to consist of three consecutive small areas.
We can now finally perform some network analysis. Of course, a proper network analysis would be more interesting if we had multiple games to analyse, so I’ll restrict myself to things that can be gleaned “by hand”, e.g., without using a computer analysis.
Things You Can Do Immediately
Nodes that don’t have any incoming edges (i.e., no edge coming into them from above) are things you can do immediately when you enter an area. You can think of there being implicit edges from the action that starts the area to all such nodes, but we don’t draw them because they don’t add any information, and would just clutter the graph.
Nodes in the graph that are not connected downward to the end of the game are optional, i.e., you don’t need to do them to win the game.
This includes talking to the important-looking pirates, talking to the sheriff in the alley, using a breath mint, putting money in the grog machine, getting the PTA minutes from the three pirates, playing with the rat, talking to the Voodoo lady, following the storekeeper to the swordmaster, opening the chest in the bedroom on the ship, picking up and reading all memos on Monkey Island, walking to the edge on the top of Monkey Island and falling down, and destroying the ship.
Of course, many of these are integral to the game’s storytelling, so you should do them – after all, exploring everything is what these kinds of games are all about. (For destroying the ship, you get two slightly different endings depending on whether you did it or not.)
Redundant Transitive Edges
The graph is not a transitive reduction: Certain dependency edges could be removed without changing the situation.
For instance in Part I, you need the pieces of eight to buy the sword, and you need the sword to train with Captain Smirk. Thus, we can infer that you must have the pieces of eight when you train with Captain Smirk, and could thus omit the link from the pieces of eight to Captain Smirk.
In this case, we include such links because of the storytelling: You need to give pieces of eight to Captain Smirk, and thus they are a logical dependency, even though it is impossible to not have the pieces of eight if you already have the sword.
Linear vs Parallel Gameplay
You can see in the graph that the game has distinctly different phases, purely based on the structure of the dependency graph:
The beginning is very dense with many possible parallel paths – as you start to explore the first area (Mêlée Island), you can do many things in parallel.
The end of the game, on the other hand, is much more linear: The thirteen last actions (starting at “use jug o’grog with dish” in the pirate ship) must all be performed in the given order.
Diversity of Puzzles
Clearly, the puzzles in the beginning of the game are much more varied than those at the end. The last “action-like” or “rarely used command” puzzle is the navigation through the underground maze in Part III – after that it’s just walking, talking, picking up objects, and using objects until the end of the game. The last action in the game however, is at least timed, so there’s that.
Compare that to the start of the game, which includes all possible commands in some way, all along with going through a maze, following a non-player character, almost dying underwater, and the whole insult swordfighting section.
(This is subjective of course, and I’d like to see how other games compare.)
Size of the Game
We can also use the graph to measure the “size” of the game. There are
153 154 nodes in the graph (if I counted correctly), but since I haven’t done this for any other game, I can’t compare that number.
(Of course, this does not take into account the “action-like” sequences, which are much more present in this game than in other games of the genre.)
If you haven’t played this game: It is supported by ScummVM. (There is also a remake which I haven’t tried, but you’d better be playing the original version, with those lovely pixely graphics.)
I also want to do this type of analysis for other games. Candidates are: Monkey Island 2 and 3, Day of the Tentacle, Flight of the Amazon Queen, The Dig, Full Throttle, Sam and Max, Simon the Sorcerer, and maybe something like Broken Sword. Oh, and I would love to do Thimbleweed Park too (haven’t played it yet!). (If I have time of course – this is not the type of analysis that they give you gigantic grants for, as fun as it is.)
If there are things that should be corrected in the graph, please drop a comment.
Fun fact: the original Amiga version of the game came on four diskettes, and is only 18.5 times larger than the full-size image above. (If my calculations are correct)
EDIT 2019-01-18: Added one more optional action that I missed
EDIT 2019-01-18: Added the death node in the underwater scene
EDIT 2019-01-18: Added PDF version
EDIT 2019-01-19: Added a link to Ron Gilbert’s page on puzzle dependency charts
EDIT 2019-01-21: Divided a dashed box into “mansion”/”underwater” scenes; small adjustments in the chart (v3)
EDIT 2019-01-21: Added note that not all dialogues are included in the graph
EDIT 2019-01-21: Added getting stuck by spending all money on the grog machine; added “enter forest” as a node which can be achieved by either following the store keeper, or by buying the map; made clear that the poisened meat can also be produced via the pot o’ stew; rearranged nodes
EDIT 2019-01-22: Made the legend better (v6)
EDIT 2019-01-23: Added bullet point about the two ways to enter the forest in Part I
EDIT 2019-02-03: For following the storekeeper to the Sword Master: the puzzle has multiple solutions (Thanks LogicDeLuxe from the Thimbleweed Park forums)