
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) в своих корыстных целях (что безусловно разрешается автором).
Рано или поздно все сталкиваются с проблемой написания интеллекта. К этому вопросу есть много подходов, например на заре своей деятельности я использовал 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) в своих корыстных целях (что безусловно разрешается автором).
- +35
- RaymondGames
Комментарии (16)
Сам сейчас ковыряю AI, правда, собираюсь использовать наборы однотипных задач (чтобы бот выбирал, скорее всего случайным образом, один из вариантов действий в данной ситуации — с целью разнообразия)
ИИ тема обширная и интересная, лишней инфа не будет, поковыряемся…
Сам я пока тоже обходился в основном обычными state для простого поведения AI.
P.S. Стандарты кодирования, стандарты кодирования, стандарты кодирования! (:
Вики похоже эта:
developer.valvesoftware.com/wiki/AI_Programming_Overview
developer.valvesoftware.com/wiki/Category:AI_Programming
Как видите класс приведенный в примере можно (и нужно) апдейтить. Например если послать в исключения всего один параметр uint то получим массив с числом элементов равным значению этого параметра :D Ну и по самому методу — можно в запросе на выбор новой схемы поведения делать свитч по текущей схеме, а внутри уже руководствоваться текущим состоянием (которое можно выбрать на предыдущем шаге). Вобщем экспериментируйте!
теперь ответы:
Hagemay у меня бот тоже выбирает рандомом свое поведение. Выбор можно делать на любом этапе — ничего не мешает.
elmortem использовать стандарты типа pPointer mMember как то не хочется во флеше. А $ это действительно особое колдунство ;)
abyss спасибо за ссылки, а то я их потерял
kishi интересный вариант. Теперь нужно попробовать реализовать сложный ИИ и сразу будет понятно насколько удобнее использовать классы вместо функций. Можешь написать об этом отдельно — будет интересно почитать.
puzzlesea предлагаю тебе написать статейку про твои подходы к реализации ИИ. Думаю всем это будет интересно.
Инструменты создания искусственного интеллекта (презентация с Casual Connect)
1) вход в состояние
2) выполнение текущего состояния
3) выход из состояния
@dlancer Ты прав. Окоп можно выкопать и ложкой. И я про это говорил в начале поста.