Metroidvanias and Exploration

“Metroidvania” is a game genre based on the operational logics of Super Metroid (Sakamoto 1994) and Castlevania: Symphony of the Night (Hagihara 1997):¹ an explorable space (usually in two dimensions) that includes various barriers, which can be passed after acquiring permanent upgrades that are scattered around the map. These upgrades usually also make the player more powerful in battle, and fighting enemies throughout the map is a staple of the genre (although some would argue it’s not a necessary aspect). Additionally, secret areas with optional upgrades are hidden throughout the map, and an in-game map view is available which automatically records what the player has discovered and which helps indicate unexplored areas. Finally, in contrast to “open-world” games, the space of Metroidvania games is constrained to a series of rooms with specific paths between them; it can be abstracted into a topological representation without loosing very much information, although spatial relationships and metrics are still important for using the map systems that these games include.

In these games and the more recent examples of the genre like Metroid Prime (in 3D) and Ori and the Blind Forest (which does away with room transitions) the excitement of exploration and discovery is central, even though combat and platforming challenges are also important (Pacini 2002; Mahler 2015). One thing that demonstrates the centrality of exploration in these games is the design of fan-made randomizers: mods which scramble the placement of items in the game (Jewett 2021). Randomizers are designed to give veteran players a fresh challenge, and while some do randomize enemy placement or statistics, the focus is on altering the exploration of the game by swapping item locations, rather than on altering the platform layouts or combat challenges.

While there is a large body of work on exploration in games, the focus has been on open-ended 2D and 3D environments, usually using maps to represent space (see e.g., Osborn et al. (2021), Si (2017), and Stahlke (2020)). At the same time, some work in both procedural content generation and reinforcement learning has emphasized graph-based topological representations, although these works have not taken the human exploration process as their main focus (see e.g., Dormans (2010), Smith, Padget, and Vidler (2018), and Zhan, Aytemiz, and Smith (2019)). In a similar dichotomy, the literature on the psychology of exploration makes a distinction between route-based and survey-like spatial knowledge, often assuming that route-based knowledge is an earlier stage of knowledge development than survey-like knowledge (see Jamshidi and Pati (2021) for a review and Foo et al. (2005) on questions of knowledge representation). For Metroidvania games, topological information alone is sufficient for most navigation tasks, which suggests a distinct player experience as well as the opportunity for a very different formal representation of that experience.

The aim of this paper is to describe how players explore these games at the abstract level of routes, in order to come up with formal structures for representing their exploration processes that could be applied in future PCG systems in a variety of ways. These structures are also the foundation for future work in topological “exploration poetics,” which would attempt to theorize how topological structures in games evoke particular feelings among players. The formal structures described here have been implemented as the open-source exploration library published on the Python Package Index.²

There are two main representations available in the exploration library: an algorithm-friendly sequence-of-graphs representation, which we term an exploration trace, and a more human-accessible text-based journal format, which we call an exploration journal. An exploration trace takes the form of a list of time steps, with a map, a position, a transition, and a game state corresponding to each time step. The individual maps in an exploration trace are multi-digraphs that can support tags and annotations for nodes and edges, and which incorporate explicit nodes representing unexplored spaces. These maps also include a structure for specifying transition requirements in terms of powers and tokens, and a structure for specifying the effects that taking a transition has on the rest of the map and on the player. As we will describe in the section on complexity, a simpler format consisting of a single map along with a trace of positions cannot fully capture exploration in Metroidvania games.

The journal format is a text format where rooms, their entrances, and their exits are specified, including information about requirements for traversing connections and about observed-but-unexplored connections in each room. We hypothesize that this information about observed connections is central to understanding the player experience of exploration, and that distinct patterns of unexplored connections will contribute to distinct feelings of gameplay. The journal format is designed as a list of entries most of which specify a single location or connection, and includes some conventions for deducing additional information (such as the entrance location when revisiting a room) in order to minimize human journaling effort.

The exploration library has routines for parsing an exploration journal to construct an exploration trace, and the opposite conversion is also possible (although not yet provided). This conversion algorithm is one of the main contributions of this work, because it makes the production and curation of exploration traces much easier. An exploration journal can be maintained during gameplay (e.g., to assist with mapping in a randomized game) or to allow more natural play, a recording of play can be re-examined by the player to produce a journal. However, only with some strong assumptions can a journal be derived from observing someone else’s gameplay (see the complexity section).

