The Metrics of Space: Molecule Design
July 30, 2014
Press Releases
July 30, 2014
PR Newswire
View All

If you enjoy reading this site, you might also want to check out these UBM Tech sites:

The Metrics of Space: Molecule Design

January 15, 2013 Page 3 of 5

It is important though to use common sense when implementing Domination Theory. Once you start to add in level geometry, you are adding another layer of complexity to your designs that will call for revising some of your rules.

Figure 16

In this example, Figure 16, I have used the spawn exclusion system to spread spawn locations in an asymmetric environment. One thing to note is that spawn point 3 has been intentionally moved further away from spawns 1 and 2.

The reason for this is due to the fact that spawns 1 and 2 have fewer approach vectors -- i.e. the player can see any oncoming enemy in their view frustum upon spawn. Spawn point 3, on the other hand, has a wide arc of approach vectors which the player cannot possibly cover within the same view frustum, hence the need to compensate by moving it further away from the other spawn points.

You can apply this same spawn exclusion system to other pickups -- the more powerful the pickup, the larger the spawn exclusion should be. As mentioned earlier though, level geometry and other factors such as pickups and the player's ability to move within the game space will necessitate the use of more sophisticated analytical tools -- namely Spanning Trees and Steiner Points.

# Using Graphing Theory to Understand Player Choice and Strategy

All game levels provide some type of spatial problem-solving puzzle. These puzzles take a number of forms, but one type of puzzle which can be improved via the application of graphing theory are puzzles relating to optimum movement strategies seen in all well-designed deathmatch style maps.

Players thrive on choice; however, too much choice can be just as bad as too little choice. Further to this, players take great pride in achieving victories via the execution of "good" strategic choices. So far we have used graphing theory to examine the construction of play spaces; however, graphing theory is especially useful when we examine our level designs with human cunning and strategy as our primary concern. The principles of Steiner trees, spanning trees, and maximum and minimum cutting are integral to understanding these human factors.

Figure 17

Figure 17 is an example of a hypothetical level. Each node, designated A-H, represents a different type of play space, and each edge represents how many different ways a player can move from space to space. Note that each edge does not represent a corridor, but rather the player's options. The length of the edge is short or long based on how complex that particular route is -- i.e., the longer an edge, the more time it should take to use that option. In the case of Figure 17, each space (node) has between three to five different options for the player to consider when exploring the space. The graph also communicates how the player needs to move through spaces in order to traverse the map.

Figure 18

Spanning trees can be used to define the most optimal connection of nodes in a graph. This tool can also be useful when we are trying to understand player behavior in a map and look for aspects of the design that may be unfair or unbalanced. We can use spanning trees such as those seen in Figure 18 to help disperse item pickups, define spawn points, and place level geometry to help counteract any significantly overpowered (OP) movement strategies that might emerge in a PvP map.

Although mapping out specific permutations of the optimal movement strategy for a level is a good way to start defining your play spaces, it is essential that we give further consideration for players' desire to exercise cunning and emergence. A good example of this point is considering the pride that people (not just players) take in identifying shortcuts. A shortcut is a set of strategic choices that sit outside of the norm. Players will look for opportunities like this in any game environment and their discovery and exploitation of this can be very satisfying on an emotional level. A great way of planning for an understanding this behavior comes from the theory of Steiner trees.

A Steiner tree is a type of spatial problem that looks for the shortest interconnection between a number of nodes. The example that Raph Koster gives in his "Games are Math" presentation is a good way to understand the application of Steiner trees in games. In his presentation, Koster states "If you have three nodes and you need to create the shortest possible route between them, what is the shortest amount of edges required?" Koster states that most people will answer something similar to Figure 19.

Figure 19

The answer to this problem is slightly more devious, as it requires adding another node in the puzzle -- a Steiner point. Via introducing the Steiner point in Figure 20, we have created the most optimal solution to this puzzle. Steiner points and the edges that they create can be treated just like any other type of graph. In the context of games, we can use weighted and directed edges to help define how a Steiner point might be a height element of a map or may be another one-way gate, like a teleporter or jump pad.

Figure 20

A Steiner Point is a shortcut. It is that element of a level's design that players will seek out in order to exploit. The secret for level designers is to make the Steiner points in your map seem less obvious than the spanning tree routes. Borderlands is a good example of this. Within the maps, spanning tree paths are clearly defined and for the most part, appear as clearly defined paths and gantries.

