- author = "Raphael Bailly",
- title = "Generation procedurale de niveaux de jeu alliant approche constructive et optimisation",
- title_en = "Procedural generation of game levels combining constructive approach and optimisation",
- school = "HESAM Universite",
- year = "2022",
- address = "France",
- month = Dec,
- keywords = "genetic algorithms, genetic programming, Genetic Algorithm, Wave Function Collapse, Diversity, Level Design, Video Games, Procedural Content Generation, Wave Function Collapse, Algorithme Genetique, Diversite, Level Design, Jeu Video, Generation Procedurale de Contenu, Ubisoft, FPS",
- number = "2022HESAC021",
- hal_id = "tel-03971457",
- hal_version = "v1",
-
URL = "
https://theses.hal.science/tel-03971457",
-
URL = "
https://theses.hal.science/tel-03971457v1/file/108442_BAILLY_2022_archivage.pdf",
- size = "238 pages",
-
abstract = "The research work in this thesis is positioned in the
field of procedural content generation in video games.
This study focuses more specifically on the questions
related to the diversity and quality of the generated
content. Indeed, in the video game industry, developers
are constantly challenged to offer a diverse range of
quality game environments to players. This perpetual
quest led us to study numerous methods and algorithms,
through a literature review of procedural content
generation. Eventually, we addressed the following
problem: How to achieve a generation method that offers
a high degree of diversity of game experiences, while
maintaining a certain structural quality in its
results? Our study is centred in particular on the
level design and the placement of objects in game
levels. We also targeted a generation of non-linear
open 3D levels for a first-person shooter, with a
settlement infrastructure whose contents are positioned
on a 2D grid.
This thesis introduces a new method, named Genetic-WFC, with the aim of providing a diversity of game experiences with levels having a certain structural quality. It is a procedural generation pipeline that combines a Search-Based approach, consisting of a genetic algorithm and simulation-based evaluation, with a constructive method, the Wave Function Collapse, to generate levels targeting specific game experiences. The Wave Function Collapse, abbreviated WFC, is an algorithm for propagating local adjacency constraints. In our approach, it extracts these constraints from level examples, and allows us to perform genetic search on results that do not exhibit object placement errors. It serves, in fact, as a repair operator for the individuals in the population of the genetic algorithm. The driving of the WFC, by the search algorithm, is made possible by influencing the selection probability of its elements. We employ a level re-encoding solution that allows us to improve the optimisation process of our evolutionary algorithm. We also use a synthetic player to evaluate the game experience using three perception heuristics, namely, the novelty, safety and complexity, during a simulation of a walkthrough.
Various experiments on our method have been conducted in order to establish its capabilities and performance. After looking at the computation time of the WFC for the generation of levels, a second experiment focused on comparing our approach to other similar methods, taking into account, in particular, the computation time and the score value of the results obtained. We also look at the visual differences between certain levels produced by these various methods. A last experiment is based on the evaluation of the diversity of game experiences that our procedural generation algorithm can provide.
We conclude this thesis by mentioning several areas of improvement and further research, which can be pursued more thoroughly. For example, a user experience with fully playable settlements could be a next step in the study of our method.",
-
notes = "In french
Also known as \cite{DBLP:phd/hal/Bailly22}
Uses GA but is it GP?
Supervisors: Guillaume Levieux and Axel Buendia",