In the rest of this paper, we first explore related work, then describe the exploration trace and journal formats in detail, comment on the complexity necessary in these formats, and finally suggest possible applications of this work.

Related Work

There is much existing literature on the topic of exploration, spanning disciplines such as urban planning, geography, psychology, cognitive science, and neuroscience (regarding human exploration), robotics and AI (more abstract and/or automated exploration), and of course game studies, both technical and non-technical. The following sections give a brief overview of each area.

Human Exploration of the Real World

Jamshidi and Pati (2021) provide an excellent and broad review of the literature on what is termed “wayfinding” which includes human exploration and navigation. On the cognitive/neuroscience side, Siegel and White (1975) provide an early overview of how space might be represented in the mind, and how such representations are learned; Peer et al. (2021) has an updated perspective on these issues and focuses explicitly on the distinction between graph-like and map-like representations. The consensus espoused by Peer et al. is that both graph-like and map-like cognitive structures exist, although there is no clear ordering in terms of which is learned first or derived from the other. Graph-like structures are assumed to be at least an encoding of specific topological relationships between spaces, possibly with associated metric information about distances or angles involved. In contrast, map-like structures are described as grid-based and Euclidean, encoding absolute positions of different objects of interest.

The Image of the City (Lynch 1964; see also Lynch 1984) provides a higher-level conception of how humans represent space (specifically cities) based on rich interviews and interactions with city residents. It is not concerned with specific cognitive structures, but it does suggest five components of spatial representations: paths, edges, districts, nodes, and landmarks. Similarly, other studies of human behavior in the real world (e.g., Gerber and Kwan (1994)) tend to produce relatively more complex and less abstract conceptions of human spatial representation. The formats we present here are more formal by design, and because of their focus on exploration in a specific game genre.

Formal Exploration

Growing out of cognitive science and AI research, a number of systems and formalisms have been created to represent exploration in computers, both in attempts to model human cognition and for practical purposes in robotics. Gopal, Klatzky, and Smith (1989) present a detailed computational model of human cognition related to exploration and navigation, which includes mechanisms of perception and memory. Focused on accurately modelling human cognitive processes, their model is more detailed than the model presented here, which would be an advantage in work that aimed to use a model to simulate gameplay, but which has disadvantages in terms of deployment effort. Their model is also designed to simulate human exploration rather than to record actual human exploration processes, in contrast to the models we present, although developing a simulator based on our models is one promising direction for future work. However, we do directly share one of their motivations, which is to “…make clear the complexities of existing theories and indicate where assumptions must be made in order to bridge theoretical gaps” (p. 310).

Remolina and Kuipers (2004) similarly present a detailed logical theory of topological maps, which would be suitable for representing the kinds of relationships that our model represents, but which is a bit unwieldy as a primary format. In theory, automatic translation from our formats into the predicate-based representation implied by Remolina and Kuipers should be possible, and might be an interesting area of future work since it would allow for automatic symbolic reasoning about explorations. Their model might need to be extended with some kind of temporal logic (Emerson 1990) to be able to represent not just instantaneous spatial relationships but also their incremental discovery over the course of an exploration. On the other hand, our present model has a weaker representation of angles and distances than their model has, although this is extensible through custom annotations or tags.

The literature in robotics and AI (particularly reinforcement learning) also addresses the issue of exploration, and includes the concept of an abstract “state space.” Gomez, Hernandez, and Barber (2019) specifically deals with a topological representation of space, and is representative of the literature in robotics, although much of that is instead grid- or map-focused. Meanwhile, Ecoffet et al. (2021) have recently advanced the state-of-the-art in reinforcement learning using a state-space exploration strategy modeled on human exploration (and which can benefit from human demonstrations). Although somewhat incidental, the domains used by Ecoffet et al. are arcade games. These research directions use human exploration as an inspiration, but are not concerned with faithfully representing human exploration processes, whereas our work aims to help understand the human experience of exploration.

Exploration in Games

Both psychology/experience based and formal notions of exploration have been investigated in the context of games specifically. In game user experience research, there is a strong body of work on spatial design patterns (e.g., Milam and El Nasr (2010)) and on how level design influences wayfinding (see e.g., Hoeg (2008), Moura and Bartram (2014)) although this work centers 3D spaces (see Khalifa, Mesentier Silva, and Togelius (2019) for an exception). Directly relevant to the current work on exploration is research on automatic exploration and mapping of games in both 2D and 3D (e.g., Stahlke (2020), Zhan, Aytemiz, and Smith (2019), Osborn et al. (2021), Campbell and Verbrugge (2019)), although these works mostly use map-like rather than graph-like representations of space.

