A literature review of Empirical Evidence on Procedural Content Generation in Game-Related Implementation <s> Game Model <s> We show that novel, linear game levels can be created using n-grams that have been trained on a corpus of existing levels. The method is fast and simple, and produces levels that are recognisably in the same style as those in the corpus that it has been trained on. We use Super Mario Bros. as an example domain, and use a selection of the levels from the original game as a training corpus. We treat Mario levels as a left-to-right sequence of vertical level slices, allowing us to perform level generation in a setting with some formal similarities to n-gram-based text generation and music generation. In empirical results, we investigate the effects of corpus size and n (sequence length). While the applicability of the method might seem limited to the relatively narrow domain of 2D games, we argue that many games in effect have linear levels and n-grams could be used to good effect, given that a suitable alphabet can be found. <s> BIB001 </s> A literature review of Empirical Evidence on Procedural Content Generation in Game-Related Implementation <s> Game Model <s> Abstract This paper presents a procedural content generation (PCG) method that is able to generate aesthetic maps for a real-time strategy game. The maps were characterized based on either their geometrical properties or their topological measures (obtained in this latter case from the sphere-of-influence graph induced by each map). Using these features, a distance function between maps can be defined. This function is used in turn to determine how close/far each map generated by the PCG method (a self-adaptive evolutionary algorithm) is to a collection of maps which were taken initially to be aesthetic or non-aesthetic. This correspondence guided a multi-objective evolutionary approach whereby maps close to aesthetic maps and far to non-aesthetic maps are sought. Self-organizing maps are used to ascertain whether the so-generated maps naturally cluster together with aesthetic maps, as well as to provide a qualitative assessment of the ability of each set of features to characterize the latter. <s> BIB002 </s> A literature review of Empirical Evidence on Procedural Content Generation in Game-Related Implementation <s> Game Model <s> Using procedural narrative generation in video games provides a flexible way to extend game play and provide more depth to the game world at low cost to the developers. Current examples of narrative generation in commercial games, however, tend to be simplistic, resulting in repetitive and uninteresting stories. In this paper, we develop a system for narrative generation using a context-aware graph-rewriting framework. We use a graph representation of the game world to create narratives which reflect and modify the current world state. Using a novel set of metrics to evaluate narrative quality, we validate our approach by comparing our generated narratives to other procedurally generated stories, as well as to authored narratives from commercially successful and critically praised games. The results show that our narratives compare favorably to the authored narratives. Our metrics provide a new approach to narrative analysis, and our system provides a unique and practical approach to story generation. <s> BIB003 </s> A literature review of Empirical Evidence on Procedural Content Generation in Game-Related Implementation <s> Game Model <s> Balancing a game is a long process and relies mainly on subjective feedback from human testers and selective interpretation from game developers. As a first step for completely automate game balancing, we propose a methodology to algorithmically choose features and calibrate their parameters for the procedural level generation of a simple runner game based on testers' feedback.This methodology is used in a 30 seconds game demo with survey and each playthrough is recorded and fed to a reinforcement learning algorithm. We show that the average fun grade steadily grows, proving the effectiveness of the proposed method. The collected data can be further analysed for insights on new features and other major changes. <s> BIB004 </s> A literature review of Empirical Evidence on Procedural Content Generation in Game-Related Implementation <s> Game Model <s> In the present work, we tackle the issue of designing, prototyping and testing a general-purpose automated level editor for platform video games. Beside relieving level designers from the burden of repetitive work, Procedural Content Generation can be exploited for optimizing the development process, increasing re-playability, adapting games to specific audiences, and enabling new games mechanics. The tool proposed in this paper is aimed at producing levels that are both playable and fun. At the same time, it should guarantee maximum freedom to the level designer, and suggest corrections functional to the quality of the player experience. <s> BIB005 </s> A literature review of Empirical Evidence on Procedural Content Generation in Game-Related Implementation <s> Game Model <s> Procedural content generation (PCG) has recently become one of the hottest topics in computational intelligence and AI game research. While some substantial progress has been made in this area, there are still several challenges ranging from content evaluation to personalized content generation. In this paper, we present a novel PCG framework based on machine learning, named learning-based procedure content generation (LBPCG), to tackle a number of challenging problems. By exploring and exploiting information gained in game development and public player test, our framework can generate robust content adaptable to end-user or target players on-line with minimal interruption to their gameplay experience. As the data-driven methodology is emphasized in our framework, we develop learning-based enabling techniques to implement the various models required in our framework. For a proof of concept, we have developed a prototype based on the classic open source first-person shooter game, Quake. Simulation results suggest that our framework is promising in generating quality content. <s> BIB006 </s> A literature review of Empirical Evidence on Procedural Content Generation in Game-Related Implementation <s> Game Model <s> A long-term goal of game design research is to achieve end-to-end automation of much of the design process, one aspect of which is creating effective level progressions. A key difficulty is getting the player to practice with interesting combinations of learned skills while maintaining their engagement. Although recent work in task generation and sequencing has reduced this effort, we still lack end-to-end automation of the entire content design process. We approach this goal by incorporating ideas from intelligent tutoring systems and proposing progression strategies that seek to achieve mastery of not only base concepts but arbitrary combinations of these concepts. The input to our system is a model of what the player needs to do to complete each level, expressed as either an imperative procedure for producing solutions or a representation of features common to all solutions. The output is a progression of levels that can be adjusted by changing high-level parameters. We apply our framework to a popular math puzzle game and present results from 2,377 players showing that our automatic level progression is comparable to expert-crafted progression after a few design iterations based on a key engagement metric. <s> BIB007 </s> A literature review of Empirical Evidence on Procedural Content Generation in Game-Related Implementation <s> Game Model <s> The co-evolution of morphology and control for virtual creatures enables the creation of a novel form of gameplay and procedural content generation. Starting with a creature evolved to perform a simple task such as locomotion and removing its brain, the remaining body can be employed in a compelling interactive control problem. Just as we enjoy the challenge and reward of mastering helicopter flight or learning to play a musical instrument, learning to control such a creature through manual activation of its actuators presents an engaging and rewarding puzzle. Importantly, the novelty of this challenge is inexhaustible, since the evolution of virtual creatures provides a way to procedurally generate content for such a game. An endless series of creatures can be evolved for a task, then have their brains removed to become the game's next human-control challenge. To demonstrate this new form of gameplay and content generation, a proof-of-concept game--tentatively titled Darwin's Avatars--was implemented using evolved creature content, and user tested. This implementation also provided a unique opportunity to compare human and evolved control of evolved virtual creatures, both qualitatively and quantitatively, with interesting implications for improvements and future work. <s> BIB008 </s> A literature review of Empirical Evidence on Procedural Content Generation in Game-Related Implementation <s> Game Model <s> Traditionally a dedicated level designer has to create every aspect of a level by hand, distribute and gather people to test it. Especially for multiplayer maps, the cyclic process of developing and testing can be quite cumbersome and time consuming. This paper presents a novel approach to provide live generation of levels for such multiplayer maps through procedural content generation and interactive evolution. The approach is demonstrated in the FPSEvolver video game that aims at replicating the look and feel of popular games like Counter-Strike. Without leaving the game a group of players can generate, play and improve levels to fit their particular preferences by voting on a selection of evolving levels. This approach focuses on maintaining the level design principles for modern first-person shooters that encourages good engagements between players, in the popular game mode “bomb defusal”. The presented approach can generate enjoyable maps that adapt to the preferences of players across a range of skill levels. Several distinct types of levels were created during testing, which range from open to closed, and complex to simple, each fitting closely with what the different players consider a good map. <s> BIB009 </s> A literature review of Empirical Evidence on Procedural Content Generation in Game-Related Implementation <s> Game Model <s> Torchless is a procedurally generated competitive dungeon crawling game where players have distinct asymmetric roles while sharing the same screen. Utilizing asymmetry, Torchless explores the relationship between players by experimenting with available information, player power, and player objectives. <s> BIB010 </s> A literature review of Empirical Evidence on Procedural Content Generation in Game-Related Implementation <s> Game Model <s> Abstract The ultimate goals of serious educational games (SEG) are to facilitate learning and maximizing enjoyment during playing SEGs. In SEG development, there are normally two spaces to be taken into account: knowledge space regarding learning materials and content space regarding games to be used to convey learning materials. How to deploy the learning materials seamlessly and effectively into game content becomes one of the most challenging problems in SEG development. Unlike previous work where experts in education have to be involved heavily, we proposed a novel approach that works toward minimizing the efforts of education experts in mapping learning materials to content space. For a proof-of-concept, we apply the proposed approach in developing a SEG game, named Chem Dungeon , as a case study in order to demonstrate the effectiveness of our proposed approach. This SEG game has been tested with a number of users, and the user survey suggests our method works reasonably well. <s> BIB011 </s> A literature review of Empirical Evidence on Procedural Content Generation in Game-Related Implementation <s> Game Model <s> The use of statistical and machine learning ap­proaches, such as Markov chains, for procedural content generation (PCG) has been growing in recent years in the field of Game AI. However, many of these level generation approaches account for only the structural properties of the levels. We developed multi-layered representations of levels, where each layer is designed to capture distinct gameplay information. Specifically, we experiment with representing levels using three layers: a structural layer that captures the object placements in the level, a player path layer that captures the path of an agent through the level, and a height layer that captures sections of the level as various height groups. We test our approach by generating levels for Super Mario Bros. with a multi-dimensional Markov chain approach. We compare the levels sampled with our multi-layered representation with those sampled using a single- layer approach that only considers the structural layer. <s> BIB012 </s> A literature review of Empirical Evidence on Procedural Content Generation in Game-Related Implementation <s> Game Model <s> Although there has been much work on procedural content generation for other game genres, very few researchers have tackled automated content generation for educational games. In this paper, we present a template-based, automatic puzzle generator for an educational puzzle programming game called BOTS. Two experts created their own new puzzles and evaluated generator-generated puzzles for meeting the educational goals, the structural and visual novelty. We show that our generator can generate puzzles with expert-designed educational goals while saving experts more than 80% of creation time, and these puzzles exhibit structural and visual novelty compared to expert-created puzzles. The contribution of this work is defined and implemented the first template-based automatic puzzle generator that saves expert time while incorporating expert-designed educational goals and enhancing puzzle creativity. <s> BIB013 </s> A literature review of Empirical Evidence on Procedural Content Generation in Game-Related Implementation <s> Game Model <s> In the context of a learning game to teach parallel programming, we describe a procedural content generation (PCG) approach that can be controlled to generate programming puzzles involving a desired set of concepts, and of desired size and "difficulty". Our approach is based on grammars to control the generation of the puzzle structure, and orthographic graph embedding techniques to render it into a two-dimensional grid for our game. The proposed PCG system is designed to work with a player model in order to provide personalized learning experiences. We present an evaluation of the variability of the generated puzzles using several metrics including challenge and solvability as evaluated by a custom-build model checker. Our evaluation shows that this PCG system can generate a large number of varied puzzles but it is still not able to generate puzzles with certain aesthetic and functional qualities found in puzzles generated by human authors. <s> BIB014 </s> A literature review of Empirical Evidence on Procedural Content Generation in Game-Related Implementation <s> Game Model <s> Procedurally generating history is a daunting task. The process of proceduralization requires codifying relationships into rules, and real-life histories are tangled networks of people, places, and events whose complexities obscure their relational mechanics. The task is further complicated by the fact that history serves a rhetorical function, i.e., historical accounts are used to promote certain cultural narratives that can belie the facts they purport to narrativize (this function is routinely neglected in video games' treatment of history). This paper describes a novel approach for procedurally generating coherent biographical narratives for historical figures, as implemented in our far-future roguelike game Caves of Qud. Using a state machine and replacement grammar as procedural tools, we construct a system that subverts the logic of cause and effect in favor of a process that first generates historical events and rationalizes them ex post facto. <s> BIB015 </s> A literature review of Empirical Evidence on Procedural Content Generation in Game-Related Implementation <s> Game Model <s> This paper reports on an ongoing attempt to develop an author-friendly approach to procedural game dialogue generation. Various affordances of the experimental authoring tool Expressionist are appropriated to allow non-computer scientist authors to design virtual characters' discourse and reasoning potential. The paper describes how the Hammurabi game project makes use of metadata-driven context free grammars to author virtual characters that can generate not only discourse but also context-relevant decisions. The author-friendliness and generativity of the approach is discussed. <s> BIB016 </s> A literature review of Empirical Evidence on Procedural Content Generation in Game-Related Implementation <s> Game Model <s> Sure Footing is a research project cum commercial product that arose from exploring generative systems for infinite runner games that balanced procedural flexibility with authorial intent. The approach taken as part of the games level generation systems allows not only for the gradual increase in difficulty as players progress, but allow for specific configurations that allow for the unique configurations that embody a level of difficulty or challenge. This paper explores ongoing development of the generation framework to to enable this flexibility, as well as raise consideration for flexible generation in the context of accessibility for players of varying competencies. <s> BIB017 </s> A literature review of Empirical Evidence on Procedural Content Generation in Game-Related Implementation <s> Game Model <s> Current research on adaptive games has mainly focused on adjusting difficulty in a variety of ways, for example, by providing some control over adaptive game world generation. These methods, however, are mostly ad-hoc and require quite some technical skills. To the best of our knowledge, so far, there has been no adaptive method that is truly generic and explicitly designed to actively include game designers in the content creation loop. In this paper, we introduce a generic method that enables designers to author adaptivity of game world generation, in a very expressive and specific fashion. Our approach uses adaptation rules , which build atop gameplay semantics in order to steer the online generation of the game content. Designers create these rules by associating skill profiles , describing skill proficiency, with content descriptions , detailing the desired properties of the specific game world content. This game content is then generated online using a matching and retrieval approach. We performed user studies with both designers and players and concluded that adaptation rules provide game designers with a rich expressive range to effectively convey specific adaptive gameplay experiences to players. <s> BIB018 </s> A literature review of Empirical Evidence on Procedural Content Generation in Game-Related Implementation <s> Game Model <s> Generating feasible levels for physics-based puzzle games is a complex and time-consuming task. This is because the mechanics of these games are based on realistic physics, so simulations are required to evaluate the playability of the generated levels. Recently, a few generators have been able to produce considerably complex levels in the context of the Angry Birds game, a very famous title of this genre. However, none of these generators are able to guarantee the playability of their produced levels. This paper presents Tanager, a level generator based on a genetic algorithm that is capable of producing feasible levels for the Angry Birds game. Evaluating playability in this game requires checking both the stability of the stacked blocks and the possibility of killing all the pigs with the given amount of birds. These two components are handled by the algorithm through a simulation. The first one is calculated by measuring the overall velocity of the blocks and the second is defined by an intelligent agent, which plays the levels. Three sets of experiments are conducted to evaluate Tanager. The first one measures the performance of the genetic algorithm underneath Tanager. The second one explores the expressivity of the generated levels considering their structural characteristics. The third one measures design quality of levels via an online user study. Results show that Tanager is capable of generating a considerable variety of feasible levels that are as engaging and enjoyable as those manually designed. However, the generated levels are less challenging than the hand-authored ones. <s> BIB019 </s> A literature review of Empirical Evidence on Procedural Content Generation in Game-Related Implementation <s> Game Model <s> This paper introduces a surrogate model of gameplay that learns the mapping between different game facets, and applies it to a generative system which designs new content in one of these facets. Focusing on the shooter game genre, the paper explores how deep learning can help build a model which combines the game level structure and the game's character class parameters as input and the gameplay outcomes as output. The model is trained on a large corpus of game data from simulations with artificial agents in random sets of levels and class parameters. The model is then used to generate classes for specific levels and for a desired game outcome, such as balanced matches of short duration. Findings in this paper show that the system can be expressive and can generate classes for both computer generated and human authored levels. <s> BIB020 </s> A literature review of Empirical Evidence on Procedural Content Generation in Game-Related Implementation <s> Game Model <s> We present a search-based approach to generating boards and decks of cards for the game Ticket to Ride. Our evolutionary algorithm searches for boards that allow for a well-shaped game arc, and for decks that promote an equal distribution of desirability for cities. We show examples of two boards generated by our algorithm and compare our results to those of the actual components of the game. Our approach creates game content that is specifically designed towards metrics that can affect gameplay in an impactful way. <s> BIB021 </s> A literature review of Empirical Evidence on Procedural Content Generation in Game-Related Implementation <s> Game Model <s> Procedural story generation has become an important research area due to its attractiveness to computer entertainment applications. Several approaches have been proposed to create procedural stories for games based mainly on logic programming and decision trees. These approaches use a set of possible events that are executed based on how the player interacts with the story. However, these approaches commonly use a fixed set of characters with predefined relationships. In contrast, in this article, we propose an approach that creates dynamic stories based on two networks: a handcrafted event network and a dynamic artificial social network created for each new story. This allows each story to have its own set of characters with a unique relationship network, resulting in an even wider range of possible stories. We demonstrate this with some examples and discuss how this approach can be implemented for interactive computer entertainment systems, such as video games. <s> BIB022 </s> A literature review of Empirical Evidence on Procedural Content Generation in Game-Related Implementation <s> Game Model <s> This paper introduces DATA Agent, a system which creates murder mystery adventures from open data. In the game, the player takes on the role of a detective tasked with finding the culprit of a murder. All characters, places, and items in DATA Agent games are generated using open data as source content. The paper discusses the general game design and user interface of DATA Agent, and provides details on the generative algorithms which transform linked data into different game objects. Findings from a user study with 30 participants playing through two games of DATA Agent show that the game is easy and fun to play, and that the mysteries it generates are straightforward to solve. <s> BIB023
 Source Explanation BIB005 , BIB010 , BIB011 , BIB017 , BIB001 game such as world generation BIB018 and level generation BIB012 , BIB005 , and is used for multiple reason such as creating variations and aesthetics BIB010 , reducing workload by using PCG BIB011 , generating variations and automation of in-game mechanics BIB017 or purely for experimental setup by using existing game as an example BIB001 . Platformer game utilizes a platform as a playing field for the player to do its actions, due to its nature, PCG are able to alter the playing field by using multiple methods BIB019 . First Person Shooter BIB020 , BIB006 Another prevalent game model that uses maps are first person shooter (FPS) games, where a player controls an in-game avatar that has a first-person view as if the player is seeing the object in real life. Similar to platformer games, maps can also be generated using PCG BIB020 . Not limited to maps, FPS require players to face another player as an opponent, be it another human player, or an A.I., which in fact, can be generated procedurally by using PCG BIB006 . Real-time Strategy BIB013 , BIB021 , BIB014 Real-time strategy (RTS) games are strategy games that require players to do their action in real-time manner, but does not require such finesse of movement precision but more of a chess-like actions. Similar to FPS and platformer, it also has a playing field that can be generated using PCG, the generated playing field are by no means perfect, as such, the aesthetics level of generated content may not be the same as hand-made ones, but the generation of such content may outweighs the aesthetic penalty BIB002 . Similar to RTS card and board games can also be implemented with PCG concepts to generate its content such as board layout BIB013 , BIB021 , BIB014 . Story-Based Games; Fantasy Games BIB015 , BIB022 , BIB003 Story-based games and fantasy games utilizes PCG in a different manner compared to previous models mentioned, focusing on creating a dynamic story contents by using PCG as a means of generation BIB015 - BIB003 . Sandbox Games; Scifi Games; Management Games BIB007 , BIB008 , BIB016 Other lesser game models utilize PCG for its content generation similarly, such as sci-fi to generate levels BIB007 , sandbox games to generate player's appearance BIB008 , as well as dialog generation for management games BIB016 . Based on its game genre, as shown in Table 6 , action games are more favored due to action games usually plays in a level or playing field, as such, most action games are also a platformer games BIB009 , BIB004 , BIB019 , BIB006 . Sandbox simulation games as mentioned earlier also taken an advantage by using PCG to generate player avatar as sandbox simulation games able to create countless amount variations BIB008 . As well as storybased simulation games to generate its dialog and story by using PCG BIB023 . 