Authors Andrea De Seta Mario Alviano
License CC-BY-4.0
An Application of ASP for Procedural Content
Generation in Video Games
Andrea De Seta, Mario Alviano
DEMACS, University of Calabria, Via Bucci 30/B, 87036 Rende (CS), Italy
Abstract
Procedural content generation eases and accelerates the development of video games by creating data
algorithmically through a combination of human-generated assets and algorithms usually coupled with
computer-generated randomness. This paper presents a use case of Answer Set Programming (ASP) for
procedural content generation of levels in a rougelike video game powered by the Godot Engine. The
main elements of a set of human-generated rooms are represented by ASP facts, among them positions of
doors, presence of treasures and power-ups. Within this knowledge, ASP is asked to generate dungeons
satisfying a few conditions, among them the correct positioning of rooms, the absence of unreachable
rooms and constraints on the occurrences of rooms. Scalability of ASP in this context is evaluated
empirically, showing that it can generate in few seconds levels that comprise thousands of rooms.
1. Introduction
Video game industry, i.e. the industry involved in the development, marketing and monetization
of video games, has grown sensibly in the recent years, and its annually generated sales are
in the order of hundreds of billions of dollars. The development of a video game is the first
step to enter such an industry, and several frameworks are nowadays available to start with
a set of common primitives that can be combined to achieve appealing results in relatively
short time. Among them there is the Godot Engine (https://godotengine.org/), a completely free
and open-source game engine under MIT license, providing a huge set of common tools that,
especially for 2D-games, significantly accelerate all the development phase.
Further acceleration in the development of video games can be provided by techniques that
go under the name of procedural content generation (PCG), and essentially consist of algorithms
that automatically create levels, maps, weapons, background scenery, and music for video
games [1, 2]. The idea is not new, and actually exploited already in the ’70s in historical
titles such as pedit5 (https://en.wikipedia.org/wiki/Pedit5) to circumvent the limited amount
of computational resources [3]. Many video games followed the idea of pedit5 and took
advantage of PCG. Later, those video games were classified as rougelike, a term originated from
’90s USENET newsgroups. Even if the exact definition of a rougelike game remains a point of
debate in the video game community, some characteristics are clearly identified. Specifically,
rougelike is a subgenre of role-playing video games characterized by a dungeon crawl through
PCG levels, turn-based gameplay, grid-based movement, and permanent death of the player
character.
CILC 2022: 37th Italian Conference on Computational Logic, June 29 – July 1, 2022, Bologna, Italy
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)
In this work the term rougelike is slightly abused and used to refer to video games that have all
the aforementioned characteristics but turn-based gameplay and grid-based movement. Stated
differently, in the following we consider a video game characterized by a dungeon crawl through
PCG levels, real-time gameplay, grid-based positioning but free movements, and permanent death
of the player character. The presented game is entitled WizardSet, is powered by the Godot
Engine and takes advantage of Answer Set Programming (ASP; [4, 5, 6]) for PCG of levels. In a
nutshell, the idea underlying WizardSet is to design some elements of the video game with the
Godot Engine, represent such elements in a format understandable by ASP systems, and then
combine such a representation with an ASP encoding to delegate the generation of a complete
level to an ASP reasoner. This way, levels are generated when needed, providing a unique
experience to the player for each game. After introducing the required background knowledge
(Section 2), we will detail on the PCG implemented in WizardSet (Section 3), and report on the
result of an experiment aimed at assessing the scalability of the proposed procedure (Section 4).
2. Background
The Godot Engine provides an Integrated Development Environment to design scenes, where a
scene represents an element of the video game and is characterized by a tree and possibly a
script. The tree of a scene is made of nodes of different nature that can be used to associate
sprites and physical properties to the element of the video game. Scripts are usually written
in GDScript, a high-level, dynamically typed programming language with a syntax similar to
Python (but a few other languages are supported as well).
ASP is a rule-based language supporting object variables and negation under stable model
semantics. Object variables are removed by means of intelligent grounding, and stable models
are searched by conflict-driven clause learning algorithms. ASP systems extend the basic
language of ASP with several constructs for representing common knowledge, among them
integer arithmetic and aggregates. The reader is referred to the ASP Core 2 [7] format for
details.
3. Procedural Content Generation within ASP
WizardSet represents a few key features of its rooms in terms of ASP facts:
• room(𝑟 ),
for each available room, where 𝑟 is a positive integer identifying the room (the
current release of WizardSet provides 17 rooms with different layout and features);
• room_door(𝑟,𝑙), if room 𝑟 has a door in the wall 𝑙, where 𝑙 is one of north, south, west,
and east;
• room_flag(𝑟,𝑓 ), if room 𝑟 has feature 𝑓 , where 𝑓 is among initial, boss, and treasure;
• flag_bounds(𝑓 ,min ,max ), for each represented feature, where min and max are in-
tegers to bound the number of rooms with feature 𝑓 in a level; in particular, we fix
flag_bounds(initial,1,1), flag_bounds(boss,1,1), and
flag_bounds(treasure,0,1), i.e. there must be exactly one initial room and boss room,
and at most one treasure room in each generated level.
Figure 1: Design view of room 4 of WizardSet, having a door in the east wall and containing a
treasure. The room is represented by the following ASP facts: room(4), room_door(4,east), and
room_flag(4,treasure).
An example room and the associated ASP facts are reported in Figure 1. Additionally, the
ASP encoding is enriched with the following facts to represent movements in the four cardinal
directions:
delta(north,-1, 0). opposite(north,south).
delta(south, 1, 0). opposite(south,north).
delta(west, 0,-1). opposite(west, east).
delta(east, 0, 1). opposite(east, west).
The reasoning core of the ASP encoding empowering WizardSet is parameterized by the
size of the grid to generate (constants rows and cols), the number of rooms to deploy (constant
required_rooms), and the health points of the player (constant hp). The ASP encoding non-
deterministically assigns rooms to cells of the grid, ensuring that a few constraints are satisfied.
The following ASP rules are used (and described below):
𝑟1 : {assign(X,Y,nil); assign(X,Y,R) : room(R)} = 1 :-
X = 1..rows, Y = 1..cols.
𝑟2 : assign(0, Y, nil) :- Y = 0..cols+1.
𝑟3 : assign(rows+1,Y, nil) :- Y = 0..cols+1.
𝑟4 : assign(X, 0, nil) :- X = 0..rows+1.
𝑟5 : assign(X, cols+1,nil) :- X = 0..rows+1.
𝑟6 : :- #count{X,Y : assign(X,Y,R), R != nil} != required_rooms.
𝑟7 : :- assign(X,Y,R), room_door(R,L), delta(L,DX,DY),
20
10 models
100 models
1,000 models
Running time (seconds) 15
10
5
0
0 10 20 30 40 50 60 70 80 90
Size of the grid (𝑛)
Figure 2: clingo performance on 𝑛 × 𝑛 level generation
assign(X+DX,Y+DY,R'), opposite(L,L'), not room_door(R',L').
𝑟8 : :- flag_bounds(F,MIN,MAX),
not MIN <= #count{X,Y : assign(X,Y,R), room_flag(R,F)} <= MAX.
𝑟9 : reachable(X,Y) :- room_flag(R,initial), assign(X,Y,R).
𝑟10 : reachable(X+DX,Y+DY) :- reachable(X,Y), assign(X,Y,R),
room_door(R,L), delta(L,DX,DY).
𝑟11 : :- assign(X,Y,R), R != nil, not reachable(X,Y).
𝑟12 : spawn_hp_potion(R) :- room_flag(R,initial), hp <= 2.
The assignment itself is generated by rule 𝑟1 , which associates each cell with a room or with
the nil value (to denote a non-playable cell of the grid, i.e. a cell not containing any room).
Rules 𝑟2 –𝑟5 introduce a border of non-playable cells, so to clearly delimit the playable boundary
of the generated level. Rule 𝑟6 enforces that the number of assigned rooms is the required
one, and rule 𝑟7 ensures the correct placement of doors. Rule 𝑟8 ensures that the presence of
represented features in the required amount. Rules 𝑟9 –𝑟11 impose that all playable cells are
actually connected. Finally, rule 𝑟12 provides an example of power-up that can be placed in
some rooms of the generated dungeon; in this case, the power-up is a health potion to be placed
in the initial room if the player starts with few health points.
4. Implementation and Experiment
WizardSet is open-source (https://github.com/Tatanka4/WizardSet). The
ASP system adopted for PCG is clingo 5.5.0 [8], and communication between the Godot
600
10 models
100 models
1,000 models
450
Memory consumption (MiB)
300
150
0
0 10 20 30 40 50 60 70 80 90
Size of the grid (𝑛)
Figure 3: clingo memory consumption on 𝑛 × 𝑛 level generation
Engine and clingo is achieved by synchronous system calls and file sharing. Parameters for
the generation of levels are adjusted to increase the size of the grid and the number of playable
cells, and therefore the expected difficulty. On ordinary playing sessions the time required
for PCG is negligible, and usually below a second. Therefore, in order to empirically evaluate
the scalability of the proposed ASP encoding, we designed a first experiment to measure the
execution time required by clingo to generate squared grids of increasing size 𝑛 × 𝑛, with the
number of requested rooms set to 𝑛×𝑛 2 . All tests are run on an Intel Xeon 2.4 GHz with 16 GiB
of memory. Time and memory were limited to 20 seconds and 4 GiB (WizardSet is expected
to be run on laptops and low-end PCs, and level generation must stay in the order of a few
seconds).
Results are shown in Figure 2 for different settings of the number of models asked to clingo;
in fact, to increase randomness in the generation of levels, WizardSet selects one model among
several that are produced by clingo. Additionally, we observed that the generation of levels
is unfeasible without limiting the number of models; the reason is to be attributed to the
high number of possible models, which is already 2,064 for grids of size 4 × 4 (0.1 seconds of
computation) and 1,360,822 for grids of size 5 × 5 (89 seconds of computation). We therefore
ran all test cases by limiting the number of models to 10, 100 and 1,000. Within these limits,
levels can be generated in less than 20 seconds up to grids of size 89 × 89. Figure 3 reports
the memory consumption for producing 10, 100 and 1,000 models, and it can be observed that
almost the same consumption was measured. Given the results of our experiment, in the release
of WizardSet we fixed the number of models to ask to clingo to 1,000 models, as there is no
significant performance gain in asking for less models.
5. Conclusion
Previous works in the literature have already shown applications of ASP to video games. For
example, ASP is used in Angry-HEX [9], an AI that can play Angry Birds, and in ThinkEngine
[10, 11], an integration of ASP in Unity. ASP can be used profitably for PCG in video games as
well, and the idea was already used in the literature [12, 13, 14]. This work provides another
concrete example of ASP-powered PCG by presenting the first combination of the Godot Engine
with an ASP system to generate levels of a rougelike video game. In our experience, the main
advantage of adopting ASP for this task relies in the declarative power of the language, thanks
to which constraints and desiderata for PCG can be specified succinctly in a few lines of code. A
similar observation is reported in [14], whose approach to generate dungeons is to partition the
space in rectangular areas, and then generate a random room in each area; in this case, the ASP
encoding models desiderata on the generation of rooms. In our approach, rooms are defined
by the programmer, their features represented in ASP, and such a knowledge base is used to
generate a dungeon. Moreover, our ASP representation is suitable for future extensions of the
approach, as for example by enriching the knowledge base with other features of the rooms so
to control the number of enemies and power-ups in the generated levels.
Acknowledgments
This work was partially supported by the projects PON-MISE MAP4ID (CUP B21B19000650008)
and PON-MISE S2BDW (CUP B28I17000250008), by the LAIA lab (part of the SILA labs) and by
GNCS-INdAM.
References
[1] M. Hendrikx, S. A. Meijer, J. V. D. Velden, A. Iosup, Procedural content generation
for games: A survey, ACM Trans. Multim. Comput. Commun. Appl. 9 (2013) 1:1–1:22.
doi:10.1145/2422956.2422957.
[2] J. Togelius, G. N. Yannakakis, K. O. Stanley, C. Browne, Search-based procedural content
generation: A taxonomy and survey, IEEE Trans. Comput. Intell. AI Games 3 (2011)
172–186. doi:10.1109/TCIAIG.2011.2148116.
[3] N. Brewer, Computerized dungeons and randomly generated worlds: From rogue to
minecraft, Proc. IEEE 105 (2017) 970–977. doi:10.1109/JPROC.2017.2684358.
[4] M. Gelfond, V. Lifschitz, Classical negation in logic programs and disjunctive databases,
New Generation Computing 9 (1991) 365–386. doi:10.1007/BF03037169.
[5] V. W. Marek, M. Truszczyński, Stable models and an alternative logic programming
paradigm, in: The Logic Programming Paradigm – A 25-Year Perspective, Springer Verlag,
1999, pp. 375–398. doi:10.1007/978-3-642-60085-2_17.
[6] I. Niemelä, Logic programming with stable model semantics as constraint programming
paradigm, Annals of Mathematics and Artificial Intelligence 25 (1999) 241–273. doi:10.
1023/A:1018930122475.
[7] F. Calimeri, et al, Asp-core-2 input language format, Theory Pract. Log. Program. 20 (2020)
294–309. doi:10.1017/S1471068419000450.
[8] M. Gebser, R. Kaminski, B. Kaufmann, M. Ostrowski, T. Schaub, P. Wanko, Theory solving
made easy with clingo 5, in: M. Carro, A. King (Eds.), TC of ICLP’16, volume 52 of OASIcs,
Schloss Dagstuhl, Germany, 2016, pp. 2:1–2:15.
[9] F. Calimeri, et al., Angry-hex: An artificial player for angry birds based on declarative
knowledge bases, IEEE Trans. Comput. Intell. AI Games 8 (2016) 128–139. doi:10.1109/
TCIAIG.2015.2509600.
[10] D. Angilica, G. Ianni, F. Pacenza, Tight integration of rule-based tools in game development,
in: M. Alviano, G. Greco, F. Scarcello (Eds.), AI*IA 2019, Rende, Italy, November 19-
22, 2019, Proceedings, volume 11946 of LNCS, Springer, 2019, pp. 3–17. doi:10.1007/
978-3-030-35166-3_1.
[11] F. Calimeri, S. Germano, G. Ianni, F. Pacenza, S. Perri, J. Zangari, Integrating rule-based AI
tools into mainstream game development, in: C. Benzmüller, F. Ricca, X. Parent, D. Roman
(Eds.), RuleML+RR 2018, Luxembourg, September 18-21, 2018, volume 11092 of LNCS,
Springer, 2018, pp. 310–317. doi:10.1007/978-3-319-99906-7_23.
[12] X. Neufeld, S. Mostaghim, D. Perez Liebana, Procedural level generation with answer set
programming for general video game playing, 2015, pp. 207–212. doi:10.1109/CEEC.
2015.7332726.
[13] A. M. Smith, M. Mateas, Answer set programming for procedural content generation: A
design space approach, IEEE Trans. Comput. Intell. AI Games 3 (2011) 187–200. doi:10.
1109/TCIAIG.2011.2158545.
[14] F. Calimeri, S. Germano, G. Ianni, F. Pacenza, A. Pezzimenti, A. Tucci, Answer set pro-
gramming for declarative content specification: A scalable partitioning-based approach,
in: AI*IA, volume 11298 of Lecture Notes in Computer Science, Springer, 2018, pp. 225–237.