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.

Exploration Design

• 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

See Peer, et al. 2021 “Structuring Knowledge with Cognitive Maps and Cognitive Graphs.”

Metroidvanias

• Exploration as a key mechanic
• Discrete rooms present predictable affordances
• Map systems foreground exploration

Super Metroid

 

• Two major decisions
  (several minor ones)
• Dead ends and blocked choices
• Feels constrained
• Areas will open up later

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)

DecisionGraphs

• 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

DecisionGraphs

• 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 DecisionGraphs
  • 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

The Graph

The Code

# 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)

# 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)

# 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')

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

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?