---
title: "Decision Mapping for Comparative Analysis"
subtitle: "Hollow Knight and Yoku's Island Express"
keywords: [exploration, graphs, player experience, metroidvania, exploration-action games, decision mapping, choice poetics, exploration poetics]
abstract: |
  Decision mapping is a distant-playing technique for analyzing decision
  spaces in games by formally mapping them as a graph, indicating which
  decisions lead to which other decisions, and tracking outcomes and
  requirements in terms of game state. While the formal definition of the
  graph language used narrows down which aspects of the player experience
  are fully captured by this techinque, this limitation makes it an
  interesting lens through which to analyze games because it focuses the
  analysis on a meso-level of decision-making which brings certain
  exploration processes into sharp focus. We have applied decision
  mapping to parts of Hollow Knight and Yoku's Island Express and
  describe the process we used, some of the theory behind it, and some
  insigts we gained about the two games. In particular, we discuss the
  fractal quality of game decisions, how space is organized differently
  by these two games, how different approaches to death affect gameplay
  cycles in both games, and how one might compare "linearity" between the
  two. In addition to insights about Hollow Knight and Yoku's Island
  Express in particular, we offer some general insights on
  exploration-action games and a template for applying decision-mapping
  to the analysis of other games. This work may be of particular interest
  to procedural content generation researchers interested in metrics
  applicable to non-linear games involving exploration.
bibliography: refs.bib
documentclass: acmart
classoption: [sigconf]
biblio-style: ACM-Reference-Format
anonymous: true
link-citations: true
...

# Introduction

The "Boss Keys" YouTube video series [@brown2016boss] analyzes various exploration-focused games (and particular spaces within them, like Legend of Zelda [@legend_of_zelda_alttp] dungeons) by reducing their play space down to an abstract graph representing just the pathways taken and key items that must be collected to beat them.
This mode of analysis offers lots of insights into particular design decisions and also affords rich comparisons between different dungeons, because it focuses on a particular meso-level of decision-making in the games, and it also focuses on the exploration process in particular.
However, Brown used an informal methodology to construct the graphs used for this analysis.
There are some differences which appear contradictory between graphs (like the inclusion of some dead-end paths while others are omitted) and replicating this analysis would be difficult because of this.
We therefore introduce "decision mapping" as a formal version of this technique, along with an open-source Python library for parsing decision journal files and applying some quantitative analysis to the resulting exploration traces.

We position "decision mapping" in the family of "distant reading" [@stefan2015close] techniques which are adjacent to (but not totally the same as) formal analysis (see [@lankoski2015formal] for a discussion of formal analysis applied to games).
By capturing specific players' subjective experiences of exploration, we do not aim to develop an "objective truth" of the game space (which would be impossible for several reasons), but we nevertheless formalize our experiences into humanistic data (see [@cordell2019teaching]).
The goal of this process is to provide a useful (if necessarily distorted) lens with which to examine games' explorable spaces, and in particular to aid in comparisons between different games and between different players' explorations of a game.

We present here a description of our decision mapping technique and a summary of the library we've made available to support it, along with some analyses of the introductory sequences in Hollow Knight [@hollow_knight] and Yoku's Island Express [@yokus_island_express] (subsequently: HK and YIE).
In particular, we discuss the fractal quality of game decisions, how space is organized differently by these two games, how different approaches to death affect gameplay cycles in both games, and how one might compare "linearity" between the two.


# Related Work

There is a wealth of existing work on exploration & navigation (often under the term "wayfinding") in real life, on exploration in games specifically, and on related aspects of game experiences.
Further connections can be made to work in game design and engineering; we attempt to summarize all of these connections briefly here, but do not have the space for an extensive literature review.

## Real-life Exploration

On real-life exploration and the cognitive structures that underlie wayfinding, [@jamshidi2021narrative] provides a nice recent review, while [@peer2021structuring] focuses more on neurobiology.
Both indicate that humans appear to represent space both in terms of a network of paths and landmarks, as well as in terms of 2D or 3D positions and/or spatial relations that can be mapped out absolutely.
Our work focuses more on the former, as we for this project have not annotated spatial positions or relationships for decisions; [@foo2005do] provides an experiment demonstrating that landmark/route navigation is quite important in real-world contexts.
Remolina and Kuipers' theory of topological maps [@remolina2004towards] also bears mention here, as it provides a formal mathematical theory that is relevant to both cognitive science and robotics.
Their ideas such as "distinctive states" and "causal maps" are quite relevant to our work, and form one strong precedent for the abstraction of space into graph-like structures.
In a similar vein, Gopal, Klatztky, and Smith's computational model of human navigation [@gopal1989navigator] foregrounds routes and choice points, and offers yet another example of a formal model of human exploration cognitive processes.

