=Paper=
{{Paper
|id=Vol-2862/paper12
|storemode=property
|title=Grammar Based Modular Level Generator for a Programming Puzzle Game
|pdfUrl=https://ceur-ws.org/Vol-2862/paper12.pdf
|volume=Vol-2862
|authors=Chaima Jemmali,Carter Ithier,Seth Cooper,Magy Seif El-Nasr
|dblpUrl=https://dblp.org/rec/conf/aiide/JemmaliICE20
}}
==Grammar Based Modular Level Generator for a Programming Puzzle Game==
https://ceur-ws.org/Vol-2862/paper12.pdf
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.