Toward a Formal Theory of Space in First-Person Shooter Games: A Container Graph and Navigation Zone Framework — Data and Code

# Toward a Formal Theory of Space in First-Person Shooter Games## A Container Graph and Navigation Zone Framework — Data and Code

This deposit contains the data, code, and figures accompanying the paper:

> *"Toward a Formal Theory of Space in First-Person Shooter Games:> A Container Graph and Navigation Zone Framework"*

Applied to all 36 maps of Ultimate DOOM (id Software, 1995).

---

## Contents

```├── README.md                        — this file├── code/│   ├── pipeline.py                  — core extraction pipeline (no dependencies)│   ├── figures.py                   — figure generation (requires matplotlib)│   ├── analysis_notebook.ipynb     — Jupyter notebook: full analysis walkthrough│   └── requirements.txt            — Python dependencies├── data/│   ├── corpus_metrics.json         — full dataset (JSON, all 36 maps)│   ├── corpus_metrics_flat.csv     — flat CSV version for easy import│   └── README_data.md              — data dictionary and field definitions└── figures/    ├── fig1_pipeline.png           — extraction pipeline diagram    ├── fig2_E1M1_container_graph.png    ├── fig3_E1M2_container_graph.png    ├── fig4_E1M8_container_graph.png    ├── fig5_E2M7_trigger_overlay.png    ├── fig6_depth_snd_scatter.png    ├── fig7a_E1M2_zone_map.png    ├── fig7b_E3M4_zone_map.png    └── fig7c_E2M7_zone_map.png```

---

## Quick Start

### Reproduce the dataset

```bashpip install -r code/requirements.txtpython code/pipeline.py --wad DOOM.WAD --output my_corpus.json```

### Reproduce a single map

```bashpython code/pipeline.py --wad DOOM.WAD --map E2M7```

### Run the full analysis notebook

```bashpip install jupyterjupyter notebook code/analysis_notebook.ipynb```

Update the `WAD_PATH` variable in the first code cell to point to your DOOM.WAD.

### Regenerate figures

```bashpython code/figures.py --wad DOOM.WAD --corpus data/corpus_metrics.json --outdir my_figures/```

---

## Key Metrics

| Metric | Definition ||--------|-----------|| **C** | Number of containers (maximal regions bounded by keycard doors) || **Z** | Number of navigation zones (bounded by keycard + remote trigger doors) || **κ** | Predicate complexity = \|portals\| / \|containers\| || **depth** | Critical path depth: mandatory keycard gates to reach exit || **SND** | Spatial Navigation Demand = NT × nav || **NT** | Fraction of world-flag triggers that are remote (d ≥ 2) || **nav** | Mean sector-graph distance of remote triggers |

---

## Corpus Summary (36 maps, Ultimate DOOM)

| Metric | Mean | SD | Range ||--------|------|----|-------|| κ | 0.49 | 0.32 | [0.00, 0.86] || depth | 0.45 | — | [0, 2] || SND | 1.99 | 1.91 | [0.00, 8.57] || Z (zones) | 8.8 | — | [1, 30] |

- Solvable in G₀: 29/36 (E1M8, E2M8, E3M8 unsolvable — boss levels)- Maps with Z > C: 28/36

---

## Important Notes

### WAD file not included

`DOOM.WAD` cannot be redistributed as part of this deposit for copyrightreasons. A legal copy is required to run the pipeline. Ultimate DOOM isavailable via Steam and GOG.

### Zone boundary detection (corrected)

Zone boundaries use **sector-based closed-door detection**, not linedef tags.A linedef is a zone boundary iff it borders a sector where `floor == ceil`(physically closed) AND whose sector tag matches a remote trigger.

This is critical: DOOM door linedefs carry `tag=0`; it is the door *sector*that carries the activation tag. An earlier linedef-tag approach producedno zone boundaries for E1M2 and other maps.

### Geometry-encoded gates

E2M7 is reported as `crit_depth=0` because the exit linedef is in the origincontainer. In practice, the exit is behind a bridge raised only by twospecific switches — a geometry-encoded gate invisible to the predicatepipeline. This is documented as a known limitation in the paper (§4).

---

## Formal Framework Summary

**Container** (Definition 7): maximal spatial region reachable bynull-predicate traversal. Bounded only by possession predicates (keycarddoors, φ_I) and boss-death predicates (φ_Γ).

**Navigation Zone** (Definition 9): maximal spatial region reachable byφ_∅, φ_I, and φ_Ω^local traversal (d ≤ 1). Bounded by possession predicatesAND physically closed doors controlled by remote triggers (d ≥ 2).

Every zone is a subset of a container. Z ≥ C always.When Z = C, navigational phasing aligns with logical gating.When Z ≫ C, logical regions contain multiple navigational phases.

---

## License

Code: MIT License  Data: CC BY 4.0  Figures: CC BY 4.0  

DOOM.WAD is © id Software and is not included.