=Paper=
{{Paper
|id=Vol-3730/paper17
|storemode=property
|title=Using Petri Nets for Analysis of Navigation Paths in Constrained Graphs - Application to Roguelike Games
|pdfUrl=https://ceur-ws.org/Vol-3730/paper17.pdf
|volume=Vol-3730
|authors=Luis Gomes,José Ribeiro-Gomes,Joao-Paulo Barros
|dblpUrl=https://dblp.org/rec/conf/apn/0001RB24
}}
==Using Petri Nets for Analysis of Navigation Paths in Constrained Graphs - Application to Roguelike Games==
https://ceur-ws.org/Vol-3730/paper17.pdf
Using Petri Nets for Analysis of Navigation Paths in
Constrained Graphs – Application to Roguelike Games
Luis Gomes1,2,3,* , José Ribeiro-Gomes4 and João-Paulo Barros2,3,5
1
NOVA University Lisbon, School of Science and Technology, Portugal
2
Center of Technology and Systems (CTS), UNINOVA, Portugal
3
Intelligent Systems Associate LAboratory (LASI), Portugal
4
Instituto Superior Técnico, Portugal
5
Polytechnic Institute of Beja, Beja, Portugal
Abstract
In many areas of application, graphs have been used to support path planning addressing navigation challenges
in dynamic environments. Applications target very diverse areas, ranging from manufacturing and robotics to
video games, including georeferencing applications in our daily lives considering real-time traffic conditions.
This paper focuses on applications where navigation through a predefined map consisting of distinct areas
(rooms or nodes) connected by pathways needs to be defined. Roguelike games, a genre defined by procedu-
rally generated environments and random map creation, are used to validate the proposal. Navigation is con-
strained by resource availability and specific conditions that allow or block movement between adjacent areas.
Players can collect specific resources in visited areas, which can be used to allow/unlock passages. The main
goals include determining whether, given a specific randomly generated map/graph, along with all associated
constraints and resources, the game is inviable (when it is not possible to reach the final area of the game), non-
viable (when depending on the player’s options, it is possible or not to reach the final goal), or viable (when the
ultimate goal area can always be reached regardless of user’s choices over time). This paper proposes a strategy
for translating the map and associated graph into a Petri net model. Then, the viability level of the game can be
determined by constructing and analyzing the associated reachability graph from the Petri net model. A set of
examples are presented illustrating typical situations.
Keywords
Procedurally generated games, Graph Analysis, Reachability graphs, Petri nets
1. Introduction
In several areas of application, selecting a strategy for navigation is of paramount importance. In
this sense, path planning is a crucial consideration in navigation. A significant number of strategies
(probably the most used ones) rely on a characterization of the environment by a set of nodes and known
costs associated with traversing from one node to another. This directly supports the construction of a
graph, facilitating the determination of the optimal path from an initial node to a destination node.
Graph-based algorithms, being easily processable [1], are extensively employed in addressing path-
planning challenges. In these algorithms, the space is characterized as a collection of cells, and each
connection between cells is assigned a weight representing its associated cost. These costs may account
for various constraints, such as distances, energy, time, resources, or other types of resources, depending
on the specific area of application.
Dijkstra introduced a pioneering algorithm in 1959 [2], which remains highly relevant for determining
a specific path with minimized associated costs. Various adaptations of Dijkstra’s algorithm have been
proposed. Best-First-Search [3] associates cost with the distance to the goal. A* [4] is an extension
that combines Dijkstra’s algorithm and Best-First-Search, evaluating paths based on both cost and the
distance of the node to the goal. Dynamic A* [5] extends A* to dynamic environments by accommodating
changing costs over time.
PNSE’24, International Workshop on Petri Nets and Software Engineering, 2024
*
Corresponding author.
" lugo@fct.unl.pt (L. Gomes); josepgomes@tecnico.ulisboa.pt (J. Ribeiro-Gomes); joao.barros@ipbeja.pt (J. Barros)
0000-0003-4299-8270 (L. Gomes); 0000-0002-0097-9883 (J. Barros)
© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
283
Luis Gomes et al. CEUR Workshop Proceedings 283–298
Several alternative approaches have been proposed to tackle path planning in different application
areas. Some still consider static scenarios, while others cope with dynamic scenarios (such as geo-
referenced traffic applications). Some are bio-inspired, while others consider some physics-related
features.
In the first group considering bio-inspired alternatives, particular reference is given to the ant colony
optimization algorithm, which mimics the behavior of ant colonies [6, 5]. This algorithm seeks to find
the shortest path from a nest to a food source and back by emulating ant behavior, which involves
the release of pheromones. These pheromones are detected by other ants, guiding them towards the
established path.
In the second group emphasizing physics-inspired approaches, one can find the artificial potential
fields method introduced in 1985 [7]. This model utilizes potential fields, where the selected path for
the movement is influenced by two forces: attraction towards the goal and repulsion from obstacles.
The combined effects of these forces determine the direction to follow.
As in Dijkstra’s algorithm and other referred algorithms, the focus is on the shortest path between
two specific nodes; one node in the path is visited once at most. In applications where additional
constraints (other than costs) need to be considered, those approaches would need severe changes (if
not wholly inadequate). This is the case when the movement along the path needs the possession of a
specific resource, which in turn can be obtained in some node not belonging to the shortest path to
the destination. For instance, while at node A, it may be necessary to visit some other node to bring a
specific resource, which will be used afterward to unlock some movement between nodes and return to
node A to proceed toward the goal. In this sense, immediate applicability of the referred algorithms is
not possible.
This is the case for the application area of roguelike games, where the game’s map is randomly
generated and can be represented using a graph. Movements between rooms in the map could be
constrained by some doors, which can be unlocked using specific resources (keys, weapons, or others);
those resources can be obtained in some other room (node). Fig. 1 shows two simple maps suffering
from an ill-formed condition.
(a) An inviable map. (b) A nonviable map.
Figure 1: Examples of ill-formed maps.
In Fig. 1(a), to go from RoomA to RoomE, it is necessary to move along RoomB to RoomC. However,
for this movement, the player needs to have a specific resource (key K1, in this case), which in turn can
only be granted when reaching RoomD. In this case, the game is inviable, as it cannot be concluded.
Another annoying situation is illustrated in Fig. 1(b), where the movement from RoomA to RoomG
needs the possession of key K1 (to move from RoomD to RoomE). However, if the player chooses to
move away from RoomC without visiting RoomB, they will be blocked in RoomD. In this case, the final
room might not be reached depending on the player’s options (actions over time). This is considered as
a nonviable map. Only maps allowing the player to reach the final room regardless of their options are
284
Luis Gomes et al. CEUR Workshop Proceedings 283–298
acceptable (as in roguelike games, resetting the game halfway would lead to an entirely new generated
map/graph, resulting in loss of player progression).
This paper analyzes potential navigation paths within a randomly generated map, where navigation is
constrained by particular conditions associated with specific movements between rooms. This scenario
is particularly relevant in roguelike games, which are procedurally generated, and where a significant
challenge lies in ensuring that, following the random generation of maps and constraints, players can
always reach the ultimate goal without encountering deadlock situations.
The proposed approach involves translating the constrained map into a Petri net model, a strategy
previously suggested in other works [8], and complementing and extending the work presented in
[9]. By constructing the Petri net model associated with the map/graph of the game, the associated
reachability graph is generated, and its analysis answers the questions mentioned earlier. To the best of
our knowledge, this is the first work tackling the classification of possible navigation paths between
two nodes in graphs, which in turn were generated as representing constrained maps.
The paper is structured as follows. In Section 1, the motivation for the work identifying the challenge
to be addressed is presented, while Section 2 briefly describes different approaches to building a roguelike
game map/graph, as well as introducing a simple map/graph random generator used for validation of
the approach afterward. Section 3 presents the proposed approach to perform the analysis of the map
characteristics, while Section 4 is devoted to presenting the steps to obtain the Petri net model from the
map/graph, and Section 5 focus on the analysis strategies. Section 6 is dedicated to the validation using
a set of examples, and Section 7 concludes.
2. Building the map and the graph of the roguelike game
The proposed approach relies on a graph representation of the map, so it can be translated to a Petri
Net representation and benefit from associated analysis techniques.
Though relying on a graph representation may seem like a too-limiting requirement, in this section,
we present a non-exhaustive list of map generation techniques used in roguelikes and show that this
is not the case and how they can be mapped to a graph representation. In fact, some map generation
techniques already rely on defining a map graph as a starting point, and others may be translated to a
graph representation afterwards. Consequently, we aim to show that the proposed approach is suitable
for diverse implementations of map generation.
We structure the section into techniques that rely on defining a map graph beforehand and then
translating it into a map, and techniques that define a map straight away but may then be represented
as graphs. All shown techniques have been used in games, and none consider including conditions to
constrain movements between nodes/rooms (such as the need to unlock doors between rooms).
2.1. Graph First
The following approaches start by defining a graph structure that represents the map only after
populating the actual playable map.
One approach is Binary Space Partitioning [10, 11], which recursively divides a space into smaller
spaces. The random subdivisions can be interpreted as rooms with different layouts, sizes, and connec-
tions between them. They inherently have a hierarchical, tree-like structure.
Another technique consists of defining a Voronoi diagram using a set of points to subdivide the
map [11]. The regions inside the diagram might correspond to different areas of interest, and the edges
may correspond to connections or transitions.
Lastly, some games have a pre-defined, manually created graph specifying the map’s layout. This
approach usually relies on a set of pre-made rooms that are randomly selected to instantiate the graph.
One such game is Enter the Gungeon1 .
1
https://enterthegungeon.com
285
Luis Gomes et al. CEUR Workshop Proceedings 283–298
2.2. Map First
Contrary to the approaches above, the following approaches focus on generating the map straight away.
Some approaches may be translated to a graph afterward, while others may be more difficult.
A common approach is to use cellular automata [11]. It considers that the map is a grid of cells, each
belonging to a specific group or state, such as room, door, wall, water, . . . . Starting from an initial cell, it
iteratively considers the neighboring cells in order to populate the world in a way such that a series of
rules are followed.
Perlin noise is also prevalent for map generation. It is a gradient noise function that produces smooth,
continuous patterns. Randomness is introduced through noise generation, creating natural-looking
variations in terrain. An example of a very popular game that uses Perlin noise to define its world is
Minecraft 2 .
Random Walk and Drunkard’s Walk [11] are both approaches that involve placing tiles in the world
by iteratively moving through the map in a random direction at each step. These techniques create
winding paths, favored for cave systems, paths, roads, or rivers.
Yet another approach is Wave Function Collapse3 , which uses an input pattern (such as an image
or small region of what the world such look like) and a set of constraints. One game that uses this
technique is Caves of Qud4 .
2.3. Map/graph random generator used for validation
In order to validate the proposed approach on randomly generated maps/graphs associated with
roguelike games, a simple map/graph generator was used. It is used in the examples in the validation
section. As stated, there is no loss of generality, as all implementations that produce a graph map are
compatible with the proposed approach.
The adopted technique for the implemented simple map/graph generator was inspired by an online
tutorial 5 , and can be seen as an extension of cellular automata. The code of the developed map/graph
random generator is available at https://github.com/miguelmtsvitoria/RandomMap, which is a result of
[12].
In this simple map/graph generator, a grid map was considered, where cells may contain a room.
These rooms may be connected to adjoining rooms by means of doors placed North, East, South, and/or
West, so that no room may have a door that connects to nothing. Furthermore, each room may have
more than one door, provided there is only one door in each direction and that all rooms are connected.
The implemented map generator starts by defining a central room with four doors, one on each side.
Afterward, it iteratively checks each available door and adds a compatible room. For example, for the
East door, we must add a room that has a West door and may have additional doors. Each room added
may contain new doors, which allow the map to develop and expand from that central node.
One key concept in this approach is that we may define a passage between two rooms as bidirectional
or unidirectional or as requiring a key (or other constraint) to open a door.
The size of the map, the overall number of connections per room, restrictions on doors, and so on
may be controlled to change the difficulty of the game.
2.4. Representing the graph
The representation of the map layout randomly generated by the application described in the previous
sub-section is a simple XML file storing the list of rooms (dungeons) and the list of transitions between
rooms, as presented in Table 1, which stores the information associated with the (very simple) map of
Fig. 2. In this example, one key is available (at RoomB), which is needed to unlock the transition from
RoomD to RoomE (the final room).
2
https://www.minecraft.net
3
https://github.com/mxgmn/WaveFunctionCollapse
4
https://www.cavesofqud.com
5
https://www.youtube.com/playlist?list=PLBIb_auVtBwA-qr2-WnWX0LjZXkqKu5Aj
286
Luis Gomes et al. CEUR Workshop Proceedings 283–298
Figure 2: A simple map.