Steiner points exist within the game in the form of height elements which allow the player to skip large sections of the spanning trees by jumping down to certain parts of the map, therefore avoiding large path traversal. Krom's Canyon in Borderlands is just one example where the player can jump down from raised platforms to quickly move to another point in the map, therefore creating a Steiner point (see Figure 21).

Figure 21

Figure 22 (taken from Krom's Canyon above) is an example of how spanning trees and Steiner points work from a level design perspective. In this example, in order for the player to get from node A to node F, they must enact a spanning tree solution. This relationship is represented in the level design by a set of gradually ascending platforms which are interconnected via bridges. A number of bonus items are implemented in this section of the map via Steiner points.

Figure 22

In Figure 23, two Steiner points have been added. Although there are actually several other Steiner points in this spatial molecule, these nodes are pickups placed on high platforms, only accessible from the nodes above them. As such, not only are these considered to be Steiner points as they offer the player a shortcut, but they are important points of interest for the player that allow them to explore the environment as a spatial puzzle.

Figure 23

Figure 24 expands this particular section of play into an even more defined molecule and adds two other major Steiner nodes that show how the player can traverse the space when they are either ascending or descending.

Figure 24

Now that we have taken a look at how Steiner points operate from a spatial puzzle perspective, lets revisit our spanning tree molecule originally introduced in Figure 17. If we applied Steiner points to link nodes in close proximity, then we would have something similar to what is seen in Figure 25.

Figure 25

These Steiner nodes could take many forms. They could be teleporters, actual level geometry, or even height elements that allow for faster path traversal. Figure 25 shows how many Steiner points we could possibly have in this spatial design. According to Koster, too many Steiner points are bad for human players, because you have provided so much opportunity; there really isn't much scope to exercise what I like to call "skillful strategy." Basically, there is no pleasure to be derived from creating shortcuts in this environment because there are so many of them.

Figure 26

Page 3 of 5

### Related Jobs

2K — Novato, California, United States
[07.29.14]

Level Architect
Respawn Entertainment — San Fernando Valley, California, United States
[07.29.14]

Senior Systems Designer
The Digital Animation and Visual Effects School — Orlando, Florida, United States
[07.29.14]

Instructor - Video Game Asset Production
Big Fish Games — Seattle, Washington, United States
[07.29.14]

Game Engineer

 James Castile
 Don't mind me. I'm still only half way through my first coffee... A valuable perspective to have in the tool bag. Thank you. :cheers:

 Simon Ludgate
Random thought, but when I saw that map on page 4 of this article, I instantly thought of the arena layout on page 4 of Yureka chapter 204 (a Korean Manhua). I wonder how that fictional layout would survive under your analysis?

 Luke McMillan
 That's not one I have ever seen before. I'll take a look and get back to you :)

 Raph Koster
Love love love. :)

As a note on further research, there is a good case to be made for the idea that a given dominion space can have a formal, quantifiable difficulty rating assigned to it based on metrics and completion rates -- in fact, multiple axes of analysis could give playstyle differentiators as well. With that, you could at a minimum get a good way to assess your levels' difficulty, and given sufficient data and some AI programming, even in theory build agents that can tell you that same info without needing to spend playtesters on it.

I am fairly sure some of those ideas, as well as some of those in the article, were presented by Andrew McLennan at GDC a few years ago.

 Luke McMillan
 Thanks for the kind words Raph - it means a lot! I have been taking an interest in some of the 3D engineering applications and how they are used to model and analyze thermal dynamics; specifically things like exhaust flow and heat distributions. I would really like to try and see if game levels can be analyzed in the same way, basically simulating what would happen under "normal" conditions and leaving the play testers for the emergent stuff :) I'll be sure to write a follow-up to this if when I figure out how to do this!

 Raymond Ortgiesen
 Excellent article. It's refreshing to see talk about the technical aspect of level design rather than just discussing environment art and spatial relations. Both are important but I think you've helped develop an area that is woefully under studied by most level designers.

 Daneel Filimonov
 This really is an awesome article! I love the fact that you can visualize the gameplay and flow of a level without wasting valuable time play-testing every single revision when all you need is just a pen and some paper (and some patience)! This has opened a new avenue for me when designing levels, thanks Luke! :)

 Kenneth Blaney
