Натыкнуўся на цікавы матэрыял аб штучным інтэлекце ў гульнях. З тлумачэннем базавых рэчаў пра ІІ на простых прыкладах, а яшчэ ўсярэдзіне шмат карысных прылад і метадаў для яго зручнай распрацоўкі і праектаванні. Як, дзе і калі іх выкарыстоўваць - таксама ёсць.
Большасць прыкладаў напісаны ў псеўдакодзе, таму глыбокія веды праграмавання не запатрабуюцца. Пад катом 35 лістоў тэксту з карцінкамі і гіфкамі, так што прыгатуйцеся.
UPD. Прашу прабачэння, але ўласны пераклад гэтага артыкула на Хабры ўжо рабіў . Прачытаць яго варыянт можна , але чамусьці артыкул прайшоў міма мяне (пошукам карыстаўся, але нешта пайшло не так). А бо пішу ў блог, прысвечаны геймдэву, вырашыў пакінуць свой варыянт перакладу для падпісчыкаў (некаторыя моманты ў мяне аформлены па-іншаму, некаторыя — наўмысна прапушчаныя па парадзе распрацоўнікаў).
Што такое ІІ?
Гульнявы ІІ засяроджаны на тым, якія дзеянні павінен выконваць аб'ект, зыходзячы з умоў, у якіх знаходзіцца. Звычайна гэта называюць кіраваннем "інтэлектуальнымі агентамі", дзе агент з'яўляецца гульнявым персанажам, транспартным сродкам, ботам, а часам і нечым больш абстрактным: цэлай групай сутнасцяў або нават цывілізацыяй. У кожным выпадку гэта рэч, якая павінна бачыць сваё асяроддзе, прымаць на яго аснове рашэнні і дзейнічаць у адпаведнасці з імі. Гэта называецца цыклам Sense/Think/Act (Адчуваць/Думаць/Дзейнічаць):
- Sense: агент знаходзіць ці атрымлівае інфармацыю аб рэчах у сваім асяроддзі, якія могуць паўплываць на яго паводзіны (пагрозы паблізу, прадметы для збору, цікавыя месцы для даследавання).
- Think: агент вырашае, як рэагаваць (разглядае, ці дастаткова бяспечна збіраць прадметы ці спачатку ён павінен змагацца/хавацца).
- Act: агент выконвае дзеянні для рэалізацыі папярэдняга рашэння (пачынае рух да суперніка ці прадмету).
- …зараз сітуацыя змянілася з-за дзеянняў персанажаў, таму цыкл паўтараецца з новымі дадзенымі.
ІІ, як правіла, канцэнтруецца на Sense-часткі цыклу. Напрыклад, аўтаномныя аўтамабілі робяць здымкі дарогі, аб'ядноўваюць іх з дадзенымі радара і лідара, і інтэрпрэтуюць. Звычайна гэта робіць машыннае навучанне, якое апрацоўвае ўваходныя дадзеныя і надае ім сэнс, здабываючы семантычную інфармацыю па тыпе ёсць яшчэ адзін аўтамабіль у 20 ярдаў наперадзе вас . Гэта так званыя classification problems.
Гульням не патрэбна складаная сістэма для вымання інфармацыі, бо вялікая частка дадзеных ужо з'яўляецца яе неад'емнай часткай. Няма неабходнасці запускаць алгарытмы распазнання малюнкаў, каб вызначыць, ці ёсць вораг наперадзе - гульня ўжо ведае і перадае звесткі прама ў працэсе прыняцця рашэнняў. Таму частка цыклу Sense часта нашмат прасцей, чым Think і Act.
Абмежаванні гульнявога ІІ
У ІІ ёсць шэраг абмежаванняў, якія неабходна выконваць:
- ІІ не трэба загадзя трэніраваць, быццам гэта алгарытм машыннага навучання. Бессэнсоўна пісаць нейрасетку падчас распрацоўкі, каб назіраць за дзясяткамі тысяч гульцоў і вывучаць лепшы спосаб гульні супраць іх. Чаму? Бо гульня не выпушчана, а гульцоў няма.
- Гульня павінна забаўляць і кідаць выклік, таму агенты не павінны знаходзіць найлепшы падыход супраць людзей.
- Агентам трэба выглядаць рэалістычнымі, каб гульцы адчувалі быццам гуляюць супраць сапраўдных людзей. Праграма AlphaGo перасягнула чалавека, але абраныя крокі былі моцна далёкія ад традыцыйнага разумення гульні. Калі гульня імітуе суперніка-чалавека, такога пачуцця не павінна быць. Алгарытм трэба змяніць, каб ён прымаў праўдападобныя рашэнні, а не ідэальныя.
- ІІ павінен працаваць у рэальным часе. Гэта значыць, што алгарытм не можа манапалізаваць выкарыстанне працэсара на працягу працяглага часу для прыняцця рашэнняў. Нават 10 мілісекунд на гэта – занадта доўга, таму што большасці гульняў дастаткова ад 16 да 33 мілісекунд, каб выканаць усю апрацоўку і перайсці да наступнага кадра графікі.
- Ідэальна, калі хаця б частка сістэмы кіруецца дадзенымі, каб «некодэры» маглі ўносіць змены, і каб карэкціроўкі адбываліся хутчэй.
Разгледзім падыходы ІІ, якія ахопліваюць увесь цыкл Sense/Think/Act.
Прыняцце базавых рашэнняў
Пачнем з найпростай гульні - Pong. Мэта: перамясціць платформу (paddle) так, каб мяч адскокваў ад яе, а не пралятаў міма. Гэта як тэніс, у якім вы прайграваеце, калі не адбіваеце мяч. Тут у ІІ адносна лёгкая задача - вырашыць, у якім кірунку перамяшчаць платформу.
Умоўныя аператары
Для ІІ у Pong ёсць самае відавочнае рашэнне - заўсёды імкнуцца размясціць платформу пад мячом.
Просты алгарытм для гэтага, напісаны ў псеўдакодзе:
every frame/update while the game is running:
калі ball is to left of the paddle:
move paddle left
Існуе, калі ball is to right of the paddle:
move paddle right
Калі платформа рухаецца з хуткасцю мяча, то гэта ідэальны алгарытм для ІІ ў Pong. Не трэба нічога ўскладняць, калі дадзеных і магчымых дзеянняў для агента не так ужо і шмат.
Гэты падыход настолькі просты, што ўвесь цыкл Sense/Think/Act ледзь замецены. Але ён ёсць:
- Частка Sense знаходзіцца ў двух аператарах if. Гульня ведае дзе мяч і дзе платформа, таму ІІ звяртаецца да яе за гэтай інфармацыяй.
- Частка Think таксама ўваходзіць у два аператары if. Яны ўвасабляюць у сабе два рашэнні, якія ў дадзеным выпадку з'яўляюцца ўзаемавыключальнымі. У выніку выбіраецца адно з трох дзеянняў - перамясціць платформу налева, перамясціць направа, ці нічога не рабіць, калі яна ўжо правільна размешчана.
- Частка Act знаходзіцца ў аператарах Move Paddle Left і Move Paddle Right. У залежнасці ад дызайну гульні, яны могуць перамяшчаць платформу імгненна ці з вызначанай хуткасцю.
Такія падыходы называюць рэагуюць - ёсць просты набор правілаў (у дадзеным выпадку аператары if у кодзе), якія рэагуюць на бягучы стан свету і дзейнічаюць.
Дрэва рашэнняў
Прыклад з гульнёй Pong фактычна роўны фармальнай канцэпцыі ІІ, званай дрэвам рашэнняў. Алгарытм праходзіць яго, каб дасягнуць "ліста" - рашэнні аб тым, якое дзеянне распачаць.
Зробім блок-схему дрэва рашэнняў для алгарытму нашай платформы:
Кожная частка дрэва завецца node (вузел) - ІІ выкарыстоўвае тэорыю графаў для апісання падобных структур. Ёсць два тыпу вузлоў:
- Вузлы прыняцця рашэнняў: выбар паміж двума альтэрнатывамі на аснове праверкі некаторай умовы, дзе кожная альтэрнатыва прадстаўлена ў выглядзе асобнага вузла.
- Канчатковыя вузлы: дзеянне для выканання, якое прадстаўляе канчатковае рашэнне.
Алгарытм пачынаецца з першага вузла («кораня» дрэва). Ён або прымае рашэнне аб тым, да якога даччынага вузла перайсці, або выконвае дзеянне, якое захоўваецца ў вузле, і завяршаецца.
У чым жа перавага, калі дрэва рашэнняў, выконвае тую ж працу, што і if-аператары ў папярэднім раздзеле? Тут ёсць агульная сістэма, дзе кожнае рашэнне мае толькі адну ўмову і два магчымыя вынікі. Гэта дазваляе распрацоўніку ствараць ІІ з дадзеных, якія прадстаўляюць рашэнні ў дрэве, пазбегнуўшы яго хардкодынгу. Прадстаўляльны ў выглядзе табліцы:
На баку кода вы атрымаеце сістэму для чытання радкоў. Стварыце вузел для кожнай з іх, падключыце логіку прыняцця рашэнняў на аснове другога слупка і даччыныя вузлы на аснове трэцяга і чацвёртага слупкоў. Вам усё яшчэ трэба запраграмаваць умовы і дзеянні, але зараз структура гульні будзе складаней. У ёй вы дадаеце дадатковыя рашэнні і дзеянні, а затым наладжваеце ўвесь ІІ, проста адрэдагаваўшы тэкставы файл з вызначэннем дрэва. Далей перадаеце файл геймдызайнеру, які зможа змяніць паводзіны без перакампілявання гульні і змены кода.
Дрэвы рашэнняў вельмі карысныя, калі яны будуюцца аўтаматычна на аснове вялікага набору прыкладаў (напрыклад, з выкарыстаннем алгарытму ID3). Гэта робіць іх эфектыўным і высокапрадукцыйнай прыладай для класіфікацыі сітуацый на аснове атрымоўваных дадзеных. Аднак мы выходзім за рамкі простай сістэмы для выбару дзеянняў агентамі.
сцэнары
Мы разабралі сістэму дрэва рашэнняў, якая выкарыстоўвала загадзя створаныя ўмовы і дзеянні. Чалавек, які праектуе ІІ, можа арганізаваць дрэва так, як хоча, але ён усё яшчэ павінен спадзявацца на кодэра, які гэта ўсё запраграмаваў. Што калі мы маглі б даць дызайнеру інструменты для стварэння ўласных умоў або дзеянняў?
Каб праграмісту не пісаць код для ўмоў Is Ball Left Of Paddle і Is Ball Right Of Paddle, ён можа зрабіць сістэму, у якой дызайнер будзе запісваць умовы для праверкі гэтых значэнняў. Тады дадзеныя дрэва рашэнняў будуць выглядаць так:
Па сутнасці гэта тое ж самае, што і ў першай табліцы, але рашэнні ўнутры сябе маюць свой уласны код, крыху падобны на ўмоўную частку if-аператара. На баку кода гэта счытвалася б у другім слупку для вузлоў прыняцця рашэнняў, але замест пошуку канкрэтнай умовы для выканання (Is Ball Left Of Paddle), яно ацэньвае ўмоўнае выраз і вяртае true ці false адпаведна. Гэта робіцца з дапамогай скрыптовай мовы Lua ці Angelscript. З дапамогай іх распрацоўшчык можа прымаць аб'екты ў сваёй гульні (ball і paddle) і ствараць зменныя, якія будуць даступныя ў сцэнары (ball.position). Акрамя таго, мова сцэнарыяў прасцей, чым C++. Ён не патрабуе поўнай стадыі кампіляцыі, таму ідэальна падыходзіць для хуткай карэкціроўкі гульнявой логікі і дазваляе "некодэрам" самім ствараць патрэбныя функцыі.
У прыведзеным прыкладзе мова сцэнарыяў выкарыстоўваецца толькі для адзнакі ўмоўнага выраза, але яе таксама можна выкарыстоўваць і для дзеянняў. Напрыклад, дадзеныя Move Paddle Right могуць стаць аператарам сцэнара (ball.position.x += 10). Так, каб дзеянне таксама вызначалася ў скрыпце, без неабходнасці праграмавання Move Paddle Right.
Можна пайсці яшчэ далей і поўнасцю напісаць дрэва рашэнняў на мове сцэнарыяў. Гэта будзе код у выглядзе цвёрда запраграмаваных (hardcoded) умоўных аператараў, але яны будуць знаходзіцца ў вонкавых файлах скрыпту, гэта значыць могуць быць зменены без перакампілявання ўсёй праграмы. Часцяком можна змяніць файл сцэнара прама падчас гульні, каб хутка пратэставаць розныя рэакцыі ІІ.
Рэагаванне на падзеі
Прыклады вышэй ідэальна падыходзяць да Pong. Яны бесперапынна запускаюць цыкл Sense/Think/Act і дзейнічаюць на аснове апошняга стану свету. Але ў больш складаных гульнях трэба рэагаваць на асобныя падзеі, а не ацэньваць усё і адразу. Pong у такім разе ўжо няўдалы прыклад. Выберам іншы.
Прадстаўце шутэр, дзе ворагі нерухомыя пакуль не выявяць гульца, пасля чаго дзейнічаюць у залежнасці ад сваёй «спецыялізацыі»: хтосьці пабяжыць «рашыць», хтосьці будзе атакаваць здалёк. Гэта ўсё яшчэ базавая якая рэагуе сістэма - "калі гулец заўважаны, то зрабі што-небудзь", - але яе можна лагічна падзяліць на падзею Player Seen (гулец заўважаны) і рэакцыю (выберыце адказ і выканайце яго).
Гэта вяртае нас да цыклу Sense/Think/Act. Мы можам накадзіць Sense-частку, якая кожны кадр будзе правяраць - ці бачыць ІІ гульца. Калі няма нічога не адбываецца, але калі бачыць, то ствараецца падзея Player Seen. У кода будзе асобная частка, у якім гаворыцца: "калі адбываецца падзея Player Seen, зрабі", дзе - адказ, які вам патрэбен для звароту да частак Think і Act. Такім чынам, вы наладзіце рэакцыі да падзеі Player Seen: на «рашаючага» персанажа - ChargeAndAttack, а на снайпера - HideAndSnipe. Гэтыя сувязі можна стварыць у файле дадзеных для хуткага рэдагавання без неабходнасці нанава кампіляваць. І тут таксама можна выкарыстоўваць мову сцэнарыяў.
Прыняцце складаных рашэнняў
Хоць простыя сістэмы рэакцый вельмі дзейсныя, бывае шмат сітуацый, калі іх нядосыць. Часам трэба прымаць розныя рашэнні, заснаваныя на тым, што агент робіць у сапраўдны момант, але прадстаўляць гэта за ўмову цяжка. Часам існуе занадта шмат умоў, каб эфектыўна ўявіць іх у дрэве рашэнняў або скрыпце. Часам трэба загадзя ацэньваць, як зменіцца сітуацыя, перш чым прымаць рашэнне аб наступным кроку. Для вырашэння гэтых праблем патрэбны больш складаныя падыходы.
Канчатковы аўтамат
Finite state machine або FSM (канчатковы аўтамат) - гэта спосаб сказаць, што наш агент у цяперашні час знаходзіцца ў адным з некалькіх магчымых станаў, і што ён можа пераходзіць з аднаго стану ў іншы. Такіх станаў пэўную колькасць - адсюль і назва. Лепшы прыклад з жыцця - дарожны святлафор. У розных месцах розныя паслядоўнасці агнёў, але прынцып той жа - кожны стан уяўляе нешта (стой, ідзі і г.д.). Святлафор знаходзіцца толькі ў адным стане ў любы момант часу, і пераходзіць ад аднаго да другога на аснове простых правіл.
З NPC у гульнях падобная гісторыя. Для прыкладу возьмем варта з такімі станамі:
- Патрулюючы (Patrolling).
- Атакуючы (Attacking).
- Уцякаючы (Fleeing).
І такімі ўмовамі для змены яго стану:
- Калі вартаўнік бачыць суперніка, ён атакуе.
- Калі вартавы атакуе, але больш не бачыць суперніка, ён вяртаецца да патрулявання.
- Калі вартавы атакуе, але моцна паранены, ён уцякае.
Таксама можна напісаць if-аператары са зменнай-станам варта і розныя праверкі: ці ёсць паблізу вораг, які ўзровень здароўя NPC і т. д. Дадамо яшчэ некалькі станаў:
- Бяздзеянне (Idling) - паміж патрулямі.
- Пошук (Searching) - калі заўважаны вораг схаваўся.
- Прасіць аб дапамозе (Finding Help) - калі вораг заўважаны, але занадта моцны, каб змагацца з ім у адзіночку.
Выбар для кожнага з іх абмежаваны - напрыклад, вартавы не пойдзе шукаць які схаваўся ворага, калі ў яго нізкае здароўе.
У рэшце рэшт велізарны спіс «калі , то », можа стаць занадта грувасткім, таму варта фармалізаваць метад, які дазволіць нам трымаць у розуме стану і пераходы паміж станамі. Каб гэта зрабіць, прымем да ўвагі ўсе станы, і пад кожным станам запішам у спіс усе пераходы ў іншыя станы, разам з неабходнымі для іх умовамі.
Гэта табліца пераходаў станаў - комплексны спосаб прадстаўлення FSM. Намалюем дыяграму і атрымаем поўны агляд таго, як мяняюцца паводзіны NPC.
Дыяграма адлюстроўвае сутнасць прыняцця рашэнняў для гэтага агента на аснове бягучай сітуацыі. Прычым кожная стрэлка паказвае пераход паміж станамі, калі ўмова побач з ёй праўдзіва.
Кожнае абнаўленне мы правяраем бягучы стан агента, праглядаем спіс пераходаў, і калі ўмовы для пераходу выкананы, ён прымае новы стан. Напрыклад, кожны кадр правяраецца ці скончыўся 10-секундны таймер, і калі так, то са стану Idling вартавы пераходзіць у Patrolling. Такім жа чынам, стан Attacking правярае здароўе агента - калі яно нізкае, то ён пераходзіць у стан Fleeing.
Гэта апрацоўка пераходаў паміж станамі, але як наконт паводзін, звязаных з самімі станамі? Што да рэалізацыі фактычных паводзінаў для канкрэтнага стану, звычайна існуе два тыпы «крука», дзе мы прысвойваем дзеянні да FSM:
- Дзеянні, якія мы перыядычна выконваем для бягучага стану.
- Дзеянні, якія мы робім пры пераходзе з аднаго стану ў іншы.
Прыклады для першага тыпу. Стан Patrolling кожны кадр будзе перамяшчаць агента па маршруце патрулявання. Стан Attacking кожны кадр будзе спрабаваць пачаць атаку ці перайсці ў стан, калі гэта магчыма.
Для другога тыпу разгледзім пераход «калі вораг бачны і вораг занадта моцны, то перайсці ў стан Finding Help. Агент павінен абраць, куды пайсці за дапамогай, і захаваць гэтую інфармацыю, каб стан Finding Help ведала куды звярнуцца. Як толькі дапамога знойдзена, агент пераходзіць назад у стан Attacking. У гэты момант ён захоча распавесці саюзніку аб пагрозе, таму можа ўзнікнуць дзеянне NotifyFriendOfThreat.
І зноў мы можам паглядзець на гэтую сістэму праз прызму цыклу Sense/Think/Act. Sense увасабляецца ў дадзеных, якія выкарыстоўваюцца логікай пераходу. Think - пераходамі, даступнымі ў кожным стане. А Act ажыццяўляецца дзеяннямі, якія здзяйсняюцца перыядычна ў межах стану ці на пераходах паміж станамі.
Часам бесперапыннае апытанне ўмоў пераходу можа быць дарагім. Напрыклад, калі кожны агент будзе выконваць складаныя вылічэнні кожны кадр, каб вызначыць ці бачыць ён ворагаў і зразумець, ці можна пераходзіць ад стану Patrolling да Attacking – гэта зойме шмат часу працэсара.
Важныя змены ў стане міру можна разглядаць як падзеі, якія будуць апрацоўвацца па меры іх з'яўлення. Замест таго, каб FSM кожны кадр правяраў умову пераходу "ці можа мой агент бачыць гульца?", можна наладзіць асобную сістэму, каб выконваць праверкі радзей (напрыклад, 5 раз у секунду). А вынікам выдаваць Player Seen, калі праверка праходзіць.
Гэта перадаецца ў FSM, які зараз павінен перайсці ва ўмову Player Seen event received і адпаведна адрэагаваць. Выніковыя паводзіны аднолькава за выключэннем амаль незаўважнай затрымкі перад адказам. Затое прадукцыйнасць стала лепш у выніку аддзяленні часткі Sense у асобную частку праграмы.
Hierarchical finite state machine
Аднак працаваць з вялікімі FSM не заўсёды зручна. Калі мы захочам пашырыць стан нападу, замяніўшы яго асобнымі MeleeAttacking (блізкі бой) і RangedAttacking (далёкі бой), нам давядзецца змяніць пераходы з усіх іншых станаў, якія вядуць у стан Attacking (бягучыя і будучыя).
Напэўна, вы заўважылі, што ў нашым прыкладзе шмат дубляваных пераходаў. Большасць пераходаў у стане Idling ідэнтычныя пераходам у стане Patrolling. Добра было б не паўтарацца, асабліва калі мы дадамо больш падобных станаў. Мае сэнс згрупаваць Idling і Patrolling пад агульным цэтлікам «небаявыя», дзе ёсць толькі адзін агульны набор пераходаў у баявыя станы. Калі мы прадставім гэты цэтлік як стан, то Idling і Patrolling стануць падстанамі. Прыклад выкарыстання асобнай табліцы пераходаў для новага небаявога падстанаўлення:
Асноўныя станы:
Стан па-за бою:
І ў форме дыяграмы:
Гэта тая ж самая сістэма, але з новым небаявым станам, якое ўключае ў сябе Idling і Patrolling. З кожным станам, якія змяшчаюць FSM з падстанамі (а гэтыя падстанні, у сваю чаргу, утрымоўваюць уласныя FSM - і гэтак далей колькі вам трэба), мы атрымліваем Hierarchical Finite State Machine або HFSM (іерархічны канчатковы аўтамат). Згрупаваўшы небаявы стан, мы выразалі кучу залішніх пераходаў. Тое самае мы можам зрабіць для любых новых станаў з агульнымі пераходамі. Напрыклад, калі ў будучыні мы пашырым стан Attacking да станаў MeleeAttacking and MissileAttacking, яны будуць падстанамі, пераходзячымі паміж адзін адным на аснове адлегласці да ворага і наяўнасці боепрыпасаў. У выніку складаныя мадэлі паводзін і падмадэлі паводзін можна ўявіць з мінімумам дубляваных пераходаў.
Дрэва паводзін
З HFSM ствараюцца складаныя камбінацыі паводзін простым спосабам. Тым не менш, ёсць невялікая цяжкасць, што прыняцце рашэнняў у выглядзе правіл пераходу цесна звязана з бягучым станам. І ў многіх гульнях гэта якраз тое, што патрэбна. А стараннае выкарыстанне іерархіі станаў можа зменшыць колькасць паўтораў пры пераходзе. Але часам патрэбныя правілы, якія працуюць незалежна ад таго, у якім стане вы знаходзіцеся ці якія прымяняюцца амаль у любых станах. Напрыклад, калі здароўе агента ўпала да 25%, вы захочаце, каб ён уцякаў незалежна ад таго, ці быў ён у баі, лайдачыў або размаўляў - вам давядзецца дадаваць гэтую ўмову ў кожны стан. А калі ваш дызайнер пазней захоча змяніць парог нізкага здароўя з 25% да 10%, то гэтым зноў давядзецца займацца.
У ідэале для гэтай сітуацыі патрэбна сістэма, у якой рашэнні "ў якім стане знаходзіцца", знаходзяцца па-за межамі саміх станаў, каб уносіць змены толькі ў адным месцы і не чапаць умовы пераходу. Тут з'яўляюцца дрэвы паводзін.
Існуе некалькі спосабаў іх рэалізацыі, але сутнасць для ўсіх прыкладна аднолькавая і падобная на дрэва рашэнняў: алгарытм пачынаецца з "каранёвага" вузла, а ў дрэве знаходзяцца вузлы, якія прадстаўляюць альбо рашэнні, альбо дзеянні. Праўда ёсць некалькі ключавых адрозненняў:
- Цяпер вузлы вяртаюць адно з трох значэнняў: Succeeded (калі праца выканана), Failed (калі нельга запусціць) ці Running (калі яна ўсё яшчэ запушчана і няма канчатковага выніку).
- Больш няма вузлоў рашэнняў для выбару паміж дзвюма альтэрнатывамі. Замест іх вузлы Decorator, у якіх ёсць адзін даччыны вузел. Калі яны Succeed, то выконваюць свой адзіны даччыны вузел.
- Вузлы, якія выконваюць дзеянні, вяртаюць значэнне Running для падання выкананых дзеянняў.
Гэты невялікі набор вузлоў можна аб'яднаць для стварэння вялікай колькасці складаных мадэляў паводзін. Прадстаўляльны HFSM варта з папярэдняга прыкладу ў выглядзе дрэва паводзін:
З гэтай структурай не павінна быць відавочнага пераходу ад станаў Idling/Patrolling да стану Attacking ці любым іншым. Калі вораг бачны, а здароўе персанажа нізкае, выкананне спыніцца на вузле Fleeing, незалежна ад таго, які вузел ён раней выконваў - Patrolling, Idling, Attacking ці любой іншай.
Дрэвы паводзін складаныя - ёсць шмат спосабаў іх скласці, ды і знайсці правільнае спалучэнне дэкаратараў і складовых вузлоў можа быць праблематычна. Ёсць таксама пытанні аб тым, як часта правяраць дрэва — мы хочам праходзіць яго кожную частку ці толькі тады, калі адна з умоў змянілася? Як захоўваць стан, якое адносіцца да вузлоў - як даведацца, калі мы былі ў стане Idling на працягу 10 секунд або як даведацца, якія вузлы выконваліся ў мінулы раз, каб правільна апрацаваць паслядоўнасць?
Менавіта таму існуе мноства рэалізацый. Напрыклад, у некаторых сістэмах вузлы дэкаратара замянілі ўбудаванымі дэкаратарамі. Яны паўторна ацэньваюць дрэва пры змене ўмоў дэкаратара, дапамагаюць далучыцца да вузлоў і забяспечваюць перыядычныя абнаўленні.
Utility-based system
У некаторых гульняў ёсць мноства розных механік. Пажадана, каб яны атрымалі ўсе перавагі простых і агульных правіл пераходу, але не абавязкова ў выглядзе поўнага дрэва паводзін. Замест таго, каб мець дакладны набор выбараў ці дрэва магчымых дзеянняў, прасцей вывучыць усе дзеянні і выбраць самае прыдатнае ў дадзены момант.
Utility-based system (сістэма, заснаваная на карыснасці) як раз у гэтым дапаможа. Гэта сістэма, дзе ў агента ёсць мноства дзеянняў, і ён сам выбірае якое выканаць, засноўваючыся на адноснай карыснасці кожнага. Дзе карыснасць - адвольная мера таго, наколькі важна ці пажадана выкананне гэтага дзеяння для агента.
Разлічаную карыснасць дзеянні на аснове бягучага стану і асяроддзя, агент можа праверыць і выбраць найбольш прыдатны іншы стан у любы час. Гэта падобна на FSM, за выключэннем таго, дзе пераходы вызначаюцца ацэнкай для кожнага патэнцыйнага стану, у тым ліку бягучае. Звярніце ўвагу, што мы выбіраем самае карыснае дзеянне для пераходу (ці застаемся, калі ўжо выканалі яго). Для большай разнастайнасці гэта можа быць узважаны, але выпадковы выбар з невялікага спісу.
Сістэма прызначае адвольны дыяпазон значэнняў карыснасці - напрыклад, ад 0 (цалкам непажадана) да 100 (цалкам пажадана). У кожнага дзеяння ёсць шэраг параметраў, якія ўплываюць на вылічэнне гэтага значэння. Вяртаючыся да нашага прыкладу са вартавым:
Пераходы паміж дзеяннямі неадназначныя - любы стан можа ісці за любым іншым. Прыярытэты дзеянняў знаходзяцца ва вяртаемых значэннях карыснасці. Калі вораг бачны, і гэты вораг моцны, а здароўе персанажа нізкае, то і Fleeing, і FindingHelp вернуць высокія ненулявыя значэнні. Пры гэтым FindingHelp заўсёды будзе вышэйшым. Аналагічным чынам, небаявыя дзеянні ніколі не вяртаюць больш за 50, таму яны заўсёды будуць ніжэй за баявыя. Трэба ўлічваць гэта пры стварэнні дзеянняў і вылічэнні іх карыснасці.
У нашым прыкладзе дзеянні вяртаюць альбо фіксаванае сталае значэнне, альбо адно з двух фіксаваных значэнняў. Больш рэалістычная сістэма мяркуе вяртанне адзнакі з бесперапыннага дыяпазону значэнняў. Напрыклад, дзеянне Fleeing вяртае больш высокія значэнні карыснасці, калі здароўе агента нізкае, а дзеянне Attacking вяртае ніжэйшыя, калі вораг занадта моцны. З-за гэтага дзеянне Fleeing мае прыярытэт над Attacking у любой сітуацыі, калі агент адчувае, што ў яго недастаткова здароўя для перамогі над супернікам. Гэта дазваляе змяняць прыярытэты дзеянняў на аснове любога ліку крытэрыяў, што робіць такі падыход больш гнуткім і варыятыўным, чым дрэва паводзін ці FSM.
Кожнае дзеянне мае шмат умоў для разліку праграмы. Іх можна напісаць на мове сцэнарыяў ці ў выглядзе серыі матэматычных формул. У The Sims, якая мадэлюе распарадак дня персанажа, дадаюць дадатковы ўзровень вылічэнняў – агент атрымлівае шэраг "матывацый", якія ўплываюць на ацэнкі карыснасці. Калі персанаж галодны, то з часам ён будзе галадаць яшчэ мацней, і вынік карыснасці дзеяння EatFood будзе расці да таго часу, пакуль персанаж не выканае яго, знізіўшы ўзровень голаду, і вярнуўшы значэнне EatFood роўным нулю.
Ідэя выбару дзеянняў на аснове сістэмы адзнак даволі простая, таму Utility-based system можна выкарыстоўваць як частка працэсаў прыняцця рашэнняў ІІ, а не як іх поўную замену. Дрэва рашэнняў можа запытаць адзнаку карыснасці двух даччыных вузлоў і абраць больш высокую. Аналагічным чынам, дрэва паводзін можа мець складовай вузел Utility для ацэнкі карыснасці дзеянняў, каб вырашыць, які даччыны элемент выканаць.
Рух і рух
У папярэдніх прыкладах у нас была платформа, якую мы перамяшчалі налева ці направа, і вартавы, які патруляваў ці атакаваў. Але як менавіта мы апрацоўваем перамяшчэнне агента на працягу вызначанага перыяду часу? Як мы ўстанаўліваем хуткасць, як мы пазбягаем перашкод, і як мы плануем маршрут, калі дабрацца да месца прызначэння складаней, чым проста рухацца па прамой? Давайце гэта разгледзім.
Кіраванне
На пачатковым этапе будзем лічыць, што кожны агент мае значэнне хуткасці, якое складаецца з, як хутка ён рухаецца і ў якім кірунку. Яна можа быць вымераная ў метрах у секунду, кіламетрах у гадзіну, пікселяў у секунду і т. д. Успамінаючы цыкл Sense/Think/Act, мы можам уявіць, што частка Think выбірае хуткасць, а частка Act ужывае гэтую хуткасць да агента. Звычайна ў гульнях ёсць фізічная сістэма, якая выконвае гэтую задачу за вас, вывучаючы значэнне хуткасці кожнага аб'екта і рэгулюючы яе. Таму можна пакінуць ІІ з адной задачай - вырашыць, якую хуткасць павінен мець агент. Калі вядома, дзе агент павінен быць, тое трэба перамясціць яго ў правільным кірунку з усталяванай хуткасцю. Вельмі трывіяльнае раўнанне:
desired_travel = destination_position - agent_position
Уявіце 2D-свет. Агент знаходзіцца ў кропцы (-2,-2), пункт прызначэння дзесьці на паўночным усходзе ў кропцы (30, 20), а неабходны шлях для агента, каб апынуцца там - (32, 22). Дапусцім, гэтыя пазіцыі вымяраюцца ў метрах - калі прыняць хуткасць агента за 5 метраў у секунду, то мы будзем маштабаваць наш вектар перамяшчэння і атрымаем хуткасць прыкладна (4.12, 2.83). З гэтымі параметрамі агент прыбыў бы да месца прызначэння амаль праз 8 секунд.
Пералічыць значэння можна ў любы час. Калі агент быў на паўдарогі да мэты, перасоўванне было б паловай даўжыні, але бо максімальная хуткасць агента 5 м/з (мы гэта вырашылі вышэй), хуткасць будзе аднолькавай. Гэта таксама працуе для якія рухаюцца мэт, дазваляючы агенту ўносіць невялікія змены па меры іх перасоўвання.
Але мы жадаем больш варыятыўнасці напрыклад, павольна нарасціць хуткасць, каб сімуляваць персанажа, які рухаецца з стаялага стану і пераходзячага да бегу. Тое ж самае можна зрабіць у канцы перад прыпынкам. Гэтыя фічы вядомыя як steering behaviours, кожнае з якіх мае канкрэтныя імёны: Seek (пошук), Flee (уцёкі), Arrival (прыбыццё) і г. д. Ідэя заключаецца ў тым, што сілы паскарэння могуць быць ужытыя да хуткасці агента, на аснове параўнання становішча агента і бягучай хуткасці з пунктам прызначэння, каб выкарыстоўваць розныя спосабы перамяшчэння да мэты.
Кожныя паводзіны мае крыху іншую мэту. Seek і Arrival - гэта спосабы перамяшчэння агента да кропкі прызначэння. Obstacle Avoidance (пазбяганне перашкод) і Separation (падзел) карэктуюць рух агента, каб абыходзіць перашкоды на шляху да мэты. Alignment (узгадненне) і Cohesion (сувязь) трымаюць агентаў пры перамяшчэнні разам. Любая колькасць розных steering behaviours можа быць падсумоўвана для атрымання аднаго вектара шляху з улікам усіх фактараў. Агент, які выкарыстоўвае паводзіны Arrival, Separation і Obstacle Avoidance, каб трымацца далей ад сцен і іншых агентаў. Гэты падыход добра працуе ў адчыненых лакацыях без лішніх дэталяў.
У больш складаных умовах, складанне розных паводзін працуе горш – напрыклад, агент можа затрымацца ў сцяне з-за канфлікту Arrival і Obstacle Avoidance. Таму трэба разглядаць варыянты, якія складаней, чым проста складанне ўсіх значэнняў. Спосаб такі: замест складання вынікаў кожнага паводзін, можна разгледзець рух у розных кірунках і абраць лепшы варыянт.
Аднак у складаным асяроддзі з тупікамі і выбарам, у які бок ісці, нам спатрэбіцца нешта яшчэ больш прасунутае.
пошук шляху
Steering behaviours выдатна падыходзіць для простага руху на адкрытай мясцовасці (футбольнае поле або арэна), дзе дабрацца ад А да Б - гэта прамы шлях з невялікімі адхіленнямі міма перашкод. Для складаных маршрутаў нам патрэбен pathfinding (пошук шляху), які з'яўляецца спосабам вывучэння свету і прыняцці рашэння аб маршруце праз яго.
Самы просты - накласці сетку на кожны квадрат побач з агентам і ацаніць у якіх з іх дазволена рухацца. Калі які-небудзь з іх з'яўляецца пунктам прызначэння, то выконвайце з яго па маршруце ад кожнага квадрата да папярэдняга, пакуль не дойдзеце да пачатку. Гэта і ёсць маршрут. У адваротным выпадку паўтарайце працэс з бліжэйшымі іншымі квадратамі, пакуль не знойдзеце месца прызначэння ці не скончацца квадраты (гэта азначае, што няма ніякага магчымага маршруту). Гэта тое, што фармальна вядома як Breadth-First Search ці BFS (алгарытм пошуку ў шырыню). На кожным кроку ён глядзіць ва ўсіх кірунках (таму breadth, шырыня ). Прастора пошуку падобна на хвалевы фронт, які перамяшчаецца, пакуль не дасягне шуканае месца - вобласць пошуку пашыраецца на кожным кроку датуль, пакуль у яе не патрапіць канчатковая кропка, пасля чаго можна адсачыць шлях да пачатку.
У выніку вы атрымаеце спіс квадратаў, па якіх складаецца патрэбны маршрут. Гэта і ёсць шлях (адсюль, pathfinding) - спіс месцаў, якія агент наведае, прытрымліваючыся да пункта прызначэння.
Улічваючы, што мы ведаем становішча кожнага квадрата ў свеце, можна выкарыстоўваць steering behaviours, каб рухацца па шляху - ад вузла 1 да вузла 2, затым ад вузла 2 да вузла 3 і гэтак далей. Найпросты варыянт - накіравацца да цэнтра наступнага квадрата, але яшчэ лепш - спыніцца на сярэдзіне грані паміж бягучым квадратам і наступным. З-за гэтага агент зможа зразаць куты на стромкіх паваротах.
У алгарытму BFS ёсць і мінусы – ён даследуе столькі ж квадратаў у "няправільным" кірунку, колькі ў "правільным". Тут з'яўляецца больш складаны алгарытм пад назовам A* (A star). Ён працуе таксама, але замест сляпога вывучэння квадратаў-суседзяў (затым суседзяў суседзяў, затым суседзяў суседзяў суседзяў і гэтак далей), ён збірае вузлы ў спіс і сартуе іх так, што наступны доследны вузел заўсёды той, які прывядзе да найкароткага маршруту. Вузлы сартуюцца на аснове эўрыстыкі, якая ўлічвае дзве рэчы - "кошт" гіпатэтычнага маршруту да патрэбнага квадрату (уключаючы любыя выдаткі на перамяшчэнне) і ацэнку таго, наколькі далёка гэты квадрат ад месца прызначэння (ссоўваючы пошук у правільным кірунку).
У гэтым прыкладзе паказана, што агент даследуе па адным квадраце за раз, кожны раз выбіраючы суседні, які з'яўляецца самым перспектыўным. Атрыманы шлях такі ж, як і пры BFS, але ў працэсе было разгледжана менш квадратаў - а гэта мае вялікае значэнне для прадукцыйнасці гульні.
Рух без сеткі
Але большасць гульняў не выкладзеныя на сетцы, і часцяком яе немагчыма зрабіць без шкоды рэалістычнасці. Патрэбны кампрамісы. Якіх памераў павінны быць квадраты? Занадта вялікімі - і яны не змогуць правільна ўявіць невялікія калідоры або павароты, занадта маленькімі - будзе празмерна шмат квадратаў для пошуку, які ў выніку зойме кучу часу.
Першае, што трэба зразумець - сетка дае нам граф звязаных вузлоў. Алгарытмы A* і BFS фактычна працуюць на графіках і наогул не клапоцяцца аб нашай сетцы. Мы маглі б паставіць вузлы ў любых месцах гульнявога свету: пры наяўнасці сувязі паміж любымі двума злучанымі вузламі, а таксама паміж пачатковай і канчатковай кропкай і прынамсі адным з вузлоў - алгарытм будзе працаваць таксама добра, як і раней. Часта гэта завуць сістэмай шляхавых кропак (waypoint), бо кожны вузел уяўляе сабою значную пазіцыю ў свеце, якая можа быць часткай любой колькасці гіпатэтычных шляхоў.
Прыклад 1: вузел у кожным квадраце. Пошук пачынаецца з вузла, у якім знаходзіцца агент, і заканчваецца ў вузле патрэбнага квадрата.
Прыклад 2: меншы набор вузлоў (пуцявых кропак). Пошук пачынаецца ў квадраце з агентам, праходзіць праз неабходную колькасць вузлоў, і затым працягваецца да пункта прызначэння.
Гэта суцэль гнуткая і магутная сістэма. Але патрэбная некаторая асцярожнасць у рашэннях, дзе і як змясціць waypoint, інакш агенты могуць проста не ўбачыць бліжэйшую кропку і не змогуць пачаць шлях. Было б прасцей, калі мы маглі аўтаматычна расставіць шляхавыя кропкі на аснове геаметрыі свету.
Тут з'яўляецца navigation mesh ці navmesh (навігацыйная сетка). Гэта звычайна 2D-сетка трыкутнікаў, якая накладваецца на геаметрыю свету – усюды, дзе агенту дазволена хадзіць. Кожны з трыкутнікаў у сетцы становіцца вузлом у графе і мае да трох сумежных трыкутнікаў, якія становяцца суседнімі вузламі ў графе.
Гэтая карціна з'яўляецца прыкладам з рухавічка Unity – ён прааналізаваў геаметрыю ў свеце і стварыў navmesh (на скрыншоце светла-блакітным колерам). Кожны палігон у navmesh - гэта вобласць, на якой агент можа стаяць або перамяшчацца з аднаго палігона ў іншы палігон. У дадзеным прыкладзе палігоны менш паверхаў, на якіх яны размешчаны - зроблена для таго, каб улічыць памеры агента, якія будуць выходзіць за межы яго намінальнага становішча.
Мы можам шукаць маршрут праз гэтую сетку, зноў выкарыстоўваючы алгарытм A*. Гэта дасць нам практычна ідэальны маршрут у свеце, які ўлічвае ўсю геаметрыю і пры гэтым не патрабуе лішніх вузлоў і стварэння шляхавых кропак.
Pathfinding - занадта шырокая тэма, пра якую мала аднаго раздзела артыкула. Калі хочаце вывучыць яе больш падрабязна, то ў гэтым дапаможа .
планаванне
Мы пераканаліся з pathfinding, што часам недастаткова проста выбраць напрамак і рухацца - мы павінны выбраць маршрут і зрабіць некалькі паваротаў, каб дабрацца да патрэбнага месца прызначэння. Мы можам абагульніць гэтую ідэю: дасягненне мэты гэта не проста наступны крок, а цэлая паслядоўнасць, дзе іншы раз патрабуецца зазірнуць наперад на некалькі крокаў, каб даведацца, якім павінен быць першы. Гэта называецца планаваннем. Pathfinding можна разглядаць як адно з некалькіх дадаткаў планавання. З пункту гледжання нашага цыклу Sense/Think/Act, гэта тое, дзе частка Think плануе некалькі частак Act на будучыню.
Разбяром на прыкладзе настольнай гульні Magic: The Gathering. Мы ходзім першымі з такім наборам карт на руках:
- Swamp - дае 1 чорную ману (карта зямлі).
- Forest - дае 1 зялёную ману (карта зямлі).
- Fugitive Wizard - патрабуе 1 сінюю ману для прызыву.
- Elvish Mystic - патрабуе 1 зялёную ману для прызыву.
Астатнія тры карты ігнаруем, каб было прасцей. Па правілах гульцу дазволена гуляць 1 карту зямлі за ход, ён можа "тапнуць" гэтую карту, каб выняць з яе ману, а затым выкарыстоўваць загаворы (уключаючы выклік істоты) па колькасці маны. У гэтай сітуацыі гулец-чалавек ведае, што трэба гуляць Forest, "тапнуць" 1 зялёную ману, а затым выклікаць Elvish Mystic. Але як пра гэта здагадацца гульнявому ІІ?
Простае планаванне
Трывіяльны падыход - спрабаваць кожнае дзеянне па чарзе, пакуль не застанецца прыдатных. Гледзячы на карты, ІІ бачыць, што можа згуляць Swamp. І гуляе яго. Ці засталіся іншыя дзеянні на гэтым хаду? Ён не можа выклікаць ні Elvish Mystic, ні Fugitive Wizard, паколькі для іх закліку патрабуецца адпаведна зялёная і сіняя мана, а Swamp дае толькі чорную ману. І ён ужо не зможа гуляць Forest, таму што ўжо згуляў Swamp. Такім чынам, гульнявы ІІ схадзіў па правілах, але зрабіў гэта дрэнна. Можна палепшыць.
Планаванне можа знайсці спіс дзеянняў, якія прыводзяць гульню ў жаданае стан. Таксама, як кожная квадрат на шляху меў суседзяў (у pathfinding), кожнае дзеянне ў плане таксама мае суседзяў ці пераемнікаў. Мы можам шукаць гэтыя дзеянні і наступныя дзеянні, пакуль не дасягнем жаданага стану.
У нашым прыкладзе, жаданы вынік "выклікаць істоту, калі гэта магчыма". У пачатку ходу мы бачым толькі два магчымыя дзеянні, дазволеныя правіламі гульні:
1. Згуляць Swamp (вынік: Swamp у гульні)
2. Згуляць Forest (вынік: Forest у гульні)
Кожнае прынятае дзеянне можа прывесці да далейшых дзеянняў і закрыць іншыя, зноў жа ў залежнасці ад правіл гульні. Прадстаўце, што мы згулялі Swamp - гэта выдаліць Swamp у якасці наступнага кроку (мы яго ўжо згулялі), таксама гэта выдаліць і Forest (таму што па правілах можна згуляць адну карту зямлі за ход). Пасля гэтага ІІ дадае ў якасці наступнага кроку - атрыманне 1 чорнай маны, таму што іншых варыянтаў няма. Калі ён пойдзе далей і абярэ Tap the Swamp, тое атрымае 1 адзінку чорнай маны і нічога з ёй не зможа зрабіць.
1. Згуляць Swamp (вынік: Swamp у гульні)
1.1 "Тапнуць" Swamp (вынік: Swamp "тапнуць", +1 адзінка чорнай маны)
Няма даступных дзеянняў - КАНЕЦ
2. Згуляць Forest (вынік: Forest у гульні)
Спіс дзеянняў выйшаў кароткім, мы зайшлі ў тупік. Паўтараем працэс для наступнага дзеяння. Мы гуляем Forest, адкрываем дзеянне «атрымаць 1 зялёную ману», якая ў сваю чаргу адкрые трэцяе дзеянне – заклік Elvish Mystic.
1. Згуляць Swamp (вынік: Swamp у гульні)
1.1 "Тапнуць" Swamp (вынік: Swamp "тапнуць", +1 адзінка чорнай маны)
Няма даступных дзеянняў - КАНЕЦ
2. Згуляць Forest (вынік: Forest у гульні)
2.1 "Тапнуць" Forest (вынік: Forest "тапнуць", +1 адзінка зялёнай маны)
2.1.1 Прызваць Elvish Mystic (вынік: Elvish Mystic у гульні, -1 адзінка зялёнай маны)
Няма даступных дзеянняў - КАНЕЦ
Нарэшце, мы вывучылі ўсе магчымыя дзеянні і знайшлі план, які заклікае істоту.
Гэта вельмі спрошчаны прыклад. Пажадана выбіраць найлепшы магчымы план, а не любы, які адпавядае нейкім крытэрам. Як правіла, можна ацаніць патэнцыйныя планы на аснове канчатковага выніку ці сукупнай выгады ад іх выканання. Можна налічыць сабе 1 ачко за гульню карты зямлі і 3 ачкі за выклік істоты. Гуляць Swamp было б планам, які дае 1 ачко. А згуляць Forest → Tap the Forest → заклікаць Elvish Mystic адразу дасць 4 ачкі.
Вось так працуе планаванне ў Magic: The Gathering, але па той жа логіцы гэта прымяняецца і ў іншых сітуацыях. Напрыклад, перамясціць пешку, каб вызваліць месца для ходу слана ў шахматах. Або схавацца за сцяной, каб бяспечна страляць у XCOM так. Увогуле, вы зразумелі сутнасць.
Палепшанае планаванне
Часам бывае зашмат патэнцыйных дзеянняў, каб разглядаць кожны магчымы варыянт. Вяртаючыся да прыкладу з Magic: The Gathering: дапусцім, што ў гульні і на ў вас на руках па некалькіх карт зямлі і істот - колькасць магчымых камбінацый хадоў можа вылічацца дзясяткамі. Ёсць некалькі рашэнняў праблемы.
Першы спосаб - backwards chaining (зваротнае фарміраванне ланцуга). Замест перабору ўсіх камбінацый, лепш пачаць з выніковага выніку і паспрабаваць знайсці прамы маршрут. Замест шляху ад кораня дрэва да вызначанага ліста, мы рухаемся ў зваротным кірунку - ад ліста да кораня. Гэты спосаб прасцей і хутчэй.
Калі ў суперніка 1 адзінка здароўя, можна знайсці план «нанесці 1 ці больш адзінак страт». Каб дабіцца гэтага трэба выканаць шэраг умоў:
1. Страты можа нанесці загавор - яно павінна быць у руцэ.
2. Каб разыграць загавор - патрэбна мана.
3. Каб атрымаць ману - трэба разыграць карту зямлі.
4. Каб разыграць карту зямлі - трэба мець яе ў руцэ.
Іншы спосаб – best-first search (найлепшы першы пошук). Замест перабору ўсіх шляхоў, мы выбіраем найбольш прыдатны. Часцей за ўсё гэты спосаб дае аптымальны план без лішніх выдаткаў на пошукі. A* - гэта форма найлепшага першага пошуку - даследуючы найбольш перспектыўныя маршруты з самага пачатку, ён ужо можа знайсці найлепшы шлях без неабходнасці правяраць астатнія варыянты.
Цікавым і ўсё папулярнейшым варыянтам best-first search з'яўляецца Monte Carlo Tree Search. Замест угадвання, якія планы лепш за іншых пры выбары кожнага наступнага дзеяння, алгарытм выбірае выпадковых пераемнікаў на кожным кроку, пакуль не дасягне канца (калі план прывёў да перамогі або паразы). Затым выніковы вынік выкарыстоўваецца для падвышэння ці паніжэнні адзнакі «вагі» папярэдніх варыянтаў. Паўтараючы гэты працэс некалькі разоў запар, алгарытм дае добрую адзнаку таго, які наступны крок лепш, нават калі сітуацыя зменіцца (калі супернік прыме меры, каб перашкодзіць гульцу).
У аповядзе аб планаванні ў гульнях не абыдзецца без Goal-Oriented Action Planning або GOAP (мэтанакіраванае планаванне дзеянняў). Гэта шырока выкарыстоўваны і які абмяркоўваецца метад, але апроч некалькіх адметных дэталяў гэта, па ісце, метад backwards chaining, аб якім мы казалі раней. Калі задача была «знішчыць гульца», і гулец знаходзіцца за хованкай, план можа быць такім: знішчы гранатай → дастань яе → кінь.
Звычайна існуе некалькі мэт, кожная са сваім прыярытэтам. Калі мэта з найвышэйшым прыярытэтам не можа быць выканана (ні адна камбінацыя дзеянняў не стварае план «знішчыць гульца», таму што гулец не бачны), ІІ вернецца да мэт з ніжэйшым прыярытэтам.
Навучанне і адаптацыя
Мы ўжо казалі, што гульнявой ІІ звычайна не выкарыстоўвае машыннае навучанне, таму што гэта не падыходзіць для кіравання агентамі ў рэальным часе. Але гэта не значыць, што нельга што-небудзь запазычыць з гэтай вобласці. Мы жадаем такога суперніка ў шутэры, у якога можна чаму-небудзь навучыцца. Напрыклад, даведацца аб лепшых пазіцыях на мапе. Або суперніка ў файтингу, які блакаваў бы часта выкарыстоўваныя гульцом комба-прыёмы, матывуючы выкарыстаць іншыя. Так што машыннае навучанне ў такіх сітуацыях можа быць вельмі карысным.
Статыстыка і верагоднасці
Перш чым мы пяройдзем да складаных прыкладаў, прыкінем, як далёка мы можам зайсці, узяўшы некалькі простых вымярэнняў і выкарыстоўваючы іх для прыняцця рашэнняў. Да прыкладу, стратэгія ў рэальным часе - як нам вызначыць ці зможа гулец пачаць атаку ў першыя некалькі хвілін гульні і якую абарону супраць гэтага прыгатаваць? Мы можам вывучыць мінулы досвед гульца, каб зразумець, якой можа быць будучая рэакцыя. Пачнем з таго, што ў нас няма такіх зыходных дадзеных, але мы іх можам сабраць - кожны раз, калі ІІ гуляе супраць чалавека, ён можа запісваць час першай атакі. Праз некалькі сесій мы атрымаем сярэдняе значэнне часу, праз якое гулец будзе атакаваць у будучыні.
У сярэдніх значэнняў ёсць і праблема: калі гулец 20 разоў "рашыў", а 20 разоў гуляў павольна, то патрэбныя значэнні будуць дзесьці ў сярэдзіне, а гэта нічога карыснага нам не дасць. Адным з рашэнняў з'яўляецца абмежаванне ўваходных дадзеных - можна ўлічваць апошнія 20 штук.
Аналагічны падыход выкарыстоўваецца пры адзнацы верагоднасці вызначаных дзеянняў, мяркуючы, што мінулыя перавагі гульца будуць такімі ж у будучыні. Калі гулец атакуе нас пяць разоў фаерболам, два разы маланкай і адзін раз урукапашную, відавочна, што ён аддае перавагу фаерболу. Экстрапалюем і ўбачым верагоднасць выкарыстання рознай зброі: фаербол=62,5%, маланка=25% і рукапашная=12,5%. Нашаму гульнявому ІІ трэба падрыхтавацца да абароны ад агню.
Яшчэ адзін цікавы метад — выкарыстоўваць Naive Bayes Classifier (наіўны байесаўскі класіфікатар) для вывучэння вялікіх аб'ёмаў уваходных дадзеных і класіфікаваць сітуацыю, каб ІІ рэагаваў патрэбнай выявай. Баесаўскія класіфікатары найбольш вядомыя за выкарыстанне ў фільтрах спаму электроннай пошты. Там яны даследуюць словы, параўноўваюць іх з тым, дзе з'яўляліся гэтыя словы раней (у спаме ці не), і робяць высновы аб уваходных лістах. Мы можам зрабіць тое ж самае нават з меншай колькасцю ўваходных дадзеных. На аснове ўсёй карыснай інфармацыі, якую бачыць ІІ (напрыклад, якія варожыя юніты створаны, ці якія загаворы яны выкарыстоўваюць, ці якія тэхналогіі яны даследавалі), і выніковага выніку (вайна ці мір, «рашыць» ці абараняцца і г. д.) — мы выберам патрэбныя паводзіны ІІ.
Усіх гэтых спосабаў навучання дастаткова, але пажадана выкарыстоўваць іх на аснове дадзеных з тэсціравання. ІІ навучыцца адаптавацца да розных стратэгій, якія выкарыстоўвалі вашыя плэйтэстары. ІІ, які адаптуецца да гульца пасля рэлізу, можа стаць занадта прадказальным ці наадварот занадта складаным для перамогі.
Адаптацыя на аснове значэнняў
Улічваючы напаўненне нашага гульнявога свету і правілаў, мы можам змяніць набор значэнняў, якія ўплываюць на прыняцце рашэнняў, а не проста выкарыстоўваць уваходныя дадзеныя. Які робіцца так:
- Няхай ІІ збірае дадзеныя аб стане свету і ключавых падзеях падчас гульні (як паказана вышэй).
- Зменім некалькі важных значэнняў (value) на аснове гэтых даных.
- Рэалізуем свае рашэнні, заснаваныя на апрацоўцы або ацэнцы гэтых значэнняў.
Напрыклад, у агента ёсць некалькі пакояў для выбару на карце шутэра ад першай асобы. Кожны пакой мае сваё value, якое вызначае наколькі яна пажадана для наведвання. ІІ выпадкова выбірае ў які пакой ісці, засноўваючыся на значэнні value. Затым агент запамінае, у якім пакоі яго забілі, і памяншае яе value (верагоднасць, што ён туды вернецца). Аналагічна для зваротнай сітуацыі - калі агент знішчае шмат супернікаў, то value пакоі павялічваецца.
Маркаўская мадэль
Што калі мы выкарыстоўваем сабраныя дадзеныя для прагназавання? Калі запомніць кожны пакой, у якім бачым гульца на працягу вызначанага перыяду часу, мы будзем прадбачыць у які пакой гулец можа перайсці. Адсачыўшы і запісаўшы перасоўванні гульца па пакоях (values), мы можам прагназаваць іх.
Возьмем тры пакоі: чырвоны, зялёны і сіні. А таксама назіранні, якія мы запісалі пры праглядзе гульнявой сесіі:
Колькасць назіранняў за кожным пакоем амаль роўнае - дзе зрабіць добрае месца для засады мы да гэтага часу не ведаем. Збор статыстыкі таксама ўскладняецца респауном гульцоў, якія з'яўляюцца раўнамерна па ўсёй мапе. Але дадзеныя аб наступным пакоі, у якую яны ўваходзяць пасля з'яўлення на карце - ужо карысныя.
Відаць, што зялёны пакой задавальняе гульцоў - большасць людзей з чырвонай пераходзяць у яе, 50% якіх застаецца там і далей. Сіні пакой наадварот не карыстаецца папулярнасцю, у яго амаль не ходзяць, а калі ходзяць, то не затрымліваюцца.
Але дадзеныя кажуць нам сёе-тое больш важнае - калі гулец знаходзіцца ў сінім пакоі, то наступны пакой, у якой мы яго хутчэй за ўсё ўбачым будзе чырвоным, а не зялёным. Нягледзячы на тое, што зялёны пакой папулярней чырвонай, сітуацыя мяняецца, калі гулец знаходзіцца ў сіняй. Наступны стан (гэта значыць пакой, у якую гулец пяройдзе) залежыць ад папярэдняга стану (гэта значыць пакоі, у якой гулец знаходзіцца цяпер). З-за даследавання залежнасцяў мы будзем рабіць прагнозы дакладней, чым калі б мы проста падлічвалі назіранні незалежна сябар ад сябра.
Прадбачэнне будучыні стану на аснове дадзеных мінулага стану завецца маркаўскай мадэллю (Markov model), а такія прыклады (з пакоямі) завуць маркаўскімі ланцугамі. Паколькі мадэлі ўяўляюць сабой верагоднасць змен паміж паслядоўнымі станамі, візуальна яны адлюстроўваюцца ў выглядзе FSM з верагоднасцю каля кожнага пераходу. Раней мы выкарыстоўвалі FSM для прадстаўлення паводніцкага стану, у якім знаходзіўся агент, але гэтая канцэпцыя распаўсюджваецца на любы стан, незалежна ад таго, звязана гэта з агентам ці не. У гэтым выпадку стану ўяўляюць пакой, які займае агент:
Гэта просты варыянт уяўлення адноснай верагоднасці зменаў станаў, які дае ІІ нейкую магчымасць прадказваць наступнае стан. Можна прадбачыць некалькі крокаў наперад.
Калі гулец у зялёным пакоі, то ёсць 50% шанец, што ён там і застанецца пры наступным назіранні. Але якая верагоднасць, што ён усё яшчэ будзе там нават пасля? Ёсць не толькі шанец, што гулец застаўся ў зялёным пакоі пасля двух назіранняў, але і шанец, што ён сышоў і вярнуўся. Вось новая табліца з улікам новых дадзеных:
З яе відаць, што шанец убачыць гульца ў зялёным пакоі пасля двух назіранняў будзе роўны 51% - 21%, што ён прыйдзецца з чырвонага пакоя, 5% з іх, што гулец наведае сіні пакой паміж імі, і 25%, што гулец наогул не сыдзе з зялёнага пакоя.
Табліца - проста наглядная прылада - працэдура патрабуе толькі множання верагоднасцяў на кожным кроку. Гэта азначае, што вы можаце зазірнуць далёка ў будучыню з адной папраўкай: мы мяркуем, што шанец увайсці ў пакой цалкам залежыць ад бягучага пакоя. Гэта называецца маркаўскім уласцівасцю (Markov Property) - будучы стан залежыць толькі ад сучаснасці. Але гэта не цалкам дакладна. Гульцы могуць мяняць рашэнні ў залежнасці ад іншых фактараў: узровень здароўя або колькасць боепрыпасаў. Так як мы не фіксуем гэтыя значэння, нашы прагнозы будуць менш дакладнымі.
N-Grams
А што наконт прыкладу з файтынгам і прадказаннем комба-прыёмаў гульца? Тое ж самае! Але замест аднаго стану або падзеі, мы будзем даследаваць цэлыя паслядоўнасці, з якіх складаецца комба-ўдар.
Адзін са спосабаў зрабіць гэта - захаваць кожны ўвод (напрыклад, Kick, Punch або Block) у буферы і запісаць увесь буфер у выглядзе падзеі. Такім чынам, гулец неаднаразова націскае Kick, Kick, Punch, каб выкарыстоўваць напад SuperDeathFist, сістэма ІІ захоўвае ўсе ўводы ў буферы і запамінае апошнія тры, якія выкарыстоўваюцца на кожным кроку.
(Тоўстым вылучаныя радкі, калі гулец запускае напад SuperDeathFist.)
ІІ ўбачыць усе варыянты, калі гулец абраў Kick, следам за іншым Kick, а пасля заўважыць, што наступны ўвод заўсёды Punch. Гэта дазволіць агенту спрагназаваць комба-прыём SuperDeathFist і заблакаваць яго, калі гэта магчыма.
Гэтыя паслядоўнасці падзей называюцца N-грамамі (N-grams), дзе N - колькасць захоўваемых элементаў. У папярэднім прыкладзе гэта была 3-грама (трыграма), што азначае: першыя два запісы выкарыстоўваюцца для прагназавання трэцяй. Адпаведна ў 5-граме першыя чатыры запісы прадказваюць пяты і гэтак далей.
Распрацоўніку трэба старанна выбіраць памер N-грам. Меншы лік N патрабуе менш памяці, але і захоўвае меншую гісторыю. Напрыклад, 2-грама (біграма) будзе запісваць Kick, Kick або Kick, Punch, але не зможа захоўваць Kick, Kick, Punch, таму ІІ не адрэагуе на комба SuperDeathFist.
З іншага боку, вялікія лікі патрабуюць больш памяці і ІІ будзе складаней навучыцца, бо з'явіцца значна больш магчымых варыянтаў. Калі ў вас было тры магчымыя ўводы Kick, Punch або Block, а мы выкарыстоўвалі 10-граму, то атрымаецца каля 60 тысяч розных варыянтаў.
Мадэль біграмы гэта просты маркаўскі ланцуг — кожная пара «мінулае стан/бягучы стан» з'яўляецца біграмай, і вы можаце прадказаць другі стан на аснове першага. 3-грама і буйнейшыя N-грамы таксама можна разглядаць як маркоўскія ланцугі, дзе ўсе элементы (акрамя апошняга ў N-граме) разам утвораць першы стан, а апошні элемент - другое. Прыклад з файтингом паказвае шанец пераходу ад стану Kick і Kick да стану Kick і Punch. Разглядаючы некалькі запісаў уваходнай гісторыі як адну адзінку, мы, па сутнасці, пераўтворым уваходную паслядоўнасць у частку цэлага стану. Гэта дае нам маркаўскую ўласцівасць, якое дазваляе выкарыстоўваць маркаўскія ланцугі для прагназавання наступнага ўводу і адгадаць, які комба-ход будзе наступным.
Заключэнне
Мы пагаварылі аб найбольш распаўсюджаных інструментах і падыходах у распрацоўцы штучнага інтэлекту. А таксама разабралі сітуацыі, у якіх іх трэба прымяняць і дзе яны асабліва карысныя.
Гэтага павінна быць дастаткова для разумення базавых рэчаў у гульнявым ІІ. Але, канешне ж, гэта далёка не ўсе метады. Да менш папулярным, але не менш эфектыўным адносяцца:
- алгарытмы па аптымізацыі, уключаючы ўзыходжанне па ўзгорках, градыентны спуск і генетычныя алгарытмы
- спаборныя алгарытмы пошуку/планавання (minimax і alpha-beta pruning)
- метады класіфікацыі (перцэптроны, нейронавыя сеткі і машыны апорных вектараў)
- сістэмы для апрацоўкі ўспрымання і памяці агентаў
- архітэктурныя падыходы да ІІ (гібрыдныя сістэмы, падмноства архітэктур і іншыя спосабы накладання сістэм ІІ)
- інструменты анімацыі (планаванне і ўзгадненне руху)
- фактары прадукцыйнасці (узровень дэталізацыі, алгарытмы anytime, і timeslicing)
Інтэрнэт-рэсурсы па тэме:
1. На GameDev.net ёсць , а таксама .
2. змяшчае мноства прэзентацый і артыкулаў па шырокім спектры звязаных з распрацоўкай гульнявога ІІ.
3. уключае ў сябе топікі з саміту GDC AI, многія з якіх даступныя бясплатна.
4. Карысныя матэрыялы таксама можна знайсці на сайце .
5. Томі Томпсан, даследчык ІІ і распрацоўшчык гульняў, робіць ролікі на YouTube-канале з тлумачэннем і вывучэннем ІІ ў камерцыйных гульнях.
Кнігі па тэме:
1. Серыя кніг Game AI Pro уяўляе сабой зборнікі кароткіх артыкулаў, якія тлумачаць, як рэалізаваць канкрэтныя функцыі або як вырашаць канкрэтныя праблемы.
2. Серыя AI Game Programming Wisdom - папярэднік серыі Game AI Pro. У ёй больш старыя метады, але амаль усе актуальныя нават сёння.
3. - гэта адзін з базавых тэкстаў для ўсіх жадаючых разабрацца ў агульнай галіне штучнага інтэлекту. Гэта кніга не аб гульнявой распрацоўцы - яна вучыць базавым асновам ІІ.
Крыніца: habr.com