Dungeons and Dimensions: Generating a Dungeon as a Network

In Part One of this series I introduced the basics of network science and how it might be applied to dungeon design.  In Part Two I went over some of the basics of analyzing a network, and what those terms might mean when applied to a dungeon.  In this third entry I'll talk about what all this buildup has been for: producing a new dungeon and describing it from scratch.  Actually, I'll be producing it from a collection of functions and subroutines designed for this express purpose.  Basically the same thing, right?

Before I go too deeply into this topic, though, I'd like to answer the most obvious question here: is this Procedural Dungeon Generation?  Well, it is a procedure that generates a dungeon, so by the most obvious definition it is.  But, is it really?

No, not really.  Most procedural content generation (PCG) systems actually produce a completed map, and I've been very explicit that that is not what I'm doing.  Not yet, anyway.  The most common PCG methods for dungeons are built around removing walls from a solid grid, placing rooms, generating mazes, and then populating the completed building with encounters.  This network based method is more about determining which encounters lead to which other encounters, then drawing a dungeon around that.

You can find a great write-up on a procedural dungeon generation method here, by the way.  There's a clear contrast between this kind of procedure with those of the network based procedure I'm employing in terms of both their method and their goal.


At its core a network is a collection of nodes connected by a collection of links.  When I talk about network generation, what I'm really referring to is a procedure which produces those links.  Since links can be contained by the adjacency matrix, A, each algorithm I describe is ultimately trying to produce that matrix.  If I decide to draw a link between nodes i and j then that means I'm writing a 1 in cell i,j of the matrix A.  In the previous two posts I analyzed a dungeon given A, now we'll look at how to produce a new dungeon and its adjacency matrix A.

If I know that I want to produce a dungeon with some number of encounters, n, then I'm producing a graph that tells me how one encounter leads into the next series of encounters.  These algorithms explore different methods of making that happen.

Linear Networks

The most obvious place to start is to simply draw a straight line from one encounter to the next.  Node 1 leads to node 2 which leads to node 3 and so on all the way up to the final node.  Node 1 is the starting point and the last node leads nowhere.

Pretty simple.  Networks like this are linear networks, since the nodes and links form a straight line.  And the algorithm to produce a network like this is also pretty simple.  It simply loops through each node and draws a link to the next node.

That's it, for every node i draw a link to the next node, i+1.  Of course, an adventure like this gets pretty boring.  A lot of people have made a lot of disparaging remarks about "linear dungeons" and "railroading" and I'm sure you've already encountered them.  Besides, what was the point of all that stuff we talked about before, with centers and hubs?  The linear network is so simple that it hardly needs us to do anything to generate it.

Ring Networks

What if we took the linear network and let it wrap around?  So we'll do the exact same thing, each node connects to the next one, but we'll let the last node also connect to the first node.  This forms the slightly more interesting ring network.

The psuedocode for this network is just a slight expansion on the  linear network, to account for the one extra link.  In this case the loop works just like the linear loop, except for the if statement.  This checks to see if we're drawing  a link from the last node and, if we are, it connects to the first node.

This is at least getting somewhere.  There are now multiple paths, at least.  Still, if every room in the dungeon only has one two doors, one of which is the way you came, it'll feel pretty dull.  The ring dungeon has potential, but we want more options.  

Regular Networks

Really, the ring network is just a special case of what's called a regular network.  In a regular network each node is connected to the next set of nodes.  Ring networks are also called "1-regular networks" meaning that each node connects to the next node.  In a "2-regular network" each node connects to the next two nodes.  And so on for any "k-regular network" where k can be any number between 1 and n, the total number of nodes.

In the 2-regular network below you'll see that each of the eight nodes connects to the next two in the circle.  This means that each room has a total of 4 doors, two leading forwards and two leading back.

The algorithm to generate this network is a simple adjustment to the ring above.  Instead of the one next node we draw links to the k next nodes.  This means adding a second loop that runs through k times, each time adding one more link.  The same if statement as before makes sure that when we hit the end of the dungeon it loops around and connects to the first few nodes again.

In a regular network every node has the same number of links and the same radius.  As a consequence the terms center and hub are meaningless, so each node above is plotted as both.

Complete Networks

As I mentioned, the ring network is really a special case of the regular network where k=1.  At the other extreme k=n, and every node is connected to every other node.  This is known as a complete network.  If we insist on having enough links then a network will end up a complete network.  A complete network of n nodes has n(n-1) links.  So if we try to draw that many, or more, links then we'll end up with a complete network.

All these networks are Regular, or predictable.  Given the same inputs they will always produce the same shapes.  A five room complete network will always look like a pentagram no matter how many times it is generated.

What about inserting some unpredictability into the design?  Suppose we allowed link generation to be at least a little random.  Then every time a dungeon is generated would be different, leading to more interesting and varied designs.  So now let's talk about randomizing our networks. 

Random Networks

