Guiding Generative Graph Grammars of Dungeon Mission Graphs via Examples Abdelrahman Madkour,1 Stacy Marsella, 1 Casper Harteveld, 1 Magy Seif El-Nasr 2 Jan-Willem van de Meent 1 1 Northeastern University 2 UC Santa Cruz madkour.a@northeastern.edu, s.marsella@northeastern.edu, c.harteveld@northeastern.edu, mseifeln@ucsc.edu, j.vandermeent@northeastern.edu Abstract widely applicable. However, coming up with a graph gram- mar that captures the intent of the designer is a difficult and Generative Graph grammars are an established technique for time-consuming task. Predicting the effects of rules on the procedural content generation (PCG) of the mission space of dungeon levels, as they allow for explicit specification of de- generative space of the grammar is hard and error-prone. sign intention. However, they are difficult to control beyond Oftentimes, unintended consequences of rules result in un- the initial specification. Defining effective grammars requires desirable artifacts, such as unplayable levels. To avoid this, both design expertise and familiarity with how grammars the design of grammars focuses on guaranteeing playability work, and even then the resulting grammar is not guaranteed above all else. to generate missions that fit a designer’s intention. In this pa- However, there are other design considerations that are per, we propose a system that attempts to allow designers to taken into account when coming up with a dungeon level. affect an existing grammar’s generative space by allowing de- For example, Adams et al. (2002) outlines that low-quality signers to control the probability distribution induced by the grammar. The system does this by learning the parameters of levels suffer from the ‘pointless area’ problem, where entire a probabilistic graph grammar from examples. Designers can sections of the level do not have any reward to the player and control the generation of these examples via specification of are not part of the main path to complete the level. Or a level assessment criteria, and a threshold above or below which the may be completable but trivially so, requiring the player to output is generated. We conclude with a demonstration of the traverse one or two rooms to reach the end. Such considera- efficacy of the system in shifting the distribution of the gen- tions are difficult to capture in grammar rules that must also erative space. guarantee playability. Therefore, some approaches opt to use a more general Introduction grammar and let designers control which rules are applied either manually step-by-step (Dormans and Bakkes 2011) Procedural content generation (PCG) in games is a growing or through a list of which rules to apply and in what order, field in game AI that has received increasing interest in re- which Dormans (2011) refers to as recipes. These recipes cent years (Liapis 2020). It promises to reduce the burden of serve as the means by which designers restrict the genera- game development by providing tools that assist with gener- tive space of the grammar to areas that fit their design intent. ating game artifacts such as levels. Designing levels is a cre- In other words, recipes adjust the probability distribution in- atively involved process that is difficult to do well, even for duced by the grammar such that the grammar is less likely to specialized experts. Therefore, despite this growing body of generate undesirable graphs, and more likely to generate de- work, automatically creating levels that are of similar qual- sirable ones. Lavender (2016) demonstrates how this could ity to those made by human designers remains a challenge be done by using the grammar given in Dormans and Bakkes (Rodriguez Torrado et al. 2020). (2011); by utilizing different recipes, they were able to gen- Because of this challenge, many techniques opt to have erate different kinds of dungeons without altering the origi- their generative process be as transparent and controllable as nal grammar. These recipes, however, operate in the space of possible, such that game developers can adjust it if needed. the grammar, and therefore requires designers to be familiar One approach to make the generation process interpretable with how grammars work. by level designers is graph grammars. Graph grammars are Ensuring design criteria are met is a common concern an established framework for visual programming (Rozen- for many level PCG techniques, especially those that rely berg 1997), and were popularized for use in the context of on machine learning algorithms (Summerville et al. 2018). dungeon level generation by Dormans and Bakkes (2011). There have been attempts to address this by reducing the Graphs are a common representation for content genera- likelihood of a generator to produce undesirable levels tion in other contexts as well (Li and Riedl 2015; Londoño (Summerville et al. 2016; Di Liello et al. 2020). Such ef- and Missura 2015), making graph grammars potentially forts have yet to be extended to graph grammars. In fact, Copyright © 2021 for this paper by its authors. Use permitted to the best of our knowledge, no previous attempt has been under Creative Commons License Attribution 4.0 International made to adjust an existing graph grammar towards captur- (CC BY 4.0). ing design considerations via learning from designer made design of the mission graphs they wish to generate and not examples or examples generated by the grammar. grammar rules. In this paper, we propose a system for adjusting the prob- Outside of dungeon generation, graph grammars have ability distribution over the mission graphs of dungeons in- found other uses in the PCG literature. Londoño and Mis- duced by a graph grammar via examples generated by the sura (2015) proposed a graph representation of Super Mario grammar. To facilitate these adjustments, we propose an ex- Levels and a system to learn a probabilistic graph gram- tension to the existing formalization of graph grammars in mar from existing levels. Hauck and Aranha (2020) extend Dormans and Bakkes (2011). We alter their definition to in- this work and propose a system for generating new Mario clude explicit probabilities at different levels of specificity. levels that utilizes the learned structure of the graph repre- This provides the system with parameters to adjust, and thus sentation. This work focuses on context-free graph gram- provides a knob by which designers can control the output mars (CFGGs). These are grammars that constrain the left- of the grammar after its specification. These parameters are hand side of a production rule to be a single non-terminal learned from examples, the generation of which is controlled vertex, whilst context-sensitive graph grammars (CSGGs) by designers. We evaluate our approach, demonstrating its are more general and allow for the left-hand side to be a ability to shape a grammar’s distribution towards that of graph comprised of both non-terminal and terminal vertices. the given examples, thereby making the grammar generate Adams et al. (2002) showed that unlike string based gram- graphs that are similar to the given examples. mars, CFGGs are significantly less expressive than CSGGs. There are many rules that can be expressed in a CSGG that Related Work cannot be reduced to rules in a CFGG. This severely lim- Previous work on dungeon level generation has largely fo- its the capability of context-free grammars as a generative cused on search-based techniques (van der Linden, Lopes, method. Due to this limitation, our work and that of Dor- and Bidarra 2014). These approaches require specification mans and Bakkes (2011) focuses on context-sensitive graph of a fitness function that summarizes the quality of the level. grammars. This function is often difficult to come up with, even for Another system that uses context-sensitive graph gram- domain experts. In most of these techniques, it is also the mars is that proposed by Valls-Vargas, Zhu, and Ontañón primary means of control designers have over the genera- (2017). They utilize multiple stochastic context-sensitive tion process. Alvarez et al. (2018) address this by provid- graph grammars to generate puzzle levels for an educational ing more control to the designer via a co-creative system. game. Each rule in the grammar has a weight associated with This system provides suggestions as the designer is creat- it and a discount factor. When a rule is used, its weight is ing a dungeon. Dungeons in this system are in a tile-based decreased by the discount factor. Despite parameterizing the representation. The system then identifies two levels of pat- rules of the grammars with weights, they did not explore terns, micro and meso. Micro patterns are concerned with learning these parameters from examples. base tiles and how they relate to the tiles surrounding it. Though little work has explored adjusting a graph gram- Meso-patterns on the other hand, consider the relation of mar based on examples, there has been work on altering micro-patterns and meso-patterns. The suggestions the sys- other types of grammars. Shaker et al. (2012) proposed a tem proposes use these tile-based patterns for chunks of the system for evolving grammar rules for a context-free gram- dungeon, whilst our work focuses on a high level depiction mar that generated Mario levels. This system operated on of the flow of the level that is specified by graphs. string-based grammars and adjusted the rules based on hand- Generation of this more abstract notion of a level via written fitness functions and not training data. graph grammars was proposed by Dormans and Bakkes Dang et al. (2015) do propose a framework that adjusts (2011). They split the generation of dungeon levels into two context-free shape grammars based on examples. The type distinct processes; ‘mission’ generation and ‘space’ gener- of shape grammars used in this work are established gram- ation. The mission, represented as a graph, encodes the de- mars for automatically generating 3D objects such as build- sired trajectory of the player through the level, whilst the ings, trees and tables. They propose a human-in-the-loop space specifies where that experience takes place. Dormans framework that allows designers to designate the distribution and Bakkes (2011) use shape grammars to turn a mission over the generated 3D models of these grammars via scor- graph into level geometry, whilst other work has explored ing of examples. This framework is similar to our system using GANs Gutierrez and Schrum (2020). We focus in this but operates on context-free shape grammars, we focus on a paper on the generation of mission graphs. more expressive type of grammars; context-sensitive graph The graph grammars proposed by Dormans and Bakkes grammars. Thus, we parameterize our grammar formulation (2011) constrains the generative space of the grammar with differently. what is referred to as recipes (Dormans 2011). The recipes dictate what rules should be applied and in what order. These Methodology recipes are hand-coded by the designers and as such they in- crease the specification requirements of this approach. In ad- The Graph Grammar System dition, these recipes are difficult to come up such that the re- There are many types and formalizations of graph grammars sulting graphs are playable and meet specific design criteria. (Rozenberg 1997). For this work, we consider the graph We extend this work by allowing the grammar to be guided grammar system proposed by Dormans and Bakkes (2011). by examples, which allows designers to think in terms of the These grammars operate by applying rules to rewrite a graph 1:s 3:T 1:S 2:T 1:s 3:T 2:T 2:T 4:T 1:S 2:G 1:s 3:T 2:g 1:T 2:G 1:k 3:T 4:l 2:g Label S/s Meaning Start S T 1:T 1:k 2:T 3:l 1:k 2:t 3:l T/t Task G/g Goal k key 1:* 2:k 3:T 1:* 2:k 4:t 1:* 2:T 3:* l * lock Wildcard G 3:* 3:l 3:* 5:l (a) Node Labels (b) Initial graph (c) The set of production rules Figure 1: An example of a simple graph grammar for generating dungeon mission graphs;a) shows the node labels of graphs in the grammar b) shows the starting graph of the grammar whilst c) shows the grammar’s production rules. The dark grey nodes in the production rules are wildcard nodes that can match with any node. Adapted from Shaker, Togelius, and Nelson (2016, Chapter 5) until no rule is applicable or a maximum number of appli- We see that there are multiple left-hand side graphs that we cations is met. Figure 1 is a toy example of such a gram- can match to the starting graph. Initially all rules are appli- mar. They are defined by an initial graph that gets altered cable, if we select the first rule to apply on the initial graph according to the production rules. Rewriting a graph works then the second is no longer applicable, and if we select by first finding a subgraph in the original graph that matches the second rule then the first would no longer be applica- the left-hand side graph of a production rule. For two graphs ble. The probability of which left-hand-side we pick controls to match, they must have the same graph topology and the which of these scenarios plays out in the generation process. same node labels. Figure 1a shows the node labels of the toy Recipes as defined in (Dormans 2011) let the designer spec- grammar. Note that graphs in production rules have nodes ify this directly by stating what rules ought to be selected and that can be labeled as ‘wild-card’ which means they can in what order. In contrast, our approach attempts to learn this match with a node that has any label. In the toy grammar, from examples. this is represented by the ‘*’ character. Next, we mark that When defining a grammar, it is tractable to specify the subgraph by copying the markers of the nodes from the left- probabilities of which right-hand-side gets chosen in a rule, hand side. These markers indicate which nodes will be re- the same cannot be said of the probabilities of which left- placed by which nodes in the right-hand side of the rule. hand-side gets picked. These probabilities are defined based Then we check if there are nodes or edges in the subgraph on which rules are applicable, and thus changes from one that exist in the right-hand side of the rule, if not then we step of the generation process to the next. Therefore, we set delete them. Then we add any nodes and edges in the right- the distribution of these probabilities to be initially uniform hand side that do not exist in the left-hand side. Finally, we and learn it from examples. To be able to do that, we need remove all the markers from the subgraph. a way of keeping track of which left-hand-side in the ap- plicable rules is selected and the set of other left-hand-side Proposed Extension graphs that could have been picked. Thus, for each graph To effectively control the generative space of the grammars, generated by the grammar, we keep track of the production we need parameters that we can adjust. To this end, we ex- rules that were applied and what production rules could have tend the graph grammar system described earlier to incorpo- been applied in what we call a generation chain. This gen- rate explicit probabilities for production rules. There are two eration chain keeps track of what the applicable production types of these probabilities: the probability of which of the rules were at every step of the generation process, and which possible left-hand-side graphs is chosen and the probability production rule in that set was selected. of which right-hand-side graph of a rule is being chosen. The probability of which right-hand-side gets chosen is what pre- Updating Grammar Parameters Once we have a train- vious work on probabilistic grammars has considered (Dang ing set, we can observe the production rules used to generate et al. 2015). However, this alone does not fully parameterize each graph and use that information to update the produc- the generation process, and a level of uncontrolled stochas- tion rule probabilities. First, we update the probabilities of ticity remains. the right-hand side graphs according to what right-hand side To illustrate this, consider the toy grammar in Figure 1. was selected in the training data. This involves counting how many times a given right-hand-side graph was chosen and adapted the metrics put forth by Lavender (2016), which dividing it by how many times its corresponding rule was were in turn inspired by Smith and Whitehead (2010): applied in the training set. Formally, given a set of graphs • Mission Linearity: which captures the linearity of the GX = {G1 . . . , Gn }, we can update the i-th right-hand side mission structure. We calculate it as follows: probability of production rule r, p(r : Gleft → Gright i | GX ) #of nodes on shortest direct path to the end by setting it equal to: Total nodes in graph C(r : Gleft → Gright i | GX ) • Map Linearity: which captures the linearity of the map (1) C(r : Gleft → Gright P Gright a a | GX ) layouts. In the graphs this is seen by how many outgoing edges a node has. We calculate it as follows: where C(r : Gleft → Gright a ) is the count of how many times #of single exit rooms + (0.5 × #of double exit rooms) Gl has been replaced with Ga in the training set GX . We then update the probabilities of the left-hand side Total rooms with exits graphs. Recall that we defined a generation chain that kept • Leniency: which captures how easy the level is to play track of which production rules were chosen and which were based on the amount of rooms where the player is likely available at the time a rule was picked. We go through the to encounter danger. We calculate it as follows: generation chains of all the graphs in our data-set and keep #of safe rooms track of which sets of options were available. We then count how many times a given left-hand side graph was chosen in Total rooms a given set of applicable rules and divide it by how many • Path Redundancy: which captures how many useless times that set of applicable rules shows up in the training rooms there are in the graph. Useless rooms in our con- set. text are defined as nodes that do not have any out-going Formally define Pd to be the set of production rules that edges and do not provide the player with any reward in are available at a given depth d of the generation chain, themselves. We calculate it as follows: C(Pd | GX ) to be the count of how many times this set #of useless rooms appears at any depth in the chains that generate the training data-set, GX and pr ∈ Pd to be a production rule in that set. Total rooms We update the probability of this production rule by Results C(pr | GX , Pd ) p(pr | Pd ) = (2) For our experimental evaluations, we utilized the grammar C(Pd | GX ) given in Dormans and Bakkes (2011). Code of our sys- where C(pr | GX , Pd ) is the count of how many times pr tem and the experiments we ran can be found on Github 1 was chosen in GX when the options for rule applications . Following the approach taken by Smith, Padget, and Vi- were Pd . dler (2018) and Lavender (2016), we generate 1000 mission graphs of the unaltered grammar and calculated their scores Generating Examples according to the four metrics we described earlier. Figure 2a shows the expressive range heat-map of the unaltered gram- Our system attempts to help designers inform grammars mar, without the use of recipes. Next we picked a threshold of their design considerations by providing examples from for Leniency, Path Redundancy and Mission Linearity. We which a grammar can learn. These examples ought to cap- then generate our training set by choosing graphs that ex- ture the desirable qualities that a designer wants the gram- ceed the threshold, train the grammar on that training set mar to replicate. The best means by which designers can and visualize the heat-map of the resulting grammar. Figure generate those examples is a research question in its own 2b shows the expressive range heat-map of the altered gram- right. For the purposes of this paper, we assess the gram- mar. We see that the generative space has moved towards the mar’s output via a scoring function and then specify a thresh- values above the threshold. old, whereby any graph that exceeds or falls short of the We repeated the same process but changed the threshold threshold is added to the training set. For example, a de- value and picked examples that were below the threshold. signer may give a function that measures how easy a mission Figure 2c shows the expressive range heat-map of the result- graph is to play through and use a certain threshold to indi- ing grammar. Once again, we see that the generative space cate the desired difficulty of graphs to be generated by the has shifted towards the specified value. grammar. We take this approach as it clearly demonstrates We additionally ran 100 trials, where we repeated the pro- how the generative space shifts towards the provided exam- cess described above and kept track of how many graphs ples. were above or below the threshold before and after training. There are many scoring functions one can define, in this Table 1 summarizes our findings. Despite not guaranteeing paper we consider metrics used in previous work to ana- that the grammar will only generate graphs that meet the de- lyze dungeon level generators. There does not exist an es- sired threshold, we greatly reduce the number of graphs that tablished set of metrics for dungeon levels like there is for fall outside it. platformer levels (Horn et al. 2014). Therefore, we follow 1 the example set by Smith, Padget, and Vidler (2018) and https://github.com/a3madkour/pgg (a) The expressive range across the metrics proposed in Lavender (2016) and used in Smith, Padget, and Vidler (2018) of the grammar before alteration. (b) The expressive range of the grammar after being trained on examples that are above a threshold. The threshold is indicated by the red line. (c) The expressive range of the grammar after being trained on examples that are below a threshold. The threshold is indicated by the white line. Figure 2: The expressive range of grammars; 2a is for the unaltered grammar, whilst 2b-c for each of the design scenarios we considered. Scenario Before After Scenario Le PR ML Le above 0.5 123 (± 10.3) 684.4 (± 25.7) Figure 2b 232 130 105 PR above 0.1 182 (± 13.6) 612.5 (± 24.3) Figure 2c 245 340 101 ML above 0.55 122 (± 10.9) 719 (± 23.2) Le below 0.3 240 (± 14.9) 762.3 (± 16.4) Table 2: The size of the training set for each scenario used PR below 0.04 325 (± 14.3) 700.8 (± 18.1) to train the grammars for Figure 2.Le is leniency, PR is path ML below 0.4 112 (± 9.5) 591.3 (± 22.8) redundancy and ML is mission linearity. Table 1: Average number of graphs (std) that were above or below a given threshold before and after grammar adjust- of adjusting a generative grammar towards their design in- ment. Le is leniency, PR is path redundancy and ML is mis- tention without needing to think about grammar rules. sion linearity. A limitation of the system is that examples that are used for training must be generated by the grammar. A promising avenue of future work is exploring the possibility of learn- Discussion ing them from designer generated examples. Another would Our experimental analysis demonstrates that learning gram- be looking into learning grammar rules from the examples. mar parameters from examples successfully adjusted the dis- Only altering the probabilities of the system does not change tribution induced by the grammar. Thus, we demonstrated the original generative space. It alters in which areas in the the feasibility of controlling generative graph grammars generative space the grammar is more likely to generate. through example generation; which gives designers a way This work also calls for a user study that assesses what mechanism designers prefer using to control distribution of Cook, M.; Gow, J.; Smith, G.; and Colton, S. 2021. Danesh: the grammar. In the context of our system, this would en- Interactive Tools For Understanding Procedural Content tail figuring out what means of generating training examples Generators. IEEE Transactions on Games 1–1. doi:10.1109/ designers prefer using, and which most facilitates thinking TG.2021.3078323. in terms of design intention as opposed to grammar rules. Dang, M.; Lienhard, S.; Ceylan, D.; Neubert, B.; Wonka, Ideally, designers only have to think in terms of the artifacts P.; and Pauly, M. 2015. Interactive design of probabil- they wish to generate, not the logic or parameters of their ity density functions for shape grammars. ACM Trans- generator. Designing well-formed and sufficiently genera- actions on Graphics 34(6): 1–13. ISSN 07300301. doi: tive grammars requires a different skill set than designing 10.1145/2816795.2818069. URL http://dl.acm.org/citation. dungeons. Thus, providing designers with the tools that al- cfm?doid=2816795.2818069. lows them to operate in the space of what they know well, and use it to adjust an existing grammar will improve the Di Liello, L.; Ardino, P.; Gobbi, J.; Morettin, P.; Teso, usability of graph grammars as a generative tool. S.; and Passerini, A. 2020. Efficient Generation of Struc- Recent work on guidelines for human-AI interaction sug- tured Objects with Constrained Adversarial Networks. In gest that for AI systems to better fit with human intention, Larochelle, H.; Ranzato, M.; Hadsell, R.; Balcan, M. F.; and more direct involvement is required (Amershi et al. 2019). Lin, H., eds., Advances in Neural Information Processing Though some work has explored how to better explain the Systems, volume 33, 14663–14674. Curran Associates, Inc. output of PCG systems (Cook et al. 2021), there is little on Dormans, J. 2011. Level Design as Model Transforma- how to make them more directly specifiable and controllable tion: A Strategy for Automated Content Generation. In Pro- by nontechnical designers. As Cook et al. (2021) describe, ceedings of the 2nd International Workshop on Procedural the parameters of generators often do not map directly to Content Generation in Games, PCGames ’11. New York, output metrics that are of relevance to designers. By allow- NY, USA: Association for Computing Machinery. ISBN ing designers to operate in the space of the outcome of the 9781450308724. doi:10.1145/2000919.2000921. URL generator, we position our work as a step towards reducing https://doi.org/10.1145/2000919.2000921. this mismatch of desired outcome and specification of PCG Dormans, J.; and Bakkes, S. 2011. Generating Missions and systems, and thus achieve more accessibility in controlling Spaces for Adaptable Play Experiences. IEEE Transactions them. on Computational Intelligence and AI in Games 3(3): 216– 228. ISSN 1943-0698. doi:10.1109/TCIAIG.2011.2149523. Conclusion We presented a system for adjusting the generative space of Gutierrez, J.; and Schrum, J. 2020. Generative adversarial a graph grammar for dungeon generation based on exam- network rooms in generative graph grammar dungeons for ples. To do so, we proposed an extension of existing graph the legend of zelda. In 2020 IEEE Congress on Evolutionary grammars to allow for the use of probabilities that can then Computation (CEC), 1–8. IEEE. be learned. Our experiments demonstrate that our approach Hauck, E.; and Aranha, C. 2020. Automatic Generation is successful in shifting the generative space towards that of of Super Mario Levels via Graph Grammars. In 2020 the generated examples. Finally, we discuss how generating IEEE Conference on Games (CoG), 297–304. doi:10.1109/ a set of high quality examples is potentially an accessible CoG47356.2020.9231526. method of providing designer control over generative gram- Horn, B.; Dahlskog, S.; Shaker, N.; Smith, G.; and Togelius, mars beyond initial specification. J. 2014. A comparative evaluation of procedural level gen- erators in the mario ai framework. In Foundations of Digital References Games 2014, Ft. Lauderdale, Florida, USA (2014), 1–8. So- Adams, D.; et al. 2002. Automatic generation of dun- ciety for the Advancement of the Science of Digital Games. geons for computer games. Bachelor thesis, Univer- Lavender, R. 2016. The Zelda Dungeon Generator: Adopt- sity of Sheffield, UK. DOI= http://www. dcs. shef. ac. ing Generative Grammars to Create Levels for Action- uk/intranet/teaching/projects/archive/ug2002/pdf/u9da. pdf Adventure Games. . Alvarez, A.; Dahlskog, S.; Font, J.; Holmberg, J.; Nolasco, Li, B.; and Riedl, M. 2015. Scheherazade: Crowd-powered C.; and Österman, A. 2018. Fostering creativity in the interactive narrative generation. Proceedings of the AAAI mixed-initiative evolutionary dungeon designer. In Proceed- Conference on Artificial Intelligence 29(1). URL https://ojs. ings of the 13th International Conference on the Founda- aaai.org/index.php/AAAI/article/view/9782. tions of Digital Games, 1–8. Liapis, A. 2020. 10 Years of the PCG Workshop: Past and Amershi, S.; Weld, D.; Vorvoreanu, M.; Fourney, A.; Future Trends. In International Conference on the Founda- Nushi, B.; Collisson, P.; Suh, J.; Iqbal, S.; Bennett, P. N.; tions of Digital Games, FDG ’20. New York, NY, USA: As- Inkpen, K.; Teevan, J.; Kikin-Gil, R.; and Horvitz, E. 2019. sociation for Computing Machinery. ISBN 9781450388078. Guidelines for Human-AI Interaction, 1–13. New York, doi:10.1145/3402942.3409598. URL https://doi.org/10. NY, USA: Association for Computing Machinery. ISBN 1145/3402942.3409598. 9781450359702. URL https://doi.org/10.1145/3290605. Londoño, S.; and Missura, O. 2015. Graph Grammars for 3300233. Super Mario Bros Levels. In FDG. Rodriguez Torrado, R.; Khalifa, A.; Cerny Green, M.; Juste- sen, N.; Risi, S.; and Togelius, J. 2020. Bootstrapping Conditional GANs for Video Game Level Generation. In 2020 IEEE Conference on Games (CoG), 41–48. doi: 10.1109/CoG47356.2020.9231576. Rozenberg, G., ed. 1997. Handbook of Graph Grammars and Computing by Graph Transformation: Volume I. Foun- dations. USA: World Scientific Publishing Co., Inc. ISBN 9810228848. Shaker, N.; Nicolau, M.; Yannakakis, G. N.; Togelius, J.; and O’neill, M. 2012. Evolving levels for super mario bros using grammatical evolution. In 2012 IEEE Conference on Com- putational Intelligence and Games (CIG), 304–311. IEEE. Shaker, N.; Togelius, J.; and Nelson, M. J. 2016. Procedural Content Generation in Games. Springer Publishing Com- pany, Incorporated, 1st edition. ISBN 3319427148. Smith, G.; and Whitehead, J. 2010. Analyzing the Ex- pressive Range of a Level Generator. In Proceedings of the 2010 Workshop on Procedural Content Generation in Games, PCGames ’10. New York, NY, USA: Association for Computing Machinery. ISBN 9781450300230. doi: 10.1145/1814256.1814260. URL https://doi.org/10.1145/ 1814256.1814260. Smith, T.; Padget, J.; and Vidler, A. 2018. Graph-based generation of action-adventure dungeon levels using answer set programming. In Proceedings of the 13th International Conference on the Foundations of Digital Games - FDG ’18, 1–10. ACM Press. ISBN 978-1-4503-6571-0. doi: 10.1145/3235765.3235817. URL http://dl.acm.org/citation. cfm?doid=3235765.3235817. Summerville, A.; Guzdial, M.; Mateas, M.; and Riedl, M. 2016. Learning player tailored content from observation: Platformer level generation from video traces using lstms. In Proceedings of the AAAI Conference on Artificial Intelli- gence and Interactive Digital Entertainment, volume 12. Summerville, A.; Snodgrass, S.; Guzdial, M.; Holmgård, C.; Hoover, A. K.; Isaksen, A.; Nealen, A.; and Togelius, J. 2018. Procedural content generation via machine learning (PCGML). IEEE Transactions on Games 10(3): 257–270. Valls-Vargas, J.; Zhu, J.; and Ontañón, S. 2017. Graph Grammar-Based Controllable Generation of Puzzles for a Learning Game about Parallel Programming. In Proceed- ings of the 12th International Conference on the Founda- tions of Digital Games, FDG ’17. New York, NY, USA: As- sociation for Computing Machinery. ISBN 9781450353199. doi:10.1145/3102071.3102079. URL https://doi.org/10. 1145/3102071.3102079. van der Linden, R.; Lopes, R.; and Bidarra, R. 2014. Proce- dural Generation of Dungeons. IEEE Transactions on Com- putational Intelligence and AI in Games 6(1): 78–89. ISSN 1943-0698. doi:10.1109/TCIAIG.2013.2290371.