Even more relevant is research on human exploration processes in games, including the work of Si (2017) on believable exploration behavior based on recorded human exploration processes (see also Biggs, Fischer, and Nitsche (2008)).³ Si’s work included annotated recordings of human exploration processes in a game supplemented by structured interviews, and this data was then used to develop heuristics for creating AI agents that could explore space in a believable manner. Although Si’s work is in a 2D domain, it was conducted in a mostly open and continuous environment and topological relationships are discussed but not foregrounded in his work. While we aim to capture the player experience of exploration as Si did, our format focuses on topological knowledge, and we are also aiming to create more structured and abstract representations of the exploration process to facilitate more quantitative comparisons between players.

Besides Si’s work, Stahlke’s work on automatically exploring game spaces is quite relevant, and notably includes both detailed model of memory for both spaces and entities, and a nice breakdown of possible motivations for exploration (pp. 51–54). Stahlke’s work like ours is explicitly motivated by a desire to understand the user experience of exploration, but it uses on a grid-based representation of space. Note that there are quite a few similarities between Stahlke’s approach and the previously mentioned work by Gopal, Klatzky, and Smith (1989). Because creating automatic models of exploration of topological graphs which mimic human exploration patterns is one of our future research directions, we will likely continue to reference this work in the design of such systems.

Finally, there is some that focuses specifically on exploration in Metroidvania games: Wahlberg (2015) has written about backtracking specifically, as well as the map configurations that lead to it, and Arnott (2017) has written about the mapping activity in the Metroid series specifically and how that relates to narrative elements of those games. Although quite relevant, neither of these works includes a formal representation of the player’s exploration process, and we believe that such a representation could be useful for both precisely describing specific configurations of game space and for quantitatively (or even qualitatively) comparing and contrasting different game spaces.

A few other works that are relevant include Toups et al. (2019) on map interfaces in games and Moura and Bartram (2014) on visualizing player traces (which includes an abstracted graph-based visualization of player movement through space). As outlined in this section, the main features of the present work that distinguish it from existing work are the focus on topological rather than Euclidean models of space and the intended use case as a means of recording and comparing abstracted records of player experience.

Formats

The main contribution of this paper is two interchangeable abstracted formal representations of human exploration processes: an algorithm-friendly sequence-of-graphs format which we term an exploration trace, and a human-accessible text-based format that we term an exploration journal. These formats are formally defined through the code behavior and associated mypy type annotations of the open-source exploration library, available on the Python Package Index (PyPI). In this section we use the system of abstract types provided in the typing module of the Python standard library to formally describe the trace representation, while the journal representation is described in terms of the trace structures it can produce.

We encourage perusal of the source code for those interested in the mechanics behind conversion between the formats, and would also welcome full or partial ports of these representations into other languages, consistent with the 3-clause BSD license that we’ve applied to the code. Concretely, the core.Exploration class represents an exploration trace, and the journal.JournalObserver class can be used to convert a journal (stored as text) into a trace.

Of the two formats, the trace format is more general, and could in theory represent many different kinds of exploration (e.g., exploring hypertext nodes or conversation states in a visual novel), although it has been designed with Metroidvania games in mind. An exploration trace includes the following four components:

1. A list of decision graphs representing how topological player knowledge evolves at discrete time points.
2. A list of positions (termed decisions) occupied at each time step.
3. A list of transitions taken at each time step, which names which connection was traversed in the topological graph to arrive at the subsequent state.
4. A list of game states at each time step (represented as flexible mappings from slot names to game state information).

The lower-level units of representation are thus decision graphs (core.DecisionGraph) and game states (core.State), the latter of which is just a type alias for the built-in dict type that offers a mapping with unique keys. Decision graphs are graphs composed of decisions (graph nodes that have unique names) connected by transitions (directed edges which have names that are unique with respect to their source node). Along with game states which are less fully specified. Although game states can include arbitrary keys and values, by default they include a 'powers' slot which holds a set of strings naming unique powers acquired (e.g., "double jump") and a 'tokens' slot which holds a mapping from string token type names to integers representing expandable tokens acquired (e.g., "small key": 3).

Complexity

Case Studies

Applications