Game spaces provide a context for the game's rules and systems, and a space for the game agents to perform mechanics. When we go about designing game spaces, sometimes thinking in pure spatial terms clouds what a designer needs to achieve with a certain game space.
For FPS games, sitting yourself down with your favorite prototyping tool kit and drawing corridors and rooms is a recipe for disaster. It is difficult to design interesting spatial puzzles when you are creating game spaces using the rules of reality. How many office blocks are fun to navigate?
Molecule design is a way of applying graphing theory for concepting and finetuning of various types of game spaces. This rational approach to design is a means to design spaces without thinking about the representational elements of space itself. This article still accepts the importance of planar maps; however, we need better tools to help us create these first.
This article will examine some useful tools gathered from the field of graphing theory that designers can use to conceptualize various game components. The latter half of this article will examine a realworld application of these tools. By doing so, we will examine how iterations of a level design benefited from this abstracted means of realizing space.
Graphing theory is a broad and diverse field of mathematics; however, this article discusses graphs that can explain spatial relationships. Core to graphs that explain spatial relationships are nodes and edges (Figure 1). Nodes can represent game spaces / rooms, pickups, spawn points and AI pathing nodes. Edges define relationships between nodes.
Figure 1
Figure 2 is a simple molecule consisting of several nodes, linked by edges. In this example, we have defined a set of tokens around the players spawn point. This is a literal depiction of space using a graphing approach. Nodes become linked by edges, and these define the shortest possible distance between the player and other node. The more powerful a token is, the longer the edge should become.
This approach works well for PvP games  to create a game space with roughly similar distributions of pickups, to achieve game balance. Repeating and rotating a molecule leads to symmetrical distributions throughout the game space. Edges are abstract ways of defining relationships but not necessarily hallways or any other level geometry. To explain this further, we need to look at weighted and directed graphs.
Figure 2
We can manipulate the physical appearance of our edges to help communicate different types of relationships between the nodes. In Figure 3, the edge between nodes A and C is thicker than the rest. If we are using graphing theory to create spaces, and the nodes represent particular game spaces, then the larger edge does not imply a bigger space between the two nodes, but rather a more direct route.
Figure 3
Figure 4 takes our molecule from Figure 3 and uses weighted edges as a guideline to place out level geometry. In this example, heavy weighted edges create a path between nodes A and C that is direct and unimpeded. Alternatively, the thin edge connecting nodes A and B results in a meandering pathway that is complex in nature. This example shows that edges do not depict geometry, but rather the relationship between nodes.
Figure 4
We can further increase the information that an edge communications by adding direction. Figure 5 is an example of a graph that has directed and weighted edges. Figure 5 uses directed and weighted edges to communicate two different ways to get between node A and node B. The thicker edge is more direct than the other. Linking nodes B and C is an indirect oneway gate. The thick edge linking nodes A and C is another oneway gate. The thickness of this edge shows a direct and unimpeded relationship between the nodes.
Figure 5
Nodes and edges can represent nearly any feature of game level design. For example, we could use a system whereby the weight of the lines also tells us about the difficulty of getting between nodes. By using edges to depict vertical space, we could say that node C is the highest point of the map. Node C is then transitive in the sense that it can only be accessed from node B. The oneway direction between nodes B and C might be achieved by having a "jump pad" at node B, pointing towards node C, but not in the opposite direction. It is really at the discretion of the designer and their team to define a key for their particular molecule system.
To further explain the concept of using spatial molecules to create play spaces, let us consider one example molecule and how it should and should not be implemented. The molecule represented in Figure 6 is a simple spatial molecule that defines a linear level progression, suitable for single player type maps. Weighted edges have not been used in this example; however directed edges have been used to create interesting spatial puzzles.
Figure 6
Figure 7 is an example of what not to do with a spatial molecule. The reason to use a moleculebased approach is to free your creative process from thinking in purely spatial terms, and instead think about creating interesting spatial relationships. Although the planar map in Figure 7 does follow the spatial relationships of the molecule, it is a boring, linear space.
There are also a number of other flaws that demonstrate why designing maps from a planar perspective is problematic. First, the linear, roombyroom layout of the map is a direct product of drawing maps out in planar space. When your imaginative space is twodimensional, your maps will be twodimensional also. As such, there are no interesting vertical spaces and, more importantly, the objective is not clearly visible from the beginning of the map.
Figure 7
James Castile 
15 Jan 2013 at 9:27 am PST

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?





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. 




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 playtesting 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 nonmathematical 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 fractallike 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. :) 








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 indepth 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?





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. 




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?







Max Quin 
Hi Luke this is a very late post but you mentioned this.
"When your imaginative space is twodimensional, your maps will be twodimensional also. As such, there are no interesting vertical spaces and, more importantly, the objective is not clearly visible from the beginning of the map." I'm wondering if you could extrapolate on that. Especially concerning something like a 2D Game, and how that can be made spatially interesting given it is literally twodimensional. Also regarding the visibility of objectives, what is the relavance and importance of this? I'd like to know more I'm intrigued. Also I find it funny that designers arive at similair ideas, I'd always used graph theory and this idea of connections aswell but never formalized it in anyway. Also that's partially because Valve utilized the concept in many of their maps, they called it a 'Bounce' I believe in HL2 where one area connects back to another and creates interesting and flowing spatial arrangements (which makes games more fun). I think by far the best use of connectivity is the mod Minerva: Metastasis, it's no wonder that guy was hired as a Level Designer by Valve. Sorry for blathering on thank you very much for your insightful article and your time. 

