Delft Integraal
Meer wetenschapsnieuws van de TU Delft
Soldaten voor het virtuele slagveld .
http://www.delftintegraal.tudelft.nl/info/index564f.html?hoofdstuk=Artikel&ArtID=2534 (1 van 10) [26-11-2009 14:28:45]
Colofon
DI-Archief
Delft Integraal
DOOR CHRISTIAN JONGENEEL
Op de middelbare school stak Jan Paul van Waveren al meer tijd in computerspelletjes dan in huiswerk. Toch liep het niet slecht met hem af, zelfs niet toen hij aan de universiteit bezig bleef om met wat vrienden computers aan elkaar te koppelen teneinde elkaar in een spelletje Doom virtueel overhoop te knallen. Binnenkort studeert Van Waveren af op de kunstmatige intelligentie die hij voor het schietspelletje Quake III Arena ontwikkelde. Inmiddels werkt hij al bij de Amerikaanse spelletjesfabrikant id Software.
http://www.delftintegraal.tudelft.nl/info/index564f.html?hoofdstuk=Artikel&ArtID=2534 (2 van 10) [26-11-2009 14:28:45]
Schermbeeld uit Quake III Arena, een zogenaamd first-person-shoot ’em up (FPS) spel, waarbij de speler de wereld ziet vanuit het eerste persoons perspectief.
Plattegrond uit Doom. In dit spel kan de speler op elk moment de plattegrond tevoorschijn halen om zich te oriënteren. Hij kan overigens op de kaart alleen dat deel van de wereld zien dat hij al heeft verkend.
Delft Integraal
Meestal heet Jan Paul van Waveren Jan Paul van Waveren, maar soms waart hij rond in duistere kelders, een onwaarschijnlijk groot wapen in zijn handen, schietend op alles wat beweegt. Dan heet hij Mr. Elusive. De laatste tijd heeft Mr. Elusive echter niet zoveel kills meer gemaakt. Dat komt niet alleen doordat hij als zesdejaars zijn studie Technische Informatica aan de TUD DELFT nu maar eens moet afmaken. Het komt ook doordat hij het aanbod van een baan door een Amerikaanse spelletjesfabrikant niet afwees. Nu programmeert hij de spellen die hij ooit speelde. Zoals iedere programmeur weet: spelletjes behoren tot de meest veeleisende software die er bestaat. Kantoorsoftware mag best wel eens een seconde haperen, bij spelletjes is dat uit den boze. In de eerste jaren van de middelbare school was Jan Paul gefascineerd door luchtkussenvaartuigen, ofwel hovercraft. Het eerste werkende exemplaar van de Engesle uitvinder Sir Christopher Cockrell (1911-1999) vloog in 1958. De vliegboten werden niet alleen voor militaire doeleinden ingezet, zo onderhielden de grote versies tot vorig jaar veerdiensten tussen Dover en Calais. Het was eigenlijk begonnen met een interesse in modellen van helicopters. Daarna ging Jan Paul radiografische bestuurbare autootjes bouwen. De autootjes hadden zo hun beperkingen, vond hij, en begon zicht toe te leggen op het ontwerpen van Hovercraft vaartuigen. Over een periode van twee jaar bouwde hij diverse modellen; eerst met elektromotoren, later met echte verbrandingsmotoren uit de modelbouw. Het waren gedegen studies en alles wees erop dat hij werktuigbouwkunde zou gaan studeren. Op gegeven moment kwam hij via een vriendje in aanraking met de PC (Intel 286), computerspelletjes en met programmeren. Het waren de spelletjes van zijn huidige werkgever id Software: Wolfenstein en Doom. Dit zijn zogenaamde first-person games . Je kijkt door de ogen van een commando, die met een bepaalde opdracht een doolhof wordt ingestuurd. Je taak is het doolhof te verkennen, geheime deuren op te sporen, verstopte schatten, wapens en andere voorwerpen op te sporen en iedereen die je tegenwerkt genadeloos af te maken. Die tegenstanders, meestal monsters genoemd, zijn niet echt intelligent: ze staan altijd op dezelfde plek te wachten en mikken niet erg nauwkeurig. Natuurlijk kun je ook geraakt worden: een gezondheidsmetertje in beeld geeft aan of het niet weer eens tijd wordt een verbanddoos op te sporen. Doom was indertijd revolutionair. Niet alleen was de grafische kwaliteit beter dan alles daarvoor, fanatieke spelers konden zelf levels maken. http://www.delftintegraal.tudelft.nl/info/index564f.html?hoofdstuk=Artikel&ArtID=2534 (3 van 10) [26-11-2009 14:28:45]
Meestal is een klein verschil in de textuur op de muur een aanduiding van een geheime deur. Door op de wand te schieten, wordt de deur geopend.
Delft Integraal
Computerspelletjes van dit type bestaan namelijk uit verschillende onderdelen, bijvoorbeeld een onderdeel voor de grafische representatie van het doolhof en een ander voor de mogelijke bewegingen van de commando. Een level is een datastructuur die onder meer de vorm van het doolhof, de locatie van de schatten en de aantallen tegenstanders vastlegt. De makers van Doom besloten de specificatie van die datastructuur openbaar te maken. Daardoor kon iedereen zijn eigen doolhoven ontwerpen. Honderduizenden fanatieke spelers die de meegeleverde doolhoven uitgespeeld hadden, konden hun eigen exemplaren maken en die uitwisselen via internet. Zo werd Doom een spel dat je nooit helemaal ‘uit’ had. Skin ‘De laatste jaren van de middelbare school, heb ik voor Doom veel levels gemaakt. Ik maakte er ongeveer één per week’, vertelt Van Waveren. ‘Eerst werden de levels via een Bullitin Board System (BBS) verspreid, later via het Internet. Toen kwam de opvolger, Quake 1. Die kon je veel beter via een lokaal netwerk of via het Internet met elkaar spelen dan Doom. Dat heb ik veel gedaan. Nu is de hele spelletjeswereld veel groter en commerciëler geworden, maar toen was het een relatief kleine Quake 1 gemeenschap. Ik zat bij een clan, een groepje spelers dat vaak samenspeelt. We hadden een eigen skin en zo.’ Skin, dat woord vraagt om toelichting. Een figuur in een computerspelletje bestaat uit een draadmodel. De vlakjes in dat model worden gevuld met een textuur, een patroon van kleuren. Al die vlakken samen, de skin, bepalen het uiterlijk van de figuur. In Quake 1 was het mogelijk zelf een skin te maken. Monsters met het hoofd van Microsoft-voorman Bill Gates werden al snel populair. ‘Regelmatig brachten we onze PC’s bij elkaar, dat waren inmiddels Pentium 133 machines’, gaat Van Waveren verder. ‘Alleen was je uren bezig om ze aan elkaar te koppelen. Dan konden we nog net een uurtje spelen voor het tijd werd om de zaak weer op te breken. Later, via het Internet, kon je meteen aan de slag. Dat had echter ook nadelen. Ten eerste krijg je een hoge telefoonrekening. Ten tweede kan een langzame verbinding met het Internet het spel moeilijk speelbaar maken. Daarnaast houd je het tegen ervaren spelers op Internet niet lang uit, als je niet goed geoefend hebt. Oefenen tegen de niet al te intelligente monsters die in Quake 1 ingebouwd zaten, had echter niet zoveel zin. Wat zou het toch mooi zijn als je kon oefenen tegen de computer, maar dan met slimmere tegenstanders, bedacht http://www.delftintegraal.tudelft.nl/info/index564f.html?hoofdstuk=Artikel&ArtID=2534 (4 van 10) [26-11-2009 14:28:45]
Voorbeeld van geheime kamers met schatten...
... en met wapens, ammunitie en verbanddozen uit Wolfenstein.
Delft Integraal
Van Waveren. Hij bleek niet de eerste. Op internet was een groot aantal bots te vinden. Bots (het woord is afgeleid van robots) zijn programmaatjes die intelligent gedrag vertonen. De programmaatjes die namens zoekmachines het internet afstruinen om informatie te catalogiseren heten ook bots. In computerspelletjes is een bot een programma dat zich gedraagt als een menselijke tegenstander, dat wil zeggen strategisch en tot op zekere hoogte onvoorspelbaar. Daardoor wordt het oefenen stukken realistischer. ‘Van de beschikbare artificiële spelers was er eentje duidelijk de beste’, aldus Van Waveren. ‘Toch gingen mij daaraan op den duur dingen opvallen. In de moeilijkste stand kon je er niet van winnen. De bot vertoonde weliswaar intelligent gedrag, maar hij schoot meteen raak op het moment dat hij tevoorschijn kwam. In een lagere stand schoot de bot minder nauwkeurig, maar deed ook meteen minder intelligente dingen.’ Daarom wilde Van Waveren hem graag aanpassen, maar de broncode was niet beschikbaar. De broncode is de oorspronkelijke, voor mensen leesbare programmatekst voor die wordt omgezet in nullen en enen. ‘Toen ben ik begonnen om zelf kleine aanpassingen te maken aan het spel.’ ‘Een van de eerste aanpassingen was een zogeheten anti-camp modificatie. Sommige spelers blijven eindeloos op een gunstige plek hangen om anderen in de hinderlaag te lokken. Dat soort campers worden niet sportief gevonden. Mijn programmaatje gaf je een waarschuwing als je te lang op dezelfde plek bleef hangen. Ging je dan niet weg, dan teleporteerde hij je naar een andere plek. Of je kreeg een regenwolkje met bliksem boven je hoofd, dat je overal achtervolgde. Dat was niet goed voor de gezondheid.’ Omicron In 1997 had Van Waveren een bot af die een menselijke speler op een betrouwbare manier simuleerde. Omicron, zoals de bot heette, was in een mum van tijd populair. Binnen een paar uur na de release hadden 10.000 mensen hem van het internet geplukt! Na twee weken had hij bijna de top van populairste Quake-bots veroverd. Van Waverens programmeertalent viel op en hij kreeg een baan aangeboden door een Amerikaans softwarebedrijf. Die liet hij lopen – hij wilde eerst zijn studie afmaken. ‘Toen ik eraan begon, wist ik niet zoveel van kunstmatige intelligentie’, zegt hij. ‘Ik browste gewoon wat door de broncode van Quake, las er een beetje over en gebruikte mijn gezond verstand.’ Dat gezonde verstand bracht hem er toe gebruik te maken van waypoints, de digitale versie van Klein Duimjes kiezels. Een waypoint is een plek in het http://www.delftintegraal.tudelft.nl/info/index564f.html?hoofdstuk=Artikel&ArtID=2534 (5 van 10) [26-11-2009 14:28:45]
Diagram van de opbouw van Quake III Arena.
Beeld uit Quake I met Waypoints. Deze, voor menselijke spelers onzichtbare, aanwijzingen worden door de bots gebruikt om de weg terug te vinden.
Delft Integraal
doolhof waarop de artificiële speler zich kan oriënteren. Zo verdwaalt hij niet tijdens zijn tocht door het doolhof. Het is slechts één van de dingen die de bot moet kunnen. Hij moet bijvoorbeeld ook een tegenstander signaleren en gericht schieten. Natuurlijk is al de informatie, zoals posities van tegenstanders, bekend bij het Quake-programma zelf, maar daar mag de bot geen gebruik van maken, want anders heeft hij een veel te grote voorsprong op zijn menselijke tegenstander en speelt hij in zekere zin vals. De bot is daarom zo geprogrammeerd dat moet uitrekenen of hij een tegenstander vanuit de plek waar hij staat menselijkerwijs kan zien, voor hij mag schieten. ‘De methode met waypoints is nog vrij primitief’, zegt Van Waveren. ‘Of je moet als mens alle waypoints voor hem inprogrammeren, wat arbeidsintensief is, of je moet hem zelf het doolhof laten verkennen. In dat laatste geval gedraagt hij zich iedere keer weer als een beginnende speler en dat schiet niet op. Een probleem met Quake 1 was bovendien dat de waypoints zich lastig lieten inprogrammeren in de datastructuren van de speciale programmeertaal die werd gebruikt om Quake 1 aan te passen.’ De komst van Quake 2 was een uitkomst. De spelregels en artificiele intelligentie werden hier geprogrammeerd in de programmeertaal C, wat in feite betekende dat alle beperkingen vervielen. Bovendien maakte id Software net als bij Quake 1 een deel van de programmacode bekend, zodat fanatici delen van het programma naar eigen smaak konden aanpassen. Voor Quake 2 schreef Van Waveren de Gladiator bot. Daar viel veel meer aan in te stellen dan aan de voorganger. Zo kunnen de tegenstanders op een subtiele manier geprogrammeerd worden. De menselijke speler kan bijvoorbeeld aangeven of zijn kunstmatige tegenspeler een voorkeur aan de dag moet leggen voor bepaalde wapens, of hij defensief is ingesteld of juist offensief. Dat instellen gebeurt onder andere met fuzzy logic. Het is dus niet zo dat de kunstmatige speler een eigenschap wel of niet heeft – dat zou hem te voorspelbaar maken. Hij kan net als een mens zijn voorkeuren hebben, maar daar regelmatig van afwijken. De tegenstanders kregen ook een vocabulaire mee, zodat ze kunnen communiceren, zowel met de menselijke speler als onderling. Ook waren ze in staat simpele, ingetikte zinnen te ‘begrijpen’. Capture the flag De Gladiator-bot verscheen vanaf december 1998 op het internet. Er was ook een ctf-variant (Capture The Flag) van het spel Quake2 beschikbaar. Normaal gesproken is het doel van het spel het bereiken van een bepaald http://www.delftintegraal.tudelft.nl/info/index564f.html?hoofdstuk=Artikel&ArtID=2534 (6 van 10) [26-11-2009 14:28:45]
Van links naar rechts: een speler (zoals zichtbaar in het spel), dezelfde speler met het draadmodel erop geprojecteerd, de losse skin (onderverdeeld in een hoofd en het lichaam). Het draadmodel bestaat zo’n 500 tot 700 driehoekige vlakjes
Schematische opbouw van de Quake III Arena bot.
Delft Integraal
eindpunt, meestal een deur naar het volgende level. Bij ctf zijn er twee teams en is het de kunst de vlag van het andere team te veroveren. Van Waveren programeerde de bots zodanig, dat ze ook dit spelvariant begrepen. Opnieuw gingen van Waverens activiteiten niet ongemerkt voorbij: ‘In juni 1999 kreeg ik een mailtje van Graeme Devine, projectleider bij id Software. Ze waren bezig met Quake 3. Ze wilden een bot inbouwen, maar daar hadden ze weinig ervaring mee, terwijl ik er al twee tot drie jaar mee bezig was. De vraag was of ik eens in Dallas, Texas langs wilde komen om wat te praten en ideeën uit te wisselen en ze stuurden me een ticket. Ik ging er totaal niet heen met de gedachte een baan mee terug te nemen. Het leek me gewoon een leuk uitje.’ ‘Eenmaal in Dallas lieten zij eerst zien hoe hun bots in elkaar zaten en daarna toonde ik de mijne’, gaat hij verder. ‘Ik had mijn bots zo gebouwd, dat ze makkelijk waren te integreren in een ander spel. We hadden toen het idee om dat dan ook maar eens te proberen. In een paar dagen hebben we hem toen aangepast voor Quake 3. Dat werkte zo goed dat ze dachten: misschien moeten we die bot of delen ervan gewoon overnemen. Ik heb de broncode aan hen verkocht. Daarna werd ik ingehuurd voor verdere integratie en uitbreiding van de botcode. In eerste instantie ben ik vooral met de kunstmatige intelligentie bezig geweest, maar nu doe ik ook allerlei andere dingen. Zo werk ik nu bijvoorbeeld aan bepaalde onderdelen van een nieuwe versie van Doom.’ Ondertussen wil hij ook nog afstuderen, en wel op zijn werk voor Quake 3. Dat betekent vooral schrijven, want het werk is al gedaan. De door van Waveren bedachte bot voor Quake 3 kan niet alleen in zijn eentje door het doolhof manoeuvreren, hij kan ook samenwerken met andere bots, als ware het een legereenheid. Basisvaardigheden ‘De bot voor Quake 3 is opgebouwd uit vier lagen’, legt Van Waveren uit. ‘In de onderste laag zit de basis: de input en output van de bot, dat wil zeggen de informatie die de bot tot zich kan nemen en de acties die hij kan ondernemen. Tot de input behoort onder meer de representatie van de omgeving en tot de output de mogelijke bewegingen. Die bewegingen zijn bijvoorbeeld lopen en springen. Voor de representatie van de omgeving maak ik gebruik van area’s. Een area is een aaneengesloten deel van de omgeving. De kunstmatige speler weet in welke area hij zich bevindt en in welk deel daarvan en kan van daaruit snel achterhalen waar hij heen kan. Bij http://www.delftintegraal.tudelft.nl/info/index564f.html?hoofdstuk=Artikel&ArtID=2534 (7 van 10) [26-11-2009 14:28:45]
Voorbeeld van een menu met commando’s die de teamleider (luitenant) gebruikt om zijn medespeler te instrueren.
Delft Integraal
het lopen is dat eenvoudig: dat zijn de aangrenzende area’s. Maar bij springen kan hij ook naar niet-aangrenzende area’s. Dat moet allemaal worden uitgerekend en vastgelegd.’ De onderste laag legt dus vast wat de kunstmatige speler allemaal aan basisvaardigheden in huis heeft en zorgt voor de algemene informatievoorziening. Maar daarmee doet hij nog niets. De laag daarboven houdt zich onder andere met korte-termijndoelen bezig. Als hij bijvoorbeeld maximaal twee dingen kan dragen en hij heeft al een verbanddoos, is het niet verstandig een tweede doos op te pikken, tenzij hij zwaar gewond is. ‘Hij moet dus bepalen hoe graag hij het voorwerp wil hebben’, zegt Van Waveren. ‘Daarvoor gebruik ik fuzzy logic. Daarmee weeg je de verschillende argumenten tegen elkaar af. Daaruit trekt hij de conclusie of hij het voorwerp wel of niet oppakt.’ De derde laag verzorgt de echte intelligentie: het bepalen van de langetermijndoelen en de overlevingsstrategie. Daartoe werkt de bot verschillende state (toestands)-procedures af. Hij begint bij zijn lange-termijndoel, bijvoorbeeld het uitschakelen van een bepaalde tegenstander. Daarvan leidt hij de korte-termijndoelen af, gezien de huidige omstandigheden. Dat kan er bijvoorbeeld toe leiden dat hij naar de puzzel-toestand moet om een probleem op te lossen. Een simpel voorbeeld: als hij een begerenswaardig voorwerp ziet liggen, maar hij kan er niet bij (bijvoorbeeld omdat er een gesloten traliedeur voor zit), dan moet hij een nieuw doel bepalen dat hij eerst moet halen, voor hij het voorwerp kan bereiken. Met zo’n keten van redeneringen lost hij de puzzel op. Komt hij een tegenstander tegen, dan gaat hij naar de ‘battle-state’. De eigenschappen van de kunstmatige speler, vastgelegd in de tweede laag, bepalen dan bijvoorbeeld of hij liever springt of bukt om kogels te ontwijken. Gaat de tegenstander ervandoor, dan moet hij bepalen wat gegeven de omstandigheden het best is: de achtervolging inzetten of terug gaan naar de lange-termijndoelen. Besluit hij de achtervolging in te zetten, dan moet hij na een paar seconden opnieuw beslissen: heeft het nog zin? Tijdens een gevecht kan de bot ook beslissen zelf de benen te nemen als hij er slecht aan toe is. Luitenant De technologie hierachter is die van een expert systeem: een heleboel alsdan-regels, die voortdurend worden afgewerkt. De intelligentie volgt uit de interactie van de vele regels. Ten opzichte van veel traditionele expert http://www.delftintegraal.tudelft.nl/info/index564f.html?hoofdstuk=Artikel&ArtID=2534 (8 van 10) [26-11-2009 14:28:45]
Quake III Arena heeft trampolines (jumppads) waarmee de speler zich snel kan verplaatsen. Dit beeld geeft weer hoe de bot zo’n trampoline ziet: het gebiedje (area) waar de trampoline zich bevindt en de area waar de speler terecht komt.
Een sprong van de ene pilaar naar de andere, zoals de bot dat voorziet.
Delft Integraal
systemen is er echter een beperkende factor: tijd. Een vloeiend verloop van het spel gaat voor alles. Het heeft ook weinig zin alle regels iedere tiende van een seconde te doorlopen (dat is de tijdseenheid waarmee de bots in Quake 3 denken). Als de kunstmatige speler net rondgekeken heeft of er begerenswaardige voorwerpen in zicht zijn, hoeft hij dat een halve stap later niet nog eens te doen. Speuren naar tegenstanders blijft echter wel cruciaal. Desgewenst kan het ook allemaal voor je worden gedaan. Een menselijke speler kan een aantal bots om zich heen verzamelen, die hij als een generaal aanvoert. Van Waveren: ‘Dat kan ook als je met mensen speelt, maar bots zijn over het algemeen gehoorzamer.’ Sterker nog, het is mogelijk een luitenant aan te wijzen die met een paar recruten bijvoorbeeld een belangrijke plek verdedigt. De intelligentie daarvoor zit in de vierde laag. Een leider moet immers niet alleen zijn eigen doelen bepalen, maar ook die van zijn ondergeschikten. Via tekst worden de bevelen uitgewisseld en het maakt de bots niet uit of die van een mens komen of van een andere bot. Als je dat zou willen, zou je zelfs legers van bots tegen elkaar kunnen laten vechten en dan voor het scherm kijken wie het er het beste vanaf brengt. Maar daar gaat het natuurlijk niet om bij schietspelletjes. Het gaat om overlevingsdrang, agressie afkoelen, puzzelen en vooral superioriteitsgevoelens tot uiting brengen. En om steeds slimmere technologie, de grondslag van een miljardenindustrie, die bezig is Hollywood qua omvang te overvleugelen.
Voor nadere informatie over dit onderwerp kunt u contact opnemen met Jan Paul van Waveren, tel. (0172) 588 264, e-mail mrelusive@idsoftware. com of met http://www.delftintegraal.tudelft.nl/info/index564f.html?hoofdstuk=Artikel&ArtID=2534 (9 van 10) [26-11-2009 14:28:45]
Visuele geschiedenis van de FPS-spellen Wolfenstein 3D (1993) Doom I (1994) Duke Nukem 3D (1995) Quake (1996) Quake II (1997) Unreal (1998) Half-Life (1998) Unreal Tournement (1999) Quake III Arena (1999)
Delft Integraal
dr. Leon Rothkrantz, tel. (015) 278 7504, e-mail rothkrantz@its. tudelft.nl
l.j.m.
http://www.delftintegraal.tudelft.nl/info/index564f.html?hoofdstuk=Artikel&ArtID=2534 (10 van 10) [26-11-2009 14:28:45]
