The answer is obviously yes and those are rhetorical questions. Otherwise this would be a very short post. Still, we have to introduce a little more theory and a few more new ideas before we get there. In the last post we were looking at the whole network but in this post we'll find information about individual nodes. We'll start talking about individual nodes and what properties the network as a whole gives them.
That sounds a little odd at first. How can the dungeon as a whole give an individual room some characteristics? Naturally, it turns out. It should seem obvious that the layout of a dungeon decides which rooms are most traveled and which are least traveled. A room that connects to many other rooms should see more traffic than a small closet with only one door, after all. By the same token a room that is near the center of the dungeon and serves as a connection between many other rooms should also get more traffic than one far removed from the beaten path. These two ideas are both accounted for in network science by the degree and radius of a node.
Degree is simply a measure of how many other nodes are connected to the given node. In a dungeon that means how many rooms the party can reach from the room they are in. Degree refers to leaving, not entering, a node. So if there is a one-way connection it counts only for the room it heads from, not the room in heads to. In short, a room's degree is the number of doors leading out of that node.
A node's radius is a measure of how far away it is from all other nodes. It is the maximum number of steps from that node to any other node. Or just the maximum of its row in the distance matrix. The higher a room's radius is the more removed it is from the rest of the dungeon.
Let's take another look at the five room dungeon. In this graph all rooms share symmetric connections (doors swing both ways) except for room three. This room forces the party to backtrack and head back to room one. Both the link into and out of node three are one-way links.
If we wanted we could find the radius and degree of each node in this graph. It's easy enough on this graph to do by hand, but why? A computer can solve these problems much more easily. Expanding on the spreadsheet from the previous post the radius and degree of each node is:
| 3 | 1 |
| 2 | 3 |
| 4 | 1 |
| 2 | 2 |
| 3 | 1 |
| Radius | Degree |
As we might expect node two looks like the "most important" node here. It leads to three other nodes and is a short number of hops from any other room in the dungeon. The node that has the highest degree is called the "hub" of a graph. It's the most well connected node in that graph, or the room that has the most doors in the dungeon. The node with the smallest radius is the "center" of the graph, it is the closest to all other nodes.
The diameter of a graph is the largest radius and the centrality is the smallest radius. No room can ever be further removed from any other room than the diameter. In this dungeon the two most removed rooms are 3 and 5, it takes four steps to get from one to the other. Centrality is really a measure of how well connected the center node is. A smaller centrality indicates a more connected center. Very disconnected graphs might still require many steps to go from the center to very distant nodes. We could also imagine a dungeon with a center room that connects to all other rooms.
Already you can spot a problem with taking too much for granted here. I've been acting like room 2 is the center this whole time without addressing the fact that room 4 has the same radius. A computer told to find the center would return whichever was first in the lineup, regardless of how many other nodes might have the same radius or degree. This is worth keeping in mind.
I should also point out here that, because of how I've defined radius and degree, it's easy to confuse a computer. Imagine if these were all one-way connections leading forwards. Then node 5 would have a radius and degree of zero, since it leads nowhere. It would be easy to confuse a computer into thinking this room is the "center" of the dungeon, even though we can see that it isn't, because it technically does have the smallest radius. While there are ways around the problem they're well beyond what we need right now. For symmetric links this issue vanishes entirely, and it's pretty clear that most doors in a dungeon should be two-way connections.
With names like "hub" and "center" it's reasonable to expect that these rooms should be important in the dungeon. Here, of course, we know that room two is important, it's where the party must decide which of two possible paths they are going to take. Any path through the dungeon must pass through this room.
This is the first indication we've had of something really useful coming out of all this, the ability to work that last statement backwards. Sure, knowing exactly how far removed two rooms are is handy, but now we can actually turn that into a means of describing individual rooms. From a simple web of rooms and doors we start to understand which rooms might be important and which might not. More than just a collection of nodes, now we're starting to describe rooms. It's still a long way removed from a playable adventure, but it's something.
Let's return to Level One of the Legend of Zelda. In the graph below the center is noted by a red number and the hub by yellow highlight. You'll see that two nodes both have the "most" links leading out of them, rooms 8 and 5 both have four doors. So both of these rooms are highlighted.
This type of graph is known as a circle plot. In this graph all nodes are evenly spread around the circumference of a circle. Links between them are represented by connecting lines. This graph is relatively straightforward and easy to read, as long as most nodes only connect to a handful of other, nearby, nodes. It can get very messy for very connected graphs, with many connections intersecting near the middle of the graph.
We can spread the nodes out by drawing them along concentric circles based on their radii. So all radius 1 nodes share an innermost circle, all radius 2 nodes a circle outside that, all radius 3 nodes a larger circle, and so on. Evenly spacing nodes along each of these circles spreads the nodes out. The same network represented in this way:
This method shows more central nodes closer to the center of the graph and more distant nodes at the extreme edges. While potentially more intuitive it also leads to many crossing lines which may be more confusing to read. The circle plot will tend to show clusters of nodes easily (assuming they are all close to the same number) while the radial plot will show the relative distance of all nodes from the center.
Neither of these plots is really a map of the dungeon. They are just computer generated methods of showing how the nodes are connected. By presenting both I hope that at least one proves easy to use and understand. What's most important here is that we can start with a matrix and produce a graph and that graph highlights critical nodes. From there a creative soul can make a map which connects all the numbered encounters in a similar manner to the graph.
There's the real trick, and the next post will address different types of network and how they can be generated.
In addition to the circle and radial plots described above the attached sheets also produce something called a spectral plot. This graphs nodes based on the eigenvectors of a matrix which is derived from a combination of the degree and adjacency matrices. I haven't bothered going into detail about this method here since the derivation is well beyond the intended scope of this post. For those interested in graph theory, it is derived from this paper: Drawing Graphs by Eigenvectors: Theory and Practice. Like the radial and circular plots I add this method in the hopes that one or more graphs will be easy to read, however since this method is prone to errors with asymmetric matrices the spectral plot may also produce useless graphs if the matrix has many one-way links. The presence of identical or similar eigenvectors can also lead to nodes being drawn on top of each other.
Already you can spot a problem with taking too much for granted here. I've been acting like room 2 is the center this whole time without addressing the fact that room 4 has the same radius. A computer told to find the center would return whichever was first in the lineup, regardless of how many other nodes might have the same radius or degree. This is worth keeping in mind.
I should also point out here that, because of how I've defined radius and degree, it's easy to confuse a computer. Imagine if these were all one-way connections leading forwards. Then node 5 would have a radius and degree of zero, since it leads nowhere. It would be easy to confuse a computer into thinking this room is the "center" of the dungeon, even though we can see that it isn't, because it technically does have the smallest radius. While there are ways around the problem they're well beyond what we need right now. For symmetric links this issue vanishes entirely, and it's pretty clear that most doors in a dungeon should be two-way connections.
With names like "hub" and "center" it's reasonable to expect that these rooms should be important in the dungeon. Here, of course, we know that room two is important, it's where the party must decide which of two possible paths they are going to take. Any path through the dungeon must pass through this room.
This is the first indication we've had of something really useful coming out of all this, the ability to work that last statement backwards. Sure, knowing exactly how far removed two rooms are is handy, but now we can actually turn that into a means of describing individual rooms. From a simple web of rooms and doors we start to understand which rooms might be important and which might not. More than just a collection of nodes, now we're starting to describe rooms. It's still a long way removed from a playable adventure, but it's something.
Let's return to Level One of the Legend of Zelda. In the graph below the center is noted by a red number and the hub by yellow highlight. You'll see that two nodes both have the "most" links leading out of them, rooms 8 and 5 both have four doors. So both of these rooms are highlighted.
We can spread the nodes out by drawing them along concentric circles based on their radii. So all radius 1 nodes share an innermost circle, all radius 2 nodes a circle outside that, all radius 3 nodes a larger circle, and so on. Evenly spacing nodes along each of these circles spreads the nodes out. The same network represented in this way:
Neither of these plots is really a map of the dungeon. They are just computer generated methods of showing how the nodes are connected. By presenting both I hope that at least one proves easy to use and understand. What's most important here is that we can start with a matrix and produce a graph and that graph highlights critical nodes. From there a creative soul can make a map which connects all the numbered encounters in a similar manner to the graph.
There's the real trick, and the next post will address different types of network and how they can be generated.
In addition to the circle and radial plots described above the attached sheets also produce something called a spectral plot. This graphs nodes based on the eigenvectors of a matrix which is derived from a combination of the degree and adjacency matrices. I haven't bothered going into detail about this method here since the derivation is well beyond the intended scope of this post. For those interested in graph theory, it is derived from this paper: Drawing Graphs by Eigenvectors: Theory and Practice. Like the radial and circular plots I add this method in the hopes that one or more graphs will be easy to read, however since this method is prone to errors with asymmetric matrices the spectral plot may also produce useless graphs if the matrix has many one-way links. The presence of identical or similar eigenvectors can also lead to nodes being drawn on top of each other.
No comments:
Post a Comment