Optimization of Procedurally Generated Planets for Mobile Video Games

Abstract

This post is concerned with the optimal design and development of Procedurally Generated Planetary assets for video games on mobile devices. Successful integration of procedural content for this technology is as yet, a heavily under documented topic. Considering the current focus on mobile platforms as a technological trend, and the implementation of video games with 3D graphics on such platforms, it is only logical to seek optimised approaches to the integration of such systems onto the technology.

The topics discussed here within will focus primarily on the Quad Tree and Noise approach to Procedural Planet Development with a build target of mobile phones in mind. 

• 1. Introduction 5
• 1.1 Procedural Content Generation (PCG) and the Video Games Industry 5
• 1.2 Optimization of PCG for Video Games 5
• 2. Procedural Planet Development 5
• 2.1 Noise Terrain 5
• 2.2 Fractal Terrain 6
• 2.3 Procedural Quad Tree Planets 7
• 3. Optimization for Mobile Devices 9
• 3.1 Issues on mobile 9
• 3.2 Optimization for System Performance 10
• 3.3 Optimization for User Experience 11
• 4. Conclusion 11
• 5. Bibliography 12
• 6. Figures 13
• 7. Glossary 15

1.     Introduction

1.1  Procedural Content Generation (PCG) and the Video Games Industry