The most obvious place to start randomizing our networks is to draw a completely random network.  Let's say for the moment that I have n nodes and I want to draw m links between them.  Then the easiest thing to do is to just randomly pick two nodes and draw a link.  I roll a die and call the result the head of this link, then roll again and call the result the tail of the link.  I do that m times and then I've created a random network.  Obviously this only has meaning if the two nodes aren't the same and if I haven't already drawn that same link.  As long as I can check for that, though, this kind of procedure should produce a totally different network every time I use it.  The following pseudocode describes a means of producing just such a random network.

This algorithm avoids duplicate links and links that connect a node to itself by simply repeating the loops until an acceptable new link is drawn.  When the outer loop finishes it will have generated a completely random network.  Shown above is a simple version of the Erdos-Renyi algorithm.

Anchored Random Network

An obvious issue with the purely random graph is the possibility of disconnected nodes.  In a dungeon this would mean rooms which exist, but are totally inaccessible from any other room.  And, really, what's the point?  If the party can't get to a room, then why have the room at all?  To avoid disconnected nodes we instead want to construct a slightly less random anchored network.  An anchored network ensures that all nodes have at least one connection.  

This anchored random network still draws random connections between nodes, however it also checks to ensure that every node is connected to at least one other node.  While this is slightly more predictable than the truly random network, it avoids the disconnected node issue.  The pseudocode below is a version of an anchored Erdos-Renyi scheme.

In order to ensure the network is anchored the first thing this algorithm does is cycle through each node.  It checks to see if that node is connected, by checking to see if it has a degree greater than one.  If so, it selects some random node as the tail of a new link.  If not, it selects the given zero degree node.  After checking each node any additional links are drawn according to the same random procedure above.  This round-robin approach ensures that every room leads somewhere.

The above algorithm still has the issue that it allows for disconnected clusters of nodes.  This means that while all nodes connect to something, it isn't necessarily possible to reach every node from every other node.  There may be two or more groups of nodes that have no connection to each other.  Such a network would represent two adjacent but unconnected dungeons.  The more links that are added the less likely this becomes, but it remains a possible issue with this algorithm.  Solutions to this problem exist, but aren't really worth investigating here.

Small World Networks

In real life it's very rare for connections between anything to be truly random.  It's much more common to find a regular structure that has some partially random nature.  If you take a regular network and then start randomly redrawing some of its links it's possible to substantially shorten the distance between any two nodes.  This is known as the small world effect, and is responsible for the famous six degrees of separation between any two individuals.  Small world behavior isn't just noted in social networks, it appears in urban planning, travel, neural networks, food chains, utility grids, and many other places.  Such networks tend to have clusters of tightly connected nodes, but these clusters are only weakly connected to each other.  It's these weak links that allow for rapid communication between nodes.

One of the first observations of the small world effect came from the "six degrees of separation" experiment.  This test involved letters sent between people in very different locations, using only known acquaintances as intermediaries.  While most social networks are formed by cliques, very tight clusters of nodes, most people also have weak links to other people outside their usual geographic or cultural area.  These weak links turn out to be much more important in allowing groups to communicate.  "Weak links" in this case means distant relations, people you know but don't see on a regular basis.  Such connections create a bridge between groups that don't otherwise communicate much.

Another application appears in urban planning.  Most cities are strongly connected locally, they have a local network of streets that allows easy access from any one location to another within the city.  Travel between cities, however, is limited to a small number of highways.  In this case highways are the weak links which permit travel between the tightly connected city-clusters.  The famous Manhattan grid layout is excellent at allowing transit within the city from any one location to any other, but would be excessively slow on a large scale.  On the other hand highways allow for rapid transit between any two areas, but don't necessarily lead to the exact location someone is trying to reach.

Scale free networks begin as regular networks and are then randomized.  The final network maintains some of its original structure, but the addition of random links makes the final result much more interesting.

This pseudocode describes the Watts-Strogatz method.  In this method we begin with a k-regular network.  Then that network is randomized by cycling through each link and randomly deciding whether or not to rewire that link.  Given a rewiring probability, p, it checks a random number and, depending on whether that number is greater or less than p, it decides whether or not to go ahead, a simple "roll-under" selection technique.

When a link is rewired the algorithm changes that link's destination node to a new one.  Since links in a regular network are connected to one of the next k nodes in line, these rewired links create shortcuts to more distant parts of the dungeon.

Scale Free Networks

Small world networks can be used to produce natural looking networks, but themselves aren't formed naturally.  A planned out building or neighborhood designed to reduce travel time between any two points may resemble a small world, but an unplanned community might instead look like a scale free network.  Scale-free networks tend to have a small number of very important hub nodes and a large number of outlying nodes.  This happens naturally over time, as a handful of locations become increasingly important centers of travel and communication.  A scale-free network grows by slowly adding new nodes and links, instead of following the prescribed structure of a regular network.
Scale free networks are formed by adding new nodes one at a time, instead of starting with a group of nodes and adding links as the previous methods.  When it is added each node draws a set number of new links to the existing nodes.  These new links are drawn in a way that favors the highest degree nodes to receive more new links.  This principle is widely known as "the rich get richer" since the more connections a node has the more likely it is to get more connections.
The decision of how to distribute new links is made using the cumulative distribution function of the degree.  That sounds complicated, but it really isn't.  Every gamer has already encountered the CDF without knowing it.  Cumulative distribution functions are how all die-roll tables work.  For a node, i, the CDF is the degree of all nodes 1 through i, added together and divided by the sum of the degree of all nodes.

