In part one of this series, “Defining Emergence and Complexity in Video Games”, I tried to define the concepts of complex systems and emergent behavior and how they apply to video games. I also tried to convince you that “emergence” is a good thing in games, and that it is worthwhile to consider designing your games so that there is a chance of “benevolent” emergence to appear. Now it’s time to introduce a number of techniques to assess the possibility and maximize the potential of emergence.

In this article, I will borrow concepts from the field of cellular automata and by studying the correspondence between CAs and video games, I am hoping to draw on the accumulated knowledge about CAs and apply it to the less formalized field of computer game design. The reason why I chose CAs as the source of comparison is the fact that they are probably the simplest constructs capable of clearly displaying emergent behavior (besides some sets of differential equations, but those are not as intuitive).

If you have no idea what Cellular Automata are, you might want to gain some familiarity with CAs before you read on. An introduction to CAs can be found on my website, and a more graphical treatment can be found on the Mathematica home pages.

Here is a short recap of how a cellular automata works:

• We have a lattice of “cells”, and each is connected to its “neighboring cells”
• We initialize each cell to be in one of its “states” randomly at t=0. This is the “initial condition” for the cellular automata.
• At each time t, each cell will read the state of its neighboring cells and that of its own, and calculate a new state using a transfer function, which it then switches to.
• The time counter, t, is increased by one and the circle goes on.
• During this process, interesting patterns of “states” might occur on the lattice. These patterns are assumed to be emergent, because neither the transfer function, nor the lattice, and indeed, neither the initial conditions seem to dictate their appearance. There seems to be no way to “guess” or even “calculate” analytically if a given pattern will emerge, beforehand.

In the following sections I will break down a CA into its functional parts, relate each to an equivalent concept in video games, and discuss how each of these concepts can contribute to emergent patterns that are detectable by players of video games.

1. The Subsystem Grid and Its Relationship to Cellular Automata

The fundamental subsystems of a CA are automatons – units that calculate a function of a number of inputs from their neighboring cells. Below is an example of a 3×3 automaton lattice in a “Von Neumann neighborhood”.

The connectivity of cells is described by a 9×9 “adjacency” matrix as follows:

Where a black cell exist on row I and column j of the lattice, if C(i) and C(j) are “connected”, i.e. they receive inputs from each other and use those inputs, and their own previous state (at t) to calculate their new state (at t+1).

In video games, fundamental sub-systems will consist of groups of functions that calculate one meaningful output from a set of inputs. E.g. in a shooter game, a simple function that calculates the damage to your opponent when you shoot at him might look like this.

ShooterFirePower = Player1.Firepower
VictimArmorRating = Player2.ArmorRating
If (HasLineOfSight(Player1, Player2) = True) then
Player2.Damage = Player1.Firepower / Player2.ArmorRating

The above pseudo-code, if turned into real code with all the necessary checks and event and error handling, would qualify for a game subsystem. Other examples of well-defined subsystems are:

• Line of sight calculation subsystem
• Player Health calculation subsystem
• Environment Collision detection subsystem

Below I have created a breakdown of subsystems for the game Team Fortress 2,

What we have here, just like the connectivity matrix for the CA lattice, is simply a representation of which subsystems are actually connected by design/code. TF2 is a pretty simple, or rather “focused” game, and yet a system breakdown can be pretty complex, as you see!

In this matrix, non-related subsystems, corresponding to the white cells, are filled with 0’s and the black cells are filled with 1’s. The matrix is symmetrical, but that is only because we considered “dependence” of subsystems. We didn’t distinguish between the directions in which the information would flow between subsystems.

For example, we know that in Team Fortress 2 the player avatars’ size depends on the players class (Heavies are big, Scouts are tiny!) but we do not necessarily know, or care, if class determines size, or if it’s the other way round.

Note that there have been experiments with bigger CA neighborhoods, and hexagonal neighborhoods are also interesting, but the fact is that humans are good at recognizing patterns in ordered grids. They are not so good at seeing a pattern, should it emerge, in a jumble of randomly connected points/systems. So, even though using local neighborhoods, in an ordered structure, does not increase emergence, it allows us to “detect” it. What properties should a game sub-system connectivity grid have in order to allow easy distinction of emergence?