Due to a rise in independent video game developments using 3^rd party software for mobile devices (Fig.1, Helgason, 2014), and an industrial focus on on mobile technology, there are increasing opportunities for the implementation of Procedural Content Generation (PCG) in this domain. These techniques allow smaller teams to compete with much larger development studios (Carli, Bevilacqua, Pozzer, & d'Ornellas, 2011) through an automatic, or semi-automatic creation of game assets using computational algorithms. Optimization of such techniques for mobile devices would therefore be beneficial to the video games industry.

Figure 1: David Helgason - Unite Keynote Conference 2014

1.2  Optimization of PCG for Video Games

A common use of PCG in the video games industry is in the formation of computer generated terrains. These can be costly in terms of system performance, such as when using Online, Generate & Test (Togelius, Yannakakis, Stanley, & Brown, 2011, Smith, 2014) variations like Fractal Noise based Adaptive Subdivision within polygonal meshes (Mandlebrot, 1978) (Duchaineau et al, 1997) , discussed later in 2.2. To address this cost on mobile performance, this project will attempt to devise a set of optimized development practices for creating 3D planetary assets on such hardware using the aforementioned procedures. This will be approached by reviewing the development of a Procedural Quad Sphere (PQS) with an embedded Quad Tree node system and fractal levels of detail, for use on Googles Android OS via Unity3D. Furthermore, this post will include considerations on optimal player experience for such an environment as defined in the MDA framework of video games design (Hunicke, LeBlanc, & Zubek, 2004).

2.     Procedural Planet Development

2.1  Noise Terrain

To procedurally generate any graphical environment in computer science, a number of logical operations must be performed in tandem with a random or pseudo-random process. In the field of PCG, this is defined in the paper ‘Search-based Procedural Content Generation: A Taxonomy and Survey (Togelius, Yannakakis, Stanley, & Brown, 2011)’ as either Random Seed or Parameter Vector based. (Togelius, Yannakakis, Stanley, & Brown, 2011). The first definition refers to an input for a mathematical function that outputs values for generated content in a manner that has little to no parameter guidance. The vectors in the second refer to a manually guided trajectory for the procedure to follow using set parameters.

In creating terrain, we must first establish a Parameter Vector that meets certain criteria for its physical properties, such as the height of hills or colour of shading, using a seed value as the parameter. A common approach to this is to use Noise values, varying sequences of numbers derived from the Frequencies and Amplitudes of noise wavelengths (Fig. 2). Wavelengths can be of any dimension and are generated from an initial seed. In 3D examples their resultant values can be spread across the Cartesian world space of iterated generations of vertices forming a 3D mesh (usually quads), hence the term procedural generation (Fig. 3 & 4).

Figure 2: 1D Noise Wavelength & Noise Values

Figure 3: Noise Based Mesh

Figure 4: 2D & 3D Noise

2.2  Fractal Terrain

The effect within the mesh can be improved by using noise waves that simulate the Fractal nature of real world physical properties. A common approach method for this is in the use of Perlin Noise (Fig. 5, See Overleaf), a single wavelength formed of combined wavelengths (Perlin, 1983). A suitable method of using Perlin Noise for terrain is as in music, where each additional wavelength is an Octave higher. An Octave is a repeat wavelength but with double the frequency, known as Lacunacrity between wavelengths. In addition, this frequency change is matched by dividing the amplitude in half. This is known as the Persistance of the wavelength. Lacunacrity and Persistence do not need to be exactly in the power of 2, although it is quite common to do so.

Figure 5: Combined Perlin Wavelength

Using this method means that different levels of detail can be present within meshes, dependent on their vertex intensity. Combinations of other fractal approaches can further be combined to one wavelength for perfecting detail even more (Fig. 6).

Figure 6: Ridged Multi-Fractal

2.3  Procedural Quad Tree Planets

Given a mesh that will contain noise data for terrains, in order to form a planetary sphere we require a topological configuration within the mesh that does not polarize, as seen in many common spherical primitives (Fig. 7). One suitable topology known as a Quad Sphere (Fig. 8), or PQS if produced procedurally, remains consistent with using quads to contain noise data by forming a sphere out of a faceted cube. It is achieved by normalizing each face of the cube toward it’s center.

Figure 7: Polarized Primitive Sphere

Figure 8: Quad Sphere

Additionally, by maintaining quads, we can introduce a Quad Tree to the mesh, a subdivision technique that allows level of detail to be incorporated into geometry, based on the position of a relative object. In context of the project, this allows excellent optimisation of system performace due to rendering high details only where they are required. The idea is that a parent node can divide by 4 into copies of itself, meaning the child nodes also have the power to divide by 4. This process repeated forms divisional branches, hence the use of the word tree. For example if we were to use a 16 x 16 quad, we can divide that quad into equal proportional children due to the power of 2 (Fig. 9). The result across faceted quads create the perfect scenario for including noise terrain on a planet for whichever view of the surface can be seen (Fig. 10). In addition, due to the nature of fractal noise, when combined with the normalization process, the child nodes display deeper and deeper levels of detail. Usually the object used to invoke a branch is the camera itself. Understanding of this system is derived from the work viewed in Kerbal Space Program (Kerbal Space Program – Squad, 2011).

Figure 9: Quad Tree Divisions

Figure 10: Quad Tree on a PQS

A quad tree system used within procedural planet development can be further visualised in figure 11 below.

  

Figure 11: Quad Tree Diagram for Procedural Planets

3.     Optimization for Mobile Devices

3.1  Issues on mobile

A system such as a procedural planet can easily overuse the available resources of a mobile device through not adhering to the constraints of mobile hardware. This may drastically lower framerates or worse, force a system out of memory or bottleneck CPU processes, such as this example in Unity3D when attempting to apply more and more textures to a procedurally generated Quad Tree.

Figure 12: Overloading of Processes through Planet Mismanagement

Furthermore, in attempting to run extensive procedures on mobile without optimization, aesthetic details can suffer loss of quality, hampering the visualization of the asset as an accurate simulation of a planet, as well as the overall user experience, such as this early attempt at reducing system cost.

Figure 13: Lowest Quad Tree Simulation

3.2  Optimization for System Performance

There are a multitude of ways in which the generation process may be improved, especially at the level of the graphics processing itself, however in a video game engine there are several approaches in which a developer may consider performance optimization. These include:

1.      Ensuring that quads within the mesh are of a suitable power of 2 to achieve minimal framerate during subdivision of a node. For example a level 3 (quads of 8 x 8) sphere to remain around a suitable target framerate of 30fps. See 3.3 for testing.

2.      Separating the generation of mesh data from the application to the mesh in order to reduce bottle-necking of the CPU (Fig. 14), especially during Quad Tree based node subdivision. This can be achieved by using a Coroutine method to delay the data applcation and caching of parent nodes as a simple approach (Fig. 15). However this can impair the visual effect if misapplied.

Figure 14: Bottleneck Spike as shown in Unity3D Profiler

Figure 15: Separation of Generation and Application Processes

3.      Setting a custom target frame rate by disabling V-Sync operations and changing the applying a custom float to a targetFrameRate variable. In Unity3D this can easily be applied with the following code:

int customFPSTarget = #;

QualitySettings.vSyncCount = 0;

if (Application.targetFrameRate != customFPSTarget)

   Application.targetFrameRate = customFPSTarget;

3.3  Optimization Testing

 Optimization Test for approach 1: Highest complexity in mesh that can achieve a smooth rate of frames per second during proximity based subdivision.

Overview

Increases in mesh complexity levels will be tested for frames per second (FPS) and process performance as well as VBO size, Mesh MB size and garbage collection allocation to find the most optimal topology that subdivides within 25-35 FPS. Use of cube primitive (labelled ‘Approach Object’) as camera parent with physics based motion used to induce distance and proximity based subdivision process within generated ‘CubeSphere’.

Conditions

CubeSphere	Approach Object
Position: 0, 0, 400 Rotation: 0, 0, 0 Scale: 50, 50, 50 Tested Parent Node: 1 Maximium Quadtree Level: 4	Start Position: 0, 0, 0 (Origin) Rotation: 0, 0, 0 Scale: 1, 1, 1 Approach Speed (C# Class): UnityEngine.Rigidbody.AddForce (transform.forward * 250)

Control Measure = 150 fps Average

System Specification (Available Testing Equipment)

CPU	Intel® Xeon® CPU E5-1620 v2 @ 3.70GHz 3.69 GHz
GPU	Nvidia Quadro K4000 3GB Graphics
RAM	HP 16.0 GB DDR3 (Max: 1066MHz)
Operating System	Windows 8.1 Enterprise 64-bit Operating System, x64-based processor
DirectX Version	DirectX 9
Mobile Handset	Sony Xperia Mobile Phone SP

Orthographic Top View of Testing Environment & Profiler using Unity3D

Results

VPN = Vertices per Node

TPN = Triangles per Node                 

VBO = Vertex Buffer Object

GC Alloc = Garbage Collection Allocation

        Quad Tree division at Levels 1, 2 & 3 are deemed optimal. This refers to cubespheres with a 2x2, 4x4 and 8x8 divide quadtree face.

Table 1: Results

3.3  Optimization for User Experience

In keeping with the MDA Framework of Video Games Design (Hunicke, et al., 2004), a developer must remember that when a procedural planet is packed as part of a product, a user may not share the same perception of that system. For instance, a player may simply see the environment as just the Game Stage (Smith, 2014) and seek play in a Game as Challenge rather than invoking, what would be anticipated, Game as Discovery (Hunicke, et al., 2004).

To counter this, the system must somehow relate to how the player would wish to traverse it. In his PhD Thesis ‘Engineering Emergence: Applied Theory for Games Design’ (Dormans, 2012, 189-190) Joris Dormans contrasts PCG against the notion of Fractal stories discussed by Marie-Laure Ryan in her book ‘Narrative as Virtual Reality: Immersion and Interactivity in Literature and Electronic Media’. He can be quoted:

“Where branching stories build towards different, predesigned endings along pre-designed paths, the fractal story transforms itself to accommodate many different paths that essentially lead towards the same goal” -  (Dormans, 2012)

This refers to designs in narrative in which more and more detail are added dependant on the trajectory through a games Probability Space, the possible states that a game may be in (Adams & Dormans, 2012). In considering Procedural Planets with a Quad Tree system, for each successive division within the terrain, the game state may include, remove, increase or decrease certain resources within a games internal economy, a theoretical construct designed to visualise play flow using numerical values (Dormans, 2012).

4.     Conclusion

The optimizations presented within this document require further research to be considered effective. Furthermore, several other approaches towards procedural planet development currently exist which may render these techniques obsolete, such as the use of Tessellation Shaders to induce LOD rather than scripted Quad Trees. However it can be confidently stated that using third party software to develop procedural content for mobile is a logical direction for any current video game developer. Advancements in technology will push such concepts more and more into the limelight, potentially overriding most other development practices, such as the prototype procedural game play and mechanic software Ludoscope (Dormans, 2012) developed by Joris Dormans. Now is the prime time to get involved.

5.     Bibliography

1. Adams, E. & Dormans, J., 2012. Game Mechanics: Advanced Game Design. Berkeley: New Riders; 1st edition.
2. Carli, D. M. D., Bevilacqua, F., Pozzer, C. T. & d'Ornellas, M. C., 2011. A survey of procedural content generation techniques suitable to game development. Salvador, Institute of Electrical and Electronics Engineers, p. 1.
3. Dormans, J., 2012. PhD Thesis: Engineering Emergence: Applied Theory for Games Design, Amsterdam: Creative Commons.
4. Duchaineau, M. et al., 1997. ROAMing Terrain: Real-time Optimally Adapting Meshes. Los Alamitos, CA, IEEE Computer Society Press, pp. 81-88.
5. Google Android Operating System, 2015. Android. [Online] 
6. Available at: http://www.android.com/
7. Google Open Source Code, 2014. libnoise-dotnet. [Online] 
8. Available at: https://code.google.com/p/libnoise-dotnet/
9. Helgason, D., 2014. Unite Keynote 2014. Seattle, Unity3D.
10. Hunicke, R., LeBlanc, M. & Zubek, R., 2004. MDA: A Formal Approch to Game Design and Game Research. San Jose, CA, AAAI Press.
11. Julia, G., 1918. Mémoire sur l'itération des fonctions rationnelles. Journal de Mathématiques Pures et Appliquées, pp. 47-246.
12. Krieger, D. H., 2014. The Mandlebrot Set, s.l.: MIT, Numberphile.
13. Mandelbrot, B., 1978. MandelbrotSet.. [Online].
14. Member:12pt, 2014. Student Game Dev: C# Voxel Tutorial. [Online] 
15. Available at: http://forum.unity3d.com/threads/tutorial-procedural-meshes-and-voxel-terrain-c.198651/
16. Perlin, K., 1983. m_perlin. [Online] 
17. Available at: http://freespace.virgin.net/hugo.elias/models/m_perlin.htm
18. Ryan, M.-L., 2001. Narrative as Virtual Reality: Immersion and Interactivity in Literature and Electronic Media. New Ed edition (3 Oct 2003) ed. Baltimore, MD: The Johns Hopkins University Press.
19. Smith, G., 2014. Understanding Procedural Content Generation: A Design-Centric Analysis of the Role of PCG in Games. New York, ACM.
20. Squad, 2011. Kerbal Space Program, s.l.: Squad.
21. Togelius, J., Yannakakis, G. N., Stanley, K. O. & Brown, C., 2011. Search-based Procedural Content Generation: A Taxonomy and Survey. Copenhagen, IEEE.

6.     Figures

Figure 1: David Helgason - Unite Keynote Conference 2014 .......................................... 5 

Figure 2: 1D Noise Wavelength & Noise Values ............................................................. 6 

Figure 3: 2D & 3D Noise .................................................................................................. 6 

Figure 4: Noise Based Mesh ............................................................................................. 6 

Figure 5: Combined Perlin Wavelength ........................................................................... 7 

Figure 6: Ridged Multi-Fractal ......................................................................................... 7 

Figure 7: Quad Sphere ...................................................................................................... 7 

Figure 8: Polarized Primitive Sphere ................................................................................ 7 

Figure 9: Quad Tree Divisions .......................................................................................... 8 

Figure 10: Quad Tree on a PQS ........................................................................................ 8 

Figure 11: Quad Tree Diagram for Procedural Planets ..................................................... 8 

Figure 12: Overloading of Processes through Planet Mismanagement ............................ 9 

Figure 13: Low Aesthetic Simulation ............................................................................... 9 

Figure 14: Bottleneck Spike as shown in Unity3D Profiler ........................................... 10 

Figure 15: Separation of Generation and Application Processes .................................... 10 

7.     Glossary

• Adaptive Subdivision – Geometry that can intelligently divide in specific ways under different conditions.
• Arbitrarily Large – In Mathematics, a set of values that increases in magnitude.
• Bounded – In Mathematics, a set of values that are restricted within a range.
• Complex Number – In Mathematics, a number derived from the relative position of an Imaginary Number across the Complex Plane.
• Complex Plane – In Mathematics, a Cartesian Coordinate system contrasting Real Numbers against Imaginary Numbers.
• Fractal – A geometric state in which each part has the same statistical characteristics as the whole.
• Generate & Test – In Procedural Generation, a system that generates data and checks to see if the result has met certain conditions.
• Imaginary Number – In Mathematics, a number that is mathematically impossible.
• MDA Framework – In Video Games Design and standing for Mechanics, Dynamics & Aesthetics, an approach to formally understand the development of a videogame as a single process for determining player experience, rather than individual processes combined together.
• Online – In Procedural Generation, a system that generates data during run time.
• Parameter Vector – In Procedural Generation, a guided method of generating data within method parameters.
• PCG – Standing for Procedural Content Generation, a system that automatically, or semi-automatically creates content for a product.
• Probability Space – The potential states of a game inherited by player trajectory.
• Procedural Quad Sphere (PQS) – In Procedural Generation, a procedurally generated, faceted cube forming a sphere with no geometric poles
• Quad Tree – A method of division that uses nodes that can divide by 4 into repeat nodes with the same divisional properties.
• Random Seed – In Procedural Generation, a generation of values in which a seeded outcome is not guided in any way.
• Real Number – In Mathematics, any number that is mathematically possible.

Emergent Mechanic Design for Video Games with Procedural Content

Abstract

This post is concerned with the optimal design and successful integration of emergent video game mechanics for systems that use Procedural Content Generation (PCG). The topics analyzed here within will provide descriptions and definitions of key approaches to video game design and procedural content generation, through research of specialized taxonomies and frameworks. A critical analysis will also attempt to address distinct correlations between emergent mechanisms in video games and PCG within complexity theory, as well as present logical conclusions and example designs.

Key Terms

Complex Systems, Design Patterns, Game Design, Game Mechanics, Emergence, Progression, Machinations, MDA Framework of Games Design, Procedural Content Generation (PCG).

Contents

1. Introduction.
  1.1 The Structure of Gameplay.
  1.2 Gameplay Optimization.
  1.3 Gameplay and Procedural Content Generation.
2 How can we Accurately Approach Gameplay Design?
  2.1 Game Design Theory as Mechanisms and Frameworks.
  2.2 Gameplay as a Vocabulary.
  2.3 Dynamic Mechanics and Internal Economies.
  2.4 Machinations.
3 How do we Integrate Gameplay Mechanics with PCG?
  3.1 Mechanism Patterns.
  3.2 Game Design Vocabularies for PCG.
  3.3 Order and Chaos.
4 Do Emergent Mechanics and PCG correlate as Complex Systems?
  4.1 On Emergence.
  4.2 Procedural Emergence.
5 Conclusions.
Bibliography

1.     Introduction

 “Emergence thrives somewhere between Order and Chaos” Joris Dormans, 2012

1.1 The Structure of Gameplay

A game in its primordial form is defined by video game scholar Jesper Juul in his paper ‘The Open and the Closed: Games of Emergence and Progression’ as “a small number of rules that combine and yield large numbers of game variations, which the players then design strategies for dealing with” (Juul, 2002). What this refers to is the emergent style of play than can be exemplified in a game of Chess. In Chess, there is a relatively small set of simple rules that when combined, create a very deep and wide pattern of game play states. The pathway that a single game of chess can take between these states is known as the games trajectory through its probability space (Adams & Dormans, 2012). There are by far more trajectories in a game of chess than the original designer could have predicted. This is the primary understanding of emergence in games and is known to yield a high threshold of replayability. Emergence as a study refers to an aspect of Complexity Theory and Complex Systems which will be discussed further within this post.

Games of Emergence differ from Games of Progression however, which is a newer style of play, as first seen within adventure games, and is defined by Juul as a predefined set of actions to be experienced by the player in a sequence, such as a traditional lock and key mechanism. This method allows the designer much more control over the final play experience, but does not yield a high threshold of replayability, as the repeating of tasks can easily become monotonous. In terms of a game’s longevity, this suggests that designs of emergence are the more practical choice. However this concern of monotony can arise in Games of Emergence if a process is out of balance, reducing probabilty space and leading to a particular strategy being more efficient (Adams & Dormans, 2012). This imbalance can be countered using design patterns and frameworks to create mechanisms that feed internal elements back into play, or conclude the game entirely.

1.2 Gameplay Optimization

In game design theory, there exists a set of formalized guidelines that a designer can consider when developing ways of play within a system. This does not mean that the designer should feel in any way restricted, but rather empowered through an aided visualization of play states. These guidelines exist within two frameworks. A computational approach, as seen in Machinations Diagrams (Dormans, 2012), and a more philosophical standing, as seen in the MDA (Mechanics, Dynamics and Aesthetics) framework of video game design (Hunicke, LeBlanc, & Zubek, 2004). Machinations view game elements as resources within an internal economy, whereas the MDA approach considers all aspects of a game’s architecture as emotional inducers to the player. It is important to distinguish between play states as a collection of patterns that culminate a design vocabulary, and the design of such patterns with an optimal player experience in mind. This is what is considered at the core of each of the two frameworks.

1.3 Gameplay and Procedural Content Generation

Procedural Content Generation (PCG) is an area of study in computer science that is concerned with the automatic, or semi-automatic processes of generating content using pre-designed algorithms. Procedural algorithms are not random. They contain mathematical formulae that create a result. This means that the generation can be guided and create content that mimics manual development. In Chris Crawford’s book Chris Crawford on Games Design (Crawford, 2003), it is shown that algorithms can be thought of as data intensive or process intensive. The notion of data intensive programming is more focused on the storing and relocation of bytes within databases, but is performance heavy. Process intensive programming on the other hand is more concerned with formulae, and so more applicable to PCG. These both attribute heavily to the mechanics of progression and emergence (Adams & Dormans, p25, 2012). For games of progression, pre-arranged sequences of stored data are appropriate for the type’s structure. Emergence on the other hand is more associated with the processing of data, and computers are natural processors, able to create complex simulations in real time. Crawford believes all video games should capitalize on this more computationally optimal feature.

Figure 1: Elite, Holdstock 1984

The applications of PCG prove heavily viable for video games, with examples seen as far back as Elite in 1984 (Holdstock, Fig. 1). Elite was a procedurally generated space flight, combat and trading simulator that included hundreds of algorithmically stored, procedural star system simulations. In the paper ‘Search-based Procedural Content Generation: A Taxonomy and Survey (Togelius, Yannakakis, Stanley, & Brown, 2011)’, it is noted that Elite displayed three very distinct benefits of using PCG in video game development.

1. Performance - Elite was able to store large amounts of data within a few tens of kilobytes using small, process ready, numerical values to represent individual planets. These are compressed as formulae until required.
2. Development - The prohibitive expense of manually crafting each game asset. Many titles make use of software such as SpeedTree (Interactive Data Visualization, Inc) that can create vast variations in, and distribution of, vegetation across large open worlds.
3. Advancements in design - PCG presents the possibility of completely new game types, with mechanics designed around generation. If content can be generated with enough variety during play, the concept of a truly endless game experience is a plausibility. (Togelius, Yannakakis, Stanley, & Brown, 2011)..

Figure 2: No Man's Sky, Hello Games

As specified in the third, this technology allows designers to consider re-playability at a much grander scale than can be conceived with traditional designs, through the inclusion of near infinite content (Smith, 2014). In the contemporary video games industry, Sean Murray, the managing director of developer Hello Games has demonstrated a procedural video game universe in their product No Man’s Sky (Hello Games, In development 2014, Fig. 2). In his blog Murray notes that the procedures involved use a 64 bit system (2 to the power of 64) to deliver a ‘seed’ value within its range. This seed in turn is calculated against other values, such as the position of the player in Cartesian space. These calculations define logical parameters that specify attributes for star systems, planets, atmospheric scattering, ecologies, audio wavelengths and much more. This form of parameter based generation is defined as a Parameter Vector in the aforementioned Taxonomy developed by Togelius et al, and will be elaborated further within this post. In numerical terms Murray states that it would take 585 billion years to visit each planet if you could visit one every second (Murray, 2014).

Figure 3: Murray on Emergent Play

It is procedural logic with pre-set formulae that allows for data to be generated and disposed of as players navigate the universe, allowing for a massive probability space, heavily in line with the understanding of emergence. In designing play for a system of this magnitude, Murray further explained during an interview at the PlayStation Experience event (December 2014, Fig. 3) that he intended to use a progressive mechanism as a means of creating structure within gameplay. His system increases the value of concrete resources, such as better performing equipment for the player to use, and abstract resources, such as threat, as the player travels towards the center of the procedural environment. The differences between concrete and abstract resources are distinguished further in this post. In correlation with the works of Deus Ex designer Harvey Smith, in his article ‘The Future of Games Design’ (Smith, 2001) on the need for game systems that focus on player expression, Murray further expresses how the game has been planned as an individual and personal journey. It is formed as a Massively Multiplayer Online Game (MMOG), with players freely exploring the universe in any manner that they see fit. He envisions the trajectory of play between players as “spokes on a wheel” around the center as players form together, although he notes events may not occur in this way, which is the true purpose of the design. Emergent play systems are, from a design perspective, a careful balance between player freedom and the control of the designer (Adams & Dormans, 2012).

In considering game design theory with PCG in mind, video game scholar Gillian Smith proposed a design framework for further developments in her paper ‘Understanding Procedural Content Generation: A Design-Centric Analysis of the Role of PCG in Games’ (Smith, 2014). Smith drew conclusions from the taxonomy of video game PCG proposed by Togelius et al. in their paper and combined them with the player-centric MDA Framework to produce a design focused vocabulary for video games with PCG that prioritises an optimal player experience, which will be discussed further in this paper. However, such existing frameworks, taxonomies and philosophies are yet to fully explore the direct implications and correlations of emergence for such content in specific regard to complexity theory, and so form the focus of this paper. Using applied research, this work will attempt to address the following questions.

1. How can we accurately approach gameplay design?
2. How do we integrate gameplay mechanics with PCG?
3. Do emergent mechanics and PCG correlate as complex systems?

2       How can we Accurately Approach Gameplay Design?

2.1 Game Design Theory as Mechanisms and Frameworks

A video game is often referred to as a state machine (Grünvogel, 2005) (Dormans, 2012).This is defined in the book ‘Game Mechanics: Advanced Game Design’ (Adams & Dormans, 2012) as a hypothetical machine that can exist in different states, with rules that govern how and when the machine should transition between these states. The term mechanics in a gameplay design context refers to theoretical structures used in directing the trajectory of a player’s interactivity through a game’s states, or probability space (Adams & Dormans, 2012).

In the PhD Thesis ‘Engineering Emergence: Applied Theory for Games Design’ by Joris Dormans, intricate combinations between several frameworks, including his own work on Machinations diagrams, are discussed extensively for creating such mechanisms. These frameworks constitute a design vocabulary that empowers designers in their work through an intrinsically focused view of gameplay. Dormans also notes however that “Due to the emergent nature of games it is often impossible to accurately predict the behavior of a game before it is implemented.” (Dormans, 2012).

2.2 Gameplay as a Vocabulary

One such framework that attempts to counter this ‘impossibility’ (of which also is a popular reference within game literature), was established in the paper ‘MDA: A Formal Approach to Game Design and Game Research’ (Hunicke, et al., 2004). MDA refers to Mechanics, Dynamics and Aesthetics. It is described as a formal lens from which to view a video game’s structure and was devised in an effort to unify the different professions found in game development, for the purposes of and optimized end user experience. It promotes a philosophy that each of these fields, such as art, technical staff and creative designers, all at some point have to consider the final experience of a game during development. These different visions combine as the project reaches conclusion, ultimately affecting the overall experience of gameplay, echoing complexity theory.

The approach views a video game as 3 combined components. These are the game rules, the game system, and the emotional experience induced upon players. A design perspective of these components equates to the Mechanics, Dynamics and Aesthetics of a game. The definitions as they appear in the paper are:

Mechanics: describes the particular components of the game, at the level of data representation and algorithms.

Dynamics: describes the run-time behavior of the mechanics acting on player inputs and each other’s outputs over time.

Aesthetics: describes the desirable emotional responses evoked in the player, when she interacts with the game system.

(Hunicke, et al., 2004)

The framework centres on ‘Aesthetics’ as the primary attribute, and expresses that the word gameplay is better replaced by a formal taxonomy to create a vocabulary that can focus more specifically on what experience the game actually delivers during play. The taxonomy as it appears in the paper is as follows:

1. Sensation -Game as sense-pleasure

2. Fantasy -Game as make-believe

3. Narrative -Game as drama

4. Challenge -Game as obstacle course

5. Fellowship- Game as social framework

6. Discovery -Game as uncharted territory

7. Expression -Game as self-discovery

8. Submission -Game as pastime

(Hunicke, et al., 2004)

‘Aesthetics’ are then used to dictate models of play, of which dictate the design of Mechanics and Dynamics for an emotive focused game. This means that the MDA framework focuses heavily on the resulting experience first, allowing the designer to choose which emotions are induced by the game. To clarify how MDA can be used, we can consider a dice roll, the Mechanics would be the roll of the dice to find a chance value, whereas the Dynamics could be how the result of that dice affects the number of movements a player may make in a board game. The design of this system could have stemmed from an intention to induce the Aesthetic of Sensation, such as risk or anticipation.

2.3 Dynamic Mechanics and Internal Economies

Figure 4: Value Probability in Two Standard Die

Using this framework, we can perceive mechanics and dynamics as a collective process that induces a predetermined emotion within a player. The framework paper shows how in board games that use two die for player progression, there is a predetermined probability in the chance value. A value of 7, as show in Fig. 4 (Hunicke, et al., 2004), has the highest chance of being rolled. This probability, by its nature, provides an average speed in which players can move around a game. Using this knowledge we can create dynamic mechanics that visualise game elements and player emotions as concrete or abstract data, forming an internal economy of resources. Resources in video games are defined in the book Game Mechanics: Advanced Game Design (Adams & Dormans, 2012) as any game element that can be defined numerically, and can be envisioned as an economy within a game. Resources can be further defined as:

• Tangible or Intangible
• Tangible resources have a physical presence within the game, such as the trees in the game warcraft (Blizzard Entertainment, 1994), which can be converted into Intangible lumber, which is stored as a numerical value  (Adams & Dormans, 2012).
•  Concrete or abstract
• Concrete resources have a definitive presence within a game where as abstract variations do not. Such as the ghosts in Pacman (Namco, 1980) as a concrete resource and the threat they pose an abstract value, possibly expressed between 1 and 100 (Adams & Dormans, 2012).
• Discrete or Continuous
• Discrete resources exist in states, such as a boolean ‘if/else statement’ within computer programming represented by binary, that can be either true (1) or false (0).  Continous resources concern any transition between states and can be represented as floating point values.

As with any economy, we can consider the dynamics across values using defined economical functions, such as Sources, Drains, Pools, Traders and Converters. A Source in economics is any factor that can create resources, a Drain removes these resources, a Pool  is a place where resources gather, a Trader divides them between other factors, and a Converter changes their type to another (Adams & Dormans, 2012). This understanding of Dynamic Mechanics in an economical structure are what form the basis of a tool to design mechanisms of play known as Machinations (Dormans, 2012).

2.4 Machinations

Figure 7: Play Visualization using Machinations

A game’s internal economy, as with any economy, can be visualised with graphs, charts and diagrams. Machinations, as depicted in the PhD Thesis ‘Engineering Emergence: Applied Theory for Games Design’ (Dormans, 2012) are theoretical constructs by which a designer can visualise the play experience of a game within diagrams of that game’s internal economy. A prime example of this would be a Feedback Mechanism. A closed loop system that is designed to stabilize, or destabilize a certain factor in a system. In a game design context this would equate to creating balanced or unbalanced play through mechanisms that modify the abstract resources of advantage and disadvantage, and feeding them back into the game. In figure 5 (Hunicke, et al., 2004), we can see an example of a Negative Feedback mechanism that stabilises temperature through negatively altering its value. Figure 6 (Hunicke, et al., 2004) shows resource management game Monopoly, where there exists a positive feedback system in which monetary value is increased or decreased further as the game progresses. Figure 7 shows a similar feedback mechanism in a typical resource management video game, such as a real time strategy (RTS). This example uses Machinations to visualize an increase in monetary gain over time, as a player invests in additional workers.

Figure 5: Negative Feedback Mechanism

Figure 6: Positive Feedback Mechanism

Figure 8 shows a more intricate example of how a designer can use Machinations diagrams to visualize gameplay as a whole using the classic videogame Pac-Man (Namco, 1980) (Adams & Dormans, 2012). In the tool itself, these diagrams can run as simulations in in real time, with abstract resources such as threat increasing as more and more as ghosts enter play.

Figure 8: Pac-Man in Machinations

Double lined modules show player interactivity. Solid Arrows show rates in resource motion through a game and dotted arrows represent modifications to the state of these rates and as a consequence, the state of play. This is an extremely accurate approach for aiding the designer to visualize play experiences in video games and can be used in a variety of imaginative ways, such as using Pools and Arrows to simulate Progression or level transition or sources to simulate player’s entering a multiplayer game world.

3       How do we Integrate Gameplay Mechanics with PCG?

3.1 Mechanism Patterns

The concept of design patterns was first introduced in the book A Pattern Language (Alexander, et al., 1977) in an attempt to capture reoccurring patterns in architecture. This work formed the basis of many structural considerations, and of particular use for the structure of programs. In the book Design Patterns: Elements of Reusable Object-Oriented Software, it is discussed how patterns in logical script can be reused as templates for different scripts. Using this as a basis to understand logic in a video game, there are several conclusions that can be made regarding the transition of resources amongst game mechanic systems (See 2.4). In the book Game Mechanics: Advanced Game Design (Adams & Dormans, 2012), several patterns of play are shown within Machinations diagrams. These patterns are found to be reoccurring when simulating many different game mechanics with the tool. They can be pieced together to form more complex systems of gameplay. This also shows how play can be designed in tandem with a game script, or alongside programmers in a MDA (Hunicke, et al., 2004) focused approach (See 2.2). Such patterns are presented by Adams and Dormans and have been evaluated by them as to how they may play a role in gameplay functionality. Example patterns fall under categories such as Engines for a game mechanism, Friction between resources and Escalation across play states. The patterns come in many forms but a few core designs have been determined. Examples include (Adams & Dormans, 2012):

Engines

Figure 9: Engine Patterns in Machinations producing resources

Engines in game design are any mechanism that can generate functionality within in a game, similar to an engine in a vehicle.

(You may notice a similar pattern in the dynamic engine on the right when viewing the example as shown in 2.4)

Friction

Figure 10: Competitive play between by players

An example of multiplayer Friction in a game. This is known as Attrition, whereby attacks on an elements strength weaken its ability to perform.

Escalation

Figure 11: A difficulty curve

A game system that rises in a particular fashion. Learning or difficulty curves can be represented by an escalating pattern.

An example of multi-player Escalation. A positive feedback mechanism for 2 combatants that can upgrade an Abstract resource for offence. This is known as an Arms Race.

Figure 12: An Arms Race between 2 players

3.2 Game Design Vocabularies for PCG

Two very prominent papers are to be considered when designing play for PCG. These are titled ‘Search-based Procedural Content Generation: A Taxonomy and Survey (Togelius, Yannakakis, Stanley, & Brown, 2011)’ and ‘Understanding Procedural Content Generation: A Design-Centric Analysis of the Role of PCG in Games’ (Smith, 2014).

The first of these papers by Togelius et al., describe PCG, for both board and video games, as an Artificial Intelligence (AI) study, concerning the focus of procedural algorithms (see 1.3) to generate content by themselves. Several distinctions are presented in this paper for defining a vocabulary to be considered when creating PCG. The base definitions within the vocabulary are:

• Online vs Offline PCG
• Online refers to content that is generated during runtime of a game, such as the environments and other systems in No Man’s Sky (Hello Games, In development 2014). Offline is generated before runtime such as the maps in Civilization (Meier & Shelley, 1991).
• Necessary vs Optional Content
• Necessary content must be experienced by the player, such as if the game is set within a procedural environment. Optional content can be avoided, such as the weapons exemplified in Borderlands (Gearbox Software, 2009) of which many procedural weapons were not required by the player.
• Random Seed vs Parameter Vector
• Random Seed refers to using random number generators within its logical program, as part of the generation process, such as terrain fluctuations. A Parameter Vector is a guided generation of content through careful direction of the program functions within their parameters.
• Stochastic vs Deterministic Generation
• The word Stochastic is closely related to chance, whereas deterministic can easily be predicted. Similar to the play styles of emergence and progression. These definitions define type of generation produced from Random Seeds and Parameter Vectors.
• Constructive vs Generate and Test
• Constructive refers to content that is only required to be generated once, such as the aforementioned weapons in Borderlands (Gearbox Software, 2009). Generate and Test performs a generation, and then uses additioanl algorithms to test if the content meets certain criteria, such as whether a clear path through generated corridors is present. The process is repeated if the content fails the test.

 (Togelius, et al., 2011)

The second of these papers, by Smith, draws from the taxonomy presented in the first, but through the philosophical lens of game experience as defined within the MDA framework (Hunicke, et al., 2004, See 2.2,). The purpose of the paper is to promote a similar vocabulary for game design and PCG that is more emotionally driven, by focusing on how PCG is aproached from each area within a game development pipeline. This is achieved in the paper through examining the concerns of the programmer, who is responsible for the generator, and the game designer who uses it. How the design of play is transmitted into the generator, is what is of most concern. This vocabulary falls under 4 key categories. These are:

• The Building Blocks
• The way in which the generator produces content.
• The Game Stage
• Online or Offline as defined in the first paper by Togelius et al.
• The Interaction Type
• Whether a player has an impact on the content. This includes no influence, parameterised influence such as altering the parameters of the generator in a UI, as seen in the map options in Civilisation (Meier & Shelley, 1991). There is also Preference that lets the user guide the generator in it’s decisions, and Direct Manipulation where the player can dynamically alter the generator, such as the creature editor in Spore (Maxis, 2008).
• The Player Experience
• Experience in this instance refers to how the generator is received by the player. Some generators may be concerned with directing the emotions of the player and others may simply create seemingly random content that let players interact with the generator in a way they choose.

 (Smith, 2014)

3.3 Order and Chaos

In recent paper by Joris Dormans ‘Making Design Patterns Work’ (Dormans, 2013). Dormans challenges the use of Taxonomies and Frameworks to define gameplay. He expresses that game literature and game development as an industry is heavily divided, and that developers are already able to form definitions in content themselves, and do not require theoretical ones by game scholars. He also states that a Taxonomy can be simplified to just categories of design patterns, and that to make them work we should not simulate initial play ‘ideas and concepts’ with patterns, but rather use them to find solutions to game design problems. He states in the paper:

“In order to make design patterns work it is due time we as academics re-evaluate how we design pattern libraries and to what purpose we design them.” (Dormans, 2013).

In another quote from the same paper he states

“What is more, most designers practically live for the initial generation of ideas at the start of a new project.” (Dormans, 2013)

Game design from concept to product is a hard process to achieve, and Dormans is suggesting that this is a possible future for design tools such as Machinations. What if we was to combine Dormans Machination patterns and PCG to form procedural patterns of play using algorithms? In his PhD Thesis ‘Engineering Emergence: Applied Theory for Games Design’ (Dormans, 2012) Dormans refers to Automated Design Tools and can be quoted:

“Procedural techniques can also be leveraged to automate game design tools!”

He has developed a prototype of this feature known as Ludoscope.

Figure 13: Procedural Game Mechanics using a prototype application called Ludoscope

4       Do Emergent Mechanics and PCG correlate as Complex Systems?

4.1 On Emergence

On considering Emergent design of mechanics, in personal correspondence with Ernest W, Adams, joint author with Dormans on the book ‘Game Mechanics: Advanced Game Design’ (Adams & Dormans, 2012) for the writing of this post, Adams can be quoted on Machinations:

“It is capable of creating emergent game situations by combining different common design patterns: positive and negative feedback loops, stopping mechanisms (also called the law of diminishing returns), arms races, attrition, and so on.” (Adams, 2014)

The use of the word emergence predates its uses in the descriptions of gameplay types by Juul (Dormans, 2012). In the paper by Marcus Christen and Laura Rebecca Franklin ‘The Concept of Emergence in Complexity Science: Finding Coherence between Theory and Practice’ (Christen & Franklin, 2002), emergence is expressed as a central factor in complexity theory and the understanding of complex systems. These are studies of the relationships between individual parts of a system as they produce behavioral patterns within that system and are exemplified everywhere, such as the neurons within the brain or smaller networks within the internet (Bar-Yam, 2002) (Ladyman, et al., 2012).

4.2 Procedural Emergence

These parts in the context of PCG refer the algorithms used to create them. Procedural Emergence has been simulated in the studies of Cellula Automota, with a prime example in the work of John Conway in his Game of Life (Conway, 1970). That uses algorithms to express if cells in an image are black (alive in the his definition) or white (dead) based on the state of neibouring cells. What was of the most note in examples created with the game, was that behavioural patterns emerge at different scales of the image when the simulation was ran. A procedural system is complex and so are mechanics within a game. They can be entwined and designed together using Feedback Loops as an example.

 “All games are systems consisting of many parts that form a complex whole” (Salen & Zimmerman, 2004, 55)

5       Conclusions

Complexity Theory and Emergence are known to be intrinsically linked to Game Theory. This is not Game Design Theory. It is the study of strategic decisions between rational thinking entities, through mathematical models of conflict and cooperation and is extensively linked to economics. Several Nobel Prizes have been presented to game theorists for advancements in the Sciences of Economics. Considering this research, there is a lot of thought that can be attributed to correlations between Internal Economies as detailed in Dormans work and real world economics. Is there room for an emergent, procedural economy in the non-virtual world?

Figure 13: Complex Systems, Binghamton University, 2014 

It is worth noting that currently, the 'indie' market of the contemporary video games industry accounts for 54% of the current mobile gaming market (McKinsey, 2014) due to ease of scope and 3rd party engine availability. The inclusion of procedurally generated content is heavily viable within this domain as the techniques allow smaller development teams to create game play environments that can compete with larger studios. Mobile gaming is a domain within the industry that is growing at a rapid rate, primarily through the rise of interest in video games for mobile devices using 3rd party software engines (Helgason, 2014).

Figure 14: David Helgason on the Mobile Gaming Market

Bibliography

Adams, E. & Dormans, J., 2012. Game Mechanics: Advanced Game Design. Berkeley: New Riders; 1st edition.

Adams, E. W., 2014. Personal Correspondence [Interview] (1 12 2014).

Alexander, C., Silverstein, M. & Ishikawa, S., 1977. A Pattern Language. s.l.:Oxford University Press.

Bar-Yam, Y., 2002. General Features of Complex Systems. Konwledge Management, Organizational Intelligence and Learning, and Complexity, Volume 1.

Binghamton University, 2014. What are Complex Systems. [Online]
Available at: http://binghamton.edu/cx/
[Accessed 12 2014].

Blizzard Entertainment, 1994. Warcraft, s.l.: s.n.

Carli, D. M. D., Bevilacqua, F., Pozzer, C. T. & d'Ornellas, M. C., 2011. A survey of procedural content generation techniques suitable to game development. Salvador, Institute of Electrical and Electronics Engineers, p. 1.

Christen, M. & Franklin, L. R., 2002. The Concept of Emergence in Complexity Science: Finding Coherence between Theory and Practice, New York: Columbia University.

Conway, J., 1970. Game of Life, s.l.: s.n.

Crawford, C., 2003. Chris Crawford on Games Design. 1st Edition ed. San Francisco: New Riders.

Dormans, J., 2012. PhD Thesis: Engineering Emergence: Applied Theory for Games Design, Amsterdam: Creative Commons.

Dormans, J., 2013. Making Design Patterns Work. Port Canaveral, International Conference on the Foundations of Digital Games (formerly known as: GDCSE).

Gamma, E., Helm, R., Johnson, R. & Vlissides, J., 1994. Design Patterns: Elements of Reusable Object-Oriented Software. USA: Addison-Wesley.

Gearbox Software, 2009. Borderlands, s.l.: s.n.

Grünvogel, S. M., 2005. Formal Models and Game Design. The International Journal of Computer Game Research, 5(1), p. 4.

Helgason, D., 2014. Unite Keynote 2014. Seattle, Unity3D.

Hello Games, In development 2014. No Man's Sky, Guilford: s.n.

Holdstock, R., 1984. Elite, s.l.: s.n.

Hunicke, R., LeBlanc, M. & Zubek, R., 2004. MDA: A Formal Approch to Game Design and Game Research. San Jose, CA, AAAI Press.

Juul, J., 2002. The Open and the Closed: Games of Emergence and Progression. Tampere, Tampere University Press.

Ladyman, J., Lambert, J. & Wiesner, K., 2012. What is a complex system. European Journal for Philosophy of Science, 3(1), pp. 2-5.

Magie, E. & Darrow, C., 1933. Monopoly. s.l.:Hasbro, Parker Brothers, Waddingtons.

Meier, S. & Shelley, B., 1991. Civilization, s.l.: s.n.

Murray, S., 2014. Exploring the 18,446,744,073,709,551,616 planets of No Man’s Sky. [Online]
Available at: http://blog.eu.playstation.com/2014/08/26/exploring-18446744073709551616-planets-mans-sky/

Namco, 1980. Pac-Man, s.l.: Midway.

Smith, G., 2014. Understanding Procedural Content Generation: A Design-Centric Analysis of the Role of PCG in Games. New York, ACM.

Smith, H., 2001. The Future of Games Design: Moving Beyond Deus Ex and Other Dated Paradigms. Montreal, Multimedia International Market.

Togelius, J., Yannakakis, G. N., Stanley, K. O. & Brown, C., 2011. Search-based Procedural Content Generation: A Taxonomy and Survey. Copenhagen, IEEE.

Wright, W., 2008. Spore, s.l.: Maxis.