Randomizers in Video Games: Algorithms and Complexity Analysis

EasyChair Preprint 12462

Abstract

Video games have become the biggest entertainment industry in the world, gathering important communities of players and modders (people that customize games). Some of these games either include randomizers natively or are modded to include randomizers. The goal of these randomizers is to change some parts of the game randomly, while keeping it playable and ensuring the game can be finished. In this paper, we formalize the most frequent forms of randomizers, analyze the complexity of generating a random configuration that still allows the game to be finished, and propose algorithms to create such configurations efficiently.

Keyphrases: complexity proofs, graph algorithms, graph models, random generation, video game randomizers

@booklet{EasyChair:12462,
  author    = {Alexandre-Quentin Berger},
  title     = {Randomizers in Video Games: Algorithms and Complexity Analysis},
  howpublished = {EasyChair Preprint 12462},
  year      = {EasyChair, 2024}}