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 fine-tuning 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 real-world application of these tools. By doing so, we will examine how iterations of a level design benefited from this abstracted means of realizing space.
The Basics of Graphing
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 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.
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 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.
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 one-way gate. The thick edge linking nodes A and C is another one-way gate. The thickness of this edge shows a direct and unimpeded relationship between the nodes.
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 one-way 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 7 is an example of what not to do with a spatial molecule. The reason to use a molecule-based 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, room-by-room layout of the map is a direct product of drawing maps out in planar space. 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.
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 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 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 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.
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).
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 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.
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.
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 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.
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.
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.
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 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.
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 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.
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.
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.
If we begin to use level geometry to reduce the amount of possible Steiner points, we are beginning to ask much more of the player. By giving them fewer options (Figure 26), we are asking the player to exercise better strategy than the other players on the map. The upside to this is that players who do well in this environment will take much more satisfaction from its successful completion, as they perceive the lack of options to be indicative of a more complex problem. To demonstrate how a reduction in Steiner points relates to increased difficulty, we need look no further than the Steiner tree problem that we see in the lower, east quadrant of the Fallout 3 overworld (see Figure 27.)
Spatial navigation problems in the early parts of Fallout 3 are negotiated via simple spanning trees where you have many possible Steiner points. This is most noticeable in the areas to the south of main Vault as this is the first (and easiest) part of the map that the player is expected to explore. As difficulty increases, though, these Steiner points are vastly reduced; this can be seen in the subway system of DC, which the player encounters later in the main quest of Fallout 3.
A Practical Implementation
So far we have examined the basic principles of graphing theory and applied this to the analysis of a number of commercial examples, but how does graphing theory stack up as a tool to concept game spaces? The following is an example of a practical implementation of the theory of molecule design created by Nassib Azar.
In this example, a molecule concept is tested, implemented, and refined in order to create a balanced, multiplayer space, which despite its simplicity, offers players with a significant amount of interesting strategic possibilities to explore.
The core idea Nassib decided to explore was a map design which had three layers of experience, represented as three concentric circles. The game space is a deathmatch style map within the default game type of Unreal Development Kit. The outer layer comprises low intensity zones designed to "feed" players into the innermost section of the game space.
For the purposes of this design, "intensity" is measured by the amount of players active