Grammar Based Modular Level Generator for a Programming Puzzle Game Chaima Jemmali Carter Ithier Seth Cooper Magy Seif El-Nasr Northeastern University Northeastern University Northeastern University UC Santa Cruz jemmali.c@northeastern.edu ithier.c@northeastern.edu se.cooper@northeastern.edu mseifeln@ucsc.edu Abstract we use a grammar based approach which insures by con- struction that the level is solvable without post-processing Procedural Content Generation is widely used in games, how- or filtering out unsolvable solutions (Traichioiu et al. 2015; ever, its use in educational puzzle games has been limited. These types of games present common challenges such as Valls-Vargas, Zhu, and Ontañón 2017; Font et al. 2016). solvability and non triviality, but also the extra challenge of We combine this approach with working backwards from preserving intended learning goals. In this paper, we present a a solved map similar to what has been done for the Sokoban modular constructive approach to generate levels in a puzzle game (Taylor and Parberry 2011). Controllability and vari- programming game. The approach uses a grammar to gen- ation are somewhat in opposition, especially when having erate game elements from code and works backwards from such a hard constraint on how the level should be solved. To the solution to ensure solvability, controllability over the so- provide variation, we allow fluidity in our level construction, lution, and variation, allowing for alternative solutions that especially in the path creation section. This allows levels to preserve the learning goals. have alternative working equally difficult solutions, of the same length as the provided solution code, but also intro- Introduction duces shorter solutions which means the player can solve There has been a lot of research on Procedural Content Gen- the level by bypassing certain elements. We further evaluate eration (PCG) and there are several techniques used to gen- the generator through the design/aesthetics lens by analyz- erate levels for different game genres. The most common ing the expressive range (Smith and Whitehead 2010) using two genres where PCG is applied for level generation are two metrics: percentages of walkable and interactable tiles. dungeons/rogue-likes and platformer games. However, the Our results show that the levels generated are 100% solvable application to puzzle games has been limited (De Kegel and by the provided solution code. On average, 47.4% of them Haahr 2019). Educational Games are another area where had an alternative working solution of the same length, while PCG has not been adopted widely (Dong and Barnes 2017). 21.3% had shorter “easier” solutions. Besides the common challenges of solvability and non- The contribution of this paper is the design and applica- triviality of the solution, these types of games present the ex- tion of a PCG system combining previously used techniques, tra challenge of preserving intended learning goals (Smith, as well as introducing new ones for path creation. The gener- Butler, and Popovic 2013; Valls-Vargas, Zhu, and Ontañón ator is applied to a programming puzzle game, but the modu- 2017; Dong and Barnes 2017). lar aspect of the approach should make parts of it applicable In this paper, we focus on two aspects of the gener- to other educational or puzzle games. ator: controllability over the educational goals and varia- tion, meaning the designer has full control over the learn- Related Work ing goals in the level to be generated. Further, generated Research on games that teach programming is significant, levels vary in size, layout, and number of alternative so- especially at the introductory level (Harteveld et al. 2014; lutions. In fact, we are not looking if a puzzle is merely Miljanovic and Bradbury 2018). Generating content for solvable, we require it to be solvable with the solution code these games can be challenging and time consuming, which provided as input which provides greater control on what is increasing the need for PCG to create content that can be gameplay is generated. This approach is similar to generat- tailored to specific player needs (Park et al. 2019). However, ing levels from the gameplay as a vocabulary (Van der Lin- a major concern in PCG is the lack of reliability (Togelius den, Lopes, and Bidarra 2013), where our gameplay is de- et al. 2011), which makes the assessment of the generator of scribed through the solution code. To guarantee solvability, utmost importance. Controllability and variability are two Copyright c 2020 for this paper by its authors. Use permitted un- of the major metrics used to assess PCG systems. In fact, der Creative Commons License Attribution 4.0 International (CC the degree of control and the set of options are very im- BY 4.0). portant characteristics of any procedural generator (Shaker Object Type Symbol Description movable m / M / can be walkable or not, may block M & PP activate a pressure plate rotating rr / RR L shaped block that rotates block around its center (rr/RR), can be walkable or not stoppable mb / MB moving block that can be block stopped fire statue FS / A rotatable or movable FSR & statue that blows wind/fire reward (see Figure 1) statue S / S & statue that has the same PP characteristics as an above Figure 1: Coding interface: bottom-left: Structure of the ground block command with examples, bottom-right: output area shows pressure PP & re- activates a reward (key, hid- syntax error or progress towards solution, top-right: Text plate ward den door, hidden block, etc) area and buttons to run/restart/help/undo/redo, top-left: Pro- hidden bh ground level block that can grammable objects and animation/code execution area. block be revealed. revealed BR above ground block that block can be hidden. et al. 2016). When dealing with puzzle levels, solvability hidden door DH A door that can be revealed. is an important constraint which can be achieved through closed door DC A door that can be opened. different techniques. Some works have used generate-and- hidden key KH A key that can be revealed. test techniques (Dong and Barnes 2017), constructive ap- fire FU / FL A fire pit that can be lit or proaches where the content is generated only once and per- unlit. formance checks may be applied throughout (De Kegel and lever LV & re- A lever that activates a re- Haahr 2019), search-based algorithms (Togelius and Shaker ward ward if it’s in the correct 2016), or answer set programming (ASP) (Smith and Mateas position. 2011), which falls somewhere in between constructive and generate-and-test. Procedural content generation via ma- Table 1: Description of game elements in the game; their chine learning (PCGML) (Summerville et al. 2018) is an symbols, mechanics, and features increasingly popular approach to generating various content, however, it does not always guarantee solvability. In the con- text of learning games, another constraint is to preserve the while allowing for variability with equally difficult codes intended learning goals or the intended difficulty of the lev- and minimizing trivial solutions. els and ascertain there are no trivial solutions. The definition of such solutions and the approaches to detect them vary de- Game pending on the game. For instance, in an educational game In this paper, we use May’s Journey, a puzzle game that that teaches parallel programming (Valls-Vargas, Zhu, and teaches the basics of programming by having learners type Ontañón 2017) a trivial puzzle is a puzzle that doesn’t re- simple instructions in the game’s custom programming lan- quire the player to make any changes to be solved and is guage to interact with objects, solve puzzles, and navigate identified through the use of a model checker that will run an environmental maze (Jemmali et al. 2019; 2018). different scenarios to check if they pass or fail. In another The game is structured in two major phases. In the first puzzle game that teaches programming (Dong and Barnes phase, players can move the avatar around using arrow 2017), solutions that violate educational goals are solutions keys, interact with different parts of the environment, talk to that contain unintentional loops and unnecessary elements. NPCs, or collect objects. In the second phase, they pull up However, the work evaluates a code synthesizer that creates a programming interface, as can be seen in Figure 1, where a solution code from a template rather than the level gener- they interact with game objects through code to solve differ- ated for that code. To ensure the absence of trivial solutions, ent puzzles, which allows them to progress through a level Smith, Butler, and Popovic (2013) used a modified version or reveal some rewards. of ASP to successfully generate levels with no undesirable Each level in the game offers a coding challenge that can solutions, however, the search space is so large that it makes be maze-based, where the reward for solving it is getting the generation time too long for online application. to the next level, or reward-based, where solving it yields a In this work, we use a constructive approach to guarantee physical reward (key, manuscript, secret area), or both. Each solvability in a computationally inexpensive manner (Shaker level has an entry and at least one exit, but could have mul- et al. 2016). We use a grammar to generate the appropri- tiple. If a level has more than one exit, only one of them ate game elements given an input code. Then, we work can be an open door. The others have to be either hidden or backwards from the solution similarly to Taylor and Par- closed and revealed by solving the level. The programming berry (2011) to ensure solvability with a specific solution language is object oriented; it is similar to Java, but with less heavy syntax. The affordances of the language are: simple section, each module is described in detail using the example instructions (commands applied to objects), simplified for in the figure. loops, if statements, variables, object attributes, and while loops. For our PCG system we considered 4 commands that Abstract Syntax Tree Generation can be applied to objects: Move, Rotate, Open and Stop. For This step takes the input code as a string and extracts the attributes, we considered 2: isMoving (bool) and position abstract syntax tree (AST) from it. This step is simple, but (Vector3 or string). Each object can have multiple attributes, allows the system to be more generalizable since from this but only one type of command applied to it. For example, if step forward, the generation does not depend on the source it is movable it can’t be rotated, but it could have more than language but only on the AST. In the first step of Figure 2, one attribute. Table 1 shows the objects in the game with a we can see that the code presents three command calls: small description of their functionality and the symbols used MoveLeft once, and Rotate(“right”) twice. to describe them in our grammar. Game objects and actions extraction From the AST, we extract each object, a list of commands applied to it, as well as a list of attributes. The same command will be merged together in this format: (com- mand name, arguments, n) where n is the number of times that command is repeated. If the command takes no ar- guments, that field will be empty. For attributes, the for- mat is (attribute name, initial state, desired state). In gen- eral, the desired state is extracted from comparison operators in an if statement or while loop. In the example, we obtain block1(MoveLeft, 1) and block2(Rotate, “right”, 2) . An ex- ample of an attribute would be if we had a stoppable block, we would have (isMoving, true, false) where the block is initially moving and should be stopped in the desired state. Grammar-based solution mini-map generation For each game object, there are possible shapes, or possi- ble gameplay elements it can incorporate. Depending on the game object name and its actions and attributes, the grammar rules are traversed until a final shape is found. The gram- mar rules are extended with probabilities so that some rules are more favored than others. The probability distribution can be chosen as input and can be either uniform (all rules have the same probability of being chosen), favors complex- ity, or favors simplicity where, respectively, rules with more complex/simple shapes will be favored. Further, when a spe- cific rule is applied, a penalty value is added. The penalty value can also be changed as input and can range between 0 (no penalty) and 1 (each rule can only be applied once). When the penalty value for a rule reaches 1, that rule is no longer considered. This penalty is to guarantee that the same rule cannot be applied too many times and that the layout is diverse. The shape obtained from the grammar traversal is Figure 2: Generation Process: 1) getting an abstract syntax placed in the solution mini-map, meaning the shape is placed tree from input code 2) extracting objects and actions 3) cre- as it would be when the map is solved. Figure 2 shows the ating solution and initial mini-maps 4) building paths for solution maps for each of the objects in step 3. Having sepa- each map 5) merging mini-maps rate mini-maps for each object maintains the intended game- play since players have to solve the level in one submission, Methodology however, this limits some gameplay opportunities where ob- The generator takes as input a solution code and outputs a jects can influence each other. level layout that can be solved using that code. The generator is divided in modules to allow for flexibility, modification, Initial mini-map creation and reuse for different purposes. In fact, it is recommended Next, the actions obtained from step 2 are applied to the so- to break the process down into multiple steps to design suc- lution maps in reverse. For example, if the action is MoveUp, cessful grammar based systems (Togelius, Shaker, and Dor- then the object is moved down. This is repeated until all ac- mans 2016). The full process can be seen in Figure 2. In this tions are applied. Path Creation Miscellaneous Placements To create a path in step 4, we use two different algorithms To have a fully functional map, we add the Player tile in front depending on the shape of the object we get from the gram- of the entry. The coding tile is placed in a way that is accessi- mar. If the shape’s gameplay is focused on revealing a re- ble from the entry. Finally, rewards are placed depending on ward, such as fire statues or levers, we use the reward path their type. Closed and hidden doors are placed along walls algorithm, which mostly fills the map with walkable tiles that are accessible. If there are no available, accessible walls, and then removes tiles from the corners up until a predefined the doors are placed and then a path is created to make sure threshold. they are accessible. Hidden keys are placed anywhere on the walkable path. Finally, headers are added to the file, which At the start of the reward path algorithm, all empty tiles in determine the actions of pressure plates, levers, and fires, as both initial and solution maps are filled with walkable blocks well as the objects that can activate them. B. Then, we get all four corner tiles of the map, choose a valid one to remove, and move to its neighbors until no valid neighbors are available. A tile is considered valid if it does Evaluation not break the path in the solution map. We chose this ap- To evaluate our system, we look at metrics related to both proach to have the tiles removed in a systematic manner and the education aspects and game aspects. For the educational not randomly in order to obtain a map that looks closer to requirements, we first check that levels generated can be the hand-designed maps. solved using our input code. Further, we check if the level If the shape’s gameplay is more maze-based, such as a can be solved using alternative codes with the same code block that can be walkable or that can obstruct a path, we length. Finally, we check if the level can be solved with use the maze path algorithm, which takes as input both the shorter alternative codes. We are not worried with longer solution map and initial map to make sure that 1) there is a codes since any level can theoretically be solved using a path between the entry and exit in the solution map, and 2) longer code than what was intended. For a code to be con- there is no path between entry and exit in the initial map. If sidered working, there should be a path from entry to exit, there is no solution that satisfies these conditions, the first and from entry to any reward in the map, after the code is rule is prioritized to assure that, when a level is solved, the applied. If one path is missing, the code is not considered player can make their way from entry to exit. If the second working. rule is not satisfied, this means the player may be able to Alternative codes are generated from the original code, walk to the exit without having to solve the puzzle. by 1) searching for alternative commands that can be ap- In the maze path algorithm, the entry and exit, which we plied to a game object and 2) constructing codes us- refer to as EN and EX, are fixed at the start. After choosing ing each combination of alternative commands. For ex- these points, we find all walkable tiles in the solution map. ample, if our code contains object1.M oveLef t() and Then, we find points (a) and (b) which are respectively the object2.Rotate(“right”), there are 4 Move commands closest tile to EN and EX in the walkable tiles. Finally, the (one in each direction) that can be applied to object1 and 2 shortest paths will be drawn from EN to (a), EX to (b), and Rotate commands (left/right) that can be applied to object2. (a) to (b). The same path is also drawn in the initial map. If This results in 8 different codes: 7 alternative codes and the the resulted path is walkable from EN to EX in the initial original input code. MoreQnbroadly, the number of alternative map, we remove tiles that break that path as long as they codes can be written as i=1 comb(Oi ) where n is the num- do not break the solution path. This again ensures the first ber of objects and comb(Oi ) is the number of combinations condition of solvability of the puzzle. Finally, the last part for object Oi . of the maze path algorithm, which adds tiles back into the Alternative shorter codes are generated by 1) creating a path, is purely for aesthetics reasons and variability to add list of all commands and constructs in the input code and different shapes of paths and not just narrow ones. 2) finding all code combinations that use at most n − 1 of commands and constructs, with n being the size of the list extracted in step 1. For example if our input code contains Mini-map Combination a while loop, an if statement, and two commands, the list Since we could have many mini maps to combine depending length would be 4, and the number of possible combina- on how many programmable objects are in the code, in step tions would be 15. More generally, the number of alterna- Pn−1 n 5, we consider the best way to combine them. We determine tive shorter codes can be written as r=0 r . If (n = 1) the best combination based on the goal of minimizing the the only shorter code possible is an empty code. cost of combination. If two maps can be combined without To evaluate the design of the levels, we look at three met- modification, they have a 0 cost, while the need for modifi- rics: map size, percentage of interactable objects over map cations can result in costs depending on the positions of the size, and percentage of walkable tiles over map size. It is doors E (EN or EX). Combining two maps needs modifica- difficult to find more appropriate metrics to evaluate the lev- tions when they don’t have opposing edges that share a door. els since the gameplay is decided through the input code. In In this scenario, the merged map is made bigger and a path is fact, the input code has the biggest impact over what kind of created between the entry and exit. This process in this step levels would be generated. Further, the variety of objects and is minimized by finding the best combination of the maps game mechanics is limited by what’s afforded in the original that guarantees the minimum cost. game. Evaluating the map shape is also not interesting since Lvl Elements Gen. Time (s) Input Sol. Alt. Sol. Alt. w/ Sol. Short Sol. Short w/ Sol. Size 0 1 moving block 0.11 ± 0.03 100% 4 49.5% 1 13.5% 99.34 11 2 moving blocks 0.39 ± 0.07 100% 16 72.1% 3 24.8% 240.98 12 moving block, moving statue 1.17 ± 0.6 100% 64 67.2% 7 27.4% 318.24 23 1 rotating fire statue 0.12 ± 0.03 100% 2 0% 1 0% 160.62 31 3 rotating blocks 0.51 ± 0.1 100% 8 91.9% 7 37.2% 464.72 32 for loop and 2 moving blocks 0.54 ± 0.16 100% 16 70.6% 7 36.4% 350.38 42 lever, door, conditional 0.06 ± 0.01 100% NA NA NA NA 89.04 46 stoppable block, while loop, 0.12 ± 0.02 100% NA NA 1 9.9% 249.87 conditional, pressure-plate avg 0.38 ± 0.13 100% 18.33 47.35% 3.85 21.31% 246.64 Table 2: Results of 1000 runs for 7 different game levels; with uniform distribution, threshold = 2, grammar penalty = 0.5. Input Sol. = the input code is a solution; Alt. Sol. / Short Sol. = number of possible alternative / shorter codes; Alt. w/ Sol. / Short w/ Sol. = percentage of times there was at least 1 alternative/shorter code that is a solution; Size = average size of the map in tiles.) Figure 3: Expressive range for each level in terms of percentage of walkable and interactable tiles (1000 runs, 0.5 penalty, 2 threshold). X axis: % walkable (0 to 0.5). Y axis: % interactable (0 to 0.1) player movements are restricted to the path and the player Overall, 21.31% of the levels generated had working shorter cannot fall off, meaning there is no difficulty attached to the solutions (Short w/ Sol.), with again variations across lev- layout of the map. els. Levels with more lines of code and more objects would have more possible alternative solutions and therefore more Results chances for them to succeed. For example, levels (1 2, 3 1, We ran the generator with the solution codes from 8 differ- 3 2) with the highest number of shorter solutions (7), unsur- ent levels in the game, including a variety of game objects prisingly, have the highest rate of shorter solutions solving and constructs. Every code was run 1000 times and the re- the puzzle. Looking at specific levels, such as level 4 2, al- sults are presented in Table 2. Overall, every level generated ternative codes and shorter codes are not applicable. This was solvable using the input code, which is expected since comes from the original design of such levels. This level’s it is guaranteed by construction. Further, on average 47.35% code cannot be modified in the game. The gameplay consists of the levels generated had an alternative working solution of understanding the code and making appropriate changes (Alt. w/ Sol.), which means about half of the levels generated in the environment so that when the code executes, it re- provide different equally difficult ways to solve the prob- veals a reward. Another particular level is level 4 6 where lem. This can be a nice balance between levels that have a we haven’t defined alternative codes for the Stop or Open unique solution vs levels that offer the players multiple ways commands which makes alternative codes not possible. to solve them. From Table 2, we can see that the percentage To analyze the variety of the levels generated, we looked varies considerably across levels, which is again expected. at the expressive range of the generator in accordance to the For example, in level 2 3 the game object can only be re- percentage walkable (X axis, 0 to 0.5) and interactable (Y ward based, which makes it impossible to have alternative axis 0 to 0.1) tiles over the size of the map. In figure 3, we solutions since the only way to get the reward would be to can see how the heat maps change depending on the level. use the input code. On the other hand, levels that are purely We notice that the expressive range tightly follows the de- maze-based and have no rewards such as 3 1 have a much sign and the possibilities allowed by the game, as well as the higher rate of alternative solutions (91.9%). These levels size of the map. For example, level 0 has a moving block would also have the highest rate of short solutions working. which has 1/3 chance of yielding a reward thus making the Figure 4: Expressive range with probability distribution variation for level 1 2. From left to right: favors simplicity, uniform, favors complexity. X axis: % walkable (0 to 0.5). Y axis: % interactable (0 to 0.1) codes. These levels may or may not be desirable. In some cases, the designer may want levels that have an obvious longer solution and perhaps a shorter cleverer one. We do not claim that this is the case with the levels generated. But, we point out that it may be desirable in some special case, and the decision can be left up to the designer. If we want to completely remove the shorter solutions, we could add constraint checkers at different stages of the generation and discard parts of the map that violate certain conditions. An- Figure 5: Examples of generated levels for level 1 2. From other way is to include the maps created by the shorter codes left to right, solvable with only input code, solvable with in the generation process and make sure none of them has a input and alternative, solvable with shorter code. solution when creating the paths. This will increase the gen- eration time, but we believe it will still be reasonable for rate of interactable objects mostly low with a few scattered in-game generation given that it is now at 0.38 seconds on higher rates. On the other hand, levels 1 2 and 4 6 are re- average. While our approach is applied to a programming ward based levels which gives a higher rate of walkable game, the same concept can be reproduced in a puzzle game tiles. Levels with many interactable objects (level 3 2 and where instead of code, the input would be game play vocab- 4 6) tend to have bigger maps which makes the percentages ulary as in (Van der Linden, Lopes, and Bidarra 2013). of interactable and walkable much more concentrated. Fig- One limitation of this work is that the creation of al- ure 4 shows the effects of varying the probability distribution ternative solutions is specific to the gameplay and affor- in level 2 1. This level was chosen because it has a combi- dances of the game and cannot be easily imported into an- nation of objects that can be maze-based or reward-based other game. Another limitation is that while inputting code which makes it more representative. In this level, players grants full control to the designer, it is not accessible to need to move a statue to the right twice and move a block non-programmers or even programmers who are not famil- up once. We can observe significant changes between the iar with the programming language of the game. One way to distribution that favors simplicity and the uniform one. The tackle this is to build a code generator that will take as in- change is not that noticeable between the uniform distribu- put coding constructs and synthesize valid code that can be tion and the one that favors complexity. However, while the input to this generator. That way, the user would only select heat maps seem similar, the brightest area on the complex the learning constructs they want. one is on the higher end and the brightest area for the uni- form one is on the lower end of the shape. Figure 5 shows some examples of generated levels for the Conclusion code of level 2 1. The left example shows a level that can In this paper, we presented a grammar based modular ap- only be solved with input code, players need to move the proach to generate levels in a programming puzzle game. fire statue to get a key and move block1 on a pressure plate The approach works backwards from a solution code and to reveal a hidden block. In the middle example, block1 can uses both the solution map and the initial map to ensure that be moved either up or right to complete the path allowing levels are solvable using the input code. The levels gener- for one alternative solution. However, in the right exam- ated allow variation in the solution space through alterna- ple, block1 does not need to be moved at all and only the tive codes while minimizing shorter, more trivial solutions. statue needs to be moved to clear the path, which results in However, some of them still allow shorter codes. In the fu- a shorter solution. ture, we want to improve on the approach, build a user- friendly interface and conduct a user-study with designers. Discussion & Limitations Further, we would like to work on integrating procedurally The results show that the generator successfully creates lev- generated levels within the game according to some player els that are solvable using the desired input code, however, model that will inform us about the coding constructs that some of them are still solvable by shorter “less difficult” the player needs practice with. Acknowledgements 2018. Procedural content generation via machine learning This research is supported by NSF AISL (Advancing Infor- (PCGML). IEEE Transactions on Games 10(3):257–270. mal STEM Learning) Award Id: 1810972. Taylor, J., and Parberry, I. 2011. Procedural generation of Sokoban levels. In Proceedings of the International North References American Conference on Intelligent Games and Simulation, 5–12. De Kegel, B., and Haahr, M. 2019. Procedural puzzle gener- ation: a survey. IEEE Transactions on Games 12(1):21–40. Togelius, J., and Shaker, N. 2016. The search-based approach. In Procedural Content Generation in Games. Dong, Y., and Barnes, T. 2017. Evaluation of a template- Springer. 17–30. based puzzle generator for an educational programming game. In Thirteenth Artificial Intelligence and Interactive Togelius, J.; Yannakakis, G. N.; Stanley, K. O.; and Browne, Digital Entertainment Conference. C. 2011. Search-based procedural content generation: A taxonomy and survey. IEEE Transactions on Computational Font, J. M.; Izquierdo, R.; Manrique, D.; and Togelius, J. Intelligence and AI in Games 3(3):172–186. 2016. Constrained level generation through grammar-based evolutionary algorithms. In European Conference on the Ap- Togelius, J.; Shaker, N.; and Dormans, J. 2016. Grammars plications of Evolutionary Computation, 558–573. Springer. and L-systems with applications to vegetation and levels. In Procedural Content Generation in Games. Springer. 73–98. Harteveld, C.; Smith, G.; Carmichael, G.; Gee, E.; and Stewart-Gardiner, C. 2014. A design-focused analysis of Traichioiu, M.; Bakkes, S.; Roijers, D. M.; et al. games teaching computer science. Proceedings of Games + 2015. Grammar-based procedural content generation from Learning + Society 10:1–8. designer-provided difficulty curves. In Proceedings of the 10th International Conference on the Foundations of Digi- Jemmali, C.; Bunian, S.; Mambretti, A.; and El-Nasr, M. S. tal Games. 2018. Educational game design: an empirical study of the Valls-Vargas, J.; Zhu, J.; and Ontañón, S. 2017. Graph effects of narrative. In Proceedings of the 13th International grammar-based controllable generation of puzzles for a Conference on the Foundations of Digital Games, 34. ACM. learning game about parallel programming. In Proceedings Jemmali, C.; Kleinman, E.; Bunian, S.; Almeda, M. V.; of the 12th International Conference on the Foundations of Rowe, E.; and El-Nasr, M. S. 2019. Using game design Digital Games, 1–10. mechanics as metaphors to enhance learning of introductory Van der Linden, R.; Lopes, R.; and Bidarra, R. 2013. De- programming concepts. In Proceedings of the 14th Inter- signing procedurally generated levels. In Ninth Artificial national Conference on the Foundations of Digital Games, Intelligence and Interactive Digital Entertainment Confer- 1–5. ence. Miljanovic, M. A., and Bradbury, J. S. 2018. A review of serious games for programming. In Joint International Conference on Serious Games, 204–216. Springer. Park, K.; Mott, B. W.; Min, W.; Boyer, K. E.; Wiebe, E. N.; and Lester, J. C. 2019. Generating educational game lev- els with multistep deep convolutional generative adversarial networks. In 2019 IEEE Conference on Games (CoG), 1–8. IEEE. Shaker, N.; Liapis, A.; Togelius, J.; Lopes, R.; and Bidarra, R. 2016. Constructive generation methods for dungeons and levels. In Procedural Content Generation in Games. Springer. 31–55. Smith, A. M., and Mateas, M. 2011. Answer set program- ming for procedural content generation: A design space ap- proach. IEEE Transactions on Computational Intelligence and AI in Games 3(3):187–200. Smith, G., and Whitehead, J. 2010. Analyzing the expres- sive range of a level generator. In Proceedings of the 2010 Workshop on Procedural Content Generation in Games, 1– 7. Smith, A. M.; Butler, E.; and Popovic, Z. 2013. Quantify- ing over play: Constraining undesirable solutions in puzzle design. In Proceedings of the 8th International Conference on the Foundations of Digital Games, 221–228. Summerville, A.; Snodgrass, S.; Guzdial, M.; Holmgård, C.; Hoover, A. K.; Isaksen, A.; Nealen, A.; and Togelius, J.