The computational complexity of Portal and other 3D video games

DOI10.4230/LIPICS.FUN.2018.19MaRDI QIDQ3301006zbMATHOpenAlexFDO

Authors Erik D. Demaine, Joshua Lockhart, Jayson Lynch

Publication date 11 August 2020

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Computational complexity of two-dimensional platform games
• Games, puzzles, and computation
• Gaming is a hard job, but someone has to do it!
• Hamilton Paths in Grid Graphs
• Lemmings is PSPACE-complete
• Lower bounds for multiplayer noncooperative games of incomplete information
• Motion planning among time dependent obstacles
• PSPACE-completeness of Bloxorz and of games with 2-buttons
• Playing games with algorithms: algorithmic combinatorial game theory
• Relationships between nondeterministic and deterministic tape complexities
• Super Mario Bros. is harder/easier than we thought
• Tetris is Hard, Even to Approximate

Cited in

(12)

• The complexity of speedrunning video games
• Games, Puzzles and Treewidth
• The computational complexity of Angry Birds
• Cooperating in video games? Impossible! Undecidability of team multiplayer games
• Super Mario Bros. is harder/easier than we thought
• Gaming is a hard job, but someone has to do it!
• Classic Nintendo games are (computationally) hard
• Celeste is PSPACE-hard
• The Legend of Zelda: the complexity of mechanics
• Computational complexity of puzzles and related topics
• Cooperating in video games? Impossible! Undecidability of team multiplayer games
• Computational complexity of two-dimensional platform games

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)