game

DecisionmakingandactioncontrollingsystemsincommonuseinthecomputergameindustryOliverWood-UniversityofDurham12Contents1.Introduction31.1.Aims31.2.History31.3.GamesGenre31.4.TheneedforAIincomputergames41.5.GroupingAImethods42.ControlofNon-PlayerCharacters52.1.Movementscripts52.2.FiniteStatemachines62.3.Hierarchicalstatemachines82.4.BehavioralAnimation92.5.FuzzyLogicandFuSMs102.6.Planners132.7.Neutralnetworks132.8.Pathfindingtechniques173.Conclusions18References1831.IntroductionThecomputergamesindustryisnowbiggerthantheHollywoodfilmsindustry[htt02].Asthehardwarecapabilityincreasesthefocusshiftsfromgraphicsandanimationtogameplay.Amajorfeatureofgoodgameplayistheperceivedlevelofintelligenceoftheotherplayers,betheyreal(multiplayernetworkgames)orcomputercontrolled(NPC’s).Themechanismsforcontrollingplayershavegotincreasinglymorecomplexinthelast20years,movingfromscriptedmovement,andatbestsituationresponsetypecodingtoforwardthinking,planning,emotiondrivenagents.1.1.Aims.Thisdocumentwill•Provideanoverviewandinsightintothecurrentlyavailabletechnologiesappertainingtoartificialintelligencewithincomputergames,namelythosewhichcontrolNonPlayerCharactersmotorfunctions.•AttempttoinvestigatethelinksbetweenacademicAIresearchandthecomputergamesindustryThisdocumentwillnot•coverotherusesofartificialdecisionmakingtechnologiessuchas“smartcameras”forcontrollingtheplayersview•CovertheauxiliarytechnologiesthatsupporttheAIimplementationingames.Forexample,sensorsystems,scriptingandpathfinding.1.2.History.Sincetheearlydaysofcomputers,infactsincetheearlydaysofoscilloscopescomputergamesseemtohavebeeninexistence.Forafarmoredetailedhistoryoftheriseofvideogamessee[KM]1.3.GamesGenre.Computergamestendtofallintoneatcategories,withveryfewcrossovers.Therearethegamesthatblendroleplayandactioncombat,buttheytendtobefewandfarbetween.Therearealsotheoddgamesthatskipallcategories,thuscreatingtheirown,TheSimsandCreaturesbeingtwothat,bytheirveryinception,definedthe“VirtualPets”genrewhichhasbeendescribedas“somewherebetweenaGodGame,areal-timesoapopera,andadigitaldollshouse”.Commonlyrecognisedgamegenreinclude...Classic:ClassicgamessuchasChess,Go,andDraughtsaregenerallyre-gardedtobeclassicdomainofacademicresearchappliedtothefieldofcomputergaming.Howevermanyalsoconsiderthisarea“have[been]more-or-lessbeen“solved”byAItechniques”[Woob]RPG:RolePlayGames,originallyverymuchinthe“dungeonsanddrag-ons”stylewereoneofthefirsttypeofcomputergametoachievewidedis-tribution.InthelastfewyearsmanyAIprogrammerhavestatedthatRPGcharactermightwellbethefutureofAIgameimplementationasitisanareawheregreatimprovementsarepossible.[Deu00]GodGame:Withtheirhighlyrecognisable“viewedfromtheair”perspec-tivegamessuchasSimCity,BlackandWhite,PopulusandCivilisationareexcellentexamplesofagenrethatwasearlyhotbedsofinnovativeap-proachestocomputergameAI.Godgamesoftenhaveahugenumberofautonomouscharactersonscreenatanyonetime,manyofwhomareoftenrepresentationofhumanbeingsandmustbeseentobehaveassuch.4FirstPersonShooter:GamessuchasDoom,QuakeandUnrealsawguntotingcarnageandeverimproving3Dgraphicsdemandcleverandcunningopponents.Itisthe1stPersonShootergameswhichhavebeenseentobe“advancingtheart”[Woo99b]inthelastcoupleofyears.SportSimulation:Sportsimulationendsupinagenreofitsownbecauseofitsinvolvementwithhumanbeing.Becausesportsaresolelyplayedbyhumans,inmuchthesamewithasGodGames,anyrepresentationofhumanon-screenthatbehavesoddlywillbepickeduponfarmoreeas-ilythatanotherautonomouscharacter.SomeAIresearchedasmindedthattechnologiessuchasneuralnetworksmightholdthekeytomimickingrecognisablehumantraits,andthattheSportsSimulationmightwelltothegenrewherethisisnotapplication.Arcade/Action:Definedtoencompassmanyothersub-genre.Actionsgamescovereverysubjectfromflightsimulators(alargeenoughgenreinitsownright)totheplatformgamessuchasMarioBrothersandSonicTheHedge-hogthatdominatedthelate80’sandearly90’s.SomegenresarenodoubtbettersuitedtotheinvestigationofAI,suchastheFirstPersonShootergenre,becausetheyfeatureeasilyidentifiedcharacterswhicharereliedontolook“realistic”.Theonecommonfeatureofmostgamesisthattherearecomputercontrolledcharacters.Someearlygamesdidnotinvolveother“characters”explicitly,howeverthereareveryfewthatdidn’tinvolvesomeformofautomatedobjectsbethosetrapdoors,platformsetc.Alloftheserequiresomeformofcharactercontrolsystem,suchasthosethatwillbeexplored.1.4.TheneedforAIincomputergames.TherearenodoubtcomputergameswhichhavenoresidentAIintheirdesign.TheobviouscontenderforsuchgamesaresologamessuchasSolitaireandminesweeper,buteversimplecardgamesmusthavesomebodytoplayagainst!Anopponent,andthechallengeofactuallybeatingsomebody(orsomething)atagameincreasestheplayabilityofthatgamenoend,andassuchishighlydesirabletogamesdevelopers.Itishardtothinkofamoderngamewithoutsomeformofautonomouscharacters.SidMeier(gamesguruandfatherofmanytobestsellinggamesofalltime)gothisfirstjobinthecomputergameindustrywhencould“consistentlyrackuphigherscores”thananex-pilotwhenplayingaflightsimulatorgame.HehadspottedthepatternsoftheAIincontroloftheoppositionandcouldthusoutp