Monday 20 June 2016

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 3rd 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 dierent, predesigned endings along pre-designed paths, the fractal story transforms itself to accommodate many dierent 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.
  • BoundedIn 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 PlaneIn 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 NumberIn 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 NumberIn Mathematics, any number that is mathematically possible.