Work-in-Progress CHI PLAY '20 EA, November 2–4, 2020, Virtual Event, Canada
To Make Sense of Procedurally Generated Dungeons
Simon Tolinsson Alberto Alvarez
Alexander Flodhag Jose Font
simontolinsson@[Link] [Link]@[Link]
alexander_flodhag@[Link] [Link]@[Link]
Malmö University Department of Computer Science and Media Technology,
Malmö University
ABSTRACT
With the growth of procedural content generation in game develop-
ment, there is a need for a viable generative method to give context
and make sense of the content within game space. We propose pro-
cedural narrative as context through objectives, as a useful means
to structure content in games. In this paper, we present and de-
scribe an artifact developed as a sub-system to the Evolutionary
Dungeon Designer (EDD) that procedurally generates objectives
for the dungeons created with the tool. The quality of the content
within rooms is used to generate objectives, and together with the
distributions and design of the dungeon, main and side objectives Figure 1: The main components in EDD. (a) A basic room,
are formed to maximize the usage of game space and create a proper (b) different placeable tiles, (c) micro patterns and (d) meso
context. patterns [3].
CCS CONCEPTS
in a dangerous dungeon, then that creates interaction between the
• Theory of computation → Evolutionary algorithms; • Ap-
user and the content, which creates the needed context.
plied computing → Computer games; • Software and its en-
The Evolutionary Dungeon Designer (EDD) is a mixed-initiative
gineering → Interactive games.
design tool used for creating and generating dungeons [5]. This
paper gathers the first step towards implementing a sub-system
KEYWORDS
for EDD, which procedurally generates objectives for dungeons.
Procedural Content Generation, Mixed-Initiative Co-Creativity The current sub-system gathers and continuously adapts to the de-
ACM Reference Format: signer’s dungeon to place different objectives based on the rooms’
Simon Tolinsson, Alexander Flodhag, Alberto Alvarez, and Jose Font. 2020. content. Through this, the designer focuses on creating the dungeon
To Make Sense of Procedurally Generated Dungeons. In Extended Abstracts while seamlessly, they are provided with the different generated ob-
of the 2020 Annual Symposium on Computer-Human Interaction in Play (CHI jectives. We evaluate the artifact’s utility, quality, and efficacy based
PLAY ’20 EA), November 2–4, 2020, Virtual Event, Canada. ACM, New York, on how well the objectives represent the layout of the dungeon
NY, USA, 4 pages. [Link]
with experimental scenarios.
1 INTRODUCTION 2 RELATED WORK
Procedural content generation (PCG) has found itself in the spot-
light within game development with games such as Minecraft [17],
2.1 The Evolutionary Dungeon Designer
No Man’s Sky [13], and Spelunky [9], improving replayability, re- EDD is a mixed-initiative tool for designers to create dungeons as a
ducing the developers’ workload, and fostering the designers’ cre- set of interconnected tile-based rooms [5]. Each tile in a room can be
ativity [4, 12, 18]. However, some type of narrative or context is modified to represent different types of paths, obstacles or rewards,
required to make sense of the PCG content when implemented into and are used to form inventorial (Fig. 1.b) or spatial (Fig. 1.c) micro
the game space [8]. An example of narrative is objectives. If there is patterns. These micro patterns can be further combined to form
an objective within the content, for example, finding a sacred gem meso patterns (Fig. 1.d) such as treasure or guarded rooms. Fur-
thermore, as the designer creates rooms, EDD dynamically offers
Permission to make digital or hard copies of all or part of this work for personal or procedurally generated room suggestions through the Interactive
classroom use is granted without fee provided that copies are not made or distributed
for profit or commercial advantage and that copies bear this notice and the full citation Constrained MAP-Elites, using such patterns as evaluation and
on the first page. Copyrights for components of this work owned by others than ACM continuously adapting to the designer’s design [6].
must be honored. Abstracting with credit is permitted. To copy otherwise, or republish,
to post on servers or to redistribute to lists, requires prior specific permission and/or a
fee. Request permissions from permissions@[Link]. 2.2 Procedural Generation of Game Narrative
CHI PLAY ’20 EA, November 2–4, 2020, Virtual Event, Canada Interactivity and narrative have conflicting demands [14]. With
© 2020 Association for Computing Machinery.
ACM ISBN 978-1-4503-7587-0/20/11. . . $15.00 narrative, the author decides the direction of the flow, while inter-
[Link] activity turns to the player for motive power. Straying from the
384
Work-in-Progress CHI PLAY '20 EA, November 2–4, 2020, Virtual Event, Canada
author’s path may make for a less satisfying story, but restricting
the player’s freedom of actions will have the same effect on the
game. But game designers are not only storytellers, but they also
sculpt and design game worlds and spaces.
Generated content needs context in the game space. A lack of
context may negatively affect user experience, with the content
being perceived as empty or meaningless [8]. The limitations of
a story are related to the quest combinations available. By under-
standing the structure of quests, we can also understand the limits
and potential of these kinds of games and how to create rich, open Figure 2: Every type of dungeon objective as both main ob-
game worlds and tell interesting stories within them [1]. jective (green) and side objective (blue). The icons represent
The common factor with objectives in games is to provide the the different types of objectives (a) “Defeat the enemies”, (b)
player a reason to further progress through the game [8]. When “Find the treasure” and (c) “Defeat the boss”.
generating content for game space, narrative, or context, needs to
be generated as well. In action-adventure games, the level design is
essential, and when procedurally generating levels for these games, Dead end. Dead ends have a higher chance of hosting interesting
it is best to break down the generation process in two steps, one content for the player [8]. Therefore, to not make the outskirts of
for generating game space and one for generating missions [10]. the dungeon feel meaningless, dead ends are prioritized locations
Charbitat bases narrative generation on sets of tiles, which par- for objective placement.
titions the game space and creates a graph that keeps track of the Distance to the player. Placing all objectives close to the start po-
player’s position. Through this, the system evaluates new possi- sition, preventing full space exploration, would break the players’
ble objectives to generate that would suit better. This evaluation immersion [14]. Therefore, large distances (measured in rooms)
takes in mind previous objectives and actions done by the player, from the player are encouraged when placing objectives.
resulting in a more adaptive experience while also increasing the
replayability [8]. Connectivity. Rooms connected to many rooms have a higher chance
Procedural narrative generation is often approached split into of the player passing through them than those with fewer connec-
two tasks, plot and space, either automatically or manually gener- tions. Therefore, to foster the exploration of these rooms, rooms
ated [2, 10, 11, 15]. The plot is defined as a set of events with an with fewer connections to other parts of the dungeon will be prior-
overall structure that represents both the temporal ordering and the itized to have an objective.
causal relations between the events. Space includes the characters,
Quality. The objectives are based on the existing meso patterns in
settings, props, and anything which is present either physically or
the room. Each meso pattern receives a quality score [7], that when
abstractly in the space of the narrative. By generating space, they
combined, create the quality of the room.
also generate context for it, thus creating a unique narrative for
Objectives are then sorted in sequential steps. The policy for,
each possible outcome of the generative process.
any given pair of objectives, choosing the more relevant one, is:
(1) Return the objective that is set in a dead end. If both are, or
3 GENERATING OBJECTIVES FOR neither of them is, then
DUNGEONS (2) return the objective with the largest distance to the player.
Using the room’s meso patterns and their qualities, each room is If both lie at the same distance, then
assigned an objective described in Figure 2: defeat the enemies, (3) return the objective with lower connectivity. In case of a tie,
find the treasure, defeat the boss, except the initial room, which is then
always excluded to avoid placing objectives where the player enters (4) return the objective with the highest quality score.
the dungeon. When all rooms have been assigned an objective, we
calculate the number of objectives 𝑁𝑜𝑏 𝑗 needed for the dungeon 4 RESULTS AND DISCUSSION
based on its size and layout. Furthermore, the number of objectives We have carried out a total of 14 simulations in EDD for testing
is calculated as 𝑁𝑜𝑏 𝑗 = max(1, 𝐷𝐸 + ((𝑅 − 𝐷𝐸)/𝐾)), where 𝐷𝐸 the objective generation with a representative set of layouts, room
is the number of dead ends, 𝑅 is the total number of rooms, and sizes, and content. In all figures and due to its importance in the
𝐾 is an adjusting variable. High values for 𝐾 lower the number calculations, the initial room is highlighted in yellow. Out of exper-
of objectives per normal (non-dead end) rooms. The designer can imentation, 𝐾 was set to 4, meaning that one additional objective
trigger the objective generation at any time in EDD by pressing a is generated per every 4 normal rooms in the dungeon.
toggle objectives button. Figure 3 shows the simplest scenario (two empty interconnected
All objectives are then sorted due to their relevance. The most rooms), where the dead end (b) turns into a "Defeat the boss" main
relevant objective is set as the only main objective of the dungeon. objective, leaving the initial room (a) as is.
Side objectives are subsequently assigned in descendant relevance Figure 4 shows two different small sequential scenarios. In simu-
order until the amount of objectives needed is reached. The sorting lation (a), the initial room is the leftmost one, and the two rightmost
algorithm for objective relevance evaluation calculates the follow- rooms become the side objective and the main objective. This spe-
ing metrics: cific order makes use of all the available game space. However, in
385
Work-in-Progress CHI PLAY '20 EA, November 2–4, 2020, Virtual Event, Canada
quality score. Notice how a similar layout in (b) places main and
side objectives differently based on a different start position, trying
to maximizing space usage.
Figure 3: The most simplistic layout of a dungeon with a
main objective (green).
Figure 7: Two large circular dungeon layouts without dead
ends.
Figure 7 generates objectives for larger circular dungeons with
no dead ends and (a) no content in any of the corners, and (b) corner
rooms with meso patterns. In (a), the lack of content in the cor-
ner rooms makes the system choose objectives in the neighboring
rooms to the furthest corner. Being both equally distant from the
initial room, the “Defeat the boss” has a higher quality and is then
Figure 4: Small single-path dungeon layouts. marked as the main goal. In (b), the corners of the dungeon lay-
out contain content, and the system makes use of this to generate
objectives in every corner of the dungeon to maximize the usage
simulation (b), the initial room is the second to the left. The system
of game space. The remaining non-corner “Find the treasure” side
adapts to this change by placing the side objective to the left of
objective is prioritized over the other rooms without an objective
the start position to use both dead ends and maximizing the game
based on its distance from the initial room.
space usage.
Figure 8: Large circular dungeons layout with dead ends.
Figure 5: Small circular dungeons.
Figure 5 shows two small scenarios without any dead ends. Only Figure 8 introduces large circular dungeons with dead ends. In
one objective (the main one) is placed under these configurations. (a), the initial room is part of the circular center of the dungeon
In both cases, to utilize most of the dungeon layout, the room on layout, and the system generates objectives in the various dead
the opposing side of the initial room gets assigned with the main ends of the layout to utilize the game space. In addition, there is a
objective. final side objective of type “Defeat the boss” which is prioritized
because of both its distance from the initial room and its lower
connectivity.
In (b), the system adapts to the placement of the initial room
in the dead end that hosted the main objective in (a). The main
objective is relocated to another dead end, being one side objective
now placed inside the inner circular structure of the layout. “Defeat
the boss” is still a side objective since it is connected to fewer rooms
than the remaining non-objective rooms, exhibiting the relevance
Figure 6: Large dungeon layouts with several dead ends. order introduced in section 3.
The dungeon layout in Figure 9 is a variation of the layout in
Figure 6 shows results in two larger scenarios with several dead Figure 8, now showing how the system reacts to different types
ends. In both cases, the main objective is placed in the furthest and sizes of dungeon layouts with minor changes to the dungeon
dead end from the start position, and side objectives with identical content. In simulation (a), we changed the different rooms’ sizes to
distance and connectivity scores are chosen according to their show that the system does not consider the size as a factor when
386
Work-in-Progress CHI PLAY '20 EA, November 2–4, 2020, Virtual Event, Canada
developed artifact also enhances the mixed-initiative creative loop
in EDD, and helps the designer to visually validate their creation
in terms of narrative.
These contributions open a promising line of research on proce-
dural narrative in mixed-initiative environments. The next steps
will be adding a coherent story that ties all objectives together, as
well as articulating them by means of "quest givers" that offer dif-
ferent starting points for each objective. Ultimately, we will make
use of all these pieces to engineer a procedural narrative generator
that intertwines story, objectives, characters, and map. We would
conduct a user study to validate the resulting worlds with game
designers and players.
REFERENCES
[1] Espen Aarseth. 2005. From hunt the wumpus to everquest: introduction to
quest theory. In International Conference on Entertainment Computing. Springer,
Figure 9: A large circular dungeon layout with dead ends, 496–506.
rooms of different sizes and varying content. [2] Ahmed M. Abuzuraiq, Arron Ferguson, and Philippe Pasquier. 2019. Taksim: A
Constrained Graph Partitioning Framework for Procedural Content Generation.
In 2019 IEEE Conference on Games (CoG). 1–8.
[3] Alberto Alvarez, Steve Dahlskog, Jose Font, Johan Holmberg, and Simon Johans-
son. 2018. Assessing Aesthetic Criteria in the Evolutionary Dungeon Designer.
In Proceedings of the 13th International Conference on the Foundations of Digital
Games (Malmö, Sweden) (FDG ’18). ACM, New York, NY, USA, Article 44,
4 pages. [Link]
[4] Alberto Alvarez, Steve Dahlskog, Jose Font, Johan Holmberg, Chelsi Nolasco, and
Axel Österman. 2018. Fostering Creativity in the Mixed-initiative Evolutionary
Dungeon Designer. In Proceedings of the 13th International Conference on the
Foundations of Digital Games (Malmö, Sweden) (FDG ’18). ACM, New York,
NY, USA, Article 50, 8 pages. [Link]
Figure 10: Two different room designs shown with and with- [5] Alberto Alvarez, Steve Dahlskog, Jose Font, and Julian Togelius. 2019. Em-
out meso patterns toggled. (a) and (c) as well as (b) and (d) are powering Quality Diversity in Dungeon Design with Interactive Constrained
the same design. The two room designs represent the bottom MAP-Elites. In 2019 IEEE Conference on Games (CoG). 1–8.
[6] Alberto Alvarez, Steve Dahlskog, Jose Font, and Julian Togelius. 2020. Interactive
room from Figure 9.b) and c), respectively. Constrained MAP-Elites: Analysis and Evaluation of the Expressiveness of the
Feature Dimensions. arXiv: 2003.03377 (2020).
[7] Alexander Baldwin, Steve Dahlskog, Jose M. Font, and Johan Holmberg. 2017.
evaluating and assigning objectives. Therefore, the objectives in 9.a) Towards Pattern-based Mixed-initiative Dungeon Generation. In Proceedings of
the 12th International Conference on the Foundations of Digital Games (Hyannis,
are nearly identical to 8.b). The only difference is that the “Defeat Massachusetts) (FDG ’17). ACM, New York, NY, USA, Article 74, 10 pages. https:
the enemies” objective in the circular structure is removed (see the //[Link]/10.1145/3102071.3110572
red-bordered rooms in 8.b) and 9.a)). The reason is that the two [8] Ashmore Calvin and Nitsche Michael. 2007. The Quest in a Generated World.
In DiGRA གྷ - Proceedings of the 2007 DiGRA International Conference: Situ-
middle rooms in the circular structure are now combined into one ated Play. The University of Tokyo. [Link]
big room, thus reducing 𝑁𝑜𝑏 𝑗 from 5 to 4. In (b), the big room in the digital-library/[Link]
[9] Derek Yu and Mossmouth, LLC. 2008. Spelunky. Game [PC]. Mossmouth,
middle is now filled with several meso patterns to show that the California, US. Last played December 2019.
system does not prioritize the amount of content in a room when [10] Joris Dormans and Sander Bakkes. 2011. Generating missions and spaces for
evaluating the dungeon objectives. adaptable play experiences. IEEE Transactions on Computational Intelligence and
AI in Games 3, 3 (2011), 216–228.
In (c), we showcase how the system generates objectives based on [11] Ken Hartsook, Alexander Zook, Sauvik Das, and Mark O. Riedl. 2011. Toward
the content in the dungeon, showing how the designer is in control supporting stories with procedurally generated game worlds. In Proceedings of
of what objectives are created. The difference between (b) and (c) the IEEE Conference on Computational Intelligence and Games, CIG 2011. 297–304.
[Link]
is the side objective at the bottom room of the dungeon, depicted [12] Erin J. Hastings, Ratan K. Guha, and Kenneth O. Stanley. 2009. Evolving content
in Figure 10.a) and b), respectively. Figure 10.c) and d) are the meso in the Galactic Arms Race video game. In 2009 IEEE Symposium on Computational
Intelligence and Games. [Link]
pattern representation for Figure 10.a) and b), respectively. The [13] Hello Games. 2016. No Man’s Sky. Game [PC]. Sony Interactive Entertainment,
meso pattern distribution is the same, but the quality of the room Tokyo, Japan. Last played March 2017.
as a guarded treasure pattern is lower than its quality as a treasure [14] Henry Jenkins. 2004. Game design as narrative. Computer 44, 53 (2004), 118–130.
[15] Ben Kybartas and Rafael Bidarra. 2016. A survey on story generation techniques
room. Therefore, swapping between a) and b) alters the nature of for authoring computational narratives. IEEE Transactions on Computational
the objective in the room, and a "Find the treasure" objective is Intelligence and AI in Games 9, 3 (2016), 239–253.
placed at the bottom of 9.c) instead. [16] Antonios Liapis, Georgios N Yannakakis, Mark J Nelson, Mike Preuss, and Rafael
Bidarra. 2018. Orchestrating game generation. IEEE Transactions on Games 11, 1
(2018), 48–68.
5 CONCLUSIONS AND FUTURE WORK [17] Mojang Studios. 2009. Minecraft. Game [PC]. Microsoft Studios, Washington,
US. Last played October 2019.
We have developed a sub-system integrated into EDD that generates [18] Noor Shaker, Julian Togelius, and Mark J Nelson. 2016. Procedural content gener-
suitable objectives based on dungeon layouts created in a mixed- ation in games. Springer.
initiative environment. This integration has been carried out in a
harmonic way [16] with EDD’s already existing functionalities. The
387