Level testen automatiseren met AI

Laten we ons verdiepen in het gebruik van AI (kunstmatige intelligentie) bij het testen van levels van een platform game.

Hoe automatiseer je het testen van procedureel gegenereerde game levels? Dat is wat wij ons afvroegen bij de ontwikkeling van de Water Battle game. De Water Battle is ontwikkeld met als doel om kinderen en volwassenen beter te leren omgaan met water. In dit spel zitten levels die gespeeld kunnen worden om punten te verdienen. Om elke week nieuwe, gevarieerde levels uit te brengen, hebben we procedurele generatie gebruikt. Het probleem waar we alleen tegenaan liepen was dat er soms nog fouten er in voorkwamen, waardoor het level niet haalbaar was. Ook was het lastig om van tevoren in te schatten hoe moeilijk de levels waren. Om hier achter te komen moeten alle levels handmatig doorgespeeld worden. Dit kost natuurlijk ongelooflijk veel tijd. Deze tijd kunnen we veel beter gebruiken om onze games nog leuker te maken.

Na een half jaar is er een systeem ontwikkeld dat zelfstandig de levels van de Water Battle game kan doorspelen en testen. Dit systeem heeft de naam Chimp (Challenge Intensity Measurement Platform) gekregen. Het probeert tijden het doorspelen zo veel mogelijk informatie over het gespeelde level te krijgen. Deze informatie bestaat onder andere uit hoeveel pickups er in het level zijn opgepakt, welke acties er allemaal uitgevoerd zijn om het level uit te spelen en waar in het level CHIMP is geweest. Op basis van deze informatie kunnen we bepalen hoe moeilijk het level is. Hierdoor kunnen we CHIMP de levels laten testen en aan de hand van de informatie die CHIMP teruggeeft de levels aanpassen zodat deze altijd haalbaar zijn.

Maar hoe zijn we bij CHIMP uitgekomen, en hoe is dit systeem tot stand gekomen? Laten we bij het begin beginnen.

Te veel levels om te testen

Voor de Water Battle game hebben we een heleboel levels gemaakt die gevarieerd kunnen worden. Om ervoor te zorgen dat de levels niet repetitief worden, hebben we een manier ontwikkeld waardoor de levels elke week variëren. Door deze grote variatie van stukken levels zijn het er te veel om allemaal met de hand te kunnen testen. Om een voorbeeld te geven van de schaal van het mogelijke aantal levels: er zijn 116 puzzel chunks (stukken level) en 68 runner chunks, die allemaal gebruikt kunnen worden om per week 15 puzzel levels te maken en 15 runner levels. Als er gemiddeld 3 chunks per level zijn, dan zijn er 116^3 mogelijke combinaties van deze puzzel chunks per level. Dat zijn ongeveer 1.5 miljoen verschillende mogelijkheden per puzzel level. Dat zijn natuurlijk te veel mogelijkheden om allemaal met de hand te gaan testen.

Het belang van performance, complexiteit en uitbreidbaarheid

Om een oplossing te vinden die het beste past bij hoe we willen dat het systeem gaat werken, zijn er een aantal factoren waar rekening mee gehouden moet worden. Bij ons waren de belangrijkste factoren performance, complexiteit en uitbreidbaarheid.

Het was belangrijk dat de performance van het systeem niet te veel ging vragen van het spel, dit omdat het voor ons belangrijk was dat we konden zien wat CHIMP aan het doen is. En hoe gaaf is het om een scherm in je kantoor te hebben waarop je kunt zien hoe je eigengemaakte spel automatisch doorgespeeld wordt!

Ook was het belangrijk dat het goed te zien was waarom gekozen werd om bijvoorbeeld een bepaald pad te kiezen of een sprong te maken. Als we dit weten kunnen we beter aanpassingen doen aan het level. Ook moest het systeem te gebruiken zijn in meerdere games zodat we niet alleen voor de Water Battle, maar ook voor de andere games die we maken de levels kunnen testen.

Interessante technieken voor AI testing

Dit zijn natuurlijk een aantal specifieke factoren die wij belangrijk vonden voor dit systeem, maar om een systeem helemaal nieuw te bedenken is erg moeilijk. Daarom hebben we veel onderzoek gedaan naar bestaande oplossingen. Daarbij zijn we een aantal interessante technieken tegengekomen. Een aantal van deze technieken zijn zelflerende algoritmes.

Neuraal Netwerk

Een neuraal netwerk is een systeem dat is gebaseerd op hoe het menselijk brein ook werkt, die zelf kan leren hoe een spel doorgespeeld moet worden. Hierbij is het alleen wel lastig om te beredeneren waarom het bepaalde keuzes maakt. Ook is het mogelijk dat het bepaalde acties gaat leren die een menselijke speler nooit zal overwegen om te doen. Bijvoorbeeld een sprong waarvan het lijkt dat het niet gehaald kan worden. Maar omdat het neurale netwerk preciezer kan beoordelen of de sprong gehaald kan worden zal hij deze wel gaan maken.

Imitation Learning algoritme

Een andere optie was een Imitiation Learning algoritme. Dit algoritme gaat het speelgedrag van een speler nabootsen. Hierdoor zal het nooit acties gaan uitvoeren die de speler ook niet uitvoert. Alleen om het Imitation Learning algoritme te laten leren, is er veel data nodig met hoe een speler het spel doorspeelt. Daardoor zouden we alsnog de levels heel vaak moeten doorspelen.

Graph based pathfinding

