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

DOI10.1007/S00224-013-9497-5MaRDI QIDQ489749zbMATH OpenOpenAlexFDO

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)

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