Gamasutra: The Art & Business of Making Gamesspacer
The Metrics of Space: Molecule Design
View All     RSS
October 30, 2014
arrowPress Releases
October 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 Article Start Previous Page 2 of 5 Next

Figure 8 is a better implementation of the same spatial molecule. This example treats each node as a "play space" and uses the edges of the molecule to define how these play spaces can interact with each other. Below is a hypothetical playthrough:

In this example, the player starts on a ledge overlooking a valley (node A). Beside them they can see play area F, a large manmade structure towering over the environment. This is the final objective and its size and scale immediately compels the player to wonder how they can get inside the structure. The player notices that the entry to the tower is locked, but they can see another structure in the distance, a large pyramid in section E of the map. The pyramid has a grand entryway that draws the player's attention -- it is the only other major point of interest in the landscape and as such acts to draw the player towards it.

Between their starting point at section A and the pyramid, the player sees a number of obstacles that they need to overcome: a large wall, a bridge with a closed gate and a canyon filled with water. The player has time to survey the landscape from their elevated position and gain situational awareness. From node A the player begins to plan their route.

The player jumps down from the elevated platform of node A -- this is a one way gate. In section B, they need to make their way to the open gate. Initially they will be drawn to the bridge that crosses the canyon, but they soon realize that it is blocked off and can only be open from the other side. Close to the bridge, the player notices that there is a section of rocks which they can use to jump into the river below without taking damage.

Once in the river, they follow it downstream towards a large open section. Here the player finds a set of stairs that will take them up to the plateau containing the pyramid. Once inside the pyramid, there is an underground road which links back to the objective at section F. This road will collapse behind them once they get close to section F so it acts as a one-way gate.

The hidden room, "a", is connected to F and to E, however it is also a one-way gate and can only be accessed from F. The room will flood once entered, causing it to be blocked off from F, and forcing the player back up into section E.

Section F is the objective, and once inside, the player can continue onwards. Note that because section A is a one-way gate and section F is closed off, the player should not be allowed to return back into the open-area space.

Figure 8

Figure 9 is another interpretation of the same molecule, this time using a more traditional room-based approach.

In this playthrough, the player starts in section A, a large room with two doors, one open and one closed. The player goes through the only open door into a large arena section -- B. There is a door in this room, but it is blocked in such a way that the player knows that it is broken and they cannot get through it. Inside B are a number of containers that the player needs to jump between in order to get out of the room.

Above this tall room is a gantry, suspended high above the floor. The player can also see a room overlooking the arena -- section E. The player jumps from container to container, slowly exploring the vertical space. Once they are in the highest position they enter a network of small service tunnels (section C) that gradually descend.

After navigating the tunnels, the player drops down into an outdoor section -- section D. From here, they can go between D and E via the stair. Once inside E, they can cross the suspended bridge that they saw earlier to their objective. On the way to F, they notice a pickup, situated on a container that they previously could not access via section B. If they player decided to jump down onto this container, then they need to backtrack via, B, C, and D.

Figure 9

Figure 8 and Figure 9 demonstrate how creating a planar map based on a molecule can be an excellent way to creatively problem-solve spatial design. This method of concepting forces the designer to create interesting spatial options at the planar map stage of level design. From my own experiences, designing levels starting at the planar stage more often than not leads to boring, linear progressions which are a consequence of trying to create interesting 3D spaces in a purely 2D creative space.

More Advanced Toolsets

Now that the basics of graphing theory have been discussed, it is time to move on examine some of the tools that designers have at fingertips when going about designing game spaces. It is important to note that these are just some of the concepts available for designers. As this article is appropriating some of these ideas, there are instances where it is necessary to deviate from some of the pure mathematical interpretations of these concepts. This article will explore the following graphing concepts:

  • Dominion Theory
  • Steiner Points
  • Spanning Trees

Dominion / Domination Theory

Domination Theory is a way to understand how nodes can have an area of effect (AOE) and how this AOE might overlap with other nodes. This tool is especially useful to analyze your existing maps from the perspective of player experience. Using this method, each node represents "zones of play" and the intensity of play that happens within each space.

This notion of "zones of play" is something that was originally explored during the design of Half-Life and is referred to as "Experiential Density". Experiential Density is a term coined by Valve's designers during the creation of Half-Life. The concept refers to play experience being distance-based, rather than time-based. The basic concept is that a player should always opt-in to the next section of the play experience. They should be given as much time as they need in order to accumulate loot or simply explore before being placed in a situation of high intensity.

Figure 10

Figure 10 is an example taken from Half-Life 2 that demonstrates how dominion theory can be used to promote Experiential Density. In this map, we have three distinct section of high-intensity play represented by nodes, A, B, and C. The area of effect around the nodes is meant to represent the intensity of play in each of these sections. The greater the AOE, the greater the challenge posed to the player.

If we are designing with Experiential Density in mind, then we can use Dominion to ensure that we are not forcing the player into consecutive, high intensity play zones. Quite literally we are looking at molecule design to ensure that we have enough emotional "cool-down" time for the player between zones. I like to think of these cool-down zones as being similar to dynamics in music. In his book The Clarinet and Clarinet Playing, musician and author David Pino sums this notion up well:

Think of it this way: If you look out from the shore upon a great expanse of ocean, you may become very quickly bored. If however the ocean is enlivened by the sudden appearance of an interesting ship, the view is more likely to hold your attention. Similarly, if your view is suddenly filled with hundreds of ships, not any single one of them will hold interest for very long. The same principle holds for the performance of music: If the listener perceives no subtleties he becomes bored; if he detects nothing but subtleties he becomes disorientated and bored... the most important element in any piece of music is its rhythmic flow.

To better demonstrate how Dominion Theory works, let us use the same example from Half-Life 2, but let's intentionally break the Experiential Density (Figure 11). In Figure 11, the overlapping play sections are represented by the overlapping, red AOEs. From a player experience perspective, this is like trying to read a book with no punctuation. The game experience lacks a satisfactory blend of emotional states as the player "detects nothing but subtleties," in Pino's words.

Figure 11

This map, therefore, is a prime candidate to apply dominion theory to in order to solve the problem of Experiential Density. Depending on the amount of cool-down space you wish the player to have you can adjust your rules for "dominion-overlap" to suit. For example, you could remove overlapping nodes from your molecule so there was no-overlap (as per Figure 10) or you could revise your zones of play so that the play intensity is lower, yet more frequent (as in Figure 12).

Figure 12

From a level concepting perspective, Dominion can also be used to define a "spawn exclusion zone" or any other type of "exclusion zone." An exclusion zone can define an area in which something should not happen -- i.e., there should not be an overlap with the dominion of another node. In this application of Dominion Theory, a node can represent a pickup or a player spawn point. The red AOE is therefore a visual representation of the spatial metric that you have decided to use to represent minimum distances to a spawn event.

Figure 13 is an example of using Dominion to define an exclusion zone. The node represents an actual player spawn point, but could be any game token. The red AOE around the node is a visual representation of the minimum distance that another spawn can occur. For example, if we are working within the confines of UDK, then we might say that based on the size of our map, each spawn point must be at least 1024UU away from another if it occupies the same vertical space. The rules of your dominion zones are flexible; however, for this example, the rule is that no other spawns are to happen within the Dominion Zone -- at least from a planar perspective.

Figure 13

Figure 14 is a dominion problem that needs to be resolved. The problem may be a result of overlapping spawns or pickups that are too close. We can remove the overlap in dominion by placing these nodes further apart or by simply using level geometry to mitigate overlap, as in Figure 15.

Figure 14

Figure 15

Article Start Previous Page 2 of 5 Next

Related Jobs

DeNA Studios Canada
DeNA Studios Canada — Vancouver, British Columbia, Canada

Analytical Game Designer
Blizzard Entertainment
Blizzard Entertainment — Irvine, California, United States

Senior User Experience Designer, Irvine
Blizzard Entertainment
Blizzard Entertainment — Irvine, California, United States

Senior User Experience Designer, San Francisco
Avalanche Studios
Avalanche Studios — New York, New York, United States

UI Artist/Designer


James Castile
profile image
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
profile image
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
profile image
That's not one I have ever seen before. I'll take a look and get back to you :)

Raph Koster
profile image
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
profile image
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
profile image
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
profile image
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
profile image
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
profile image
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 ( 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
profile image
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
profile image
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
profile image
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
profile image
Very interesting and worthwhile, thank you for sharing Luke! :)

Frank Washburn
profile image
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
profile image
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
profile image
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
profile image
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
profile image
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
profile image
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
profile image
Great article.

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

Nick Harris
profile image
Exactly my thoughts on reading this article. However, I feel that this "London Underground Map" has no relevance to the automatic creation of interesting maps for a first-person shooter because it fails to represent sight-lines. It really is only a refinement of the old adventure games drawn out on grid, or hex paper for late night Dungeons & Dragons sessions. Leaning out from behind minimal cover for a rapid expert headshot just isn't simply represented here.

The article did make me think about the problem of procedurally generated combat maps though and my initial notion involves pitting AI driven teams against each other on a variety of maps generated for their atmosphere and credibility - i.e. the algorithm's sole concern is the creation of, say, multiple war-torn Beirut-style maps. Due to the inevitable asymmetry to these (as a bunch of ruined streets wouldn't happen to have convenient reflectional symmetry for the purposes of deathmatch balance), you would have to limit your battles to Attrition, Bomb, Conquest, Duel, or Espionage with one team being the attackers and the other attempting to hold onto their defensive position. The game profiler could adjust the equipment, armament, transportation and number of players independently for each team in order to rebalance the game if the defenders used their "hill" (or somesuch topographical, or topological, advantage to their strategic advantage), it could make the attackers more numerous, or allow for fewer 'tickets' on the defenders side, or none: letting them get permanently eliminated by only giving them one life, whilst the attackers drew on a substantial pool of respawn tickets, Alamo style, some of which could be taken by deceased defenders who were tired of being neutral observers.

Another, perhaps more pragmatic course is to leverage User Generated Content, something which has already proven itself with the Halo 3 Forge and over seven million maps made for Little Big Planet.

Lewis Wakeford
profile image
Well no they don't take complex geometry into consideration, but I was thinking they would be the very starting point of generation. So you build a rough plan for the level first with molecule design which just outlines how intense certain areas will be and ensures they are enough calm areas in between. It also specifies the minimum number of exits/entrances to an area and in which general direction they are. Then a different algorithm and/or prefabs are used to generate those areas as mostly self contained challenges.

Max Quin
profile image
Hi Luke this is a very late post but you mentioned this.

"When your imaginative space is two-dimensional, your maps will be two-dimensional 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 two-dimensional. 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.