2. Subsystem Connectivity Rules

The rules I propose for game subsystem connectivity design, take their merit from the fact that they clearly correspond to the setup in CAs, which in themselves, not only allow for emergent patterns, but also allow for easy detection of emergence. In a simple 2D lattice of cellular automata with a Von Neumann neighborhood (each cell is connected to four immediate neighbors that touch its edges) the total number of connections of each subsystem does not grow as fast as the number of cells within that subsystem. In fact, it grows as fast as the square root of the number of cells. This is easy to see. Consider a single cell. It has 2 x 4 = 8 connections to the rest of the lattice.

Now consider the 5 x 5 lattice as part of a larger lattice as shown below.

As you see, the number of connections of the 5×5 lattice to the rest of the system is 2 x (5 + 5 + 5 + 5) = 40. The number of connections is essentially twice the perimeter of the 5 x 5 lattice, while the number of cells within the lattice portion enclosed in the red box (which we consider a sub-system here) is equal to the area of the lattice which is 5 x 5 = 25. The perimeter will grow slower than the area, and for big-enough subsystems, we can always be sure that the connection front (i.e. the cells that are connected to cells outside the given sub-system) is small compared to the total number of cells within the sub-system. Keeping this fact in mind, here are the rules I propose for the game sub-system connectivity design, in order to increase the possibility of emergent behavior:

Rule 1) Design your systems hierarchically and make the hierarchy visible to the player, i.e. group player-relevant subsystems into larger system clusters.

Above system configuration was not grouped into hierarchies. Neither can the player understand which subsystems are “closer” in the sense that they are more related. Though complex behavior can certainly happen in such systems, it would not “emerge”, i.e. players would not notice it, or think that it is merely a glitch in the convoluted game mechanics.

The above configuration was designed hierarchically (related subsystems have the same color) but the hierarchy (which corresponds to the special arrangement and gives players a sense of how “near” features are to each other) was not communicated to the player. Detecting emerging patterns in this sort of system is very hard.

Rule 2) Small clusters of subsystems should be strongly connected.

This diagram shows hierarchically-designed, but very “loosely” connected clusters of subsystem clusters. The clusters (defined by the cell colors) themselves, are loosely connected, which ignores Rule 2. This sort of configuration does not allow for a lot of complexity or emergence with simple transfer rules.

Rule 3) The connection fronts between each two small clusters, i.e. the cells within each cluster that are part of the interconnection, should be few, but strongly connected.

This diagram shows hierarchically-designed, but very “loosely” connected clusters of subsystem clusters. The clusters (defined by the cell colors) themselves, are highly connected, and though there might be signs of local complexity, the loose connections between the clusters will limit emergence on a more global scale.

This image shows a hierarchically-designed system, but the connection fronts between sub-system clusters are large, and the number of interconnections between clusters, though allowing for emergence to “happen” will make its detection hard for the player.

Above system follows all the rules of system design that allows for emergence. As you can see each cluster is highly connected. Additionally, the design is hierarchical, and clusters of relevant subsystems are communicated to the player. The “connection fronts” between clusters (e.g. cells 2 & 4 in the blue cluster, and 6, 5 & 10 in the red cluster) are small, but highly connected in themselves.

3. Connectivity Analysis of TF2

Having talked about the theory, let’s have a look at the subsystem connectivity matrix of TF2. In order to obtain the image below, I have used UCINET(c) to convert my connectivity matrix to the UCS format, and NetDraw(c), to visualize and analyze the resulting connection graph. Both programs are free and originally intended as social network analysis and visualization tools.

In the first diagram, I grouped together (spatially and by color) subsystems that, I as a player would relate closely to each other. As you see, the overall system looks highly connected, but there are no distinguishable “connection fronts” within the clusters, and the clusters themselves are not internally more “connected” than the overall system.

