](res/sable-exploration.webp)
- Exploration is a core part of many games
- Spaces shape choices
- Experience can be good or bad...
## Long-term Research Goals
- Develop a theory of 'exploration poetics'
* Develop formal language
* Identify design patterns
* Create methods for analysis
- Quantify exploration with metrics
* E.g., "unexplored option count"
* Potentially useful for PCG
## Representing Exploration
- Human cognitive structures
* Pairwise spatial relations
* 2+D maps
* Routes + landmarks
- A sequential decision-making process
* Affordances as observed are important
- Exploration as a key mechanic
- Discrete rooms present predictable affordances
- Map systems foreground exploration
# Example
## Super Metroid
{width=100% alt="A video showing an exploration process for the first two rooms of Super Metroid after Ceres Station. At the start, the avatar is on top of a ship, with nothing visible around it. After choosing to go right, the avatar falls off the ship onto bumpy ground, and continues right until they come to a cliff, with a tunnel beneath it clogged with blocks. The avatar then progresses left until they come to a blue barrier set into a cave entrance. After shooting it it opens, and going inside loads another room. In this room (the 'cave') we first pass by two narrow tunnels downwards, the first of which is also blocked by rocks. Both are too short to enter. Further left, there is a gap in the floor, and some rocks blocking the way left. Jumping over the gap and shooting the rocks proves ineffective, so the avatar jumps into the floor gap, at which point the camera scrolls down and the avatar begins to fall from ledge to ledge. At the end of the video, the avatar lands on a ledge across from another blue door, although this one is blocked with another too-short gap in front of it."}
{style="position: absolute; left: 50%; top: 17%; width: 45%;" .fragment
.fade-in data-fragment-index="1"}\
- Two major decisions
(several minor ones)
- Dead ends and blocked choices
- Feels constrained
- Areas will open up later
# The `exploration` Library
## Library Info
- Open source (BSD 3-clause)
- Python library (3.x; tested on 3.10)
- Available as `exploration` on PyPI
- Builds on the popular open-source `networkx` graph library
- Current version is 0.1.2 (alpha phase)
## `DecisionGraph`s
- A **directed** **multi-graph** with **self-links**
- Both nodes (**decisions**) and edges (**transitions**) are named
* Transition names must be unique per node
- Transitions can have **requirements** and/or **effects**
* *Tokens* and/or *powers* required/granted
* Transitions have explicit reciprocals
## `DecisionGraph`s
- Decisions and transitions can store tags and annotations
- Unexplored areas are represented as tagged decisions
- Decisions assigned to one or more zones for grouping
* Zones can contain other zones too
## `Exploration` Objects
- A sequence of `DecisionGraph`s
* Records **decision** made + **transition** taken at each step
* Also tracks *tokens* and *powers* as part of game state
- Methods for adding to current graph or advancing via a transition
* Can also wait or warp
* Arbitrary additional game state can be tracked
## Journal Conversion
- Not finished in v0.1.2
- Converts text-based journal format into an `Exploration`
* Streamlines stuff by remembering defaults, e.g., if an entry point
is omitted on revisit it can be deduced
- Current protocol for recording exploration involves transcribing a
recorded play session into this format
# Code Example
## The Graph
\
## The Code
```{.sourceCode .py .smallCode}
# Create first two decisions
e = core.Exploration()
e.start('on ship', ['left', 'right'])
e.explore('right', 'cliff', ['up cliff', 'through tunnel'], 'to ship')
# Add requirements to cliff options we can't take yet
g = e.currentGraph()
g.setTransitionRequirement('cliff', 'up cliff', 'high_jump')
g.setTransitionRequirement('cliff', 'through tunnel', 'breaker')
```
## The Code (part 2)
```{.sourceCode .py .smallCode}
# Add decision point before door
e.retrace('to ship')
e.explore('left', 'cave entrance', ['through door'], 'to ship')
# Add decision point for top room
e.explore('through door', 'cave',
['down blocked', 'down short', 'left', 'down pit'],
'door to outside')
```
## The Code (part 3)
```{.sourceCode .py .smallCode}
# Set some requirements
g = e.currentGraph()
g.setTransitionRequirement('cave', 'down blocked', 'crawl&breaker')
g.setTransitionRequirement('cave', 'down short', 'crawl')
g.setTransitionRequirement('cave', 'left', 'breaker')
# Explore down to the first ledge where a door is visible
e.explore('down pit', 'cave ledge', ['down', 'recessed door'], 'up')
# Set requirement for the door
g = e.currentGraph()
g.setTransitionRequirement('cave ledge', 'recessed door', 'crawl')
```
# Future Plans
## Journal Format
- Needs to be finalized and tested
- Will be refined with use
## Representing Open Spaces
- How will decision graphs hold up in open-world games?
- Can we do something better, or augment decision graphs?
## Metrics
- E.g., "number-of-unexplored doors at each step"
- Given examples, look for patterns
- Can we reliably infer level design idioms from metrics?
## PCG Applications
- If there's a metric, we can evolve it...
- Could develop AI to generate human-like explorations of novel spaces
- Ideally, run user studies to establish relationships between metrics +
player experience aspects, then use metrics for PCG without needing as
many user studies.
- More axes for Q/D charts? :P
# Discussion
## Representing Space
- Graph-based vs. grid-based representation of space?
* How will it translate to other genres?
## Decision Graphs
- Is a multi-di-graph the right format?
* How could/should spatial relations be annotated?
## Graph Sequences
- Could 'trace-in-a-single-graph' work instead?
- Are there things that graph-sequence will have trouble with?