You've played it fast and loose with the math and notation of graph theory, but it is all in service of a larger point aimed at a non-mathematical audience so it is forgivable. If you are interested in fleshing this out more in a significantly more concrete and rigorous way I could recommend a few texts for you. (Teaching math and being strict about people's use of language in math proofs is my day job. Please pardon me if that came off rude in any way.)

I'm not sure if they are aware of it, but the development of Portal 2 heavily depended on the type of level design you are working with here. Specifically, they created individual levels with the idea that certain areas would be linked (either physically or just visually). The advantage they gained by designing
They then used portals to link the areas together. The final step in the level design was to stitch the various pieces together, add bridging geometry where appropriate and remove the portals.

I'm currently working on a project for which I've taken a similar level design strategy as what you mention here. That is, using directed graphs that represent the moment to moment player experience (and not just the level geometry). We too are working in UDK and I've found extensive use of the UTPortal class for this purpose. The directed graphs have been helpful to estimate player performance within a setting thus defining a good baseline for some of the goals and game balance issues well before testing has begun.

Finally, this method lends itself to a fractal-like expansion fairly readily. That is, since each of your nodes is representative of a player experience, it follows that the entire graph is representative of a larger player experience. Those larger player experiences can then, just as easily, be linked in a directed graph. If you were really clever, you could then force a certain consistency to the experience of your game by having the large experience graph be similar to the smaller experience graph which in turn is similar to an instantaneous experience graph. I recently did a study of Cyan's "Myst" along these lines which I would be happy to share with you if you are interested in doing some follow up to this.

This is way too long a response, but you hit upon a combination of subjects I'm intensely interested in. :)

 Luke McMillan
 Hi Kenneth, thanks for reply. In regards to the math - accessibility of these models was really high on my agenda. Plus, I rely on Jesse Schell's 10th rule of what game designers need to know about math and probability :) What you mention in regards to your UDK project sounds really interesting. One of my students (http://www.gamenbrain.com/) who used this model created a recursive space death match map. What I really like about it is for all intensive purposes it is a single, arena space. But as you mentioned, the portal class in UDK allows this space to be much, much more. I'll add more of a reply when I get a chance to use a real keyboard!

 Luke McMillan
 Actually, there was a section from this article which I needed to cut because I couldn't concisely explain it's application. I was discussing node distribution based on Voronoi Diagrams & Delaunay Triangulation. If you know of a good layman's explanation for Delaunay triangulation and how it can be used for better node distribution then I would love to hear your thoughts.

 Kenneth Blaney
 If you want to talk about triangulation I'm not sure if there is anyway to get around talking about the circumcircle of a triangle. That said most people will follow you if you tell them that any three points not in a line forms a unique circle (the visual explanation of which would be to show that you can draw two circles with 0 points in common, 1 point in common or 2 points in common, but 3 just won't happen). You might then want to suggest that a designer will want to place nodes and edges that try to obey the Delaunay condition: when you scribe the circumcircles no nodes end up inside of a circle. This sort of goes in with what you were saying about the edge lengths earlier in the paper which confused me earlier. That is, normally in graph theory we don't care too much about edge lengths, however in computational geometry we do. (More properly, computational geometry falls into computer science, but we are being interdisciplinary here so I'll step a little bit out of my comfort zone.) If the length of an edge represents something like the difficulty of an area in the level setting up a graph this way will help balance the experience. A graph that obeys the Delaunay condition will have a property that all of its triangles will tend towards equilateral (it maximizes the minimum angle of the triangles and the maximum value the smallest angle can have is 60 degrees, which only happens in the equilateral case) and so avoid stretched triangles. Avoiding stretched triangles minimizes long edges, which in turn minimizes inequity in paths through a level. If an area of the game is too hard and optional, players will quickly learn to avoid that area unless you make it worth the time. (For instance, speed runners of Super Metroid always avoid Spore Spawn because killing it takes a long time and it gives a useless reward. So that miniboss would be represented by a long edge and a fairly unattractive node if we were to create a graph of Super Metroid.) That said, there is nothing to prevent a good designer from breaking this rule and creating a truly grueling set of paths if the game design allows for it. (Example there could be the purely optional Red Knight in the first level of Demon's Souls.) As I'm sure you know because you grouped them, calculating a Voronoi diagram is functionally similar to confirming that a graph obeys Delaunay. That is, connect the centers of the circumcircles you drew and then, where necessary, bisect the outer edge of the triangle (much easier to explain with a drawing). Now, the only thing that springs to mind about how a Voronoi diagram would be useful for level design would be it would start to inform you where level geometry might need to go to restrict player movement and more clearly define the zones of play from your Half-Life 2 example. You can see that Valve did this to an extent by using bridges, tunnels, curved roads and water giving you your figure 12 from figure 11. That said, this feels a little more like something you'd end up doing to fix problems with the pacing of the map after the fact. I'd be interested to hear more about how you use Voronoi diagrams in level design. I really don't understand it at a deep enough level to do anything great with it.

 Elif Bugdaycioglu
 I'm not designing a PvP game right now, but you gave me a whole new vision to use a modified molecular design in a single player adventure game! Thanks for this thorough article. :)

 David OConnor
 Very interesting and worthwhile, thank you for sharing Luke! :)

 Frank Washburn
