Gaming is a hard job, but someone has to do it!

DOI10.1007/S00224-013-9497-5MaRDI QIDQ489749zbMATHOpenAlexFDO

Authors G. Viglietta

Publication date 21 January 2015

Published in Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

complexitygamesPac-ManStarcraftTron

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Abstract: We establish some general schemes relating the computational complexity of a video game to the presence of certain common elements or mechanics, such as destroyable paths, collectible items, doors opened by keys or activated by buttons or pressure plates, etc. Then we apply such "metatheorems" to several video games published between 1980 and 1998, including Pac-Man, Tron, Lode Runner, Boulder Dash, Deflektor, Mindbender, Pipe Mania, Skweek, Prince of Persia, Lemmings, Doom, Puzzle Bobble~3, and Starcraft. We obtain both new results, and improvements or alternative proofs of previously known results.

Recommendations

• The computational complexity of Portal and other 3D video games
• 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 610968 (Why is no real title available?)
• Computational complexity of two-dimensional platform games
• Games, puzzles, and computation
• Playing games with algorithms: algorithmic combinatorial game theory
• Some simplified NP-complete graph problems
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• Undirected connectivity in log-space

Cited in

(25)

• Restricted Power - Computational Complexity Results for Strategic Defense Games
• LaserTank is NP-Complete
• The computational complexity of Portal and other 3D video games
• The complexity of speedrunning video games
• The computational complexity of Evil Hangman
• Games, puzzles, and computation
• Characterizing the decidability of finite state automata team games with communication
• Games, Puzzles and Treewidth
• PSPACE-completeness of Bloxorz and of games with 2-buttons
• The computational complexity of Angry Birds
• Cooperating in video games? Impossible! Undecidability of team multiplayer games
• Breakout
• Lemmings is PSPACE-complete
• The complexity of Snake and undirected NCL variants
• Trainyard is NP-hard
• Super Mario Bros. is harder/easier than we thought
• HOW DIFFICULT IS IT TO INVENT A NONTRIVIAL GAME?
• 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
• The parameterized complexity of motion planning for snake-like robots
• Cooperating in video games? Impossible! Undecidability of team multiplayer games
• Computational complexity of two-dimensional platform games
• Mario Kart is hard

This page was built for publication: Gaming is a hard job, but someone has to do it!

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