Uiteindelijk zijn we uitgekomen op een Graph Based Pathfinding systeem. Dit systeem zal op basis van het level een diagram (graph) maken waar een algoritme op losgelaten kan worden die het kortste pad door deze diagram heen vindt. Omdat er al veel kennis is van hoe het level doorgespeeld moet worden en het makkelijker te lezen is waarom het algoritme voor een bepaald pad of actie kiest, paste dit het beste bij ons probleem. Deze methode kunnen we ook makkelijker toepassen op onze andere games. Het systeem hoeft namelijk niet eerst een andere game opnieuw te leren spelen. Het kan gewoon de levels elke keer weer opnieuw analyseren.

Afwegen van alle mogelijke acties

Door te kijken vanaf de huidige situatie welke acties mogelijk zijn, wordt er een diagram opgebouwd. In de bovenstaande afbeelding is te zien hoe deze verschillende acties eruitzien. Vanaf de huidige positie kan er een actie naar links of rechts gedaan worden (de groene kubussen en lijnen), een enkele sprong naar links of naar rechts (de rode kubussen en lijnen), of een dubbele sprong (de zwarte kubussen en lijnen). Bij deze dubbele sprongen zijn er meer variaties die gemaakt kunnen worden.

Als zo’n actie dan mogelijk is, dan kan er vanaf dat punt verder gekeken worden welke acties mogelijk zijn. Door dit tot een bepaalde diepte te doen, wordt er een diagram gemaakt die uitgelezen kan worden door een algoritme om een kortste pad te vinden.

Lagen maken van diagrammen met mogelijke acties

Wanneer er obstakels in de weg zitten, word de diagram op een andere manier uitgebouwd. Simpele obstakels, zoals een blok waar overheen gesprongen kan worden, zijn op deze manier wel te overwinnen. Maar obstakels, zoals een waterspuit die uitgeschakeld moet worden d.m.v. een knop, wordt anders in de diagram geplaatst. Omdat het voor de speler gelijk duidelijk is met welke knop een waterspuit uitgeschakeld kan worden, hebben we dit ook makkelijk gemaakt voor CHIMP.

Wanneer CHIMP een knop tegenkomt, dan weet het gelijk welke waterspuit door die knop uitgeschakeld wordt. Alleen kunnen de acties die door de uitgeschakelde waterspuit niet op dezelfde manier bij de diagram ingevoegd worden als de normale acties. Deze acties kunnen pas gedaan worden als er op de knop gedrukt wordt. Om dit op te lossen worden de acties in een aparte laag van de diagram gevoegd nadat de knop is ingedrukt. In de onderstaande afbeelding is hier een voorbeeld van te zien. In de onderste laag gaat het pad niet verder dan de knop. Om dan het indrukken van de knop te simuleren in de diagram worden de acties in een andere laag verder uitgevoerd. In deze laag staat de waterspuit wel uitgeschakeld en kan er dus overheen gesprongen worden.

Het de gelaagde diagram kunnen we zo opbouwen dat deze rekening houdt met de volgorde van de acties die uitgevoerd worden. Als zo’n diagram helemaal is uitgewerkt dan ziet het er zoals de onderstaande afbeelding uit.

Dit ziet er nu nog uit als een grote waas van verschillende acties, maar voor het systeem ziet dit er heel logisch uit. Met het Dijkstra of AStar algoritme kan er een pad gevonden worden vanaf het beginpunt van de speler tot het einde van het level. In de onderstaande afbeelding is te zien hoe dat pad er uit ziet nadat een algoritme door de diagram heeft gezocht. Door acties aan deze verbindingen toe te wijzen, kan de speler door de computer bewogen worden en het gevonden pad aflopen.

Door deze stappen achter elkaar te blijven uitvoeren kan CHIMP het level zelfstandig doorspelen. In de onderstaande gifjes is te zien hoe het eerste puzzel en het eerste  runner level van de Water Battle doorgespeeld worden.

Analyseren en rapporteren van doorspeelsessies

Nadat CHIMP de levels heeft doorgespeeld, maakt het een rapport voor ons waarin staat wat CHIMP allemaal tegen is gekomen in het level. Hierin staan bijvoorbeeld dingen zoals hoe vaak hij gesprongen heeft, hoe lang hij over het level heeft gedaan en hoeveel pickups er zijn opgepakt. Ook staat waar CHIMP is geweest in het level, en of het ergens vast is komen te zitten. Als we deze rapporten samenvatten kunnen we gelijk zien welke levels niet of nauwelijks haalbaar zijn.

Optimaliseren van de performance

De performance van CHIMP is een probleem waar we tegenaan liepen tijdens de ontwikkelingsfase. We hebben alle verschillende instellingen, zoals hoever de diagram uitgebreid moet worden, zo afgesteld dat we een acceptabele framerate krijgen. Maar dit gaat wel ten koste van het vooruitkijken van CHIMP. Doordat er veel rekenkracht nodig is om het level te analyseren, hebben we de diepte van de diagram teruggebracht. Hierdoor kan CHIMP maar beperkt om zich heen kijken en heeft het soms niet direct in de gaten wat het goede pad precies is. Om het juiste pad dan te vinden heeft CHIMP wat meer tijd nodig terwijl dit voor de speler misschien direct duidelijk is.

Ter afsluiting

We kunnen concluderen dat Graph Based pathfinding de beste manier is om de levels van onze games automatisch te laten testen met inachtneming van onze overwegingen: het balanceren van de performance optimalisatie, de mogelijkheid om vooruit te kijken en de uitbreidbaarheid naar andere games.

Hopelijk zal CHIMP ons in de toekomst gaan helpen om de levels van al onze games te testen. Dan hebben we zeker genoeg tijd om onze spellen nog leuker en uitdagender te maken!

Vond je dit artikel interessant? Lees dan ook onze verdiepingsartikelen over procedureel gegenereerde waterverfeffecten en ‘Everything Procedural‘. Blijf op de hoogte van nieuwe artikelen door je in te schrijven voor de nieuwsbrief.