Dungeons and Dimensions: Network Theory Applied to Gaming

Quick confession, when I learn about some new concept my first thought isn't always about how it can be applied to space travel.  That is what I think of when I learn new things about science or engineering, but when the subject is mathematics or programming my first thought is usually, "how can I use this in gaming?"  Specifically, tabletop gaming like Dungeons and Dragons.
So when I started learning more about network science the very first thing I thought to do was see how I could use it in D&D.  So I started looking at the abstract definitions of a network, nodes, and links as a dungeon with rooms and doors.  Then I started trying to see where I could go with it.
Of course, there's some basics to get out of the way first.  Like what is a network?


Network theory refers to a specific branch of mathematics relating to networks, not necessarily computer networking.  A network shows how a collection of things are connected.  These things, called nodes on a network graph, could be people, places, states, chemicals, virtually anything.  Links between nodes represent some kind of relationship which connects two nodes, whether they represent a change of state, a physical connection, a social interaction or what have you.  Network theory is extremely versatile and can be used in almost all branches of science on some level.  The famous "six degrees of separation" is an example of applied network theory.
The simple network shown below demonstrates several key features.  There are five numbered nodes, with five links connecting them.  If we start at node "1" there is a direct path to node "5" which takes us three steps.  There is also a loop, which leads back to node "1" and takes 3 steps.  Here all the links are directional, they lead one way only, the direction the arrow is pointing.  Links can go one way or two ways, with two way links having arrow heads at both ends or no arrows at all.  If all the links are bidirectional then the network is symmetric.  Otherwise it is asymmetric.

We've labelled all the nodes in this graph with numbers, but the links have no labels.  We could give each link a unique identifier, like "a,b,c,..." but it would actually be unnecessary.  Instead we'll label each link based on what node it starts at and which node it ends at.  For the link connecting nodes "1" and "2" we'll assign the label "(1,2)" where the first number is where the link starts and the second label is where it ends.  So any link leading from node "i" to node "j" is represented as link (i,j) for us.  If a network is symmetric then the existence of link (i,j) requires the existence of link (j,i) but this isn't necessarily the case for asymmetric links.
Instead of listing all the links in this graph it will be easier to write a table with 5 rows and 5 columns.  If there is a link between nodes "i" and "j" then we'll write a "1" in the ith row of the jth column.  Otherwise we'll write a "0" in that space.  Writing the table out for this network:

Which is actually a mathematical construct called a matrix.  This specific square matrix is called the transition or adjacency matrix.  It tells us if two nodes are adjacent, meaning connected, or if it is possible to transition from one to the next.  We represent the transition matrix by A.  Because of the rules of matrix algebra if we multiply A by itself we'll see if there is a transition from node "i" to node "j" in two steps.
This continues to hold for any higher power of A.  From the nth power of A we see if there is a path from node "i" to node "j" in n steps.  Now let's say we multiply A by some variable, s, just to keep track of how many steps we've taken.  We're not concerned with what s is, just its degree, what power it is raised to.  Because of the loop a 5 step path looks exactly like a 1 step path, except for the power of s:

It's possible that we'll end up with more than one path that takes n steps leading from "i" to "j" and that is actually represented by having a number larger than one in that space.  In A there is only one connection, but in some higher power of A that isn't necessarily true.  So a "0" means no possible, while some larger number k means there are k paths that take n steps.  If we add up all these matrices we'll be able to see all possible paths between any two nodes.

This series actually looks just like the Taylor series expansion of another function:

So, in effect, we can find the number of possible paths between any two points for any possible number of steps.

Okay, so what gives?  That's all very interesting but didn't I promise you gaming?  What's with all the matrices and algebra stuff?  Well, remember how I said that the nodes of a network could represent anything?  Anything could include the key points and locations, or even rooms, of an adventure.  Let's borrow an idea from Justin Alexander's "Node Based Adventure Design" series, where he discusses the key elements of adventure design in the form of nodes and links.  We'll talk about one of the easiest adventure concepts to understand, the classic dungeon crawl.
So from here on out instead of nodes we have rooms in a dungeon.  Instead of links we have doors.  Instead of abstractly moving from node to node, we'll follow a party of adventurers exploring from room to room.
Look at the simplest possible dungeon, the five room dungeon.  This sort of adventure has five key rooms, each with an important element.

1. Entrance - Something has kept previous explorers out.
2. Puzzle - Left or right?
3. Setback - Turns out you should have taken the right turn.
4. Conflict - Before you get the treasure there's one more obstacle.
5. Reward - Was it all worth it?

Does this look a little familiar?  Maybe if it had circles instead of squares and lines connecting them where those doors are?  If we take the summation above, and stop at n=5, enough to go all the way around the loop once and still get to the end, the matrix looks like this:

