How I make a dependency graph (Patreon)

Hello everybody! It’s been really interesting to see my graph system, which I developed for Boss Keys, being used by different people for different purposes.

Here’s doctoral researcher Thomas Smith, using Answer-Set Programming to generate Zelda graphs.

Here’s designer Sébastien Bénard using my Zelda analysis to help generate levels in Dead Cells.

And here's studio Ice Beam, using the graphs to generate levels in a game called Socketeer. 

Which is awesome! I’m incredibly proud to have contributed something useful to the world of game design and analysis. I’d love to see this system used more widely and for lots of different purposes - both for analysing games, and making them. 

And so I wanted to create a central resource for info on the subject that people can use to better understand these graphs, their use, and how to make them. To do so, I'm going to show off a step-by-step tutorial for how I use the graphs to analyse an existing game. In this case, Super Metroid. 

1 - Play the game

The first you should do is simply play the game through from start to finish, without thinking too much about graphs or dependencies or level design. 

You want to see (and possibly note down) your experience with the game. Did it feel too linear? Like you had too many options? Too much backtracking? Like you suddenly got completely lost?

You need to do this before making the graph. Because analysing the level design in this much depth, and charting out all the different routes, will forever change the way you see the game - no longer as a magical world of possibilities, but now just a cold collection of locks and keys.

And here’s the thing: the graphs are there to explain the experience you had when playing. The graph will show you that the game was linear, or had too many options, or too much backtracking, or had moments of forward progression that suddenly turned into choice.

Your experience is key. The graphs just help explain it in a visual manner.

2 - Decide what’s relevant

Now we know how the game works, we need to decide what information we’ll be recording on our graph. 

The most important thing, of course, is the things you need to do to complete the game (or level or dungeon). In Zelda that’s locked doors and their keys, obstacles and their associated items, and puzzle elements like in the Water Temple and Sandship. In Metroid, that’s mostly obstacles (like pink doors) and their associated upgrades (missiles).

That’s the whole point of the graphs. It shows the steps you need to take to get to the end of the game, and which step is dependent on another. 

But you may wish to include other things, if you feel they are interesting or relevant to your experience.

For Super Metroid, I felt like the game was chockfull of locked doors - pink doors and green doors and yellow doors and crumbling blocks and grapple hook points and superheated rooms - and the experience of the game was checking all of them, after getting a power up. 

Sometimes it was the path forward, but sometimes it was non-essential items like missile tanks, optional upgrades, and even tutorials for the wall jump and shinespark. With no way of knowing, you've got to check them all. 

So I decide that for this graph, I needed to record that information too.

3 - Map out the game, step by step

Okay, next thing to do is to make a map of the game world. 

Luckily, almost every popular game has maps online. So for Super Metroid I used this handy map by Falcon Zero. Sometimes you can use the in-game map, though sometimes you’re going to have to go through the arduous process of drawing out your own. I only had to do that once, for the (then-unreleased) Metroid: Samus Returns.

Next, load the map into a program with layers, like Photoshop or Gimp or Pixelmater. 

Now, play the game and explore as much of the space as possible. Every time you get to an obstacle, put a marker on your map and hide the rooms that continue after that roadblock. Also mark down any power-ups you can get. 

I use a simple colour scheme of red for locks, blue for power-ups, green for optional goodies, and purple for bosses. If power-ups are not needed to complete the game, I give them yellow text. Just do whatever works for the game you're analysing.

So, above, I have explored the opening areas of Super Metroid. I can walk around a small part of Crateria and a tiny part of Brinstar, but my path is blocked by narrow gaps (need the Morph Ball), pink doors (missiles), crumbling walls (bombs), and too-high platforms (Space Jump). But I can go and get the Morph Ball.

Then pick up a power-up, duplicate the previous layer (or layer group) in Photoshop, and repeat the process. Here, after getting the Morph Ball, I can now go through these three Morph Ball locks from earlier, giving me access to two new locked doors (one needs a missile, another needs a bomb) and another power-up: missiles. 

Keep doing this for the rest of the game.

At the end of the game, you should have layers like this.

Things get more tricky if you can do stuff in different orders. Like if you could pick up two critical power-ups at the same time.

For this, I found it useful to keep the locked door icons on the graph, just semi-transparent, to remind myself what power-up was used to open that locked door. 

4 - Create the graph draft

Okay, now for the tricky bit. Because you’ll need to be able to move stuff around as you go, it’s not really feasible to do these by hand on paper. You need to do it via some kind of software.

Photoshop would work again, but I personally prefer to do it on the iPad app Paper, with my Apple Pencil. That lets me doodle these things by hand, but also have the flexibility to move stuff around. Find something that works for you.

Now, go back to your Photoshop file for your map and just show the layer (or layer group) for everything you can do before the first power-up. 

On your draft graph, draw a start icon, then draw squares for all the locked doors, and diamonds for any power-ups. Draw a horizontal line coming out of the start icon, and then connect it, vertically, to any power-ups.

Now, move the square locks below the diamond of the same type, and connect them to the top line with a vertical line. Here, I’m taking the morph ball locks and putting them below the morph ball diamond.

Go back to Photoshop, and go to the next layer.

And then fill in the next bits of the graph.

