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

DOI10.1007/S00224-013-9497-5zbMATH Open1303.68075arXiv1201.4995OpenAlexW2152152733MaRDI QIDQ489749FDOQ489749

Authors: G. Viglietta 

Publication date: 21 January 2015

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

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.

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

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

zbMATH Keywords

complexitygamesPac-ManStarcraftTron

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Title not available (Why is that?)
• Undirected connectivity in log-space
• Some simplified NP-complete graph problems
• Games, puzzles, and computation
• Playing games with algorithms: algorithmic combinatorial game theory
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• Computational complexity of two-dimensional platform games

Cited In (21)

• The Computational Complexity of Portal and Other 3D Video Games
• The Parameterized Complexity of Motion Planning for Snake-Like Robots
• The complexity of Snake and undirected NCL variants
• Trainyard is NP-hard
• The complexity of speedrunning video games
• Games, Puzzles and Treewidth
• Title not available (Why is that?)
• Restricted Power - Computational Complexity Results for Strategic Defense Games
• HOW DIFFICULT IS IT TO INVENT A NONTRIVIAL GAME?
• LaserTank is NP-Complete
• The computational complexity of Evil Hangman
• Mario Kart Is Hard
• Games, puzzles, and computation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lemmings is PSPACE-complete
• Cooperating in video games? Impossible! Undecidability of team multiplayer games
• The computational complexity of Angry Birds
• Classic Nintendo games are (computationally) hard
• PSPACE-Completeness of Bloxorz and of Games with 2-Buttons
• Computational complexity of two-dimensional platform games

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)