Mi trovis iun interesan materialon pri artefarita inteligenteco en ludoj. Kun klarigo de bazaj aferoj pri AI uzante simplajn ekzemplojn, kaj interne estas multaj utilaj iloj kaj metodoj por ĝia oportuna disvolviĝo kaj dezajno. Kiel, kie kaj kiam uzi ilin ankaŭ estas tie.
La plej multaj el la ekzemploj estas skribitaj en pseŭdokodo, do neniu altnivela programa scio estas bezonata. Sub la tranĉo estas 35 folioj de teksto kun bildoj kaj gifoj, do pretiĝu.
UPD. Mi pardonpetas, sed mi jam faris propran tradukon de ĉi tiu artikolo pri Habré . Vi povas legi lian version , sed ial la artikolo preterpasis min (mi uzis la serĉon, sed io misfunkciis). Kaj ĉar mi skribas en blogo dediĉita al luddisvolviĝo, mi decidis lasi mian version de la traduko por abonantoj (kelkaj punktoj estas formatitaj malsame, iuj estis intence preterlasitaj laŭ konsilo de la programistoj).
Kio estas AI?
Luda AI temigas kiajn agojn objekto devas plenumi surbaze de la kondiĉoj en kiuj ĝi situas. Tio estas kutime referita kiel "inteligenta agento-" administrado, kie agento estas rolanto, veturilo, bot, aŭ foje io pli abstrakta: tuta grupo de unuoj aŭ eĉ civilizo. En ĉiu kazo, ĝi estas afero, kiu devas vidi sian medion, fari decidojn surbaze de ĝi kaj agi laŭ ili. Ĉi tio nomiĝas la ciklo Senco/Pensi/Agi:
- Senco: La agento trovas aŭ ricevas informojn pri aferoj en sia medio, kiuj povas influi ĝian konduton (minacoj proksime, aĵoj por kolekti, interesaj lokoj por esplori).
- Pensu: La agento decidas kiel reagi (konsideras ĉu estas sufiĉe sekure kolekti erojn aŭ ĉu li unue devus batali/kaŝi).
- Ago: la agento faras agojn por efektivigi la antaŭan decidon (komencas moviĝi al la malamiko aŭ objekto).
- ...nun la situacio ŝanĝiĝis pro la agoj de la roluloj, do la ciklo ripetas kun novaj datumoj.
AI tendencas koncentriĝi sur la Senco-parto de la buklo. Ekzemple, aŭtonomaj aŭtoj fotas la vojon, kombinas ilin kun radaraj kaj lidaraj datumoj kaj interpretas ilin. Ĉi tio estas kutime farita per maŝina lernado, kiu prilaboras envenantajn datumojn kaj donas al ĝi signifon, ĉerpante semantikajn informojn kiel "estas alia aŭto 20 metrojn antaŭ vi." Ĉi tiuj estas la tiel nomataj klasifikaj problemoj.
Ludoj ne bezonas kompleksan sistemon por ĉerpi informojn, ĉar la plej multaj el la datumoj jam estas integra parto de ĝi. Ne necesas ruli algoritmojn de rekono de bildoj por determini ĉu estas malamiko antaŭen—la ludo jam scias kaj nutras la informojn rekte en la decidan procezon. Tial, la Senco-parto de la ciklo ofte estas multe pli simpla ol la Pensi kaj Agu-parto.
Limigoj de Game AI
AI havas kelkajn limojn kiuj devas esti observitaj:
- AI ne bezonas esti trejnita anticipe, kvazaŭ ĝi estus maŝinlernada algoritmo. Ne havas sencon skribi neŭralan reton dum evoluo por monitori dekojn da miloj da ludantoj kaj lerni la plej bonan manieron ludi kontraŭ ili. Kial? Ĉar la ludo ne estis publikigita kaj ne estas ludantoj.
- La ludo devus esti amuza kaj defia, do agentoj ne devus trovi la plej bonan aliron kontraŭ homoj.
- Agentoj devas aspekti realismaj por ke ludantoj sentas, ke ili ludas kontraŭ realaj homoj. La programo AlphaGo superis homojn, sed la ŝtupoj elektitaj estis tre malproksimaj de la tradicia kompreno de la ludo. Se la ludo simulas homan kontraŭulon, ĉi tiu sento ne devus ekzisti. La algoritmo devas esti ŝanĝita tiel ke ĝi faru kredindajn decidojn prefere ol idealajn.
- AI devas funkcii en reala tempo. Ĉi tio signifas, ke la algoritmo ne povas monopoligi CPU-uzadon dum longaj tempodaŭroj por fari decidojn. Eĉ 10 milisekundoj estas tro longaj, ĉar plej multaj ludoj bezonas nur 16 ĝis 33 milisekundojn por fari la tutan prilaboradon kaj pluiri al la sekva grafikkadro.
- Ideale, almenaŭ parto de la sistemo devus esti datuma, tiel ke ne-kodistoj povas fari ŝanĝojn kaj alĝustigoj povas okazi pli rapide.
Ni rigardu alirojn de AI, kiuj kovras la tutan ciklon Sento/Pensi/Ag.
Farante Bazajn Decidojn
Ni komencu per la plej simpla ludo - Pong. Celo: movu la padelon tiel ke la pilko resaltu de ĝi prefere ol preterflugi ĝin. Estas kiel teniso, kie oni perdas se oni ne batas la pilkon. Ĉi tie la AI havas relative facilan taskon - decidi en kiu direkto movi la platformon.
Kondiĉaj deklaroj
Por la AI en Pong, la plej evidenta solvo estas ĉiam provi meti la platformon sub la pilko.
Simpla algoritmo por tio, skribita en pseŭdokodo:
ĉiu kadro/ĝisdatigo dum la ludo funkcias:
se la pilko estas maldekstre de la padelo:
movi padelon maldekstren
alie se la pilko estas dekstre de la padelo:
movu padelon dekstren
Se la platformo moviĝas kun la rapideco de la pilko, tiam ĉi tiu estas la ideala algoritmo por la AI en Pong. Ne necesas kompliki ion ajn se ne estas tiom da datumoj kaj eblaj agoj por la agento.
Ĉi tiu aliro estas tiel simpla, ke la tuta ciklo Senco/Pensi/Ago estas apenaŭ rimarkebla. Sed ĝi estas tie:
- La Senco-parto estas en du se deklaroj. La ludo scias kie estas la pilko kaj kie estas la platformo, do la AI serĉas tiun informon.
- La Think-parto ankaŭ estas inkluzivita en la du if-deklaroj. Ili enkorpigas du solvojn, kiuj en ĉi tiu kazo estas reciproke ekskluzivaj. Kiel rezulto, unu el tri agoj estas elektita - movu la platformon maldekstren, movu ĝin dekstren aŭ faru nenion se ĝi jam estas ĝuste poziciigita.
- La Ago-parto troviĝas en la deklaroj Move Paddle Left kaj Move Paddle Right. Depende de la luddezajno, ili povas movi la platformon tuj aŭ je specifa rapideco.
Tiaj aliroj nomiĝas reaktivaj - ekzistas simpla aro de reguloj (en ĉi tiu kazo se deklaroj en la kodo), kiuj reagas al la nuna stato de la mondo kaj ekagas.
Arbo de decido
La Pong-ekzemplo estas fakte ekvivalenta al formala AI-koncepto nomata decidarbo. La algoritmo trairas ĝin por atingi "folion"—decidon pri kia ago fari.
Ni faru blokdiagramon de la decida arbo por la algoritmo de nia platformo:
Ĉiu parto de la arbo estas nomita nodo - AI uzas grafikan teorion por priskribi tiajn strukturojn. Estas du specoj de nodoj:
- Decidnodoj: elektado inter du alternativoj bazitaj sur testado de iu kondiĉo, kie ĉiu alternativo estas reprezentita kiel aparta nodo.
- Finnodoj: La ago por plenumi, kiu reprezentas la finan decidon.
La algoritmo komenciĝas de la unua nodo (la "radiko" de la arbo). Ĝi aŭ faras decidon pri kiu infana nodo iri, aŭ ĝi efektivigas la agon stokitan en la nodo kaj eliras.
Kio estas la avantaĝo de havi decidan arbon fari la saman laboron kiel la if-deklaroj en la antaŭa sekcio? Estas ĝenerala sistemo ĉi tie kie ĉiu decido havas nur unu kondiĉon kaj du eblajn rezultojn. Ĉi tio permesas al la programisto krei AI el datumoj reprezentantaj decidojn en arbo sen devi malmola kodigi ĝin. Ni prezentu ĝin en formo de tabelo:
Sur la koda flanko vi ricevos sistemon por legi ŝnurojn. Kreu nodon por ĉiu el ili, konektu decidlogikon bazitan sur la dua kolumno, kaj infannodojn bazitajn sur la tria kaj kvara kolumnoj. Vi ankoraŭ bezonas programi la kondiĉojn kaj agojn, sed nun la strukturo de la ludo estos pli kompleksa. Ĉi tie vi aldonas pliajn decidojn kaj agojn, kaj poste agordu la tutan AI per simple redaktado de la tekstdosiero de arbdifino. Poste, vi transdonas la dosieron al la luddezajnisto, kiu povas ŝanĝi la konduton sen rekompili la ludon aŭ ŝanĝi la kodon.
Decidarboj estas tre utilaj kiam ili estas konstruitaj aŭtomate el granda aro de ekzemploj (ekzemple, uzante la ID3-algoritmon). Ĉi tio faras ilin efika kaj alt-efikeca ilo por klasifiki situaciojn surbaze de la datumoj akiritaj. Tamen ni preterpasas simplan sistemon por ke agentoj elektu agojn.
Scenaroj
Ni analizis decidarban sistemon, kiu uzis antaŭkreitajn kondiĉojn kaj agojn. La persono desegnanta la AI povas organizi la arbon kiel li volas, sed li ankoraŭ devas fidi la kodilon, kiu programis ĉion. Kio se ni povus doni al la dezajnisto la ilojn por krei siajn proprajn kondiĉojn aŭ agojn?
Por ke la programisto ne devas skribi kodon por la kondiĉoj Estas Ball Left Of Paddle kaj Is Ball Right Of Paddle, li povas krei sistemon en kiu la dezajnisto skribos kondiĉojn por kontroli ĉi tiujn valorojn. Tiam la datumo de decida arbo aspektos jene:
Ĉi tio estas esence la sama kiel en la unua tabelo, sed la solvoj en si mem havas sian propran kodon, iom kiel la kondiĉa parto de se deklaro. Sur la kodflanko, ĉi tio legus en la dua kolumno por la decidnodoj, sed anstataŭ serĉi specifan kondiĉon por ekzekuti (Ĉu Ball Left Of Paddle), ĝi taksas la kondiĉan esprimon kaj resendas veran aŭ malveran laŭe. Ĉi tio estas farita per la skriptlingvo Lua aŭ Angelscript. Uzante ilin, programisto povas preni objektojn en sia ludo (pilko kaj padelo) kaj krei variablojn kiuj estos disponeblaj en la skripto (ball.position). Ankaŭ, la skriptlingvo estas pli simpla ol C++. Ĝi ne postulas plenan kompilfazon, do ĝi estas ideala por rapide ĝustigi ludlogikon kaj permesas al "ne-kodistoj" krei la necesajn funkciojn mem.
En la supra ekzemplo, la skriptlingvo estas uzata nur por taksi la kondiĉan esprimon, sed ĝi ankaŭ povas esti uzata por agoj. Ekzemple, la datumoj Move Paddle Right povus fariĝi skripto-deklaro (ball.position.x += 10). Por ke la ago ankaŭ estas difinita en la skripto, sen neceso programi Movu Paddle Dekstren.
Vi povas iri eĉ plu kaj skribi la tutan decidan arbon en skriptlingvo. Ĉi tio estos kodo en formo de malmolaj kondiĉaj deklaroj, sed ili troviĝos en eksteraj skriptodosieroj, tio estas, ili povas esti ŝanĝitaj sen rekompili la tutan programon. Vi ofte povas redakti la skriptodosieron dum ludado por rapide testi malsamajn AI-reagojn.
Eventa Respondo
La supraj ekzemploj estas perfektaj por Pong. Ili senĉese kuras la ciklon Senco/Pensi/Agi kaj agas surbaze de la plej nova stato de la mondo. Sed en pli kompleksaj ludoj vi devas reagi al individuaj eventoj, kaj ne taksi ĉion samtempe. Pong ĉi-kaze jam estas malbona ekzemplo. Ni elektu alian.
Imagu pafilon, kie la malamikoj estas senmovaj ĝis ili detektas la ludanton, post kio ili agas depende de sia "specialiĝo": iu kuros por "rapidi", iu atakos de malproksime. Ĝi ankoraŭ estas baza reaktiva sistemo - "se ludanto estas ekvidita, faru ion" - sed ĝi povas esti logike dividita en eventon de Ludanto Vidita kaj Reago (elektu respondon kaj plenumu ĝin).
Ĉi tio revenas nin al la ciklo Senco/Pensi/Ago. Ni povas kodi parton de Sense, kiu kontrolos ĉiun kadron ĉu la AI vidas la ludanton. Se ne, nenio okazas, sed se ĝi vidas, tiam la evento Ludanto Vidita estas kreita. La kodo havos apartan sekcion, kiu diras "kiam okazas la evento de Ludanto Vidita, faru", kie estas la respondo, kiun vi bezonas por trakti la partojn Pensi kaj Agi. Tiel, vi starigos reagojn al la evento Player Seen: por la "rapidanta" karaktero - ChargeAndAttack, kaj por la kaŝpafisto - HideAndSnipe. Ĉi tiuj rilatoj povas esti kreitaj en la datumdosiero por rapida redaktado sen devi rekompili. Skriptlingvo ankaŭ povas esti uzata ĉi tie.
Farante malfacilajn decidojn
Kvankam simplaj reagsistemoj estas tre potencaj, ekzistas multaj situacioj kie ili ne sufiĉas. Kelkfoje vi devas fari malsamajn decidojn surbaze de tio, kion la agento nuntempe faras, sed estas malfacile imagi ĉi tion kiel kondiĉo. Kelkfoje estas tro da kondiĉoj por efike reprezenti ilin en decida arbo aŭ skripto. Kelkfoje vi devas taksi anticipe kiel la situacio ŝanĝiĝos antaŭ ol decidi pri la sekva paŝo. Pli kompleksaj aliroj estas necesaj por solvi ĉi tiujn problemojn.
Finhava ŝtatmaŝino
Fina ŝtatmaŝino aŭ FSM (finia ŝtatmaŝino) estas maniero diri ke nia agento estas nuntempe en unu el pluraj eblaj statoj, kaj ke ĝi povas transiri de unu ŝtato al alia. Estas certa nombro da tiaj ŝtatoj — de tie la nomo. La plej bona ekzemplo de la vivo estas semaforo. Estas malsamaj sekvencoj de lumoj en malsamaj lokoj, sed la principo estas la sama - ĉiu stato reprezentas ion (halti, marŝi, ktp.). Semaforo estas en nur unu stato en ajna momento, kaj moviĝas de unu al alia surbaze de simplaj reguloj.
Ĝi estas simila rakonto kun NPC-oj en ludoj. Ekzemple, ni prenu gardiston kun la sekvaj statoj:
- Patrolado.
- Atakante.
- Fuĝante.
Kaj ĉi tiuj kondiĉoj por ŝanĝi ĝian staton:
- Se la gardisto vidas la malamikon, li atakas.
- Se la gardisto atakas sed ne plu vidas la malamikon, li revenas por patroli.
- Se gardisto atakas sed estas grave vundita, li forkuras.
Vi ankaŭ povas skribi se-deklarojn kun gardanta stato variablo kaj diversaj kontroloj: ĉu estas malamiko proksime, kio estas la sannivelo de la NPC, ktp. Ni aldonu kelkajn pliajn ŝtatojn:
- Senlaboreco - inter patroloj.
- Serĉado - kiam la ekvidita malamiko malaperis.
- Trovi Helpon - kiam malamiko estas ekvidata, sed estas tro forta por batali sola.
La elekto por ĉiu el ili estas limigita - ekzemple, la gardisto ne iros serĉi kaŝitan malamikon se li havas malaltan sanon.
Post ĉio, ekzistas grandega listo de "se" , Tio " povas fariĝi tro maloportuna, do ni devas formaligi metodon kiu ebligas al ni konservi ŝtatojn kaj transirojn inter ŝtatoj en menso. Por fari tion, ni konsideras ĉiujn ŝtatojn, kaj sub ĉiu ŝtato ni skribas en listo ĉiujn transirojn al aliaj ŝtatoj, kune kun la kondiĉoj necesaj por ili.
Ĉi tio estas ŝtata transirtabelo - ampleksa maniero reprezenti FSM. Ni desegnu diagramon kaj ricevu kompletan superrigardon pri kiel NPC-konduto ŝanĝiĝas.
La diagramo reflektas la esencon de decido por ĉi tiu agento bazita sur la nuna situacio. Plie, ĉiu sago montras transiron inter ŝtatoj se la kondiĉo apud ĝi estas vera.
Ĉiun ĝisdatigon ni kontrolas la nunan staton de la agento, trarigardas la liston de transiroj, kaj se la kondiĉoj por la transiro estas plenumitaj, ĝi akceptas la novan staton. Ekzemple, ĉiu kadro kontrolas ĉu la 10-sekunda tempigilo eksvalidiĝis, kaj se jes, tiam la gardisto iras de la Idling-ŝtato al Patrolado. En la sama maniero, la Atakanta stato kontrolas la sanon de la agento - se ĝi estas malalta, tiam ĝi iras en la Fuĝantan staton.
Ĉi tio pritraktas transirojn inter ŝtatoj, sed kio pri la konduto asociita kun la ŝtatoj mem? Koncerne efektivigi la realan konduton por speciala ŝtato, ekzistas tipe du specoj de "hoko" kie ni asignas agojn al la FSM:
- Agoj, kiujn ni periode plenumas por la nuna stato.
- La agoj, kiujn ni faras dum transiro de unu ŝtato al alia.
Ekzemploj por la unua tipo. La Patrolŝtato movos la agenton laŭ la patrola itinero ĉiun kadron. La Atako-ŝtato provos komenci atakon ĉiun kadron aŭ transiron al ŝtato kie ĉi tio eblas.
Por la dua tipo, konsideru la transiron "se la malamiko estas videbla kaj la malamiko estas tro forta, tiam iru al la stato Trovi Helpon. La agento devas elekti kien iri por helpo kaj konservi ĉi tiujn informojn por ke la stato de Trovi Helpon sciu kien iri. Post kiam helpo estas trovita, la agento iras reen al la Ataka stato. Je ĉi tiu punkto, li volos rakonti al la aliancano pri la minaco, do la ago NotifyFriendOfThreat povas okazi.
Denove, ni povas rigardi ĉi tiun sistemon per la lenso de la ciklo Senco/Pensi/Agi. Senco estas enkorpigita en la datumoj uzataj de la transira logiko. Pensu - transiroj haveblaj en ĉiu ŝtato. Kaj Ago estas efektivigita per agoj periode faritaj ene de ŝtato aŭ ĉe transiroj inter ŝtatoj.
Foje kontinue baloti transirkondiĉojn povas esti multekosta. Ekzemple, se ĉiu agento faras kompleksajn kalkulojn ĉiu kadro por determini ĉu ĝi povas vidi malamikojn kaj kompreni ĉu ĝi povas transiri de la Patrolado al Ataka stato, ĉi tio prenos multe da CPU-tempo.
Gravaj ŝanĝoj en la stato de la mondo povas esti opiniitaj kiel eventoj, kiuj estos prilaboritaj dum ili okazas. Anstataŭe de la FSM kontrolanta la transirkondiĉon "ĉu mia agento povas vidi la ludanton?" ĉiun kadron, aparta sistemo povas esti agordita por kontroli malpli ofte (ekz. 5 fojojn je sekundo). Kaj la rezulto estas elsendi Ludanton Vidita kiam la ĉeko pasas.
Ĉi tio estas transdonita al la FSM, kiu nun devus iri al la ricevita kondiĉo de la evento Ludanto Vidita kaj respondi laŭe. La rezulta konduto estas la sama krom preskaŭ nerimarkebla prokrasto antaŭ respondi. Sed agado pliboniĝis rezulte de apartigo de la Senco-parto en apartan parton de la programo.
Hierarkia finhava maŝino
Tamen, labori kun grandaj FSM-oj ne ĉiam estas oportuna. Se ni volas vastigi la atakan staton por apartigi MeleeAttacking kaj RangedAttacking, ni devos ŝanĝi la transirojn de ĉiuj aliaj ŝtatoj, kiuj kondukas al la Attacking-ŝtato (nuna kaj estonta).
Vi verŝajne rimarkis, ke en nia ekzemplo estas multaj duplikataj transiroj. La plej multaj transiroj en la Idling-ŝtato estas identaj al transiroj en la Patroling-ŝtato. Estus bone ne ripeti nin, precipe se ni aldonas pli da similaj statoj. Estas senco grupigi Idling kaj Patrolling sub la ĝenerala etikedo de "ne-batala", kie ekzistas nur unu komuna aro de transiroj por kontraŭbatali ŝtatojn. Se ni pensas pri ĉi tiu etikedo kiel ŝtato, tiam Idling kaj Patroling fariĝas subŝtatoj. Ekzemplo de uzado de aparta transirtabelo por nova ne-batala subŝtato:
Ĉefaj ŝtatoj:
Eksterbatala statuso:
Kaj en diagrama formo:
Ĝi estas la sama sistemo, sed kun nova ne-batala stato kiu inkluzivas Idling kaj Patroling. Kun ĉiu ŝtato enhavanta FSM kun subŝtatoj (kaj ĉi tiuj subŝtatoj, siavice, enhavantaj siajn proprajn FSM-ojn - kaj tiel plu tiel longe kiel vi bezonas), ni ricevas Hierarkian Finhavan Ŝtatan Maŝinon aŭ HFSM (hierarkian finhavan ŝtatmaŝinon). Grupigante la ne-batala staton, ni eltranĉas amason da redundaj transiroj. Ni povas fari la samon por iuj novaj ŝtatoj kun komunaj transiroj. Ekzemple, se en la estonteco ni vastigos la Atakan staton al la MeleeAttacking kaj MissileAttacking-ŝtatoj, ili estos subŝtatoj kiuj transiras unu la alian surbaze de distanco al la malamiko kaj municio havebleco. Kiel rezulto, kompleksaj kondutoj kaj subkondutoj povas esti reprezentitaj kun minimumo de duplikataj transiroj.
Konduta arbo
Kun HFSM, kompleksaj kombinaĵoj de kondutoj estas kreitaj en simpla maniero. Tamen, estas eta malfacilaĵo, ke decidado en formo de transirreguloj estas proksime rilata al la nuna stato. Kaj en multaj ludoj tio estas ĝuste tio, kio necesas. Kaj zorgema uzo de ŝtata hierarkio povas redukti la nombron da transiraj ripetoj. Sed foje vi bezonas regulojn, kiuj funkcias, negrave en kia stato vi estas, aŭ kiuj validas en preskaŭ ajna ŝtato. Ekzemple, se la sano de agento falas al 25%, vi volos, ke li forkuru sendepende de ĉu li estis en batalo, senmova aŭ parolanta - vi devos aldoni ĉi tiun kondiĉon al ĉiu stato. Kaj se via dezajnisto poste volas ŝanĝi la malaltan sanan sojlon de 25% al 10%, tiam ĉi tio devos esti farita denove.
Ideale, ĉi tiu situacio postulas sistemon en kiu decidoj pri "kiu stato esti" estas ekster la ŝtatoj mem, por fari ŝanĝojn nur en unu loko kaj ne tuŝi la transirajn kondiĉojn. Kondutaj arboj aperas ĉi tie.
Estas pluraj manieroj efektivigi ilin, sed la esenco estas proksimume la sama por ĉiuj kaj similas al decidarbo: la algoritmo komenciĝas per "radiko" nodo, kaj la arbo enhavas nodojn kiuj reprezentas aŭ decidojn aŭ agojn. Tamen estas kelkaj ŝlosilaj diferencoj:
- Nodoj nun resendas unu el tri valoroj: Sukcesita (se la laboro estas finita), Malsukcesa (se ĝi ne povas esti komencita), aŭ Running (se ĝi ankoraŭ funkcias kaj ne ekzistas fina rezulto).
- Ne plu estas decidnodoj por elekti inter du alternativoj. Anstataŭe, ili estas Decorator-nodoj, kiuj havas unu infannodon. Se ili Sukcesas, ili ekzekutas sian nurinfanan nodon.
- Nodoj kiuj plenumas agojn resendas Kurantan valoron por reprezenti la agojn farantajn.
Ĉi tiu malgranda aro de nodoj povas esti kombinita por krei grandan nombron da kompleksaj kondutoj. Ni imagu la HFSM-gardiston de la antaŭa ekzemplo kiel konduta arbo:
Kun ĉi tiu strukturo ne devus esti evidenta transiro de Idling/Patrolling-ŝtatoj al Attacking aŭ ajnaj aliaj ŝtatoj. Se malamiko estas videbla kaj la sano de la karaktero estas malalta, ekzekuto ĉesos ĉe la Fuĝanta nodo, sendepende de kiu nodo ĝi antaŭe ekzekutis - Patrolado, Idling, Attacking, aŭ ajna alia.
Kondutaj arboj estas kompleksaj—estas multaj manieroj komponi ilin, kaj trovi la ĝustan kombinaĵon de dekoraciistoj kaj kunmetitaj nodoj povas esti malfacila. Estas ankaŭ demandoj pri kiom ofte kontroli la arbon - ĉu ni volas trarigardi ĉiun parton de ĝi aŭ nur kiam unu el la kondiĉoj ŝanĝiĝis? Kiel ni konservas staton pri nodoj - kiel ni scias, kiam ni malaktivis dum 10 sekundoj, aŭ kiel ni scias, kiuj nodoj ekzekutis la lastan fojon, por ke ni povu ĝuste prilabori la sekvencon?
Tial estas multaj efektivigoj. Ekzemple, kelkaj sistemoj anstataŭigis dekoraciistnodojn kun enliniaj dekoraciistoj. Ili retaksas la arbon kiam dekoraciistkondiĉoj ŝanĝiĝas, helpas aliĝi al nodoj kaj disponigas periodajn ĝisdatigojn.
Utilaĵ-bazita sistemo
Iuj ludoj havas multajn malsamajn mekanikojn. Estas dezirinde, ke ili ricevu ĉiujn avantaĝojn de simplaj kaj ĝeneralaj transiraj reguloj, sed ne nepre en la formo de kompleta arbo de konduto. Anstataŭ havi klaran aron de elektoj aŭ arbo de eblaj agoj, estas pli facile ekzameni ĉiujn agojn kaj elekti la plej taŭgan en la momento.
La Servo-bazita sistemo helpos nur ĉi tion. Ĉi tio estas sistemo, kie la agento havas diversajn agojn kaj elektas kiujn plenumi surbaze de la relativa utileco de ĉiu. Kie utileco estas arbitra mezuro de kiom grava aŭ dezirinda estas por la agento plenumi ĉi tiun agon.
La kalkulita utileco de ago bazita sur la nuna stato kaj medio, la agento povas kontroli kaj elekti la plej taŭgan alian staton iam ajn. Tio estas simila al FSM, krom kie transiroj estas determinitaj per takso por ĉiu ebla ŝtato, inkluzive de la nuna. Bonvolu noti, ke ni elektas la plej utilan agon por pluiri (aŭ resti se ni jam plenumis ĝin). Por pli da vario, ĉi tio povus esti ekvilibra sed hazarda elekto el malgranda listo.
La sistemo asignas arbitran gamon da utilvaloroj - ekzemple, de 0 (tute nedezirinda) ĝis 100 (tute dezirinda). Ĉiu ago havas kelkajn parametrojn, kiuj influas la kalkulon de ĉi tiu valoro. Revenante al nia gardista ekzemplo:
Transiroj inter agoj estas ambiguaj — ĉiu ŝtato povas sekvi ajnan alian. Agoprioritatoj troviĝas en la resenditaj utilaj valoroj. Se malamiko estas videbla, kaj tiu malamiko estas forta, kaj la sano de la karaktero estas malalta, tiam kaj Fuĝi kaj FindingHelp resendos altajn ne-nulajn valorojn. En ĉi tiu kazo, FindingHelp ĉiam estos pli alta. Same, nebatalaj agadoj neniam revenas pli ol 50, do ili ĉiam estos pli malaltaj ol batalaj. Vi devas konsideri ĉi tion kiam vi kreas agojn kaj kalkulas ilian utilecon.
En nia ekzemplo, la agoj resendas aŭ fiksan konstantan valoron aŭ unu el du fiksaj valoroj. Pli realisma sistemo resendus takson de kontinua gamo de valoroj. Ekzemple, la ago Fuĝanta redonas pli altajn utilajn valorojn se la sano de la agento estas malalta, kaj la Ataka ago resendas pli malaltajn utilajn valorojn se la malamiko estas tro forta. Pro tio, la ago Fuĝanto havas prioritaton super Atakado en ajna situacio kie la agento sentas ke li ne havas sufiĉe da sano por venki la malamikon. Tio permesas al agoj esti prioritatitaj surbaze de iu nombro da kriterioj, igante ĉi tiun aliron pli fleksebla kaj varia ol konduta arbo aŭ FSM.
Ĉiu ago havas multajn kondiĉojn por programa kalkulo. Ili povas esti skribitaj en skriptlingvo aŭ kiel serio de matematikaj formuloj. La Sims, kiu simulas la ĉiutagan rutinon de karaktero, aldonas plian tavolon de kalkulo - la agento ricevas serion da "motivoj" kiuj influas servaĵojn. Se rolulo malsatas, ili fariĝos eĉ pli malsata kun la tempo, kaj la utilvaloro de la ago EatFood pliiĝos ĝis la karaktero plenumos ĝin, reduktante la malsatnivelon kaj resendante la valoron EatFood al nulo.
La ideo elekti agojn bazitajn sur taksa sistemo estas sufiĉe simpla, do sistemo bazita sur Utilaĵo povas esti uzata kiel parto de AI-decidprocezoj, anstataŭ kiel kompleta anstataŭaĵo por ili. La decidarbo povas peti servaĵorangigon de du infannodoj kaj elekti la pli altan. Simile, konduta arbo povas havi kunmetitan Utilaĵnodon por taksi la utilecon de agoj por decidi kiun infanon ekzekuti.
Movado kaj navigado
En la antaŭaj ekzemploj, ni havis platformon, kiun ni movis maldekstren aŭ dekstren, kaj gardiston, kiu patrolis aŭ atakis. Sed kiel precize ni pritraktas agentan movon dum tempodaŭro? Kiel ni agordas rapidon, kiel ni evitas obstaklojn, kaj kiel ni planas itineron kiam atingi cellokon estas pli malfacila ol simple moviĝi en rekta linio? Ni rigardu ĉi tion.
Administrado
En la komenca etapo, ni supozos, ke ĉiu agento havas rapidecan valoron, kiu inkluzivas kiom rapide ĝi moviĝas kaj en kiu direkto. Ĝi povas esti mezurita en metroj je sekundo, kilometroj je horo, pikseloj je sekundo, ktp. Rememorante la buklon Sento/Pensi/Ag, ni povas imagi, ke la parto Pensi elektas rapidon, kaj la parto Akto aplikas tiun rapidon al la agento. Tipe ludoj havas fizikan sistemon, kiu faras ĉi tiun taskon por vi, lernante la rapidecvaloron de ĉiu objekto kaj ĝustigante ĝin. Sekve, vi povas lasi la AI kun unu tasko - por decidi kian rapidecon havu la agento. Se vi scias, kie devas esti la agento, tiam vi devas movi ĝin en la ĝusta direkto je fiksita rapideco. Tre bagatela ekvacio:
dezirata_vojaĝado = celloko_pozicio – agento_pozicio
Imagu 2D mondon. La agento estas ĉe punkto (-2,-2), la celloko estas ie en la nordoriento ĉe punkto (30, 20), kaj la postulata vojo por la agento por alveni tien estas (32, 22). Ni diru, ke ĉi tiuj pozicioj estas mezuritaj en metroj - se ni prenas la rapidecon de la agento kiel 5 metrojn sekundo, tiam ni skalos nian movovektoron kaj ricevos rapidecon de proksimume (4.12, 2.83). Kun ĉi tiuj parametroj, la agento alvenus al sia celloko en preskaŭ 8 sekundoj.
Vi povas rekalkuli la valorojn iam ajn. Se la agento estus duonvoje al la celo, la movado estus duono de la longo, sed ĉar la maksimuma rapido de la agento estas 5 m/s (ni decidis ĉi tion supre), la rapido estos la sama. Ĉi tio ankaŭ funkcias por movi celojn, permesante al la agento fari malgrandajn ŝanĝojn dum ili moviĝas.
Sed ni volas pli da variado - ekzemple, malrapide pliigi la rapidecon por simuli karakteron moviĝantan de starado al kurado. La sama povas esti farita ĉe la fino antaŭ ĉesi. Tiuj trajtoj estas konataj kiel stirkondutoj, ĉiu el kiuj havas specifajn nomojn: Serĉi, Fuĝi, Alveno, ktp. La ideo estas ke akcelfortoj povas esti aplikitaj al la rapideco de la agento, surbaze de komparo de la pozicio de la agento kaj nuna rapideco kun la celloko en por uzi malsamajn metodojn por movi al la celo.
Ĉiu konduto havas iomete malsaman celon. Serĉi kaj Alveno estas manieroj movi agenton al celloko. Obstaklo-Evitado kaj Apartigo ĝustigas la movadon de la agento por eviti obstaklojn survoje al la celo. Paraleligo kaj Kohezio pluigas agentojn moviĝi kune. Ĉiu nombro da malsamaj stirkondutoj povas esti sumigita por produkti ununuran padvektoron enkalkulantan ĉiujn faktorojn. Agento kiu uzas la kondutojn de Alveno, Apartigo kaj Evitado de Obstaklo por resti for de muroj kaj aliaj agentoj. Ĉi tiu aliro funkcias bone en malfermaj lokoj sen nenecesaj detaloj.
En pli malfacilaj kondiĉoj, la aldono de malsamaj kondutoj funkcias pli malbone - ekzemple, agento povas blokiĝi en muro pro konflikto inter Alveno kaj Obstaklo-Evitado. Tial vi devas konsideri eblojn pli kompleksajn ol simple aldoni ĉiujn valorojn. La maniero estas jena: anstataŭ aldoni la rezultojn de ĉiu konduto, vi povas konsideri movadon en malsamaj direktoj kaj elekti la plej bonan eblon.
Tamen, en kompleksa medio kun sakstratoj kaj elektoj pri kiu vojo iri, ni bezonos ion eĉ pli progresinta.
Trovi vojon
Stirkondutoj estas bonegaj por simpla movado en malferma areo (piedpilko aŭ areno) kie atingi de A al B estas rekta vojo kun nur malgrandaj kromvojoj ĉirkaŭ obstakloj. Por kompleksaj itineroj, ni bezonas vojtrovadon, kio estas maniero esplori la mondon kaj decidi pri itinero tra ĝi.
La plej simpla estas apliki kradon al ĉiu kvadrato apud la agento kaj taksi kiuj el ili rajtas moviĝi. Se unu el ili estas celloko, tiam sekvu la itineron de ĉiu kvadrato al la antaŭa ĝis vi atingos la komencon. Jen la vojo. Alie, ripetu la procezon kun proksimaj aliaj kvadratoj ĝis vi trovos vian celon aŭ vi elĉerpas kvadratojn (tio signifas, ke ne estas ebla itinero). Jen kio estas formale konata kiel Breadth-First Search aŭ BFS (larĝo-unua serĉo-algoritmo). Je ĉiu paŝo li rigardas ĉiujn direktojn (do larĝo, "larĝo"). La serĉspaco estas kiel ondofronto, kiu moviĝas ĝis ĝi atingas la deziratan lokon - la serĉspaco disetendiĝas ĉe ĉiu paŝo ĝis la finpunkto estas inkluzivita, post kio ĝi povas esti spurita reen al la komenco.
Kiel rezulto, vi ricevos liston de kvadratoj laŭ kiuj la dezirata itinero estas kompilita. Ĉi tio estas la vojo (do, vojtrovado) - listo de lokoj, kiujn la agento vizitos sekvante la cellokon.
Konsiderante ke ni konas la pozicion de ĉiu kvadrato en la mondo, ni povas uzi stirkondutojn por movi laŭ la vojo - de nodo 1 al nodo 2, tiam de nodo 2 al nodo 3, ktp. La plej simpla opcio estas iri al la centro de la sekva kvadrato, sed eĉ pli bona elekto estas halti meze de la rando inter la nuna kvadrato kaj la sekva. Pro tio, la agento povos tranĉi angulojn ĉe akraj turnoj.
La BFS-algoritmo ankaŭ havas malavantaĝojn - ĝi esploras tiom da kvadratoj en la "malĝusta" direkto kiel en la "ĝusta" direkto. Jen kie pli kompleksa algoritmo nomita A* (A-stelo) venas en ludon. Ĝi funkcias same, sed anstataŭ blinde ekzameni najbarajn kvadratojn (tiam najbaroj de najbaroj, poste najbaroj de najbaroj de najbaroj, ktp), ĝi kolektas la nodojn en liston kaj ordigas ilin tiel ke la sekva nodo ekzamenita ĉiam estas la unu kiu kondukas al la plej mallonga vojo. Nodoj estas ordigitaj surbaze de heŭristiko kiu enkalkulas du aferojn - la "kosto" de hipoteza itinero al la dezirata kvadrato (inkluzive de iuj vojaĝkostoj) kaj takso de kiom malproksima tiu kvadrato estas de la celloko (biasante la serĉon en la kvadrato). ĝusta direkto).
Ĉi tiu ekzemplo montras, ke la agento esploras unu kvadraton samtempe, ĉiufoje elektante la apudan, kiu estas la plej promesplena. La rezulta vojo estas la sama kiel BFS, sed malpli da kvadratoj estis pripensitaj en la procezo - kio havas grandan efikon al ludrendimento.
Movado sen krado
Sed la plej multaj ludoj ne estas aranĝitaj sur krado, kaj ofte estas neeble fari tion sen ofero de realismo. Kompromisoj necesas. Kian grandecon devas esti la kvadratoj? Tro grandaj kaj ili ne povos ĝuste reprezenti malgrandajn koridorojn aŭ turnojn, tro malgrandajn kaj estos tro da kvadratoj por serĉi, kio finfine daŭros multe da tempo.
La unua afero por kompreni estas ke maŝo donas al ni grafeon de ligitaj nodoj. La algoritmoj A* kaj BFS efektive funkcias pri grafikaĵoj kaj tute ne zorgas pri nia maŝo. Ni povus meti nodojn ie ajn en la ludmondo: kondiĉe ke ekzistas konekto inter iuj du ligitaj nodoj, same kiel inter la komencaj kaj finpunktoj kaj almenaŭ unu el la nodoj, la algoritmo funkcios same bone kiel antaŭe. Tio ofte estas nomita vojpunktosistemo, ĉar ĉiu nodo reprezentas signifan pozicion en la mondo kiu povas esti parto de iu nombro da hipotezaj padoj.
Ekzemplo 1: nodo en ĉiu kvadrato. La serĉo komenciĝas de la nodo kie la agento situas kaj finiĝas ĉe la nodo de la dezirata kvadrato.
Ekzemplo 2: Pli malgranda aro de nodoj (vojpunktoj). La serĉo komenciĝas ĉe la kvadrato de la agento, trairas la postulatan nombron da nodoj, kaj poste daŭras al la celloko.
Ĉi tio estas tute fleksebla kaj potenca sistemo. Sed necesas iom da zorgo por decidi kie kaj kiel meti vojpunkton, alie agentoj eble simple ne vidos la plej proksiman punkton kaj ne povos komenci la vojon. Estus pli facile se ni aŭtomate povus meti vojpunktojn bazitajn sur la geometrio de la mondo.
Ĉi tie aperas la navigada maŝo aŭ navmesh (naviga maŝo). Ĉi tio estas kutime 2D maŝo de trianguloj, kiu estas supermetita sur la geometrio de la mondo - kien ajn la agento rajtas marŝi. Ĉiu el la trianguloj en la maŝo iĝas nodo en la grafeo, kaj havas ĝis tri apudajn triangulojn kiuj iĝas apudaj nodoj en la grafeo.
Ĉi tiu bildo estas ekzemplo de la Unity-motoro - ĝi analizis la geometrion en la mondo kaj kreis navmesh (en la ekrankopio en helblua). Ĉiu plurangulo en navmesh estas areo kie agento povas stari aŭ moviĝi de unu plurangulo al alia plurangulo. En ĉi tiu ekzemplo, la pluranguloj estas pli malgrandaj ol la etaĝoj sur kiuj ili situas - tio estas farita por konsideri la grandecon de la agento, kiu etendiĝos preter ĝia nominala pozicio.
Ni povas serĉi itineron tra ĉi tiu maŝo, denove uzante la A*-algoritmon. Ĉi tio donos al ni preskaŭ perfektan itineron en la mondo, kiu konsideras la tutan geometrion kaj ne postulas nenecesajn nodojn kaj kreadon de vojpunktoj.
Vojetro estas tro vasta temo por kiu unu sekcio de artikolo ne sufiĉas. Se vi volas studi ĝin pli detale, tiam ĉi tio helpos .
Planado
Ni lernis per vojtrovado, ke foje ne sufiĉas simple elekti direkton kaj movi - ni devas elekti itineron kaj fari kelkajn turnojn por atingi nian deziratan celon. Ni povas ĝeneraligi ĉi tiun ideon: atingi celon ne estas nur la sekva paŝo, sed tuta sinsekvo, kie foje necesas rigardi antaŭen plurajn paŝojn por ekscii, kio devus esti la unua. Ĉi tio nomiĝas planado. Pathfinding povas esti opiniita kiel unu el pluraj etendaĵoj al planado. Laŭ nia ciklo Senco/Pensi/Ag, ĉi tie la Pensi parto planas plurajn Aktajn partojn por la estonteco.
Ni rigardu la ekzemplon de la tabulludo Magic: The Gathering. Ni unue iras kun la sekva aro de kartoj en niaj manoj:
- Marĉo - Donas 1 nigran manaon (terkarto).
- Arbaro - donas 1 verdan manaon (terkarto).
- Fugitive Wizard - Postulas 1 bluan manaon por alvoki.
- Elfish Mystic - Postulas 1 verdan manaon por alvoki.
Ni ignoras la ceterajn tri kartojn por faciligi ĝin. Laŭ la reguloj, ludanto rajtas ludi 1 terkarton per turno, li povas "frapi" ĉi tiun karton por eltiri manaon de ĝi, kaj tiam ĵeti sorĉojn (inkluzive de alvoki estaĵon) laŭ la kvanto de manao. En ĉi tiu situacio, la homa ludanto scias ludi Arbaron, frapeti 1 verdan manaon, kaj poste alvoki Elvish Mystic. Sed kiel la ludo AI povas eltrovi ĉi tion?
Facila planado
La bagatela aliro estas provi ĉiun agon laŭvice ĝis ne restas taŭgaj. Rigardante la kartojn, la AI vidas kion Marĉo povas ludi. Kaj li ludas ĝin. Ĉu restas iuj aliaj agoj ĉi-tiun? Ĝi ne povas alvoki aŭ Elvish Mystic aŭ Fugitive Wizard, ĉar ili postulas verdan kaj bluan manaon respektive por alvoki ilin, dum Swamp nur disponigas nigran manaon. Kaj li ne plu povos ludi Arbaron, ĉar li jam ludis Marĉon. Tiel, la ludo AI sekvis la regulojn, sed faris ĝin malbone. Povas esti plibonigita.
Planado povas trovi liston de agoj, kiuj alportas la ludon al la dezirata stato. Same kiel ĉiu kvadrato sur pado havis najbarojn (en vojtrovado), ĉiu ago en plano ankaŭ havas najbarojn aŭ posteulojn. Ni povas serĉi ĉi tiujn agojn kaj postajn agojn ĝis ni atingos la deziratan staton.
En nia ekzemplo, la dezirata rezulto estas "alvoki estaĵon se eble." Komence de la vico, ni vidas nur du eblajn agojn permesitajn de la reguloj de la ludo:
1. Ludu Marĉon (rezulto: Marĉon en la ludo)
2. Ludu Arbaro (rezulto: Arbaro en la ludo)
Ĉiu ago farita povas konduki al pliaj agoj kaj fermi aliajn, denove depende de la reguloj de la ludo. Imagu, ke ni ludis Marĉon - ĉi tio forigos Marĉon kiel sekvan paŝon (ni jam ludis ĝin), kaj ĉi tio ankaŭ forigos Arbaron (ĉar laŭ la reguloj vi povas ludi unu terkarton por turno). Post ĉi tio, la AI aldonas ricevi 1 nigran manaon kiel la sekvan paŝon ĉar ne ekzistas aliaj ebloj. Se li iras antaŭen kaj elektas Frapu la Marĉon, li ricevos 1 unuon da nigra manao kaj ne povos fari ion ajn per ĝi.
1. Ludu Marĉon (rezulto: Marĉon en la ludo)
1.1 "Frapeta" Marĉo (rezulto: Marĉo "frapita", +1 unuo da nigra manao)
Neniuj agoj disponeblaj - END
2. Ludu Arbaro (rezulto: Arbaro en la ludo)
La listo de agoj estis mallonga, ni atingis sakstraton. Ni ripetas la procezon por la sekva paŝo. Ni ludas Arbaron, malfermas la agon "akiru 1 verdan manaon", kiu siavice malfermos la trian agon - alvoku Elvish Mystic.
1. Ludu Marĉon (rezulto: Marĉon en la ludo)
1.1 "Frapeta" Marĉo (rezulto: Marĉo "frapita", +1 unuo da nigra manao)
Neniuj agoj disponeblaj - END
2. Ludu Arbaro (rezulto: Arbaro en la ludo)
2.1 "Tap" Arbaro (rezulto: Arbaro estas "frapeta", +1 unuo da verda manao)
2.1.1 Alvoku Elvish Mystic (rezulto: Elvish Mystic en ludo, -1 verda manao)
Neniuj agoj disponeblaj - END
Fine, ni esploris ĉiujn eblajn agojn kaj trovis planon, kiu alvokas estaĵon.
Ĉi tio estas tre simpligita ekzemplo. Estas konsilinde elekti la plej bonan eblan planon, anstataŭ nur ajnan planon, kiu plenumas iujn kriteriojn. Ĝenerale eblas taksi eblajn planojn bazitajn sur la rezulto aŭ ĝenerala profito de ilia efektivigo. Vi povas gajni vin 1 poenton pro ludado de terkarto kaj 3 poentojn pro alvokado de estaĵo. Ludi Marĉon estus 1-punkta plano. Kaj ludante Arbaro → Frapu la Arbaron → alvoki Elvan Mistikon tuj donos 4 poentojn.
Tiel funkcias planado en Magic: The Gathering, sed la sama logiko validas en aliaj situacioj. Ekzemple, movante peonon por fari lokon por la episkopo moviĝi en ŝako. Aŭ kovriĝu malantaŭ muro por sekure pafi en XCOM tiel. Ĝenerale, vi ricevas la ideon.
Plibonigita planado
Kelkfoje estas tro da eblaj agoj por konsideri ĉiun eblan elekton. Revenante al la ekzemplo kun Magic: The Gathering: ni diru, ke en la ludo kaj en via mano estas pluraj terkartoj kaj estaĵoj - la nombro da eblaj kombinaĵoj de movoj povas esti en dekoj. Estas pluraj solvoj al la problemo.
La unua metodo estas malantaŭen ĉenado. Anstataŭ provi ĉiujn kombinaĵojn, estas pli bone komenci kun la fina rezulto kaj provi trovi rektan vojon. Anstataŭ iri de la radiko de la arbo al specifa folio, ni moviĝas en la kontraŭa direkto - de la folio al la radiko. Ĉi tiu metodo estas pli facila kaj rapida.
Se la malamiko havas 1 sanon, vi povas trovi la planon "fari 1 aŭ pli da damaĝo". Por atingi tion, kelkaj kondiĉoj devas esti plenumitaj:
1. Damaĝo povas esti kaŭzita de sorĉo - ĝi devas esti en la mano.
2. Por sorĉi, vi bezonas manaon.
3. Por akiri manaon, vi devas ludi terkarton.
4. Por ludi terkarton, vi devas havi ĝin en via mano.
Alia maniero estas plej bona unua serĉo. Anstataŭ provi ĉiujn vojojn, ni elektas la plej taŭgan. Plej ofte, ĉi tiu metodo donas la optimuman planon sen nenecesaj serĉkostoj. A* estas formo de plej bona unua serĉo - ekzamenante la plej esperigajn itinerojn de la komenco, ĝi jam povas trovi la plej bonan vojon sen devi kontroli aliajn eblojn.
Interesa kaj ĉiam pli populara plej bona unua serĉopcio estas Monte Carlo Tree Search. Anstataŭ diveni kiuj planoj estas pli bonaj ol aliaj dum elektado de ĉiu posta ago, la algoritmo elektas hazardajn posteulojn ĉe ĉiu paŝo ĝis ĝi atingas la finon (kiam la plano rezultigis venkon aŭ malvenkon). La fina rezulto tiam estas uzata por pliigi aŭ malpliigi la pezon de antaŭaj elektoj. Ripetante ĉi tiun procezon plurajn fojojn en vico, la algoritmo donas bonan takson de kio la plej bona sekva movo estas, eĉ se la situacio ŝanĝiĝas (se la malamiko ekagas por malhelpi la ludanton).
Neniu rakonto pri planado en ludoj estus kompleta sen Cel-Orientita Agado-Planado aŭ GOAP (cel-orientita agadplanado). Ĉi tio estas vaste uzata kaj diskutita metodo, sed krom kelkaj distingigaj detaloj, ĝi estas esence la retroĉeniga metodo, pri kiu ni antaŭe parolis. Se la celo estis "detrui la ludanton" kaj la ludanto estas malantaŭ kovro, la plano povus esti: detrui per obuso → ricevi ĝin → ĵeti ĝin.
Estas kutime pluraj celoj, ĉiu kun sia propra prioritato. Se la plej alta prioritata celo ne povas esti plenumita (neniu kombinaĵo de agoj kreas planon "mortigi la ludanton" ĉar la ludanto ne estas videbla), la AI refalos al pli malaltaj prioritataj celoj.
Trejnado kaj adapto
Ni jam diris, ke ludo AI kutime ne uzas maŝinlernadon ĉar ĝi ne taŭgas por administri agentojn en reala tempo. Sed ĉi tio ne signifas, ke vi ne povas prunti ion el ĉi tiu areo. Ni volas kontraŭulon en pafisto, de kiu ni povas lerni ion. Ekzemple, eksciu pri la plej bonaj pozicioj sur la mapo. Aŭ kontraŭulo en batala ludo, kiu blokus la ofte uzatajn kombomovojn de la ludanto, instigante lin uzi aliajn. Do maŝinlernado povas esti sufiĉe utila en tiaj situacioj.
Statistiko kaj Probablecoj
Antaŭ ol ni eniros kompleksajn ekzemplojn, ni vidu kiom malproksimen ni povas iri prenante kelkajn simplajn mezurojn kaj uzante ilin por fari decidojn. Ekzemple, realtempa strategio - kiel ni determini ĉu ludanto povas lanĉi atakon en la unuaj minutoj de la ludo kaj kian defendon prepari kontraŭ tio? Ni povas studi la pasintajn spertojn de ludanto por kompreni kiajn estontajn reagojn povus esti. Komence, ni ne havas tiajn krudajn datumojn, sed ni povas kolekti ĝin - ĉiufoje kiam la AI ludas kontraŭ homo, ĝi povas registri la tempon de la unua atako. Post kelkaj sesioj, ni ricevos mezumon de la tempo, kiun la ludanto bezonos por ataki estonte.
Ankaŭ estas problemo kun averaĝaj valoroj: se ludanto rapidis 20 fojojn kaj ludis malrapide 20 fojojn, tiam la postulataj valoroj estos ie en la mezo, kaj ĉi tio ne donos al ni ion utilan. Unu solvo estas limigi la enigajn datumojn - la lastaj 20 pecoj povas esti konsiderataj.
Simila aliro estas utiligita dum taksado de la verŝajneco de certaj agoj supozante ke la pasintaj preferoj de la ludanto estos la samaj en la estonteco. Se ludanto atakas nin kvinfoje per fajroglobo, dufoje per fulmo, kaj unufoje per manbatalo, estas evidente, ke li preferas fajroglobon. Ni eksterpolu kaj vidu la probablecon uzi malsamajn armilojn: fajroglobo=62,5%, fulmo=25% kaj manbatalo=12,5%. Nia ludo AI bezonas prepariĝi por protekti sin kontraŭ fajro.
Alia interesa metodo estas uzi la Naive Bayes Classifier por studi grandajn kvantojn da enigaĵoj kaj klasifiki la situacion por ke la AI reagu laŭ la dezirata maniero. Bajezaj klasigiloj estas plej konataj pro sia uzo en retpoŝtaj spamfiltriloj. Tie ili ekzamenas la vortojn, komparas ilin al kie tiuj vortoj antaŭe aperis (en spamo aŭ ne), kaj eltiras konkludojn pri alvenantaj retpoŝtoj. Ni povas fari la samon eĉ kun malpli da enigaĵoj. Surbaze de ĉiuj utilaj informoj, kiujn la AI vidas (kiel kiaj malamikaj unuoj estas kreitaj, aŭ kiaj sorĉoj ili uzas, aŭ kiajn teknologiojn ili esploris), kaj la fina rezulto (milito aŭ paco, rapido aŭ defendo, ktp.) - ni elektos la deziratan AI-konduton.
Ĉiuj ĉi tiuj trejnaj metodoj sufiĉas, sed estas konsilinde uzi ilin surbaze de testaj datumoj. La AI lernos adaptiĝi al la malsamaj strategioj, kiujn viaj ludtestantoj uzis. AI kiu adaptiĝas al la ludanto post liberigo povas iĝi tro antaŭvidebla aŭ tro malfacila por venki.
Valorbazita adapto
Konsiderante la enhavon de nia ludmondo kaj la regulojn, ni povas ŝanĝi la aron de valoroj, kiuj influas decidadon, anstataŭ simple uzi la enigajn datumojn. Ni faras ĉi tion:
- Lasu la AI kolekti datumojn pri la stato de la mondo kaj ŝlosilaj eventoj dum la ludo (kiel supre).
- Ni ŝanĝu kelkajn gravajn valorojn bazitajn sur ĉi tiuj datumoj.
- Ni efektivigas niajn decidojn bazitajn sur prilaborado aŭ taksado de ĉi tiuj valoroj.
Ekzemple, agento havas plurajn ĉambrojn por elekti sur unuapersona pafisto mapo. Ĉiu ĉambro havas sian propran valoron, kiu determinas kiom dezirinda estas viziti. La AI hazarde elektas al kiu ĉambro iri surbaze de la valoro. La agento tiam memoras en kiu ĉambro li estis mortigita kaj reduktas ĝian valoron (la probableco ke li revenos tien). Simile por la inversa situacio - se la agento detruas multajn kontraŭulojn, tiam la valoro de la ĉambro pliiĝas.
Markov-modelo
Kio se ni uzus la kolektitajn datumojn por fari antaŭdirojn? Se ni memoras ĉiun ĉambron en kiu ni vidas la ludanton dum certa tempodaŭro, ni antaŭdiros al kiu ĉambro la ludanto povus iri. Spurante kaj registrante la movojn de la ludanto tra ĉambroj (valoroj), ni povas antaŭdiri ilin.
Ni prenu tri ĉambrojn: ruĝan, verdan kaj bluan. Kaj ankaŭ la observoj, kiujn ni registris spektante la ludsesion:
La nombro da observoj en ĉiu ĉambro estas preskaŭ egala - ni ankoraŭ ne scias kie fari bonan lokon por embusko. Kolekti statistikojn ankaŭ malfaciliĝas pro la renaskiĝo de ludantoj, kiuj aperas egale tra la mapo. Sed la datumoj pri la sekva ĉambro, kiun ili eniras post aperado sur la mapo, jam estas utilaj.
Videblas, ke la verda ĉambro konvenas al la ludantoj - la plej multaj homoj moviĝas de la ruĝa ĉambro al ĝi, 50% el kiuj restas tie plu. La blua ĉambro, male, ne estas populara; preskaŭ neniu iras al ĝi, kaj se ili faras, ili ne restas longe.
Sed la datumoj diras al ni ion pli gravan - kiam ludanto estas en blua ĉambro, la sekva ĉambro, en kiu ni vidos lin, estos ruĝa, ne verda. Eĉ se la verda ĉambro estas pli populara ol la ruĝa ĉambro, la situacio ŝanĝiĝas se la ludanto estas en la blua ĉambro. La sekva stato (t.e. la ĉambro al kiu la ludanto iros) dependas de la antaŭa stato (t.e. la ĉambro en kiu la ludanto estas nuntempe). Ĉar ni esploras dependecojn, ni faros pli precizajn antaŭdirojn ol se ni simple nombris observaĵojn sendepende.
Antaŭdiri estontan staton bazitan sur datenoj de pasinta ŝtato estas nomita Markov-modelo, kaj tiaj ekzemploj (kun ĉambroj) estas nomitaj Markov-ĉenoj. Ĉar la padronoj reprezentas la probablecon de ŝanĝoj inter sinsekvaj ŝtatoj, ili estas vide montritaj kiel FSMoj kun verŝajneco ĉirkaŭ ĉiu transiro. Antaŭe, ni uzis FSM por reprezenti la kondutisman staton en kiu agento estis, sed ĉi tiu koncepto etendiĝas al iu ajn ŝtato, ĉu ĝi estas asociita kun la agento aŭ ne. En ĉi tiu kazo, la ŝtatoj reprezentas la ĉambron, kiun la agento okupas:
Ĉi tio estas simpla maniero reprezenti la relativan verŝajnecon de ŝtatŝanĝoj, donante al la AI iun kapablon antaŭdiri la sekvan staton. Vi povas antaŭvidi plurajn paŝojn antaŭen.
Se ludanto estas en la verda ĉambro, ekzistas 50% ŝanco ke li restos tie la venontan fojon kiam li estas observita. Sed kiaj estas la ŝancoj, ke li ankoraŭ estos tie eĉ poste? Ne nur ekzistas ŝanco ke la ludanto restis en la verda ĉambro post du observoj, sed ankaŭ ekzistas ŝanco ke li foriris kaj revenis. Jen la nova tabelo konsiderante la novajn datumojn:
Ĝi montras, ke la ŝanco vidi la ludanton en la verda ĉambro post du observoj estos egala al 51% - 21%, ke li estos el la ruĝa ĉambro, 5% el ili, ke la ludanto vizitos la bluan ĉambron inter ili, kaj 25% ke la ludanto ne forlasos la verdan ĉambron.
La tablo estas simple vida ilo - la proceduro postulas nur multobligi la probablojn ĉe ĉiu paŝo. Ĉi tio signifas, ke vi povas rigardi malproksimen en la estontecon kun unu averto: ni supozas, ke la ŝanco eniri ĉambron dependas tute de la nuna ĉambro. Ĉi tio nomiĝas Markov-Edaĵo - la estonta stato dependas nur de la nuntempo. Sed ĉi tio ne estas cent-procente preciza. Ludantoj povas ŝanĝi decidojn depende de aliaj faktoroj: sannivelo aŭ kvanto de municio. Ĉar ni ne registras ĉi tiujn valorojn, niaj prognozoj estos malpli precizaj.
N-Gramoj
Kio pri la ekzemplo de batala ludo kaj antaŭdiro de la kombomovoj de la ludanto? La sama! Sed anstataŭ unu stato aŭ evento, ni ekzamenos la tutajn sekvencojn, kiuj konsistigas kombinan strikon.
Unu maniero fari tion estas stoki ĉiun enigaĵon (kiel Kick, Punch aŭ Block) en bufro kaj skribi la tutan bufron kiel eventon. Do la ludanto plurfoje premas Kick, Kick, Punch por uzi la SuperDeathFist-atakon, la AI-sistemo stokas ĉiujn enigaĵojn en bufro kaj memoras la lastajn tri uzatajn en ĉiu paŝo.
(La linioj en grasa skribo estas kiam la ludanto lanĉas la SuperDeathFist-atakon.)
La AI vidos ĉiujn eblojn kiam la ludanto elektos Piedbato, sekvita de alia Piedbato, kaj poste rimarkos, ke la sekva enigo ĉiam estas Punch. Ĉi tio permesos al la agento antaŭdiri la kombinmovon de SuperDeathFist kaj bloki ĝin se eble.
Tiuj sekvencoj de eventoj estas nomitaj N-gramoj, kie N estas la nombro da elementoj stokitaj. En la antaŭa ekzemplo ĝi estis 3-gramo (trigramo), kio signifas: la unuaj du enskriboj estas uzataj por antaŭdiri la trian. Sekve, en 5-gramo, la unuaj kvar enskriboj antaŭdiras la kvinan kaj tiel plu.
La dezajnisto devas zorge elekti la grandecon de N-gramoj. Pli malgranda N postulas malpli da memoro sed ankaŭ konservas malpli da historio. Ekzemple, 2-gramo (bigramo) registros Kick, Kick aŭ Kick, Punch, sed ne povos stoki Kick, Kick, Punch, do la AI ne respondos al la kombo SuperDeathFist.
Aliflanke, pli grandaj nombroj postulas pli da memoro kaj la AI estos pli malfacile trejni, ĉar estos multaj pli da eblaj opcioj. Se vi havus tri eblajn enigojn de Kick, Punch aŭ Block, kaj ni uzis 10-gramon, tio estus ĉirkaŭ 60 mil malsamaj ebloj.
La bigrama modelo estas simpla Markov-ĉeno - ĉiu pasinta stato/nuna stato paro estas bigramo, kaj vi povas antaŭdiri la duan staton surbaze de la unua. La 3-gramaj kaj pli grandaj N-gramoj ankaŭ povas esti opiniitaj kiel Markov-ĉenoj, kie ĉiuj elementoj (krom la lasta en la N-gramo) kune formas la unuan staton kaj la lasta elemento la duan. La batalludekzemplo montras la ŝancon transiri de la stato de Piedbato kaj Piedbato al la stato de Piedbato kaj Punĉo. Traktante multoblajn enighistoriajn enskribojn kiel ununuran unuon, ni esence transformas la enigsekvencon en parton de la tuta ŝtato. Ĉi tio donas al ni la Markov-posedaĵon, kiu ebligas al ni uzi Markov-ĉenojn por antaŭdiri la sekvan enigaĵon kaj diveni, kia kombina movo estos venonta.
konkludo
Ni parolis pri la plej oftaj iloj kaj aliroj en la disvolviĝo de artefarita inteligenteco. Ni ankaŭ rigardis la situaciojn en kiuj ili devas esti uzataj kaj kie ili estas speciale utilaj.
Ĉi tio devus sufiĉi por kompreni la bazojn de ludo AI. Sed, kompreneble, ĉi tiuj ne estas ĉiuj metodoj. Malpli popularaj, sed ne malpli efikaj inkluzivas:
- Optimumigo-algoritmoj inkluzive de montetogrimpado, gradienta deveno kaj genetikaj algoritmoj
- kontraŭaj serĉo/planado-algoritmoj (minimax kaj alfa-beta-tondado)
- klasifikmetodoj (perceptronoj, neŭralaj retoj kaj subtenaj vektoraj maŝinoj)
- sistemoj por prilaborado de la percepto kaj memoro de agentoj
- arkitekturaj aliroj al AI (hibridaj sistemoj, subaro arkitekturoj kaj aliaj manieroj supermeti AI-sistemojn)
- animaciaj iloj (planado kaj moviĝkunordigo)
- rendimentfaktoroj (nivelo de detalo, iam ajn, kaj tempotranĉaj algoritmoj)
Retaj rimedoj pri la temo:
1. GameDev.net havas Kaj .
2. enhavas multajn prezentojn kaj artikolojn pri larĝa gamo de temoj ligitaj al ludo AI-evoluo.
3. inkluzivas temojn de la GDC AI-Pintkunveno, multaj el kiuj estas disponeblaj senpage.
4. Utilaj materialoj troviĝas ankaŭ en la retejo .
5. Tommy Thompson, AI-esploristo kaj ludprogramisto, faras filmetojn en Jutubo kun klarigo kaj studo de AI en komercaj ludoj.
Libroj pri la temo:
1. La serio de libroj Game AI Pro estas kolektoj de mallongaj artikoloj, kiuj klarigas kiel efektivigi specifajn funkciojn aŭ kiel solvi specifajn problemojn.
2. AI Game Programming Wisdom-serio estas la antaŭulo de la serio Game AI Pro. Ĝi enhavas pli malnovajn metodojn, sed preskaŭ ĉiuj estas gravaj eĉ hodiaŭ.
3. estas unu el la bazaj tekstoj por ĉiuj, kiuj volas kompreni la ĝeneralan kampon de artefarita inteligenteco. Ĉi tio ne estas libro pri luddisvolviĝo - ĝi instruas la bazojn de AI.
fonto: www.habr.com