From any room this tells you how many steps are needed to get to any other room.  Notice that along the main diagonal (those positions where i = j) the first three entries are no longer 0.  Because I've taken the setback at room "3" to be something that kicks you out of the dungeon, back to the entrance room "1" there's a loop just like before.  This means that three steps from room "1" will take a party right back to room "1" and the same can be said for rooms "2" and "3" but not, you'll note, the other two rooms.  That's because it's not possible to backtrack from either of these rooms.
For this dungeon I've assumed the doors are all dimensional, meaning that the party never deliberately decides to backtrack.  That isn't necessary, though.  I could just as easily have made my transition matrix symmetric. In this case I'll assume that, instead of sending the party back to room "1" the setback in room "3" just wastes their time, the room is a dead end.

Then we just do the same thing, take the sum above up to five, since there are only five rooms.  This gives a slightly messier, but not really any more complicated result:

Okay, maybe it looks a little intimidating, but really it isn't that bad.  Just look at any given cell, perhaps cell (1,5) the number of paths and steps from room "1," the entrance, to room "5," the reward.  According to this cell there are 4 possible paths of 5 steps and one possible path of 3 steps.  You can trace this out on the map above, just ignore the door leading outside from room "3" and remember you're allowed to backtrack anywhere.  You'll also see that the same entry appears in the opposite corner, (5,1), the number of paths leading back from the reward to the entrance.  This works for any set of two rooms.
Let's say you wanted to know the minimum number of steps from room "i" to room "j" in this dungeon.  It would just be the lowest polynomial term in the matrix above.  So I'll construct a new matrix with just that information, just the lowest degree of each cell above.  I'll call this new matrix the distance matrix, D.

Just from knowing which rooms have doors, without even really knowing the shape or layout of the dungeon, I can tell how far any two rooms are from one another.  Obviously in this I've lost information.  I can tell you how many steps a given path has but not what those steps are.

Okay, you're probably wondering now what the point of all that was.  It seems like I've come up with a really complicated mathematical way of doing something a 5 year old could do.  Which, to be fair, is a decent description of D&D to begin with.  But there is a bit more to it than that.  While I'm talking about a very simple dungeon, everything I've said can be expanded to any number of complicated dungeons with any number of connections.  Any combination of rooms and doors, even if the dungeon itself has non-Euclidean geometry.  I've connected these rooms in 2d, but they could be arranged in 3 or even more dimensions!  All the matrix cares about is whether or not they share connections, not what those connections are.
The psuedocode below presents a very simple program to do exactly this.  It converts the adjacency matrix, A, into a distance matrix, D.  It does this using an n-step transition matrix as an intermediary.  Note that this program assumes that the matrix exponentiation function has meaning in whatever language you might be employing.  Be cautious here, as some languages may assume this means take the nth power of each entry in A, not take the nth power of A.  This is why I'm using the five room dungeon as a test, it's easy to see where errors show up.

Having done all that we can get a little more involved.  Let's try applying the system I just talked about to a more complicated dungeon.  A great example of everything I'm talking about is actually the dungeon design from the beloved 1987 Nintendo video game The Legend of Zelda.
In LoZ, for short, dungeons are composed of rectangular rooms, all the same size, which can have at the most, five passages leading in and out (four doors and one hidden passage).  This gives us easy, discrete rooms to serve as nodes.  Most doors allow passage both ways but some are exclusively one-way links, so a good choice of dungeon is asymmetric.  The dungeons are also quite complex and very interconnected, leading to a well-populated adjacency matrix.  Finally, there is a clear start and end point for each dungeon.
What I've just said is slightly misleading.  It isn't always possible in LoZ to get to each door at all times.  You need to find keys to open certain rooms, and some rooms are designed so that certain doors are only accessible depending on how you entered the room.  Also you need bombs to open up walls in locations.  Fortunately we can just ignore the keys and bombs issue, and Level 1 of the game all doors in a room are always accessible, even if they won't open.

Level 1: "The Eagle"

I've broken this dungeon into a simple network graph, seen below.  Notice that one-way doors are represented by arrows.  It's been a while, so some of these might not actually be one way doors, but we'll assume they are for now.

Level 1: "The Eagle"

For this dungeon the adjacency matrix is:

Level 1: "The Eagle"

Where the blank sections are all zeroes.  I've left those areas blank to improve readability.  You may notice that the matrix is almost, but not quite, symmetric.  This is because of the one-way connections in this graph.  Now we can find the distance matrix, which tells us the minimum number of steps necessary to find our way from any of these 17 rooms to any other room, including what number of steps might cause you to end up right back where you started.

Level 1: "The Eagle"

Below I've attached Excel workbooks that calculate the distance matrices for the two dungeons I've looked at here given their adjacency matrices.  The VBA script here will fill in blanks in any given adjacency matrix, aiming for symmetry where possible.  Any given adjacency matrix, and thus any given dungeon, can be analyzed like this.
Level 1: The Eagle
The Five Room Dungeon

Later I'll spend more time talking about the more impressive things we can actually do with this concept, like generating and describing multi-dimensional dungeons or analyzing different paths through dungeons.  For now we'll have to settle for just this bit of useful background information.