The Computational Complexity of Portal and Other 3D Video Games
From MaRDI portal
Publication:3301006
DOI10.4230/LIPIcs.FUN.2018.19zbMath1489.68106arXiv1611.10319OpenAlexW2558463491MaRDI QIDQ3301006
Erik D. Demaine, Jayson Lynch, Joshua Lockhart
Publication date: 11 August 2020
Full work available at URL: https://arxiv.org/abs/1611.10319
Analysis of algorithms and problem complexity (68Q25) Game theory (91A99) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (4)
Games, Puzzles and Treewidth ⋮ Cooperating in video games? Impossible! Undecidability of team multiplayer games ⋮ Unnamed Item ⋮ The computational complexity of Angry Birds
Cites Work
- Unnamed Item
- Unnamed Item
- Gaming is a hard job, but someone has to do it!
- Motion planning among time dependent obstacles
- Lemmings is PSPACE-complete
- Relationships between nondeterministic and deterministic tape complexities
- PSPACE-Completeness of Bloxorz and of Games with 2-Buttons
- Tetris is Hard, Even to Approximate
- Computational Complexity of Two-Dimensional Platform Games
- Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
- Hamilton Paths in Grid Graphs
- Super Mario Bros. Is Harder/Easier than We Thought
- Lower bounds for multiplayer noncooperative games of incomplete information
This page was built for publication: The Computational Complexity of Portal and Other 3D Video Games
