Quality diversity in procedural generation of first person shooter maps

Quality Diversity algorithms are a relatively recent type of evolutionary algorithm which take inspiration from the process of biological evolution to generate a set of solutions which are not only trying to optimize for a certain objective, but that are also diverse and novel. These algorithms, such as MAP-Elites, have seen widespread use in many scientific fields, including for Procedural Content Generation in various games, such as platformers, puzzle games and card games. Many commercial games have utilized Procedural Content Generation to great success, yet competitive First-Person Shooters, despite being among the most popular games in the industry, rarely utilize it in any capacity, let alone for the generation of maps, which could decrease the time spent on the hard and time-consuming task of level design. Scientific studies have recently started to explore the use of evolutionary algorithms for the generation of maps for FPS games, but have yet to use Quality Diversity algorithms, which are particularly suited for the task, given their focus on both diversity and quality. In this work we aim to fill this gap by using MAP-Elites with Sliding Boundaries (MESB) to generate maps for Project Arena, a research-oriented Unity framework for First-Person Shooters. We will define two new map representations (Point-Line and SMT-Genome) and extract metrics that describe each map, study the correlation between these metrics and use some of them to search for diverse and high-quality maps using MESB. Results show that Quality Diversity algorithms can be successfully used for this purpose, and we compared the performance of our new representations with two existing ones, All-Black and Grid-Graph, showing that the new representations can generate maps with higher diversity and overall quality, suggesting that the representation used for the generation of maps is a key factor.

Gli algoritmi di Quality Diversity sono una categoria di algoritmi evolutivi relativamente recente che si ispira al processo dell'evoluzione biologica al fine di generare un insieme di soluzioni che siano ottimali rispetto ad un obiettivo, ma che allo stesso tempo siano anche varie. Tali algoritmi, quale MAP-Elites, sono stati utilizzati in molti campi scientifici, tra i quali spicca per interesse la Genrazione Procedurale di Contenuti nei giochi, tra cui si annoverano ad esempio platformer, giochi puzzle e giochi di carte. Molti giochi hanno utilizzato la Generazione Procedurale di Contenuti con successo, tuttavia gli Sparatutto in Prima Persona competitivi, nonostante siano tra i più popolari del settore, raramente la utilizzano, tantomeno al fine di generare mappe di gioco, quando questa tecnica potrebbe ridurre il tempo speso per il dispendioso compito di level design. Di recente, diversi studi hanno utilizzato algoritmi evolutivi per la generazione di mappe per giochi FPS, ma ancora non sono stati utilizzati algoritmi di Quality Diversity, i quali risultano particolarmente indicati dato il loro focus sia sulla diversità che sulla qualità. In questa tesi ci proponiamo di colmare questa lacuna utilizzando MAP-Elites with Sliding Boundaries (MESB) per generare mappe per Project Arena, un framework sviluppato in Unity orientato alla ricerca per gli Sparatutto in Prima Persona. Definiremo due nuove rappresentazioni per le mappe (Point-Line e SMT-Genome) ed estrarremo metriche che descrivono ciascuna mappa, studieremo la correlazione tra queste metriche e ne utilizzaremo alcune per evolvere mappe che siano varie e di alta qualità utilizzando MESB. I risultati mostrano che gli algoritmi di Quality Diversity possono essere utilizzati con successo per questo scopo, e abbiamo confrontato le prestazioni delle nostre nuove rappresentazioni con due esistenti, All-Black e Grid-Graph, mostrando che le nuove rappresentazioni generano mappe con maggiore diversità e qualità complessiva, suggerendo che la rappresentazione scelta per la generazione di mappe è un fattore chiave.