Shedule-based AI

Не нашёл подходящего блога под этот пост, так что буду писать здесь (код всё равно прилагается).

Рано или поздно все сталкиваются с проблемой написания интеллекта. К этому вопросу есть много подходов, например на заре своей деятельности я использовал STATE машину (надеюсь называется она так). Принцип простой – у организма есть состояния, согласно которым мы и выбираем действия (много много if-ов или в результате эволюции один switch и много if-ов внутри case-ов :D ) Можно конечно еще проще, но когда дело доходит до комплексным организмов эти подходы начинают давать сбои. Проще говоря if-ов попросту не хватает. Собственно наступив на эти грабли я и полез рыть интернет в поисках каких-либо приемлемых способов написания интеллекта…и наткнулся на вики от source движка (half-life).

Сейчас я почему-то не могу найти ту самую статью, так что буду объяснять своими словами – сразу оговорюсь – не претендую на истину в высшей инстанции и на чистоту/оптимальность кода, просто хотел поделиться с комрадами интересной вроде бы штукой.

Итак база описываемого интеллекта состоит из:

а) Shedules
б) Interrupts
в) Conditions
г) Tasks
д) States (знакомое?)

Как видите всё довольно просто. А теперь по порядку. Точнее в обратном порядке:

States – это мы знаем. Текущее состояние объекта. Например я_бегу, или я_ловлю_противника, или я_нажимаю_на_кнопку. Тут вроде все понятно.
Tasks – это то чем занят организм во время выполнения выбранного Shedule. Один task это одна функция, которая выполняет строго определенные локальные задачи. Пример таска – запустить_анимацию_на_кадр_три. Еще пример – выбрать_противника. Еще – гнаться_за_противником. Другими словами таски это единицы массива локальных задач выполняемых организмом для решения текущей глобальной задачи (Shedule). Причем естественно таски можно перекидывать из одной задачи в другую (например проигрывание определенной анимации).

Conditions – это суждения организма об окружающем мире. Например – я_вижу_противника, или – я_могу_схватить_противника_за_ногу, или я_падаю.

Interrupts – это набор Conditions которые ВСЕГДА прерывают текущую глобальную задачу. Например задача схватить_противника_за_ногу может легко прерываться суждением – противник_не_в_поле_зрения.

Shedules – это последовательный набор тасков и произвольный набор интерраптов. Глобальная задача, которую объекту предстоит выполнить с начала и до конца, ЕСЛИ вдруг не наступит один из интерраптов.

Да да – всё очень просто. Но зато насколько логичнее и нагляднее выглядит код с использованием этого ИИ!

Итак давайте сразу же разберем простейший пример – у нас есть некий организм который может идти если ходится, анимировать падение если падается и гнаться за врагом если видит врага.

Кондишены будут такими: мне_ходится, мне_падается, мне_виднеется_враг.
Шедули:
— падать (интеррапты: мне_ходится, таски: анимировать_падение, я_падать);
— ходить (интеррапты: мне_падается, мне_виднеется_враг, таски: анимировать_ходить, я_ходить);
— гнаться(интеррапты: мне_падается, таски: анимировать_злобно_бегать, злобно_бегать);

Согласитесь код уже несёт некий смысл.

Далее всё довольно просто. Сколько то раз в секунду (на Ваше усмотрение) организм должен подумать (Think). Думает он функцией GenerateConditions, которая в нашем случае должна определить находится ли организм на приемлемой для хождения поверхности, падает ли организм и видит ли организм врага. В ходе этих проверок организму назначаются соответствующие кондишены в массив Conditions.

Далее мы проверяем текущий шедуль на предмет его завершенности (в т.ч. на основе выбранных кондишенов) Shedule.isDone(Conditions). [ шедуль может быть завершен и естественным образом (все таски выполнены)]. Если шедуль завершен – мы выбираем новый. SelectNewShedule(). Дальше начинается самое интересное – мы знаем какие кондишены могли завершить выполнение шедули, а так же знаем State (не забыли?). На основе этой информации мы и выбираем дальнейший шедуль. Кстати у valve стейты использовались и на этапе генерации решений – это тоже имеет место быть. Тут уже Вам решать где и что использовать (специфика диктует).

Возвращаясь к нашему примеру: свитч по стейтам – дальше:
кейс ходим: если есть кондишен мне_падается – выбираем шедуль «падать» и стейт «падаем»; если есть кондишен мне_виднеетсся_враг – выбираем шедуль «гнаться» и стейт «гонимся»;
кейс падаем: выбираем шедуль «ходить» и стейт «ходим» (других вариантов нет)
кейс гонимся: выбираем шедуль «падать» и стейт «падаем» (тоже вариантов нет)

Пока кодили пришли к выводу что злобный организм остановится от погони только если упадет. Чтобы это исправить нужно добавить дополнительный кондишен – «мне_врага_не_видно» или «горизонт_чист» и добавить это событие в интеррапты погони и в стейт погони.

Таски я думаю всем понятны. Все умеют переводить спрайт на нужный кадр. Специфические штуки (например положение врага) можно находить на этапе генерации кондишенов, а можно и внутри тасков. Например отдельным таском будет поиск пути к врагу, затем путь до врага с подсчетом расстояния. Фантазировать уже можно бесконечно – всё поддается последовательному кодингу :D И совсем забыл – Shedule.Run() выполняется каждый кадр. В отличие от Think которое может быть например раскидано по кадрам в зависимости от загруженности уровня организмами (вариант тюнинга приложения). Кстати явные и неоспоримые преимущества этого подхода над обычными стейтами проявляются в работе с довольно комплексными организмами (о чем я уже пожалуй и говорил). В том числе на шедулях можно сделать и игрока (делаю сейчас и не жалею). В самом деле – чем игрок отличается от любого другого организма на уровне?…

Прилагаю к этому манускрипту исходный код на as3. Он состоит из готовых классов шедулей и кондишенов и из файла примера использования этих классов (base_actor) в своих корыстных целях (что безусловно разрешается автором).