Video Games Randomizers: Models, Complexity Analysis and Probabilistic Algorithms to Properly Randomize Games

Diplôme Thèse Video Games Randomizers: Models, Complexity Analysis and Probabilistic Algorithms to Properly Randomize Games eng 2025-11-17 2026-01-28 author Berger Alexandre-Quentin 697601 director Casteigts Arnaud 0000-0002-7819-7013 414872 Département d'informatique (DINFO) director Rolim Jose 27265 Département d'informatique (DINFO) 152 10.13097/archive-ouverte/unige:191942 urn:nbn:ch:unige-1919426 Sc. 5976 Many video games include randomizers natively or can be augmented with external randomizers. The goal of these randomizers is to change some parts of the game randomly, while keeping it playable and ensuring that the game can still be finished. In this thesis, we investigate the problem of randomizing a game for various types of games. We start by formalizing this problem as a labeling problem in directed graphs. Unfortunately, we show that a general randomizer (i.e., one that can possibly generate any finishable game) involves solving NP-hard problems as a subroutine for the vast majority of games. Motivated by this limitation, we define a restricted family of randomizers that produce finishable games by construction. We classify games in two categories, lossless and lossy games, and present multiple polynomial time randomizers for both categories. For lossless games, we present first a simple algorithm, which we then improve with multiple parameters and other options to extend as much as possible the diversity of generated games. Similarly, we follow with algorithms for lossy games, using the lossless algorithms as a base and adding another graph structure tracking resources importance in the game. Finally, we also perform practical experiments with these algorithms on a real video game, which demonstrate that these randomizers have the potential to generate meaningful games for the community of players, and so, for a broad range of video games. Algorithms Complexity Graph theory Video Game Randomizer Dewey 025.063 32 Département d'informatique 18 false 1417 Algorithms, Graph theory, and Complexity d185bd44-30c0-4cd7-a16d-793fb10cda5f Thesis Public BERGER_These_Finale_with_Imprimatur.pdf 10619303 application/pdf CC BY-4.0 a28a813b99efed3f2ba252ded1ee86e521b4cc282bd2b8d3abe856f9e70fdcc4 41736a72-a859-4070-ad5b-0b278e6a1827 Imprimatur Public BERGER_Imprimatur_signed.pdf 58012 application/pdf e0d0f6bf6d73ac0d5d360f878a7b8d5fce74960fa053d36388d14ef62afe5236 Vignette Public Capture d'écran 2026-02-25 133910.png 71678 image/png openAccess Faculté des sciences / Département d'informatique

Title	Published in	Access level	OA Policy	Year	Views	Downloads

Video Games Randomizers: Models, Complexity Analysis and Probabilistic Algorithms to Properly Randomize Games				2026	89	149

Archive ouverte UNIGE

Berger, Alexandre-Quentin

account_balance UNIGE affiliation entities

UNIGE research groups

UNIGE affiliation entities