Excellent article. Do you have any caveats for designing level flow for a game that is literally in 2D space, like a metroidvania? Trying to keep in mind verticality is obviously very helpful for the in-depth examples you've listed, but mentally I'm having a difficult time trying to avoid any of these "linear, boring level traps" that you illustrated. Any notable examples of games and levels in 2D games that would you say use this kind of methodology in a 2D plane?

 Raymond Ortgiesen
 It sounds like using nodes to represent major areas of the world, then distributing nodes that represent each of the types of pick ups you get and mapping where those allow you to go and where you can't go would be really helpful for establishing the flow of that type of game. In a way the items functions as gates or keys and you could represent that using the molecule.

 Luke McMillan
Thanks for the comments Frank. In one of the lectures I do about this topic, I apply the methodology to Sonic the Hedgehog II from an analytical perspective to examine the level layout and the notion of public vs. private spaces. I have the materials in lecture format so it is no problem for me to put together a quick blog post.

In regards to games which do this well in 2D space one comes immediately to mind however I haven't played it in about 10 years so I might be remembering it to be better than it was! The game is Another World. It was a really slow paced platformer with rotoscoped animations. The game makes good use of the space by not using scrolling. Instead, each section of the level is represented in a new window. The game space is classified as "Adjacent spaces displayed one room at a time" (Mark Wolf - The Medium of the Video Game).

What is cool about Another world is that each screen is not a node, but rather contains several spatial nodes. For instance, you might be in one screen with two levels, but there is no way to get to the other level in the screen you are currently in. This means that you will need to go to other screens and figure out the spatial relationships for your self. The game play is largely based around this concept, especially in the later levels.

Raymond is also on the money. According to Koster, humans are pattern recognition monsters! We get great pleasure from discovering patterns and using them to preempt risk & reward scenarios. This is why I really like the molecule approach because it immediately lends itself to this human desire.

 Frank Washburn
 Thanks for the thoughtful response Luke. I haven't heard of Another World but I will surely have to look it up. If you were to put together a blog post about public vs. private spaces I would be eager to see what you came up with! Looking forward to any more of your analyses! :)

 Axel Cholewa
 Excellent article on a very interesting topic! But I have one little problem with the AOEs and their possible overlap in figs. 10+. The AOE you defined to represent "intensity of play". Meaning, the bigger the circle, the more intense the challenge. But this means that, when you combine it with a physical map like in the HF2 maps, the overlap of AOE doesn't mean anything. The radius of the circle is a measure of play intensity, while the distance between the circles is a measure of physical distance. You can just draw smaller circles without changing their meaning, because you can anyway only compare the AOEs with each other, but not with the edges. Of course, if you use the AOE (as you probably did here) to show the actual, physical areas of activity (maybe that would be a good name for it: AOA), then your method works. I hope I made myself clear :)

 Axel Cholewa
 Oh, and since your using an abstract method, you can also use this in completely different areas. For example, a game like FTL doesn't have much level design, but it contains challenges which can be represented by graphs. Teachers could use a method like this to design exercises for their students, with the edges representing the time it takes for a student to go from one problem to next (if they have a choice).

 Robert Casey
 Great article.

 Lewis Wakeford
Awesome article. I wonder, has anyone tried incorporating these theories into procedural level generation?

 Nick Harris