Quality diversity for racing track design

Quality Diversity (QD) refers to a class of evolutionary algorithms that focus on finding high-performing yet diverse solutions. They have been applied in several areas, including the exploration of search spaces for video game content. In this thesis, we investigate the use of quality diversity algorithms as tools for the procedural generation of racing tracks for the TORCS and Speed Dreams open-source racing games; the two games use an almost identical representation of the tracks. Specifically, we apply the MAP-Elites algorithm to generate racing tracks for these games, automatically using evaluation functions computed by simulating racing competitions with existing AIs. Our methodology involved developing novel genotype representations based on Voronoi diagrams and convex hulls, an end-to-end pipeline for generation and evaluation, and the use of dimensionality reduction for robust behavioral characterization.

La Quality Diversity (QD) denota una classe di algoritmi evolutivi che si concentrano sulla ricerca di soluzioni ad alte prestazioni ma diverse tra loro. Sono stati applicati in diverse aree, inclusa l'esplorazione dello spazio delle soluzioni per i contenuti dei videogiochi. In questa tesi, indaghiamo l'uso di algoritmi di quality diversity come strumenti per la generazione procedurale di tracciati di gara per i giochi di corsa open-source TORCS e Speed Dreams; i due giochi utilizzano una rappresentazione quasi identica dei tracciati. In particolare, applichiamo l'algoritmo MAP-Elites per generare tracciati di gara per questi giochi, utilizzando automaticamente funzioni di valutazione calcolate simulando competizioni di gara con IA esistenti. La nostra metodologia ha comportato lo sviluppo di nuove rappresentazioni genotipiche basate sui diagrammi di Voronoi e sugli inviluppi convessi, una pipeline end-to-end per la generazione e la valutazione, e l'uso della riduzione della dimensionalità per una robusta caratterizzazione comportamentale.