Next, the subsystems were spatially re-arranged to reflect how close features are to each other. Features that are “closer” to each other and form localities have a larger number of connections amongst them. The size of each node defines the degree of “betweenness” of the node, i.e. the number of paths passing through them. It is easy to see, e.g. how closely related the enemies’ weapon selection in to the life of a player’s buddy (a turret made by the engineer player, or a teammate healed by the doctor player)

In the next diagram NetDraw has divided the system into five “factions” and colored the cells accordingly. “Factions” are clusters of subsystems that are highly interconnected and are constructed so that the “interface” (number of connections) between individual factions is as small as possible. Interestingly, some features that seem not to be directly related are in the same faction nevertheless, e.g. “Enemy class” and “teleports”.

As you can see by comparing the first and last diagrams, there is some similarity between the clustering of subsystems, even though the first clustering was done by hand and with knowledge of the design and the last was done automatically by calculating five factions, e.g. in both cases a large number of player- or enemy-related subsystems have been bunched together. It is also interesting to see that almost all environment-related subsystems have been grouped together in the last diagram.

Having analyzed the subsystems in TF2, it is time to answer the question: does the design of TF2, at least as far as it is related to the interconnections of its subsystems allow for emergence? And the answer, derived from applying our three rules, is YES, but the emergence does not necessarily come from the interaction within subsystem clusters that the player might expect. The high number of connections, and the fact that we have localized factions that are highly connected, encourages us to think that TF2, at least when looking at its “grid” design, can allow for emergent gameplay. This is a good thing, and not every game design will boast this property. Remember, that all of these statement can be made, without ever having player the game itself! Our analysis is merely based on the subsystem interactions out of which the game mechanics are constructed.

4. How to Choose your Subsystem States

Having tried our hand at designing the connectivity of our game sub-systems, we can turn our attention to the state variables within each of these subsystems. A state variable is the

resulting value that is calculated at the end of a cycle from all the inputs from other sub-systems. This value can be a single Boolean value (e.g. Is the player alive or dead?), an array of values (e.g. the agro list for an NPC character in an MMO) or it can be as complex as a relational database (which can be used for an inter-object messaging system in large scale MMOs).

Contrary to games, where each single subsystem, has its very own state variable(s) which might or might not be of similar types, in a CA, all cells have the same simple type of state variable. Though states are mostly Boolean, there are examples of cells with more than two states, and even if many of those “extra” states are only treated as a way to record the history of the original state change, it is certainly possible to imagine CA’s with many more states. The problem here, is that as state types become more and more complex, visibility of the overall behavior suffers. It is

a lot easier to follow the shifting of black and white dots on a Game of Life grid, than to follow the changes across a huge number of different state variable types in a game, but there are still some general pointers we can take away from our knowledge of CAs. I will list dome of them, in the hopes that the parallels will be obvious enough, not to require a separate explanation:

Rule 4) Transition between any two values should be possible, even if it requires some specific inputs/transition rules.

As an over-simplified example, following this rule, perma-death would be considered anti-emergent design, as it allows for the transition from alive to dead, but not vice-versa. This rule is taken into account in almost any CA that shows emergent behaviors, as each cell can transition from 1 to 0 and 0 to 1 under “death” and “birth” conditions. These transitions are so vital, that sometimes CA rules are written out in terms of their states, and neighbors required for “birth” and “survival” (i.e. not dying!).

Rule 5) Keep “history states”, or rather break them down into a logical sequence of states. These are states that change, even if the inputs to the CA do not change in a time cycle.

This will allow players more time (i.e. more time cycles) to take note of the change that is happening and it is done in many CA’s, including the “Star Wars Rule”. You can download “Visions of Chaos” and experiment with this rule by increasing and decreasing the number of “history” states.

The game equivalent of keeping “history states”, is to have several states of decay for your characters. E.g. if a player is hit badly, they can go into injured mode where they cannot move. Then, if not helped, they will go into incapacitated mode, where they can’t shoot anymore. If their

