License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2018.27
URN: urn:nbn:de:0030-drops-88187
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8818/
Go to the corresponding LIPIcs Volume Portal

Lafond, Manuel

The complexity of speedrunning video games

pdf-format:
LIPIcs-FUN-2018-27.pdf (2 MB)

Abstract

Speedrunning is a popular activity in which the goal is to finish a video game as fast as possible. Players around the world spend hours each day on live stream, perfecting their skills to achieve a world record in well-known games such as Super Mario Bros, Castlevania or Mega Man. But human execution is not the only factor in a successful speed run. Some common techniques such as damage boosting or routing require careful planning to optimize time gains. In this paper, we show that optimizing these mechanics is in fact a profound algorithmic problem, as they lead to novel generalizations of the well-known NP-hard knapsack and feedback arc set problems.
We show that the problem of finding the optimal damage boosting locations in a game admits an FPTAS and is FPT in k + r, the number k of enemy types in the game and r the number of health refill locations. However, if the player is allowed to lose a life to regain health, the problem becomes hard to approximate within a factor 1/2 but admits a (1/2 - epsilon)-approximation with two lives. Damage boosting can also be solved in pseudo-polynomial time. As for routing, we show various hardness results, including W[2]-hardness in the time lost in a game, even on bounded treewidth stage graphs. On the positive side, we exhibit an FPT algorithm for stage graphs of bounded treewidth and bounded in-degree.

BibTeX - Entry

@InProceedings{lafond:LIPIcs:2018:8818,
  author =	{Manuel Lafond},
  title =	{{The complexity of speedrunning video games}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{27:1--27:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Hiro Ito and Stefano Leonardi and Linda Pagli and Giuseppe Prencipe},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8818},
  URN =		{urn:nbn:de:0030-drops-88187},
  doi =		{10.4230/LIPIcs.FUN.2018.27},
  annote =	{Keywords: Approximation algorithms, parameterized complexity, video games, knapsack, feedback arc set}
}

Keywords: Approximation algorithms, parameterized complexity, video games, knapsack, feedback arc set
Collection: 9th International Conference on Fun with Algorithms (FUN 2018)
Issue Date: 2018
Date of publication: 04.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI