Как да създадете игрови ИИ: ръководство за начинаещи

Срещнах интересен материал за изкуствения интелект в игрите. С обяснение на основните неща за ИИ чрез прости примери, а също така има много полезни инструменти и методи за удобна разработка и проектирането му. Как, къде и кога да ги използваме — също е налично.

Повечето примери са написани в псевдокод, затова задълбочени знания по програмиране не са необходими. Под кат има 35 страници текст с картинки и гифове, така че се пригответе.

UPD. Извинявайте, но вече направих свой собствен превод на тази статия в Хабре. PatientZero. Можете да прочетете неговата версия тук, но поради някаква причина статията ми убягна (използвах търсене, но нещо не се получи). И тъй като пиша в блог, посветен на геймдев, реших да оставя своя вариант на превода за подписчиците (некои моменти съм оформил по различен начин, а някои — умишлено пропуснати по съвет на разработчиците).

Какво е ИИ?

Игровият ИИ е фокусиран върху това, какви действия трябва да предприеме обектът в зависимост от условията, в които се намира. Обикновено това се нарича управление на „интелигентни агенти“, където агентът може да бъде игров персонаж, превозно средство, бот или понякога нещо по-абстрактно: цяла група същества или дори цивилизация. Във всеки случай това е нещо, което трябва да възприема околната си среда, да взема решения на нейна основа и да действа съобразно тях. Това се нарича цикъл Sense/Think/Act (Чувстване/Мислене/Действие):

• Sense: агентът намира или получава информация за неща в околната си среда, които може да повлияят на поведението му (заплахи наблизо, предмети за събиране, интересни места за изследване).
• Think: агентът решава как да реагира (обмисля дали е безопасно да събира предмети или първо да се бие/скрие).
• Act: агентът извършва действия за реализиране на предишното решение (започва движение към противник или предмет).
• …сега ситуацията се е променила заради действията на персонажите, така че цикълът се повтаря с нови данни.

Изкуственият интелект обикновено се фокусира върху частта Sense от цикъла. Например, автономните автомобили заснемат пътя, съчетават данни от радари и лидари и ги интерпретират. Обикновено това се извършва от машинно обучение, което обработва входящите данни и придава смисъл, извличайки семантична информация като "има още един автомобил на 20 ярда напред от вас". Това са т.н. classification problems.

На играта не ѝ е необходима сложна система за извличане на информация, тъй като голяма част от данните вече са неразривна част от нея. Не е необходимо да се стартират алгоритми за разпознаване на изображения, за да се установи дали има враг напред — играта вече знае и предава информация директно в процеса на вземане на решения. Поради това частта от цикъла Sense често е много по-проста от Think и Act.

Ограничения на игровия ИИ

ИИ има редица ограничения, които трябва да се спазват:

• Не е необходимо ИИ предварително да се обучава, сякаш е алгоритъм за машинно обучение. Няма смисъл да се пише невронна мрежа по време на разработката, за да се наблюдават десетки хиляди играчи и да се изучи най-добрият начин за игра срещу тях. Защо? Защото играта не е пусната, а играчи няма.
• Играта трябва да развлекателна и предизвикателна, затова агентите не трябва да намират най-добрия подход срещу хора.
• Агентите трябва да изглеждат реалистично, за да могат играчите да чувстват, че играят срещу истински хора. Програмата AlphaGo надмина човека, но избраните ходове бяха много различни от традиционното разбиране на играта. Ако играта имитира противник-човек, такова чувство не трябва да се получава. Алгоритъмът трябва да бъде променен, така че да взема правдоподобни решения, а не идеални.
• ИИ трябва да работи в реално време. Това означава, че алгоритъмът не може да monopolize използването на процесора за дълго време, за да вземе решения. Дори 10 милисекунди за това — е твърде дълго, защото на повечето игри им е достатъчно от 16 до 33 милисекунди, за да извършат цялата обработка и да преминат към следващия кадър графика.
• Идеално би било поне част от системата да се управлява от данни, така че "некодерите" да могат да правят промени и корекциите да стават по-бързо.

Нека разгледаме подходите на ИИ, които обхващат целия цикъл Sense/Think/Act.

Вземане на основни решения

Да започнем с най-простата игра - Pong. Целта е да преместиш платформата (paddle) така, че топката да се отблъсне от нея, а не да мине покрай. Това е като тенис, в който губиш, ако не отбиеш топката. Тук на ИИ е сравнително лесно да реши в каква посока да премести платформата.

Условни оператори

За ИИ в Pong има най-очевидното решение - винаги да се опитва да постави платформата под топката.

Прост алгоритъм за това, написан в псевдокод:

всеки кадър/обновление, докато играта тече:
ако топката е отляво на платформата:
премести платформата наляво
иначе, ако топката е отдясно на платформата:
премести платформата надясно

Ако платформата се движи със скоростта на топката, то това е идеалният алгоритъм за ИИ в 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. С тях разработчикът може да взема обекти в играта си (top 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, която на всеки кадър ще проверява — дали AI вижда играча. Ако не — нищо не се случва, но ако вижда, се създава събитие Player Seen. Кодът ще има отделен раздел, в който е написано: «когато се е случило събитието Player Seen, направи », където — отговорът, който ви трябва, за да взаимодействате с частите Think и Act. По този начин ще настроите реакциите на събитието Player Seen: на „втурващия се“ персонаж — ChargeAndAttack, а на снipers — HideAndSnipe. Тези връзки могат да бъдат създадени в данни файл за бърза редакция без необходимост от повторно компилиране. И тук също може да се използва език за скриптове.

Приемане на сложни решения

Въпреки че простите системи на реакция са много ефективни, има много ситуации, когато те не са достатъчни. Понякога е необходимо да се взимат различни решения, основани на това, което агентът прави в момента, но представянето им като условие е трудно. Понякога съществуват твърде много условия, за да могат да бъдат ефективно представени в дърво на решения или скрипт. Понякога е необходимо предварително да се оцени как ще се промени ситуацията, преди да се вземе решение за следващата стъпка. За решаването на тези проблеми са нужни по-сложни подходи.

Краен автомат

Крайният автомат или FSM (Finite state machine) — е начин да се каже, че нашият агент в момента се намира в едно от няколко възможни състояния и че може да преминава от едно състояние в друго. Има определено количество от такива състояния — откъдето и името. Най-добрият пример от живота — светофар. На различни места има различни последователности на светлините, но принципът е същият — всяко състояние представлява нещо (спри, иди и т.н.). Светофарът е в едно състояние по всяко време и преминава от едно към друго на базата на прости правила.

С NPC в игрите ситуацията е подобна. Например, нека вземем страж със следните състояния:

• Патрулиращ (Patrolling).
• Атакуващ (Attacking).
• Бягащ (Fleeing).

И с такива условия за промяна на неговото състояние:

• Ако стражът види противник, той атакува.
• Ако стражът атакува, но вече не вижда противника, той се връща към патрулирането.
• Ако стражът атакува, но е тежко ранен, той бяга.

Може също да напишете if операторите с променливи за състояния на стража и различни проверки: има ли враг наблизо, какъв е нивото на здравето на NPC и т.н. Нека добавим още няколко състояния:

• Бездействие (Idling) — между патрулите.
• Търсене (Searching) — когато видян враг е изчезнал.
• Търсене на помощ (Finding Help) — когато врагът е забелязан, но е твърде силен, за да се бори с него сам.

Изборът за всеки от тях е ограничен — например, стражът няма да търси изчезнал враг, ако има ниско здраве.

Накрая, огромният списък "ако" <x и y, но не z>, тогава <p>", може да стане прекалено обширен, затова трябва да формализираме метод, който ще ни позволи да запазим в паметта състоянията и преходите между състоянията. За да постигнем това, ще разгледаме всички състояния и под всяко състояние ще запишем в списък всички преходи към други състояния, заедно с необходимите условия за тях.

Таблицата представя преходите между състоянията — комплексен начин за представяне на 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 в отделна част от програмата.

Йерархична крайна состоянина машина

Въпреки това, работата с големи FSM не винаги е удобна. Ако искаме да разширим състоянието на атака, заменяйки го с отделни MeleeAttacking (близък бой) и RangedAttacking (дистанционен бой), ще трябва да променим преходите от всички други състояния, които водят до състояние Attacking (текущи и бъдещи).

Сигурно сте забележили, че в нашия пример има много дублирани преходи. Повечето преходи в състояние Idling са идентични на преходите в състояние Patrolling. Би било добре да не се повтаряме, особено ако добавим повече подобни състояния. Има смисъл да групираме Idling и Patrolling под общ етикет „небойни“, където има само един общ набор от преходи към бойни състояния. Ако представим този етикет като състояние, Idling и Patrolling ще станат подсъстояния. Пример за използването на отделна таблица за преходи за новото небойно подсъстояние:

Основни състояния:


Състояние извън бой:


И под формата на диаграма:

Това е същата система, но с ново небойно състояние, което включва Idling и Patrolling. С всяко състояние, съдържащо FSM с подсъстояния (а тези подсъстояния, от своя страна, съдържат собствен FSM — и така нататък, колкото е необходимо), получаваме Иерархична крайна автоматизирана машина или HFSM (hierarchical finite state machine). Чрез групирането на небойното състояние сме намалили много от излишните преходи. Същото можем да направим за нови състояния с общи преходи. Например, ако в бъдеще разширим състоянието Attacking до състояния MeleeAttacking и MissileAttacking, те ще бъдат подсъстояния, които преминават едно в друго въз основа на разстоянието до врага и наличието на боеприпаси. В крайна сметка сложните поведенчески модели и подмодели могат да бъдат представени с минимум дублирани преходи.

Дърво на поведението

С HFSM се създават сложни комбинации от поведения по прост начин. Въпреки това, има малко затруднения, тъй като вземането на решения под формата на правила за преход е тясно свързано с текущото състояние. И в много игри това е точно това, от което се нуждаем. А внимателното използване на йерархията на състоянията може да намали количеството повторения при прехода. Но понякога са необходими правила, които работят независимо от това в какво състояние се намирате или които се прилагат почти във всяко състояние. Например, ако здравето на агента падне до 25%, ще искате да избяга независимо дали е бил в бой, бездействал или разговарял — ще трябва да добавите това условие във всяко състояние. А ако вашият дизайнер по-късно реши да променя прага за ниско здраве от 25% на 10%, отново ще е необходимо да се занимавате с това.

В идеалния случай за тази ситуация е необходима система, при която решенията „в какво състояние да се намираме“ са извън самите състояния, за да може да се правят промени само на едно място, без да се засягат условията за преход. Тук се появяват дърветата на поведението.

Съществуват няколко начина за тяхното реализиране, но същността за всички е приблизително една и съща и наподобява дърво на решения: алгоритъмът започва с „коренов“ възел, а в дървото има възли, представляващи или решения, или действия. Вярно е, че има няколко ключови разлики:

• Сега възлите връщат едно от трите значения: Succeeded (ако работата е изпълнена), Failed (ако не може да се стартира) или Running (ако все още е в процес на изпълнение и няма окончателен резултат).
• Няма повече възли на решения за избор между две алтернативи. Вместо тях, възлите Decorator имат един дочерен възел. Ако те успеят, изпълняват своя единствен дочерен възел.
• Възлите, изпълняващи действия, връщат стойност Running, за да представят извършваните действия.

Този малък набор от възли може да бъде комбиниран, за да създаде голямо количество сложни модели на поведение. Нека представим HFSM охранител от предишния пример във вид на дърво на поведението:

С тази структура не бива да има явен преход от състоянията Idling/Patrolling към състоянието Attacking или каквито и да било други. Ако врагът е видим и здравето на персонажа е ниско, изпълнението ще спре на възела Fleeing, независимо от това, кой възел е изпълнявал преди това — Patrolling, Idling, Attacking или какъвто и да е друг.

Дърветата на поведението са сложни — има много начини за тяхното изграждане, а и намирането на правилната комбинация от декоратори и сложни възли може да бъде проблематично. Съществуват също въпроси относно това колко често да проверяваме дървото — искаме ли да минаваме през всяка част от него или само когато едно от условията се е променило? Как да съхраняваме състоянието, свързано с възлите — как да разберем, когато сме били в състояние Idling в продължение на 10 секунди или как да разберем, кои възли са били изпълнявани последния път, за да обработим правилно последователността?

Точно затова съществуват много реализации. Например, в някои системи възлите декоратори са заменени с вградени декоратори. Те препроверяват дървото при промяна на условията на декоратора, помагат за свързването на възлите и осигуряват периодични актуализации.

Система, основана на полезност

Някои игри имат множество различни механики. Желателно е те да получат всички предимства на простите и общи правила за преход, но не е задължително в рамките на пълно дърво на поведението. Вместо да имат ясен набор от избори или дърво на възможни действия, е по-лесно да проучат всички действия и да изберат най-подходящото в момента.

Системата, основана на полезността, точно в това ще помогне. Това е система, в която агентът има множество действия и сам избира кое да извърши, основавайки се на относителната полезност на всяко. Където полезността е произволна мярка за това, колко важно или желателно е изпълнението на това действие за агента.

Сметнатата полезност на действието, базирана на текущото състояние и среда, агентът може да провери и да избере най-подходящото различно състояние по всяко време. Това е подобно на FSM, с изключение на това, че преходите се определят от оценка за състоянието, включително текущото. Обърнете внимание, че ние избираме най-полезното действие за преход (или оставаме, ако вече сме го извършили). За по-голямо разнообразие, това може да бъде тежестен, но случаен избор от малък списък.

Системата назначава произволен диапазон от стойности на полезността – например от 0 (изцяло нежелателно) до 100 (напълно желателно). Всяко действие има набор от параметри, влияещи на изчислението на тази стойност. Връщайки се на примера със стража:

Преходите между действията не са еднозначни – всяко състояние може да следва всяко друго. Приоритетите на действията се основават на стойностите на полезността. Ако врагът е видим и този враг е силен, а здравето на героя е ниско, както Fleeing, така и FindingHelp ще върнат високи ненулеви стойности. При това FindingHelp винаги ще бъде на по-високо място. По подобен начин, небоевите действия никога не връщат повече от 50, така че винаги ще бъдат по-ниски от бойните. Това трябва да се вземе предвид при създаването на действия и изчисляването на тяхната полезност.

В нашия пример, действията връщат или фиксирана константна стойност, или една от две фиксирани стойности. По-реалистичната система предполагава връщане на оценка от непрекъснат диапазон от стойности. Например, действието Убягство връща по-високи стойности на полезността, ако здравето на агента е ниско, а действието Атакуване връща по-ниски стойности, ако врагът е твърде силен. Поради това действието Убягство има приоритет над Атакуването във всяка ситуация, когато агентът усеща, че има недостатъчно здраве, за да победи противника. Това позволява да се променят приоритетите на действията въз основа на множество критерии, което прави този подход по-гъвкав и променлив от поведенческото дърво или FSM.

Всяко действие има много условия за изчисление на програмата. Те могат да бъдат написани на език за сценарии или под формата на серия математически формули. В The Sims, която моделира дневния ред на персонажа, се добавя допълнително ниво на изчисления - агентът получава редица "мотивации", които влияят на оценките на полезността. Ако персонажът е гладен, то с времето той ще огладнява още повече, а резултатът от действието Ядене на храна ще нараства, докато персонажът не го извърши, намалявайки нивото на глад и връщайки стойността на Ядене на храна обратно на нула.

Идеята за избор на действия на база система от оценки е доста проста, затова системата, основана на полезността, може да бъде използвана като част от процесите на вземане на решения на ИИ, а не като тяхна пълна замяна. Дървото на решенията може да поиска оценка на полезността от два дочерни възела и да избере по-високата. По подобен начин, поведенческото дърво може да има композитен възел за Оценка на полезността на действията, за да реши кой дочерни елемент да изпълни.

Движение и навигация

В предишните примери имахме платформа, която премествахме наляво или надясно, и страж, който патрулираше или атакуваше. Но как точно обработваме движението на агента през определен период от време? Как задаваме скорост, как избягваме препятствия и как планираме маршрута, ако достигането до целта е по-сложно от простото движение по права линия? Нека разгледаме това.

Управление

В начален етап ще приемем, че всеки агент има стойност на скорост, която включва колко бързо се движи и в каква посока. Тя може да бъде измерена в метри в секунда, километри в час, пиксели в секунда и т.н. Спомняйки си цикъла 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 всъщност работят върху графики и не се интересуват от нашата решетка. Можехме да поставим възли на всякакви места в игровия свят: при наличие на връзка между всяка две свързани точки, както и между началната и крайната точка и поне един от възлите — алгоритъмът ще работи също толкова добре, колкото и преди. Често това се нарича система на пътни точки, тъй като всеки възел представлява значима позиция в света, която може да бъде част от каквото и да е количество хипотетични пътища.

Пример 1: възел в всеки квадрат. Търсенето започва от възела, в който се намира агентът, и завършва в възела на желания квадрат.

Пример 2: по-малък набор от възли (пътни точки). Търсенето започва в квадрата с агента, преминава през необходимото количество възли и след това продължава към крайната точка.

Това е доста гъвкава и мощна система. Но е необходима известна внимание в решенията къде и как да се поставят пътни точки, иначе агентите може просто да не видят най-близката точка и да не могат да започнат пътя. Би било по-лесно, ако можехме автоматично да поставим пътните точки на базата на геометрията на света.

Тук се появява навигационната мрежа или 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 (целенаправленное планирование действий). Это широко используемый и обсуждаемый метод, но, за исключением нескольких отличительных деталей, это, по сути, метод обратной цепочки, о котором мы говорили ранее. Если задача — «уничтожить игрока», а игрок находится за укрытием, план может быть таковым: уничтожить снарядом → достать его → бросить.

Обычно есть несколько целей, каждая с собственным приоритетом. Если цель с наивысшим приоритетом не может быть выполнена (ни одна комбинация действий не создает план «уничтожить игрока», так как игрок не виден), ИИ вернется к целям с более низким приоритетом.

Обучение и адаптация

Мы уже обсуждали, что игровой ИИ обычно не использует машинное обучение, так как это не подходит для управления агентами в реальном времени. Однако это не означает, что из этой области нельзя почерпнуть что-то полезное. Мы хотим, чтобы в шутере был противник, у которого можно чему-либо научиться. Например, узнать о лучших позициях на карте. Или противник в файтинге, который блокировал бы часто используемые игроком комбо-приемы, побуждая использовать другие. Таким образом, машинное обучение в таких ситуациях может быть весьма полезным.

Статистика и вероятности

Преди да преминем към сложни примери, нека да видим колко далеч можем да стигнем, като вземем предвид няколко прости измерения и ги използваме за вземане на решения. Например, стратегическите действия в реално време — как можем да определим дали играч ще започне атака в първите няколко минути на играта и каква защита да подготвим срещу това? Можем да проучим предишния опит на играча, за да разберем каква би могла да бъде бъдещата му реакция. Започваме с това, че нямаме такива данни, но можем да ги съберем—всеки път, когато ИИ играе срещу човек, той може да записва времето на първата атака. След няколко сесии ще получим средната стойност на времето, след което играчът ще атакува в бъдеще.

Средните стойности имат и проблем: ако играчът е атакувал 20 пъти бързо и 20 пъти бавно, нужните стойности ще бъдат някъде по средата, а това не би било полезно за нас. Едно от решенията е да се ограничи входящият набор от данни—можем да вземе предвид последните 20 случая.

Подобен подход се използва при оценка на вероятността от определени действия, предполагаща, че предишните предпочитания на играча ще останат същите и в бъдеще. Ако играчът ни атакува пет пъти с огнени топки, два пъти с мълнии и веднъж на ръка, е очевидно, че той предпочита огнената топка. Извеждаме и вероятността за използване на различно оръжие: огнена топка = 62,5%, мълния = 25% и ръчен бой = 12,5%. Нашият игрови ИИ трябва да се подготви за защита срещу огън.

Още един интересен метод — използването на Naive Bayes Classifier (наивен байесов класификатор) за анализиране на големи обеми от входни данни и класифициране на ситуацията, за да може ИИ да реагира по подходящ начин. Байесовите класификатори са най-известни с използването си в спам филтрите за електронна поща. Там те анализират думите, сравняват ги с това, къде тези думи са се появявали преди (в спам или не) и правят заключения за входящите писма. Можем да направим същото дори с по-малко данни. На база на цялата полезна информация, която ИИ вижда (например, какви враждебни юнити са създадени или какви заклинания използват, или какви технологии са изследвали), и крайния резултат (война или мир, „рушене“ или защита и т.н.) — ще изберем подходящото поведение за ИИ.

Всички тези методи на обучение са достатъчни, но е желателно да се използват на базата на данни от тестване. ИИзкуственият интелект ще се научи да се адаптира към различни стратегии, които са използвали вашите играчи. ИИ, който се адаптира към играча след пускането на играта, може да стане твърде предсказуем или обратно, прекалено труден за победа.

Адаптация на базата на стойности

Като имаме предвид съдържанието на нашия игрови свят и правилата, можем да променим комплекта стойности, които влияят на вземането на решения, а не просто да използваме входни данни. Правим следното:

• Нека ИИ събира данни за състоянието на света и ключовите събития по време на играта (както е посочено по-горе).
• Нека променим няколко важни стойности (value) въз основа на тези данни.
• Реализираме нашите решения, основани на обработката или оценката на тези стойности.

Например, агентът има няколко стаи за избор на картата на FPS игра. Всяка стая има своя стойност, която определя колко желателна е тя за посещение. ИИ случайно избира в коя стая да отиде, основавайки се на стойността. След това агентът запомня в коя стая е бил убит и намалява стойността й (вероятността да се върне там). Аналогично за обратната ситуация – ако агентът унищожи много противници, стойността на стаята ще се увеличи.

Марков модел

Какво ако използваме събраните данни за прогнозиране? Ако запомним всяка стая, в която виждаме играча за определен период от време, ще можем да предскажем в коя стая играчът може да премине. Следяки и записвайки движенията на играча по стаите (стойности), можем да правим прогнози.

Нека вземем три стаи: червена, зелена и синя. И наблюденията, които сме записали при преглеждането на игровата сесия:

Броят на наблюденията за всяка стая е почти равен – все още не знаем къде да направим добро място за засада. Събирането на статистика също е затруднено от респаун на играчите, които се появяват равномерно по цялата карта. Но данните за следващата стая, в която влизат след появата си на картата – вече са полезни.

Ясно е, че зелената стая удовлетворява играчите – повечето хора от червената стая преминават в нея, а 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. AiGameDev.com съдържа множество презентации и статии по широк спектър, свързан с разработката на игрови ИИ.
3. The GDC Vault включва теми от саммита GDC AI, много от които са достъпни безплатно.
4. Полезни материали могат също да се намерят на сайта AI Game Programmers Guild.
5. Томми Томпсън, изследовател на ИИ и разработчик на игри, прави видеоклипове на YouTube канала AI and Games с обяснения и изследвания на ИИ в търговски игри.

Книги по темата:

1. Серия книги Game AI Pro включва сборници от кратки статии, които обясняват как да реализирате конкретни функции или как да решавате специфични проблеми.

Game AI Pro: Събрана Мъдрост на Професионалисти в Игровия ИИ
Game AI Pro 2: Събрана Мъдрост на Професионалисти в Игровия ИИ
Game AI Pro 3: Събрана Мъдрост на Професионалисти в Игровия ИИ

2. Серията AI Game Programming Wisdom е предшественик на серията Game AI Pro. Тя съдържа по-стари методи, но почти всички остават актуални и до днешния ден.

AI Game Programming Wisdom 1
AI Game Programming Wisdom 2
AI Game Programming Wisdom 3
AI Game Programming Wisdom 4

3. Изкуствен Интелект: Съвременен Подход — това е един от основните текстове за всеки, който иска да разбере общата област на изкуствения интелект. Тази книга не е за разработка на игри — тя учи основите на ИИ.

Източник: habr.com