buddies keep ignoring them, after some time, they will go into a coma, from which they still might be saved, but all they can do is see the battlefield (from above…). Ignore them again, and they are gone. Note that if the input to the death system does not change, the state still changes over time. This is what I mean by keeping histories, and it is a great way to allow the players some time to find emerging patterns in your system. Don’t forget, “emergent” patterns only exist because someone is perceiving them!

You can see the effect of “history states” in making emerging patterns visible below. Both CAs are running the “Starwars” rule for 200 epochs. The first CA is using 3 states (1 of them a history state) and the second is using 10 states for each cell (where 8 are history states). In CAs, as with frienships, the more history you got, the better!

“Starwars” CA with 3 states (1 memory state)

Same CA rules with 10 states (8 memory states)

5. Transfer Functions

Transfer functions describe the relationship between the state variable values at T+1 and T in a networked system. The transfer function can give the player’s position based on user input and prior position, or provide a formula for calculating a “berserking” buff, based on how many enemies the player has killed in the past 10 seconds. below, I will present a few rules that should be followed if you don’t want to stymie emergence in your game.

Rule 6) Avoid linearity in your transfer functions.

Here I define “linearity” as the ability to write out the state of a cell at T+1 as a linear function of its state, and the state of its neighboring cells at T. E.g. if we define the value of a cell in terms of the state variables of its Von Neumann neighborhood as:

Here we have a linear relationship. As the relationship doesn’t change over time, the values for the state variables will most probably either blow up (i.e. go to infinity) or saturate(all cells reach the ceiling value) or die out (i.e. all cells go to zero). Periodic behavior is possible too, but that’s as complex as it gets. These cellular automata can be represented by a matrix and if that matrix has a non-zero determinant, the automata will be invertible, which means you can go back in time from any given state, and always calculate previous states from the current one (something that is impossible, e.g. in the Game of Life automata).

Let’s forego the mathematical jargon for a moment, and try to describe transfer function linearity is in terms of games.  If you can arrive at the next state from the current one via a simple linear calculation, you are dealing with a linear transfer function, and this should immediately ring an alarm with you, as it has the potential to reduce the overall emergence in your system. For example, it is easy to see how it’s a bad idea to make the amount of damage mitigation a player has simply the added sum of all mitigations from gear he is currently wearing, without any multipliers or dependencies on other systems such as player level, damage type, buffs, etc., however, linearity, even in its purely mathematical definition can pop up in places we don’t expect it.

Imagine an FPS game, with a completely empty and flat playfield, and a player who can move across it at constant velocity. Here, the position of the moving player at any time is a linear function of his last position and the velocity vector of the movement. This kind of design is obviously bad, and not many designers would defend it, but I brought it up to see how we can add elements of non-linearity to our little empty playfield:

a) Add teleport/jump pads with randomized destinations: Because the next location of a player who steps onto these pads, will be picked randomly, it isn’t a linear function of the current location or speed anymore.

b) Add acceleration to the player’s movement, which will add a second order term to your position formula for T+1, thus breaking linearity.

c) Add obstacles, vertical drops, flows, etc. to your level. Streams of water that drag you along, as well as drops from higher up points to lower points on the map help to further break the linearity. Obstacles, set limits on where the player can go, thus they change the linear calculation of Pos(T+1) into a piecewise and bounded formula, essentially attenuating its true linearity.

Linearity, helps simplify mathematical and engineering problems, but turns out to be a deal-breaker for complex systems. Most systems that we encounter, even on the lowest rungs of life (as an example of a complex system) for example, are highly non-linear: A few molecules of an enzyme can catalyze a huge number of chemical interactions and tilt the balance of materials within a cell. The same is true about slight changes in energy inflow in the complex system of the Earth’s climate e.g., which can amount to the difference between barren deserts and tropical rain forests.

Even though overall complexity depends on many factors outside the transfer function, it is always a good idea to “seed” the system with a few non-linear state relationships. Voting processes (you get a huge buff if you have all pieces in a set of armor), cut-offs (the boss monster gains healing abilities at 50% of his health), higher-power relationships (the boss will gain x amount of life and mana if he inflicts x amount of damage on a raid party) and randomness (the teleport pad will teleport you randomly to any one of three points in a level) all work well as such seeds, when used in the right amounts.

