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.