Занимаясь я тут разработкой всякого рода игровых и околоигровых штук, время от времени задумываюсь - а как тот или иной момент был реализован в Великом и Ужасном? Технологии тогда были проще, компьютеры - слабее, и, тем не менее, многие вещи были хороши, и им до сих пор можно и нужно поучиться.
Реализуя AI в одной из своих вещей, я всерьёз задумался - а как же был сделан искусственный интеллект монстров в Doom? Их поведение достаточно простое и местами заведомо неэффективное - но такое, что только умелый игрок может воспользоваться их слабостями. Вместе с тем, не возникает ощущения наигранного идиотизма происходящего, как в некоторых современных шутерах В целом, монстры глуповаты, но свирепы и действуют будто бы с минимальным элементом случайности. Как раз то, что нужно от монстров.
Так вот, к чему это я... знает кто-нибудь хорошее описание алгоритмов их AI? В исходник напрямую лезть за этим не очень хочется - чувствую, специфики там будет изрядно. А нагугливаются, в основном, какие-то обрывки знаний, которые в стройную систему укладываться не очень желают сами по себе.
Navy Ну, не знаю, как в "настоящем" DooM, но я думаю, что вряд ли в его портах всё устроено ещё проще. У каждого типа монстров есть несколько состояний (например: бездействие; поведение, если замечен игрок; атака; смерть). Эти состояния содержат описание фреймов, каждый из которых занимает целое число игровых тиков (~1/35 секунды), присваивает монстру текстуру на это время [у нас же 2.5D, не так ли?] и выполняет какую-нибудь стандартную функцию (вроде "метнуть файрболл", в случае с импом). Ещё можно делать безусловные и условные переходы между фреймами и состояниями. Можно также объявлять свои состояния. Алгоритмов, как таковых, нет. Весь "ИИ" сосредоточен в паре-тройке десятков функций вроде "перемещение по уровню" или "выстрел n хитскановыми пулями в кого-то". Было бы странно ожидать от игры, которую изначально планировали сюжетной, повсеместного использования каких-нибудь крутых фишек вроде нейросетей. А что именно за "вещь", если не секрет?
У каждого типа монстров есть несколько состояний (например: бездействие; поведение, если замечен игрок; атака; смерть). Эти состояния содержат описание фреймов, каждый из которых занимает целое число игровых тиков (~1/35 секунды), присваивает монстру текстуру на это время [у нас же 2.5D, не так ли?] и выполняет какую-нибудь стандартную функцию (вроде "метнуть файрболл", в случае с импом). Ещё можно делать безусловные и условные переходы между фреймами и состояниями. Можно также объявлять свои состояния.
В общем-то, старая-добрая машина состояний, я примерно так и предполагал по прочитанному на DoomWiki Интерес представляют конкретно эти самые состояния, условия, виды функций - вид на всю картину в целом, про отдельные аспекты я почитал малость.
Например, как тот же зомбимен осуществляет атаку? Если я помню матчасть правильно, конечно, то он чередует выстрелы, замирание на месте, движение то в произвольном направлении, и какое-то хитрое блуждание, а то и движение к игроку. У каких-то монстров атаки чаще (по ощущениям - у Арчей время "забегов" короче прочих), кто-то больше любит потоптаться на месте И это ещё не говорим о pain state. Конечно, можно и на глазок примерно восстановить основные элементы, но всё-таки хотелось бы понять, как это на самом деле внутри сделано.
"Вещь" - даже как-то неудобно рассказывать %)
Скрытый текст:
Вообще, я довольно давно любительски мучаю нишу геймдева, активно изучая эту область и пытаясь сделать что-нибудь достойное выхода за пределы собственного компьютера. Нынешняя идея, над которой я работаю - простенькая олдскульная аркадная стрелялка, основная задумка которой - сделать "Doom на гусеницах" (отчасти в противовес грядущему "Doom на скейтборде"). Во всяком деле обучение начинается с творческого подражания образцам, и потому, вдохновившись темпом и базируясь на балансе Doom, хочу сделать нечто того же рода и духа, но с чем-нибудь бронированным, скоростным и тяжеловооружённым в качестве действующих лиц. И без псевдо-реализма, да - а то надоел он. Но, поскольку я ленивая задница сильно пропадаю на основной работе, то разработка двигается со скоростью сонной черепашки
Но в процессе разработки выяснилось, что сделать тупых и неинтересных монстров - невелика наука. Игрок появляется в "комнате" с пятью местными "зомбименами", обращёнными к нему лицом - и ему в мгновение одним слитным залпом без пауз прилетает пять хитсканов. После этого вся толпа уныло и нудно с синхронностью роботов перезаряжается, позволяя игроку безнаказанно хоть защекотать их в этот промежуток. Некрасиво. В классике было не так.
Конкретно эта проблема решилась введением крохотной произвольной задержки скорострельности - но таких моментов обнаруживается множество.
Например, как тот же зомбимен осуществляет атаку? Если я помню матчасть правильно, конечно, то он чередует выстрелы, замирание на месте, движение то в произвольном направлении, и какое-то хитрое блуждание, а то и движение к игроку. У каких-то монстров атаки чаще (по ощущениям - у Арчей время "забегов" короче прочих), кто-то больше любит потоптаться на месте И это ещё не говорим о pain state.
Конечно, можно и на глазок примерно восстановить основные элементы, но всё-таки хотелось бы понять, как это на самом деле внутри сделано.
Я не знаю как в чистой классике. Но говоря о здуме - в нём скорость атаки напрямую зависит от тиков и внутреннего счётчика(типа рандомайзер вроде бы). Т.е. прикол у того же зомбимена в атаке в том - как часто вызывается функция A_Chase. По стандарту в декорейте вот так: POSS AABBCCDD 4 A_Chase Но если настрочить вот так POSS AAAABBBBCCCCDDDD 1 A_Chase То моб будет шпарить гораздо резвее, даже без флага, который убирает "внутренний рандомайзер-счётчик". 4 больше 1, а собсна ожидание в 4 - больше чем ожидание в 1 и функция будет вызываться гораздо чаще и быстрее.
N00b2015 Первое читал - есть полезные вещи о разных аспектах, но общего представления это не даёт. Второе интересно, но это скорее про структуру данных - про поведение монстров я ничего особо почерпнуть там не смог. Нашёл ещё пару тем на Doomworld, но там тоже не то.
LEX SAFONOV Я помню мод, в котором зомбименам то ли добавляли стрейф, то ли изменяли приоритет действий в сторону более осмысленного убегания - так они становились достаточно неприятной ударной силой.
LEX SAFONOV:
POSS AAAABBBBCCCCDDDD 1 A_Chase
В Декорейте, увы, я не разбираюсь POSS - от Possesed Human, как я знаю, а что есть что ещё в строке?
Navy Есть возможность подсмотреть сорцы Doom на предмет? Грубо говоря читаешь исходники надеюсь, лучше чем я? Да и Кармак достаточно подробно всё комментирует. А сама тема достаточно интересная, продолжаем.
POSS - от Possesed Human, как я знаю, а что есть что ещё в строке?
POSS - название спрайта AAAABBBBCCCCDDDD - кадры, как видишь тут их много. Каждый кадр, как отдельный элемент, выполняется. 1 - ожидание, с которым висит на экране конкретный кадр A_Chase - функция ходьбы у моба.(Летание мобов тоже самое, только там даётся флаг полёта +FLOAT)
Navy:
Я помню мод, в котором зомбименам то ли добавляли стрейф, то ли изменяли приоритет действий в сторону более осмысленного убегания - так они становились достаточно неприятной ударной силой.
И это тоже результат работы функций. Либо функция взята с хексена(A_FastChase вроде бы), либо ему в коде написали рандомный стрейф и тоже через функцию(правда функцию не помню, но толкание актора в произвольные стороны вроде как есть).
Navy Интересны не столько набор команд здума (все эти A_Chase, A_Look и т.п.), а внутренние алгоритмы, зашитые на уровне движка. Например, как работает та же команда A_Chase: движок же каким-то образом высчитывает, что моб пойдет направо, потом налево, приближаясь к игроку. А есть еще A_FastChase - она дает более сложное поведение "ходьбы", резкие стрейфы влево и вправо и т.п. Опять же - в какой момент подается переход к стату Fire: тоже рандом присутствует, но этот рандом надо запрограммировать сначала на уровне движка. А манипуляция командами здума - это уже более высокий уровень, тупо комбинации команд и условий их выполнения. Можно неплохие алгоритмы создавать, однако от базовых ограничений, зашитых в коде движка, они не уведут.
движок же каким-то образом высчитывает, что моб пойдет направо, потом налево, приближаясь к игроку.
Если говорить точнее - моб просто идёт в сторону игрока, а повороты влево-вправо как правило рандомные, чтобы компенсировать повороты на карте и прочую лабуду.
Вот ссылка на (немного изменённый) сишный source DooM'а в месте, где описано поведение монстров. Как можно убедиться, там тоже нет особо сложных ухищрений; более того, почти у всех монстров "ИИ" примерно одинаковый. Интересующие функции можно искать через Ctrl+F (они имеют те же названия).
Есть возможность подсмотреть сорцы Doom на предмет? Грубо говоря читаешь исходники надеюсь, лучше чем я? Да и Кармак достаточно подробно всё комментирует.
Я вообще раньше думал, что исходник Doom выглядит довольно страшно по нынешним временам, но по твоему совету полез посмотреть - и не остался разочарован. Очень приятный стиль, всё написано просто и понятнее, чем у большинства моих коллег весьма доступно.
Немного по находкам Анимация
Скрытый текст:
Вообще, решения встречаются достаточно нетривиальные и спорные, из того, что я пока увидел. Например (для модеров, думаю, это не большой секрет) каждое состояние конечного автомата, регулирующего работу AI, привязано к конкретному кадру анимации. Анимация двигается вперёд, меняется кадр - происходит смена состояния на следующее из прописанных. После смены состояния вызывается действие (функция движка вроде A_Chase, дальше по тексту для краткости - просто "функция"). Ветвлений тут совсем мало, алгоритм практически линеен. Описание всего набора состояний жёстко зашито в исходнике для всего, что есть в игре, и выглядит примерно так:
где структура строки: {имя "спрайта", номер кадра (?), число тиков на кадр, {действие}, следующее состояние, misc1, misc2}
Состояние также может меняться внешними условиями (в монстра попали, крутим анимацию pain state) или внутренними функциями (например, вызванное действие заставляет монстра начать стрельбу). Некоторые источники, правда, говорят, что первично тут действие, а ему в соответствие ставятся кадры анимации. Надо будет читать исходник ещё.
Тем же путём прописана анимация оружия - например, BFG имеет 7 состояний (плюс 12 состояний для полёта заряда и его попадания в цель), каждому из которых соответствует своё действие.
Также, часть спрайтов, как я понял, имеет варианты с сущностью, повёрнутой в каждую из 8 сторон. Для каждого из акторов (интересующая сущность в движке называется так, как я понял) в движке ещё зашита структура mobjinfo_t, содержащая информацию о том, к какому из состояний (кадров анимации) требуется совершит переход при том или ином событии в жизни монстра - когда он только заспавнен, когда ему больно, когда он хочет атаковать врукопашную или на расстоянии, и так далее. Для зомбимена, например:
Сейчас такой подход практически не используется - это анимацию подчиняют машине состояний, а не наоборот. Впрочем, для тех времён, когда 4Мб RAM были солидными системными требованиями, это позволяло, наверняка, сэкономить несколько Кб на устранении лишних уровней абстракции. Интересно. Вообще, по всему этому надо будет построить нормальный такой граф/дерево состояний, чтобы вникнуть. Попробую в середине следующей недели, как рабочих дел станет поменьше.
Реализация зашитых функций - A_Chase (преследование)
Вообще, как выяснилось, на Вики есть кое-какие описания - неплохие, но фрагментарные. Исходник таких функций читается после ознакомления с ними легко и с удовольствием. Видны будто бы некоторые заигрывания с ООП, что делает код чётче. В качестве примера, распишу функцию A_Chase как одну из самых интересных. Кое-что нагло украду с Вики, в чём честно признаюсь.
Используемые понятия:
Скрытый текст:
- Сон - когда монстр появляется на карте, он "спит" (в оригинале это называется idle, но коротко и красиво это на русский не переводится). Спящий монстр стоит на месте, проигрывая первые два кадра анимации движения. У него есть конус обзора в 180 градусов, развёрнутый в направлении его первоначальной ориентации на местности. Разбудить монстра можно входом в его область обзора, звуком атаки, или непосредственно атакой в его тушку. Также, монстру можно установить флаг "засады" - такой монстр атакует игрока только при входе в зону обзора, иначе он делает вид, что продолжает спать, даже услышав его.
-Реакция - у каждого монстра есть показатель задержки его первой атаки, называемый реакцией (reactiontime в коде). Для всех монстров по умолчанию он имеет значение как минимум 8 тиков [i](м.б. больше?). Попадание в монстра сбрасывает показатель реакции в ноль. На Nightmare (и, может быть, с флагом fastmonsters) монстры реагируют сразу, реакция жёстко = 0.
- Порог(он же таймер злости) - показатель, отвечающий за то, насколько охотно монстр бросает свою цель и выбирает следующую (в коде называется просто thershold). Первая пришедшаяся по монстру атака устанавливает значение таймера равным 100 тикам (~3 сек.). Как только значение таймера доходит до нуля, монстр становится способным сменить цель на другую, если та его намеренно или ненамеренно обидела. Если цель погибла, порог сбрасывается в ноль. Арчи порога не имеют и потому охотно должны переключаться на любого другого противника, посмевшего их ранить. И правда, "архи-злюки"
- Счётчик шагов - уменьшается некоторыми действиями. Когда доходит до нуля, монстр выбирает другое направление движения.
Алгоритм A_Chase: Опущу незначительные и очевидные моменты, попытавшись оставить только самое ценное. Не все моменты также я понял - я же не настоящий сварщик, дяденька всё-таки ещё во многом учусь. Без общего графа состояний, наверное, это не так уж полезно, но, если это кому-то показалось интересным, и любопытно, как устроена какая-то конкретная функция из вшитых, спрашивайте - распишу. Да, мной тут упоминается монстр, но в качестве монстра тут может быть использована, по сути, любая сущность, хоть файербол манкубуса или даже BFG в руках игрока (не исключено, что последнее вызовет разрыв шаблона у движка).
А алгоритм таков:
Скрытый текст:
1) Уменьшаем таймеры реакции и порог.
2) У монстра есть отдельно направление движения и угол поворота сущности, которые в движке при этом самом движении вполне могут не совпадать. Если монстр повёрнут слишком далеко от направления его движения, доворачиваем его за этот конкретный тик на 90 градусов (тут зарыто много битовой магии).
3) Если у монстра нет цели, или он прицелился во что-то, что не имеет флага объекта-доступного-для-ведения-огня, то он будет искать новую цель (приоритетно - игрока). Это делается в функции P_LookForPlayers, её постараюсь расписать завтра. В случае нахождения цели A_Chase прерывается (возможно, снова будет вызвана на следующем тике, если что-либо не сменит состояния монстра), на этом тике монстр ничего не делает. Если цель найти не удалось, то монстр просто вернётся к стартовому состоянию, в котором он находился до начала действия (?).
4) Производится проверка, не атаковал ли монстр недавно (на предыдущем тике?). Судя по комментариям, монстр не может атаковать два раза подряд, не перемежая атаки другим действием. На Nightmare или при игре с fastmonsters монстр просто ничего не делает дальше на этом тике, A_Chase прерывается, в иных случаях же монстр сразу начинает двигаться в новом направлении, не прерывая преследования. Для этого дальше всем занимается на том же тике функция P_NewChaseDir, тоже интересная внутри, распишу также завтра.
5) Если монстр умеет драться врукопашную (есть состояние, соответствующее рукопашной атаке), и расстояние позволяет, то он издаёт соответствующий звук (при наличии) и переходит в состояние таковой атаки (на следующем тике (?) проигрывается анимация рукопашной, в результате чего уже будет вызвана соответствующая состоянию "дерёмся врукопашную" функция). A_Chase в этом случае прерывается.
6) Если рукопашная атака не состоялась, то умеет ли монстр стрелять? Проверка также производится по наличию состояния "стреляем" (правда, оно названо missilestate, но исследование показано, что хитсканеры тоже этим пользуются).
7) Монстр решает, произвести ли выстрел сейчас, или ещё потоптаться вокруг. Если игра идёт НЕ на Nightmage или с fastmonsters, а на счётчике шагов что-то есть - монстр отправляется побродить в ожидании выстрела. В случае с Nightmare/fastmonsters, монстр игнорирует значение счётчика.
8) Проверяется расстояние до цели. Если стрелять далеко - монстр отправляется побродить. Если расстояние устраивает - монстр переходит в состояние "стреляем", отмечает в своём состоянии, что только что стрелял. Функция A_Chase также на этом прерывается.
9) Как монстр бродит вокруг, если он бродит? Для сетевой игры, потеряв игрока из вида и доведя до нуля значение таймера порога, он отправится искать любого игрока, с кем сможет сражаться. Если же нет, то монстр шагает вперёд, в выбранном им направлении - один шаг на один тик, уменьшая соответственно счётчик шагов. Если на пути какое-то препятствие - монстр выбирает новое направление с использованием P_NewChaseDir. Если счётчик шагов ушёл за ноль - также выбираем новое направление (?). Иногда, если монстр умеет издавать звуки в состоянии бодрствования, и рандом выдал нужное значение - монстр издаёт соответствующий звук.
В общем-то, вот такое небольшое исследование одной функции и кусочка структуры движка
Правила 
Поиск
Да и Кармак достаточно подробно всё комментирует.
