Evolutionary algorithms for generating interesting fighting game character mechanics

Abstract

Abstract: Procedural content generation (PCG) is the process of generating video game content through algorithms and has been used in the game industry for a long time. "Content" refers to elements in a game such as levels, terrain, or game rules. PCG has several benefits for the industry since computer-generated content can inspire human designers, and be used to create games with endless content. Research interest in the PCG field has grown over the last couple of decades, where PCG problems are often formulated as search problems. Evolutionary algorithms have frequently been applied as the search mechanism, with an objective defined by a desired content quality. The optimal quality in entertainment games can be formulated as the question "will a player enjoy this content?" This quality has been quantified by heuristics within different game genres, with success. A promising approach is based on evaluating content while it is played in a game, referred to as simulation-based evaluation. Constraint novelty search is an evolutionary algorithm that has emerged and shown promise in the field of PCG. The commonly used objective given by a fitness function is replaced by the objective of novelty alone. This thesis is a first attempt at using constraint novelty search, with constraints based on simulation-based evaluation, to generate character mechanics in a fighting game. Character mechanics refer to the technical design of characters, i.e., how they may behave in a game. Aesthetics like graphics and sound are not considered. A simple two-player fighting game will be used for this research, developed by the thesis authors. The game is based on design patterns seen in commercial fighting games. User studies are conducted to evaluate the generated character mechanics, based on the enjoyment of test subjects. The results show that the applied generation method can produce multiple characters that are perceived as more interesting than human-designed characters. However, characters of high quality are not generated consistently. The amount of test subjects is limited, such that further research is needed to verify our results. The proposed generation method can be applied to other fighting games on the conceptual level. However, the implemented system is dependent on technical aspects and heuristics of the game used for this thesis.

Sammendrag: Prosesuell generering (Procedural Content Generation, PCG på engelsk) er en metode brukt i spillutvikling for å generere spillinnhold ved bruk av algoritmer fremfor menneskelig arbeid. Spillinnhold er elementer som for eksempel baner eller terreng. PCG er nyttig siden det kan inspirere til nytt design, spare arbeidstimer, og produsere spill med ubegrenset innhold. Som forskningsfelt har interessen for PCG økt de siste tiårene, hvor PCG problemer ofte blir formulert som søkeproblemer. Evolusjonære algoritmer er en av de mest brukte algoritmene i PCG, hvor algoritmens mål (objective) er spillinnhold av høy kvalitet fra et menneskeperspektiv. Tidligere forskning på PCG har lyktes med å kvantifisere kvaliteten på spillinnhold ved å bruke heuristikker basert på kunsitg intelligente algoritmer som spiller gjennom innholdet. Denne kvantifiseringsteknikken kalles simuleringsbasert evaluering. Denne oppgaven er et forsøk på å benytte evolusjonære algoritmer i PCG-feltet for å generere fyiskken til spillkarakterer i "fighting game"-sjangeren. Vi bruker en variant av evolusjonære algoritmer kalt "Constrained novelty search", som fokuserer på å genere unike karakterer som oppfyller visse kvalitetskriterier under en simuleringsbasert evaluering. Med fysikken til en spillkarakter, refererer vi til karakteresn fysiske egenskaper, som f. eks farten, styrken og størrelsen til karakteren. Spillkarakterenes grafiske elementer og lydelementer er ikke vurdert i denne oppgaven. Vi konstruerte et system som genererer spillkarakterer for et enkelt 2D-spill i fighting game-sjangeren. Vi utførte brukertester for å vurdere systemet ved å trekke ut et sett med karakterer for testing. Resultatene viser at karakterene generert av systemet vårt i flertallet av tilfellene var mer interessante enn de andre, menneskekonstruerte karakterene, sett fra brukernes perspektiv. Enkelte av de genererte karakterene var dog lite interessante, så systemet vårt var ikke helt konsistent. I tillegg var antallet brukertestere lavt, så mer forskning behøves for å trekke klarere konklusjoner. Systemet for karaktergenerering kan brukes til spill i fighting game-sjangeren generelt, men mye av systemet er implementert med hensyn på spillet som er brukt i denne oppgaven.