Using Petri Nets for Analysis of Navigation Paths in Constrained Graphs: Application to Roguelike Games

Luís Gomes, José Ribeiro-Gomes, João Paulo Barros

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

16 Downloads (Pure)

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 procedurally generated environments and random map creation, are used to validate the proposal. Navigation is constrained 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), nonviable (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.
Original languageEnglish
Title of host publicationPetri Nets and Software Engineering 2024
EditorsMichael Köhler-Bussmeier, Daniel Moldt, Heiko Rölke
PublisherCEUR Workshop Proceedings
Pages283-298
Number of pages16
Publication statusPublished - 24 Jun 2024
Event2024 International Workshop on Petri Nets and Software Engineering, PNSE 2024 - Geneva, Switzerland
Duration: 24 Jun 202425 Jun 2024

Publication series

NameCEUR Workshop Proceedings
PublisherCEUR Workshop Proceedings
Volume3730
ISSN (Print)1613-0073

Conference

Conference2024 International Workshop on Petri Nets and Software Engineering, PNSE 2024
Country/TerritorySwitzerland
CityGeneva
Period24/06/2425/06/24

Keywords

  • Graph Analysis
  • Petri nets
  • Procedurally generated games
  • Reachability graphs

Cite this