Outside of cognitive science, Lynch's "The Image of the City" [@lynch1964image; see also @lynch1984reconsidering] is an incredibly important work because it offers a foundational theory of how humans understand space which fits well with many videogame environments (although somewhat less-well with 2D games of the kind we're focused on here).
While our current system just has decisions and transitions between them, we are already engaged in further work on a version of the system which uses Lynch's spatial forms (nodes, landmarks, edges, paths, and regions) to annotate exploration processes in open-world games.

## Game Studies

Although not formal academic scholarship, the "Boss Keys" Youtube series [@brown2016boss] is one of the best examples of formal analysis applied to exploration-based games, and the abstraction of game spaces into graphs used here is a direct inspiration for our work.
This video [@brown2017how] explains in detail how these graphs are (manually) constructed; our decision graphs are somewhat different as we do not attempt to simplify the structure of the space to focus exclusively on key items.
However, in theory it should be possible to create an automated algorithm that can simplify our decision graphs into graphs of the same form used in these videos (which are referred to elsewhere as "mission graphs" [@smith2018graph]).

Several other academic treatments of exploration or navigation in games are also relevant [@flynn2003languages], including specifically in the Metroidvania genre [@arnott2017mapping, @wahlberg2015blockades, @mackenzie2021interactive].
Most of these are not as formal as our approach, and we hope that while our approach will doubtless obscure details which don't fit into the abstractions we're using, that same rigidity will provide an interesting and fresh perspective on questions surrounding the player experience of exploration.

More formal projects similar to our own (although with different focuses) include Debus' work on classifying navigational acts [@debus2016video], Wolf's work on navigable space in games [@wolf2011theorizing], and Mawhorter et al.'s work on choice poetics [@mawhorter2018choice].
None of these is focused on exploration, but they are examples of the kind of formalist games studies we are doing.
This work on decision mapping can be seen as complimentary to the work on choice poetics in particular, since that work focuses on detailed formal analysis of individual discrete choices, and this work seeks to abstract gameplay experience into a network of discrete and essentially repeatable choices.

Works that don't focus on exploration but that do focus on Hollow Knight and/or Yoku's Island Express are of course also relevant: Ofner's thesis on Hollow Knight [@ofner2021play], Horn's comparison of Hollow Knight and Ori and the Blind Forest [@horn2019insects], and House and Kocik's analysis of Yoku's Island Express [@house2020serious] stand out to us.
In particular Horn's project is similar to ours in terms of comparing two similar Metroidvania games, albeit using hermeneutics as a framework and focusing on the level of themes, rather than attempting comparison based on abstract game structures observed via a specific formalism.

Although it is not the focus of this paper, we should mention that we find it odd that none of these works analyze the colonialist themes in Hollow Knight, nor have we found other works that do so.
To do so briefly here: the lore of Hollow Knight places the City of Tears and the Kingdom of Hallownest as colonial invaders who replaced a former moth society; the curse of infection central to the game was placed by the Radiance, which was the god of the moths, as revenge for their displacement by the White Wyrm and its children.
In the "true ending" to the original game, the player defeats the Radiance, freeing the kingdom from its curse (and presumably thus allowing its colonial domination to finally be rid of the pesky persistence of the original inhabitants).
Unsurprisingly given this plot line, the game makes heavy use of appropriated Native American imagery (dream catchers to represent the world of dreams) and includes two moth characters who are either ghosts or aging and decrepit, further cementing their place in the story as a "dying race."
These themes and plot lines are deeply problematic in both their reproduction of American colonialist myths (most centrally that the indigenous population is already so the sins of colonialism can be consigned to the past) and in their positioning of the player's completion of colonialist ambitions as righteous; we would be glad to discover an actual in-depth analysis of these themes.

## Distant Reading/Playing

