TY - GEN
T1 - Using Petri Nets for Analysis of Navigation Paths in Constrained Graphs
T2 - 2024 International Workshop on Petri Nets and Software Engineering, PNSE 2024
AU - Gomes, Luís
AU - Ribeiro-Gomes, José
AU - Barros, João Paulo
N1 - Funding Information:
This work was financed by Portuguese Agency FCT \u2013 Funda\u00E7\u00E3o para a Ci\u00EAncia e Tecnologia, in the framework of project UIDB/00066/2020, and under the PhD scholarship with the reference PRT/BD/154920/2022. The authors would like to thank Miguel Vit\u00F3ria for making available the application that allowed the generation of the maps used to validate the presented work.
Publisher Copyright:
© 2024 Copyright for this paper by its authors.
PY - 2024/6/24
Y1 - 2024/6/24
N2 - 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.
AB - 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.
KW - Graph Analysis
KW - Petri nets
KW - Procedurally generated games
KW - Reachability graphs
UR - http://www.scopus.com/inward/record.url?scp=85199921800&partnerID=8YFLogxK
UR - https://ceur-ws.org/Vol-3730/
M3 - Conference contribution
AN - SCOPUS:85199921800
T3 - CEUR Workshop Proceedings
SP - 283
EP - 298
BT - Petri Nets and Software Engineering 2024
A2 - Köhler-Bussmeier, Michael
A2 - Moldt, Daniel
A2 - Rölke, Heiko
PB - CEUR Workshop Proceedings
Y2 - 24 June 2024 through 25 June 2024
ER -