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