The Computational Complexity of Angry Birds and Similar Physics-Simulation Games

Authors

  • Matthew Stephenson Australian National University
  • Jochen Renz Australian National University
  • Xiaoyu Ge Australian National University

DOI:

https://doi.org/10.1609/aiide.v13i1.12947

Keywords:

Angry Birds, NP-hard, NP-complete, Computational Complexity, Physics games

Abstract

This paper presents several proofs for the computational complexity of the popular physics-based puzzle game AngryBirds. By using a combination of different gadgets within this game’s environment, we can demonstrate that the problem of solving Angry Birds levels is NP-hard. Proof of NP-hardness is by reduction from a known NP-complete problem, in this case 3-SAT. In addition, we are able to show that the original version of Angry Birds is within NP and therefore alsoNP-complete. These proofs can be extended to other physics-based games with similar mechanics.

Downloads

Published

2021-06-25

How to Cite

Stephenson, M., Renz, J., & Ge, X. (2021). The Computational Complexity of Angry Birds and Similar Physics-Simulation Games. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 13(1), 241-247. https://doi.org/10.1609/aiide.v13i1.12947

Issue

Vol. 13 No. 1 (2017): Thirteenth Artificial Intelligence and Interactive Digital Entertainment Conference

Section

Poster Papers