So above, I put new locks, for missiles and bombs, below two of the morph ball locks. I put a power-up diamond for a missile below the third morph ball lock. And then moved all the missile locks down, below that diamond.

I don’t put vertical lines on the locks until they’re in the right place, to remind myself that they’ll need to be moved later. 

Here’s one more step. This time, I’m using triangles to denote non-essential power-ups. They’re important for this graph (see step two, above), but they don’t actually affect the dependency, so they need a unique symbol.

After a lot of jiggery pokery, this is the final graph for Super Metroid. Trying to fit everything in is a bit of an art, and it requires some messing around. Admittedly that’s not ideal, but maybe I’ll figure that out in the future.

Sometimes a graph will need some special considerations. In this case, there’s a section of Super Metroid where you enter Norfair and can’t return to Brinstar or Crateria until you unlock the power bomb. So the red line shows when you can return to these previous areas, and now access a bunch of locked doors. And the blue line shows where there are two entrances to Maridia. 

You can also do other things to make it easier to digest. Like, here, I’ve colour coded the sections to show where they are in Zebes: In Crateria, Brinstar, Norfair, Maridia, the wrecked ship, or Tourian. 

5 - Making the graph pretty

If you want to present the graphs to people, such as in a YouTube video!, you might want to make them look a bit more pretty. That basically just means remaking your draft with proper graphics, in a program like Photoshop.

Here are the files for the Zelda graphs. It’s got some basic symbols, the background, and a sample PSD file. Sorry it’s a bit messy! If someone wants to make a better version, or some online tool, then let me know. 

Now, the graphics might be different for different games. For Super Metroid, for example, I used these icons. And you might need to make special symbols for special dependencies. In The Wind Waker, I needed icons for using Makar in the Wind Temple, for example. 

The basic rule is the same, though. Square for locks. Diamonds for keys. Circles for things like the start and bosses. Triangles for non-essential items. Locks and keys should be the same colour as each other, and have the same symbol.

Here’s the final version of the Super Metroid graph.

And here’s a simplified version, with just upgrades and locked doors - no pick-ups like energy tanks and missiles.

6 - Reading the graph

Okay. So what does this graph actually tell us? There are a number of things we can look at to get some information on the game’s design. 

First: look at the horizontal lines. If they are really long, and have lots of lines coming off of them, this tells us that the player can explore a lot of the game at once and come across a great number of locked doors.

Check out this one. So, you’ve done some initial exploration in Crateria, bombed through a wall in the top left corner, and venture into Brinstar. From here, you can explore a great deal of places and find:

• Two areas that require the speed booster to visit
• An area that needs the grapple hook
• Two sections that can’t be visited until you have a power bomb
• A green door, which needs the super missile
• The super missiles (after a boss fight)
• The map room for Brinstar
• The charge beam
• The entrance to the final area: Tourian 

That’s a lot of places to explore, remember, and stumble upon. That’s good!

Next, look at the stuff that’s on the same horizontal plane. This tells us how much stuff we can do at the same time. 

Look at this row here. After getting the grappling hook, we can use it:

• In Brinstar, to get a missile tank
• In Brinstar, to get the x-ray beam
• In Norfair, to get a power bomb
• In Norfair, to get an energy tank
• In Norfair, to get a reserve tank and a missile tank
• In Norfair, to get the wave beam
• In Crateria, to enter the wrecked ship (and continue your adventure forward).

This is really cool. It gives the player more choice in what they do next, and it means a new item completely recontextualises the world.

We can also look at the vertical lines. These show backtracking. For example, you have to go all the way back to the very beginning of the game, Crateria, to get to the final zone, Tourian. However, this doesn’t tell us too much information from the graph alone, because we need to know how the world is designed.

In the Zebes-set Metroid games, Brinstar acts as a hub world so it’s easy to get from place to place. And in some Zelda dungeons, a path will take you directly from the item to the obstacle its needed for, so the backtracking work is done for you.

But it can still show interesting info. Like in this graph for Zero Mission, we can see that while the player will routinely return to Brinstar, there’s no pressing need to ever return to Kraid’s area and Crateria after you’ve finished with them, which reduces that feeling of being in an ever-expanding world.  

The basic rule, though, is that graphs that are very tall and thin represent very linear games. Graphs that are short and wide are used to describe more open and choice-driven games. 

Other things

So, these graphs are a pretty good way of analysing a game with non-linear level design, such as Zelda, Metroid, Castlevania, Hollow Knight, Resident Evil, and System Shock 2. They show the dependencies between different locks and keys, to show you everything you need to do to get from the beginning of the game to the end.

But maybe they could be used for other things? Writing this article reminded me of Ron Gilbert’s puzzle dependency charts that he uses for point and click adventures like Monkey Island. Maybe they could be relevant for upgrade trees, or tech trees, or dialogue trees? A whole orchid of trees! I dunno! You tell me. 

For game analysts like myself, their use is very obvious. But they can also be used by developers. Maybe to evaluate your Metroidvania while its still in prototype. Maybe to create a procedural generation system. Maybe for something else, I don’t know.

I’m going to keep working on them, as part of Boss Keys, but this is what I’ve got for now. I hope it’s useful!