If a random number is between the CDF of i and i-1 then we'll select i.  This is exactly the same as any lookup table which tells you to roll a die and then compare to the entries on the table, each entry being valid for a specific range of rolls.  Nodes with very high degree will have a very large range that can be rolled, while nodes with a low degree will have a very small range.
In this case we're deciding based on that roll which node should be the head of the new link we're drawing.  The tail of that link is the new node we just drew.
To draw a scale-free network we start with a certain number of nodes, say 3, and draw links connecting all of them.  So we have a 3-complete graph to start.  Then we add one new node and draw some number of links, k, between that node and the existing nodes.  We decide which nodes to connect the new one to by generating a random number and using the CDF, just like if we rolled a die and based our decision on the result.  Then we keep doing that until all nodes are drawn.  This method is known as the Barabasi-Albert method and is outlined in the psuedocode below:

As we draw new links certain nodes will tend to collect more links than others, which increases their likelihood of attracting yet more links.  However, the random element still allows connections to smaller nodes to form, increasing their importance and their chance at accumulating more links.  Such networks have an underlying order, but not the rigid order of a regular network.  This is where the idea of hubs is extremely useful, as scale-free networks tend to produce a small number of well connected hubs with a large number of satellite nodes attached to them.

This is how most structures slowly develop over time.  While a deliberately planned construction may resemble a small world network, most natural formations will be produced as scale-free networks.  As certain areas see more traffic, whether through trade in a community or the flow of water through a cave system, these areas become increasingly important.  This encourages more and more direct connections to those specific nodes to form, while less important areas are ignored.  As outlying areas become more well connected they also begin to attract new connections from even more distant locations.  Roundabout paths still exist, but most traffic goes through a small collection of hubs.

Using Networks as Dungeons

Now we come to the big question you're doubtless asking: "What is all of this and what does any of it have to do with dungeons?"  You may even have skipped all the preceding sections and jumped down here just to figure out what I'm on about.  At their core networks represent connections between things, with nodes as things and links as the connections between them.  Those could be physical connections, like doors, or social connections or causal connections or temporal connections.

In the case of a physical dungeon nodes would represent different rooms or areas in the dungeon and links would represent the doors or passageways that connect them.  A graph of such a dungeon still functions as a map, in the sense that it tells you how things are connected and how to navigate, but it isn't a useful picture of what the dungeon actually looks like.  Rooms aren't to scale and their relative position isn't obvious.

In some sense that doesn't really matter.  Depending on the nature of the game and the specific challenge, many groups will find that the specifics a room's layout isn't all that important.  Solving a puzzle, navigating traps, or answering a riddle doesn't require the party know all that much about the room itself, which is little more than set dressing.  Even combat encounters can be solved by some groups without an actual area map.  In this case a detailed scale map isn't much more useful than a rough sketch or a bubble diagram.  Players only care what's in the room, not necessarily how big the room is or exactly how it sits in a larger structure.  After all, most players don't care what the building codes in your setting are or exactly how the plumbing is routed through the building.  For many groups a detailed floor plan is just as extraneous as a detailed wiring diagram.
In a game like that all you need is a rough outline of how one encounter leads to the next, and that's what the graphs we're generating here are.  Each node is an encounter and each link is a path from one encounter to the next.  For most adventures a designer would start with a map and then place encounters on it, seeing how areas connect to each other in order to decide how encounters are linked.  Here, though, we're doing the opposite.  We start with the encounters, draw the connections, and then create a dungeon around the encounters.
To get to a dungeon map you would start with the encounter layout and then draw your map to accommodate the links between encounters.  Corridors, rooms, halls, gardens, and whatever else are created as set dressing around the obstacles encountered there.  You size and select each room based on what goes in it, and then draw the rest of the map so that these rooms and areas fit together as prescribed.  In the next entry in this series I'll expand on this, to go from network generation to encounter placement to dungeon generation.

Attachments

I've produced an Excel spreadsheet which generates the networks I just went over in this post and calculates their properties and plots them as described in the previous two posts.  It can produce Complete, Regular, Random, Small World, and Scale Free networks according to the algorithms described above.  The VBA code I've written is not optimized for performance, however, but rather conceptual simplicity.  It should be easy to read but may be slow to run for extremely large networks.

Several details I left out of the above psuedocode are resolved in the VBA script, if you're interested in examining it in more detail.  It is not password protected and I invite you to look through the code and make improvements.  This sheet will allow you to generate asymmetric connections, except on complete and scale free graphs.  In both cases asymmetry makes no sense.

If you aren't interested at all in the details of how the sheet works but are interested in using networks, then you can simply press the "Generate New" button and make a few selections.  VBA will handle everything after you hit "OK" and all you need to worry about is the final graph.

I believe I've tested the script thoroughly and there should be no issues.  Feel free to let me know if you encounter any problems with this script, though.  I'm actively working to get more comfortable with VBA and welcome the input.

gen1.xlsm