From the early steps of the video game industry, one of the main problems was the reduced amount of memory available. Techniques were devised to the automatic generation of game levels from a small set of data. One of the first use cases emerged in the 80’s, with a game called Elite – a spacecraft simulator which offered eight galaxies, each containing 256 planets and their space stations – all this being generated procedurally. Many other titles have emerged over time, from the highly acclaimed Diablo, to the Elder Scrolls saga games (such as Oblivion and Skyrim). This solution has been pushed forward to include also the whole characters’ generation, as in the game Spore.
Procedural Content Generation is the term that describes a methodology that produces content automatically, or with minimum manually intervention, through techniques, computer algorithms and a certain degree of randomness. The first approaches on procedural generation began with the mathematician Benoît Mandelbrot, with the fractal geometry [Man83] to describe a family of shapes, which, when following some pattern repeatedly, could result in more complex shapes. This process is based on an iterative and recursive approach, also the basis of formal grammars, such as L-Systems [PL96] and shape grammars [Sti80]. Formal grammars control the evolution of the iterative process of modelling, from an initial “seed”, by using a set of production rules. These techniques are specified with a strong emphasis in the process, and not on the result, being difficult to parameterize in order to obtain the required result. More recently, approaches such as through 3D manipulators [KK12] that provide a visual representation of adjustable parameters directly in model space, or by employing visualization in the form of a node-based system [Pat12; SMBC13], improved expressiveness. Search-based procedural content generation is a special case of the generate-and-test approach to PCG, not only relying on evolutionary algorithms, but on all forms of heuristic and stochastic search/optimisation algorithms [TYSB11].
Procedural content generation is often used in the three-dimensional modelling of real-world features such as terrain elevation, natural organisms and urban environments. The correct understanding of how these processes actually take place, how they are organised and how they influence each other is one of the foundations of PCG techniques. The terrains can be generated randomly from fractal geometry (like Perlin noise) or physical erosion simulation. But we can also use data from Digital Elevation Models (DEM) to reproduce real places accurately. Vegetation and ecosystems are quite complex and have a random look that is prone to the PCG techniques. L-Systems [PL96] have been used with great results, both for the modelling of plants, the interaction between plants in ecosystems and to simulate artificial techniques such as pruning, leading to very realistic landscapes. Road networks are also an important element of the urban landscape. The network shape of this component was initially approached with L-systems as well, but to be able to control it more efficiently, other techniques were proposed, based on tensor fields [CEW*08] or the civil engineering rules that govern the construction process [CLC15]. The buildings are one of the most characteristic components of urban environments and, although the first attempts using L-Systems presented good results, it become clear the necessity to evolve it integrating the concept of shape [Sty80]. This led to the development of split grammars [WWSR03] first, and CGA shape grammars [MWH*06] later on. Other techniques were based on using images for generating the façades of the buildings or to capture the rules that can generate them [MZWvG07]. Finally, since all of these elements are integrated, semantics have also been explored into modelling the whole virtual environment in an integrated mode [STKB11].
Besides the modelling of the game worlds, there are other game elements that can be generated.Game levels can be generated automatically, by putting together small segments, controlled by a grammar defined by the game designer [SWM*11]. Game levels can also be dynamically generated in order to adapt to the players profile [LTB12]. Procedural Audio [Far07] can generate sounds and music in real-time according to the definition of processes and rules dependent on the gameplay, this way enhancing the players’ experience by providing distinct moods and audio cues. The narrative can also be procedurally generated [NAM06; War09] and even characters and their behaviour can evolve and adapt to the storyline (specially in multiplayer games) by using Artificial Intelligence (AI) techniques [MM06]. At a higher level, PCG can be used to drive the players’ experience [YT11].
Yet, PCG still faces some challenges. Attempting to reduce the manual intervention of the users, by providing declarative and high-level means to generate content, ends up restricting their descriptive power. Many approaches rely on building rules using lower-level grammars but they can be difficult to manage, especially for large sets of rules and for more complex designs. When reproducing real-world urban environments, PCG can benefit from the integration of external data sources (GIS, photographs or texts) that carry semantics. However, these heterogeneous sources imply that specific rules have to be designed.
PCG has an enormous potential to SG for the modelling of realistic game worlds (ex. for situated learning), and for the generation of game levels and narratives according to the purpose of the game. A basic framework can be adapted to distinct learning objectives in the scope of a diversity of courses. Besides, by using game analytics, we can adapt the progression of the learner/player by generating the game levels accordingly, into adaptive gameplay solutions.
In conclusion, PCG techniques enable SG teams to develop complex and extensive game worlds, with a lower budget and with reduced time to market. Furthermore, the potential to generate game levels dynamically allows the development of adaptive games, leveraging the potential to broaden the target market and audiences.
António Fernando Coelho is Assistant Professor at the Department of Informatics Engineering of the Faculty of Engineering of the University of Porto where he teaches in the areas of Computer Graphics, Programming and Digital Games. He is the director of the Doctoral Program in Digital Media at the University of Porto and member of the Board of advisors of the UT Austin | Portugal Program.
António Fernando Coelho is also a senior researcher at INESC TEC, having completed his PhD thesis in 2006 at the Faculty of Engineering of University of Porto, in the area of Computer Graphics. His research interests are focused in the areas of Computer Graphics, Serious Games and Geospatial Systems.
[CEW*08] Chen G., Esch G., Wonka, P, Müller P., Zhang E.: Interactive procedural street modeling. In ACM Transactions on Graphics (TOG). Vol. 27. No. 3. ACM, 2008.[CLC15] Campos C., Leitão J. M., Coelho, A.: Integrated Modeling of Road Environments for Driving Simulation. In International Conference on Computer Graphics Theory and Applications (GRAPP 2015), Berlin, Germany, 2015.
[Far07] Farnell A.: An introduction to procedural audio and its application in computer games. In Audio Mostly Conference, pp. 1-31, 2007.
[KK12] Krecklau L, Kobbelt L.: Interactive modeling by procedural high-level primitives. In Computers & Graphics 36.5 (Aug. 2012), pp. 376–386. 2012.
[LTB12] Lopes R., Tutenel T., Bidarra R.: Using gameplay semantics to procedurally generate player-matching game worlds. Proceedings of PCG 2012 – Workshop on Procedural Content Generation for Games, co-located with the Seventh International Conference on the Foundations of Digital Games, 29 May-1 June, Raleigh, NC, 2012.
[Man83] Mandelbrot B. B.: The fractal geometry of nature. Macmillan, 1983.
[MM06] Merrick K., Maher M. L.: Motivated reinforcement learning for non-player characters in persistent computer game worlds. In Proceedings of the 2006 ACM SIGCHI international conference on Advances in computer entertainment technology (ACE ’06). ACM, New York, NY, USA, 2006.
[MWH*06] Müller P., Wonka P., Haegler S., Ulmer A., van Gool L.: Procedural Modeling of Buildings. Volume 25. 3. Boston, Massachusetts: ACM, pp. 614-623, 2006.
[MZWvG07] Müller P., Zeng G., Wonka P., van Gool L.: Imagebased Procedural Modeling of Facades. In ACM Transactions on Graphics (TOG). Vol. 26. No. 3. ACM, 2007.
[NAM06] Nelson M. J., Ashmore C., Mateas M.: Authoring an interactive narrative with declarative optimization-based drama management. In AIIDE, pp. 127-129, 2006.[Pat12] Patow, P.: User-Friendly Graph Editing for Procedural Modeling of Buildings. In IEEE Computer Graphics and Applications, (April 2012), pp. 66-75, 2012.
[PL96] Prusinkiewicz P., Lindenmayer A.: The Algorithmic Beauty of Plants. Springer-Verlag, 1996.
[SMBC13] Silva P., Müller P., Bidarra, R., Coelho, A.: Node-Based Shape Grammar Representation and Editing. Proceedings of PCG 2013 – Workshop on Procedural Content Generation for Games, co-located with the Eigth International Conference on the Foundations of Digital Games, 14–17 May, Chania, Crete, Greece, 2013, pp. 1-8.
[Sti80] Stiny, G.: Introduction to shape and shape grammars. In Environment and Planning B 7.3, pp. 343–351, 1980.
[STKB11] Smelik RM, Tutenel T, de Kraker KJ and Bidarra R (2010) A declarative approach to procedural modeling of virtual worlds. In Computers and Graphics 35(2), pp. 352-363, 2011.
[SWM*11] Smith G., Whitehead J., Mateas M., Treanor M., March J., Cha M.: Launchpad: A rhythm-based level generator for 2-d platformers. In Computational Intelligence and AI in Games, IEEE Transactions on, 3(1), pp. 1-16, 2011.
[TYSB11] Togelius J., Yannakakis G. N., Stanley K. O., Browne C.: Search-Based Procedural Content Generation: A Taxonomy and Survey. In IEEE Transactions on Computational Intelligence and AI in Games, Vol. 3, No. 3, September, pp. 172-186, 2011.
[War09] Wardrip-Fruin N.: Expressive Process. Cambridge, MA: MIT Press, 2009.[WWSR03] Wonka P., Wimmer M., Sillion F., Ribarsky W.: Instant architecture. In ACM SIGGRAPH 2003 Papers. Volume 22. 3. San Diego, California: ACM, pp. 669–677, 2003.
[YT11] Yannakakis G. N., Togelius J.: Experience-driven procedural content generation. In Affective Computing, IEEE Transactions on 2.3, 147-161, 2011.