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) в своих корыстных целях (что безусловно разрешается автором).

Комментарии (16)

0
Плюсанул — пятибальный и нужный пост! Да еще и с примером!
Сам сейчас ковыряю AI, правда, собираюсь использовать наборы однотипных задач (чтобы бот выбирал, скорее всего случайным образом, один из вариантов действий в данной ситуации — с целью разнообразия)
0
Тоже плюсанул,
ИИ тема обширная и интересная, лишней инфа не будет, поковыряемся…
  • FreeS
  • FreeS
0
Видимо через state машину все прошли =)). Спасибо за пост.
0
Нифига! У меня она ниразу не прижилась. Имо состояния — устаревшая техника идущая из древних принципов программирования в разных главных циклах.
0
Прижилась или нет это другой вопрос. Я говорю о том, что все через неё прошли, считай сталкивались с ней.
0
Отличная запись! Очень интересно было прочитать :)
Сам я пока тоже обходился в основном обычными state для простого поведения AI.
0
Сделай простейшую демку.

P.S. Стандарты кодирования, стандарты кодирования, стандарты кодирования! (:
+2
P.P.S. А зачем некоторые переменные имеют в своём имени $? Это какое-то хитрое колдунство или по фану? А-то код сразу дико становится похож на PHP, что немного смущает. (:
+2
Спасибо за толковую статью и примеры!

Вики похоже эта:
developer.valvesoftware.com/wiki/AI_Programming_Overview
developer.valvesoftware.com/wiki/Category:AI_Programming
  • abyss
  • abyss
0
+1 — Толковое исследование на животрепещущую тему ))
  • flazm
  • flazm
+1
интересный пост, ifolder.ru/19318209 вот накидал такой примерчик, получается забавно, но я использовал вместо функций тасков классы
  • kishi
  • kishi
0
Извиняюсь перед всеми что не мог ответить — провайдер подкачал. Во-первых спасибо за плюсы, видимо действительно полезная штука. Во-вторых, оказывается, эта схема называется schedules а не shedules)) Но это конечно сильно сути не меняет.

Как видите класс приведенный в примере можно (и нужно) апдейтить. Например если послать в исключения всего один параметр uint то получим массив с числом элементов равным значению этого параметра :D Ну и по самому методу — можно в запросе на выбор новой схемы поведения делать свитч по текущей схеме, а внутри уже руководствоваться текущим состоянием (которое можно выбрать на предыдущем шаге). Вобщем экспериментируйте!

теперь ответы:
Hagemay у меня бот тоже выбирает рандомом свое поведение. Выбор можно делать на любом этапе — ничего не мешает.
elmortem использовать стандарты типа pPointer mMember как то не хочется во флеше. А $ это действительно особое колдунство ;)
abyss спасибо за ссылки, а то я их потерял
kishi интересный вариант. Теперь нужно попробовать реализовать сложный ИИ и сразу будет понятно насколько удобнее использовать классы вместо функций. Можешь написать об этом отдельно — будет интересно почитать.

puzzlesea предлагаю тебе написать статейку про твои подходы к реализации ИИ. Думаю всем это будет интересно.
0
Вот еще отличная презентация с описанием по теме:

Инструменты создания искусственного интеллекта (презентация с Casual Connect)
  • abyss
  • abyss
+1
Стейт машина по сути дает тоже самое, если она правильно сделана :)
1) вход в состояние
2) выполнение текущего состояния
3) выход из состояния
0
А остальное (флаги, прерывания, условия) вполне себе живут в объектах.
0
@abyss спасибо за ссылку. Я думал об этой модели тоже (помню читал подобную статейку году в 2003м), но для моих целей больше подошёл заранее известный набор тасков. Тем не менее этот функционал не помешает. Он очень хорошо работает, когда набор задачек нельзя выявить изначально. Осталось придумать как соединить эти две модели, но думаю у вас не будет с этим сложностей.

@dlancer Ты прав. Окоп можно выкопать и ложкой. И я про это говорил в начале поста.
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.