The computational complexity of Portal and other 3D video games

DOI10.4230/LIPICS.FUN.2018.19zbMATH Open1489.68106arXiv1611.10319OpenAlexW2558463491MaRDI QIDQ3301006FDOQ3301006

Erik D. Demaine, Jayson Lynch, Joshua Lockhart

Publication date: 11 August 2020

Abstract: We classify the computational complexity of the popular video games Portal and Portal 2. We isolate individual mechanics of the game and prove NP-hardness, PSPACE-completeness, or (pseudo)polynomiality depending on the specific game mechanics allowed. One of our proofs generalizes to prove NP-hardness of many other video games such as Half-Life 2, Halo, Doom, Elder Scrolls, Fallout, Grand Theft Auto, Left 4 Dead, Mass Effect, Deus Ex, Metal Gear Solid, and Resident Evil. These results build on the established literature on the complexity of video games.

Full work available at URL: https://arxiv.org/abs/1611.10319

Recommendations

• Gaming is a hard job, but someone has to do it!
• Computational complexity of two-dimensional platform games
• Classic Nintendo games are (computationally) hard
• Super Mario Bros. is harder/easier than we thought
• Games, puzzles, and computation

zbMATH Keywords

hardnessmotion planningPSPACENPvideo gamesPortal

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Game theory (91A99)

Cites Work

• Title not available (Why is that?)
• Relationships between nondeterministic and deterministic tape complexities
• Hamilton Paths in Grid Graphs
• Lower bounds for multiplayer noncooperative games of incomplete information
• Title not available (Why is that?)
• Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
• Motion planning among time dependent obstacles
• Computational Complexity of Two-Dimensional Platform Games
• Gaming is a hard job, but someone has to do it!
• Tetris is Hard, Even to Approximate
• Lemmings is PSPACE-complete
• PSPACE-Completeness of Bloxorz and of Games with 2-Buttons
• Super Mario Bros. Is Harder/Easier than We Thought

Cited In (5)

• The complexity of speedrunning video games
• Games, Puzzles and Treewidth
• Title not available (Why is that?)
• Cooperating in video games? Impossible! Undecidability of team multiplayer games
• The computational complexity of Angry Birds

This page was built for publication: The computational complexity of Portal and other 3D video games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3301006)