As already mentioned, our analysis is formalist and a form of "distant playing" analogous to "distant reading".
We should note that "distant reading" has two related connotations.
One focuses more on analyses of multiple works together, where "distant" implies that the investigator has zoomed out from the focus on an individual work to find patterns across multiple sources [@underwood2017genealogy; see @rochat2019quantitative for an example in game studies].
A second, which we are using, positions "distant" as the opposite of "close" as in "close reading," and indicates that rather than attending closely to specific details of a text, one abstracts away those details to focus on patterns (but still within a particular work).
Lankoski and Björk do not use the term "distant play" that we are adopting here, but their description of formalist analysis [@lankoski2015formal] fits our work.
Stefan et al. provide a nice survey of distant reading (not dealing with games) that emphasizes this connotation of the phrase [@stefan2015close].

## Game Design & Engineering

Moura, El-Nasr, and Shaw's visualization tool for gameplay trace analysis [@moura2011visualizing] is extremely relevant to our work, as they represent player movement through game worlds as movement through an abstract graph of analyst-defined game regions, which is analogous to our decision graphs.
In their tool, however, the analyst determines which areas of the game world map to which graph nodes, and all players' movements are mapped onto these nodes automatically.
In contrast, our system allows for the fact that different players may chunk the same environment differently, and each of us created separate decision graphs for the same game space.
Moura and El-Nasr have authored a number of other papers in this space, notably an analysis of design techniques for in-game navigation [@moura2015design] which used a very similar methodology to ours involving introspection during play, although that paper used thematic analysis of informal notes rather than developing a formal structure for observations beforehand.

There are a few procedural content generation (PCG) systems which rely on graph-based representations of game spaces, most notably [@dormans2010adventures] which was used for the game Unexplored [@unexplored].
Other notable work in this space has involved logic programming for creating or embedding "mission graphs" which are based on the Boss Keys graph distillations mentioned previously [@smith2018graph, @abuzuraiq2019taksim].
Although not a PCG system itself, Dahlskog, Björk, and Togelius' work on dungeon design patterns [@dahlskog2015patterns] is geared towards use in PCG, and it is also relevant because we hope that our system will enable automatic analysis of design patterns in exploration graphs (rather than in a 2D grid space).
See [@vanderlinden2014procedural] for a nice overview of PCG work on dungeon level generation which positions these approaches within a broader array of techniques.

## Robotics & AI

Several works in robotics and game AI not already mentioned use graph-like structures to guide exploration and/or focus on key decision points as part of their algorithm.
For example, the Go-Explore algorithm family for reinforcement learning [@ecoffet2021first] uses structures similar to a decision graph, although typically this is on a lower level of game states that represent individual frames.
As mentioned already in the section on real-world exploration, topological maps have been used for robotics [@gomez2019topological].
The use of navmeshes and/or waypoint graphs for NPC navigation in games [@halldorsson2021automated, @brewer2019tactical] is also related, as these structures decompose the game spaces into graph representations, albeit purely for efficiency reasons.

There are also existing AI systems for automatically exploring game spaces [@zhan2018taking, @osborn2021mappyland], which use graph or tree structures in their abstractions of space.
Osborn et al.'s work on Mappyland [@osborn2021mappyland] stands out because it derives a graph similar to a decision graph automatically from gameplay videos.
However, their work cannot capture information about which routes a player actually notices at what point in time, because it works purely from a gameplay video.
While that information is not completely necessary in mapping the space of the game, it is critical to understanding the human experience of exploration, which is why our methodology is purely manual and involves introspection.
However, their work is a clear example of the feasibility of automating at least some of the information extraction, and the information they are able to extract could be used for many kinds of analysis.

Another connection here is to AI agents designed to mimic human exploration patterns [@si2017believable, @stahlke2020synthesizing].
Si's work [@si2017believable] here is notable for their methodology (particularly in [@si2016exploration]) involving a think-aloud process during exploration plus structured interviews with video review, which is somewhat similar to our methodology of recording a video of gameplay (often with think-aloud observations) and then transcribing that later.
On the other hand, Stahlke's work includes an interesting typology of motivations for exploration.


# The Fractal Quality of Decisions in Games