Rule 7) Avoid Transfer functions that have a high probability of “saturation”

Saturation can be defined as a condition where most or all cells are stuck in one state only, and have a low or zero probability of exiting that state. The main culprits in creating this situation are badly set up initial conditions (e.g. starting out with an all-zero grid in the Game of Life CA) or transfer functions that favor a specific state very highly. It is hard to separate the effects of initial conditions and a badly selected transfer function that have been addressed in this rule, but generally, if the transfer functions are not mapping too many states to specific output states, any random initial patterns should result in dynamic changes that do not die out or stabilize in a short duration of time. The examples below show two cases of badly chosen transfer function in a 2D CA.

In this CA which has completely stabilized into the above pattern, a “0” cell will only turn “1” if it has exactly seven neighbors. As the probability of this happening is generally low for almost any random starting pattern, the CA is stuck in this sparse pattern.

In this CA, a “live” cell will “survive” if it has any number of neighbors from two to six (i.e. 5 out of the total 9 possibilities). This clearly is a cause for “overcrowding” and the CA above is stuck in the overcrowded configuration.

6. Helping Players Detect Emergent Patterns

Emergence, like the metaphorical falling tree, if not observed, isn’t really emergence. In games, as in any other complex system, we rely on the intelligent observer to surmise the emergence of a new pattern in the “whole” that was not implied by the “part”. Here I try to offer a few loose design guidelines to make this detection process easier for your players.

Rule 8 ) Eliminate “noise” in your designs

Any rule that makes a very particular exception to the general rules in your system can be considered noise. A good sample is when a system designer adds a clause to block players from stacking the effects of two very specific buffs.

Designers add these rules for the very important reason that without them the game might simply blow up (or become extremely unbalanced in the case of an MMO e.g.), but if you find yourself in a high noise/system ratio it is time to redesign your entire rule-set, because more noise, will hide the true functions in the system, thus masking any emergence that might be conceivable. Note that I’m not claiming that “noise” reduces the chance of emergence, it merely veils its existence from the player, who will perceive that emergent behavior just as more noise amidst chaos.

Rule 9) Limit the number of differing states each cell/subsystem can have

Observing patterns in simples “states” is easier. The more “digital” your state is, the better. E.g. limit the levels by which your character can grow to say 10, or 20. In this way, not only does each level become significant, the interactions between the leveling system, allows for easier recognition of emergent patterns. “Analog” values should really be avoided, unless changes in them affect other systems step-wise. Increasing the life of players by 0.3123% for the duration of 6:41 minutes whenever they consume a “Potion of rather high vitality” is a bad idea.

Rule 10) Allow for emergent UI behavior

If a player decides to have a water element buff (blue icon) and a fire element buff (red icon) on them at the same time, maybe the particle that is playing on them should be a mixture of those colors (e.g. purple). If the visual elements of the GUI are calculated from the game mechanics, they get the potential to be systems in themselves, furthering the overall complexity, but also making emergence very recognizable.

Rule 11) Try to mimic existing emergent systems

One easy way to create emergent behavior is to try and mimic systems around us. Any creative use of physics or sound can lead to lots of emergent gameplay. Twigs breaking under your feet an alarming a near-by enemy of your presence, Water hiding your trail so the beast hunting you will loose your scent, and mines that stick on the wall, but can also be used to scale walls, are all examples of emergent gameplay- the result of attempts to model the world around us within our games. This not only gives you a head start in creating actual emergence, but also helps the player detect those behaviors by mapping them unto something they already have experience with.

To sum up, though the eleven rules outlined in this article may seem mechanistic and hard to apply within a framework of game design, I hope that they will at the very least provide a minimal set of guidelines in designing game systems that are required to display some degree of emergence. This article is a work in progress, and I will try to add useful examples (from actual, or proposed games) for every rule outlined above. As always, comments and help with examples from actual games that enhance the strength or falsify any of the rules I proposed are certainly welcome.