Paper by Erik D. Demaine
- Jeffrey Bosboom, Josh Brunner, Michael Coulombe, Erik D. Demaine, Dylan H. Hendrickson, Jayson Lynch, and Lorenzo Najt, “The Legend of Zelda: The Complexity of Mechanics”, in Abstracts from the 23rd Thailand-Japan Conference on Discrete and Computational Geometry, Graphs, and Games (TJCDCGGG 2021), September 3–5, 2021, pages 132–133.
We analyze some of the many game mechanics available to Link in the classic
Legend of Zelda series of video games. In each case, we prove that the
generalized game with that mechanic is polynomial, NP-complete, NP-hard and in
PSPACE, or PSPACE-complete. In the process we give an overview of many of the
hardness proof techniques developed for video games over the past decade: the
motion-planning-through-gadgets framework, the planar doors framework, the
doors-and-buttons framework, the “Nintendo” platform game / SAT
framework, and the collectible tokens and toll roads / Hamiltonicity
- The full paper is available as arXiv:2203.17167.
- The abstract is available in PDF (245k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Zelda_TJM (The Legend of Zelda: The Complexity of Mechanics)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated November 6, 2023 by