In setting out to map decisions, one of the first challenges we encountered was to define what counts as a "decision."
Different theoretical approaches to games have different perspectives on this.
For example, most game theory modelling of decisions, and some player-modelling approaches (see e.g., [@holmgard2014generative]), side-step the issue by focusing on (possibly simultaneous) turn-based decision-making, where one turn is one decision (see also [@mawhorter2018choice] for work in games studies that takes this approach).
Similarly, reinforcement learning often models each frame of a game as a decision, although this approach means each "decision" is a tiny part of a larger-scale behavior (see [@ladosz2022exploration] for an overview of specifically "deep" reinforcement learning focused on the kinds of exploration we're interested in here).
To address this issue, hierarchical decision models have been used in both reinforcement learning [@kulkarni2016hierarchical] and other game AI contexts such as in planning agents for real-time strategy games ([@robertson2014review] provides a review).
In fact, the real-time strategy game literature makes an explicit distinction between "strategic" and "tactical" decision contexts which hints at the fact that multiple layers of decision are relevant to gameplay, and hierarchical task network planning explicitly uses a hierarchy of decisions [Ibid.].

Mason provides a nice breakdown of hierarchies of action in games in her work on agency, specifically when discussing levels of abstraction [@mason2021responsiveness pp. 66–69].
To illustrate this idea, one might break down decisions into several levels:

1. At the level of frame-to-frame button presses, both decisions of what to press when, and executions of carrying that out control the player's avatar's basic course of action in the game.
2. Above this level, there are moment-to-moment decisions about actions to take, like "attack that enemy" or "get up to that platform." The outcomes of these decisions form micro-level plans which the first layer of decisions is used to carry out.
3. Above that level, are meso-level decisions about where to go or what to do, like "kill the enemies in this room" or "go north to the next room.
4. But of course, those decisions are in service of carrying out even higher-level decisions, like "go to the fountain room" or "farm this area for more money."

...we can continue to identify higher decision levels, like "find the red key" or "level up to level 50," and above that, whole-game-level goals, like "beat the final boss" or "find the true ending."
One could even continue with goals outside of the game context, like "play some Hollow Knight" or "show off to my new friend."

These decisions each break down into actions which themselves involve further decisions about the details, which break down again, and so on.
Rather than talking about "the N levels of decisions in games" we instead see things as a continuous scale of *fractal* decision-making.
At the bottom, there is pure execution and reflex, where the carrying out of a decision no longer involves further decisions.
But the decisions above that do not necessarily resolve themselves into distinct layers, and instead many decisions may cross between multiple "layers," so it seems simplest to just think of the entire structure as *fractal*: decisions lead to plans of action, which in turn are carried out by making lower-level decisions, down to some limit of simple actions like "press the 'A' button."

An important note: not all of these plans of action are really the result of a conscious decision, but instead at multiple levels of decision-making there may be subconscious processes which result in action plans that structure lower-level decisions.
In addition, some actions taken (at multiple levels) are mistakes, rather than the result of correctly following higher-level plans.
We do not have the space here to delve into these aspect in detail, and for now treat consciously- and subconsciously-decided action plans as equivalent, and treat mistakes as decision outcomes (but will note them when they happen).
Mason's thesis goes into more detail and similarly talks about a continuum of levels of abstraction [Ibid.].

Note that Debus, Zagal, and Cardona-Rivera also discuss a hierarchy of actions in games, although they are focused on goals, not outcomes [@debus2020typology].
In their section on "The Paradox of Game Goals" they also discuss the issues with treating games as either completely independent-of-player objects or as completely-particular-to-player processes.
Where their work lands on the as-objects side of that divide, we find it more useful to be on the as-processes side: each person's decision map includes decisions particular to them, and is thus not directly comparable to another decision map of the same game.
Of course, having mapped several players' idiosyncratic decision graphs for a particular game, although difficult it is not impossible to attempt to find correspondences between them based on the shared underlying game topology being explored; this is something that we want to explore further in future work.

When we talk about "decision mapping" in games, we do not intend to map all decisions at every level.
Instead, we try to focus on a meso-level of decision, around the granularity of "go to the next room to the right."
This focus allows our maps to capture the key exploration moves that the player makes without getting too bogged down in the details of movement.
Some of our journals will also attempt to capture certain higher-level decisions also related to exploration, like "find a way to get to the elevator."
We also try to focus on only decisions relevant to exploring the virtual space of the game, as opposed to those that consider powering up or defeating enemies, although these concerns are often intertwined.


# Decision Mapping

Having chosen to focus on meso-level decisions related to exploration, we make the further observation that especially in room-based Metroidvania games, many of these decisions form a repeating network: a decision to go left, right, or back at a certain junction is effectively the same decision (with different information available) when one visits that junction again.
Additionally, from the choice poetics perspective thinking about a single meso-level exploration decision, the relevant outcomes (and knowledge of them) depend on the architecture of the world beyond the specific transition being considered, especially in terms of any challenges, rewards, and/or unexplored areas, plus their distribution in space.
Making a choice to "go left here" might be motivated by things such as "there's an option I haven't explored yet 3 rooms away in that direction" or "the boss is that way" or "there's a chest 2 rooms away that I saw earlier but I now have the key for."
The actual rewards that the player seeks are often several decisions away, so analyzing the nuances of each individual decision in isolation is difficult.
On the other hand, because the options for action are consistent when returning to the same room we can represent the space as a network of decision points, where the potential rewards of any given option can be derived from the structure of the rest of the network beyond that point.
Note that the assumption that decisions can be revisited and can therefore be organized into a graph representing the topology of a space has been used in robotics [@remolina2004towards] and also has some basis in human cognition [@siegel1975development].

In order to be able to represent cases where options at a given location do change (e.g., some world-changing event opens certain possibilities while foreclosing others) we track exploration as a *sequence* of decision graphs, by default copying the previous graph at each step and then making any modifications for new possibilities observed as a consequence of a single decision.
By representing unknown destinations using specially tagged nodes in these graph sequences, we can effectively model player knowledge of the world, and the graph at a certain step explicitly encodes which transitions the player has not yet explored (and therefore might be attracted to).

Furthermore, by including notions of "powers" and "tokens" which may be required (singly or in combinations) to traverse certain edges, and which may be gained (or lost) as a result of taking certain transitions, we can model complex patterns of dependency.
A power represents an inherent ability that may be required to traverse certain edges, such as the power to swim or climb, but may also represent conditions such as the possession of a certain item or even the fact that a certain character has been convinced of something.
A token in contrast represents something where multiple copies can be obtained, and which may in some cases be used up in order to traverse certain edges (we track these with an integer count).
Empirically we have found that tracking these two kinds of game state can account for or at least approximate all of the traversal requirements in typical Metroidvania games, allowing us to encode in the decision graph requirements like "in order to open door A you first need key B, but that can only be obtained in region C which requires either power D or power E to enter."
In cases where a more continuous resource is used, we find it productive to approximate that as an integral number of tokens, as this can still capture the spatial dependency of obtaining and using a resource while reducing the complexity of the model.

Our decision mapping process consists of writing statements in a domain-specific "journal" language (see [@mawhorter2022representing]) which compiles into a sequence of decision graphs as mentioned above.
A more informal process could also be used, but the key analytical leverage lies in the abstraction of gameplay into a structure that captures the evolution of the decision graph over time.
This of course offers a very distorted view of gameplay; for example, combat and similar challenges are not formally represented and are instead reduced to annotations or tags.
That distortion serves to foreground the topology of the space and the particular way in which it was explored, which is the point of the process, and which makes it one useful lens with which to pick apart certain details of a game.

While it might seem desirable to map decisions in "natural" gameplay, there are some issues with attempting this.
When attempting to map the decisions of another player, without the ability to engage in introspection, many situations are necessarily ambiguous.
In our work, we found that each author mapped spaces somewhat differently, and there is not a single "canonical" decision graph for a particular game.
Accordingly, trying to tease out the nuances of how a third party perceives the game space is a challenge that we do not undertake here, although we think that it's a productive place for future work.

Because decision mapping is currently a laborious manual process, we focused our efforts on the introductory sequences of Hollow Knight and Yoku's Island Express (through the first boss fight in the Forgotten Crossroads in HK, and through the delivery of the badge to Nim the Translator in YIE).
We have several journal files from different authors covering these areas of each game, and our analysis in the following sections is based on those.
Because the journal format is machine-readable, we have also written some basic analysis routines to compute statistics about the exploration process, like a count of the number of unexplored options at each step.
Where relevant in those sections, we mention the specific metrics we applied, although much of our insight comes from human consideration and from the experience of the decision mapping process rather than from quantitative metrics.


# The Organization of Space in HK and YIE

 how different approaches to death affect gameplay cycles in both games, and how one might compare "linearity" between the two.

# Death and Cycles in HK and YIE

TODO: Cite @melcer2020death and @lahdenpera2018live

# Linearity in HK and YIE

# Conclusions

## Acknowledgements

This work was done on land stolen from the Massachusett, Wampanoag,
Nipmuck, Uypi, Amah Mutsun, and Chumash peoples, and the authors are
grateful for their stewardship of that land in the past, in the present,
and in the future. The history of this land is important because this
work could not have happened without its use. We acknowledge that we
directly benefit from this ongoing injustice.