Инструменты создания искусственного интеллекта
27.10.2010, автор Stormit, рубрики: ActionScriptНедавно съездил с докладом на Casual Connect. Как обычно бывает после подобных встреч, вернулся с массой впечатлений. Час общения с компетентными людьми даёт больше опыта и знаний, чем пол-года сёрфинга в сети. Поэтому в очередной раз советую всем: посещайте такие мероприятия как можно чаще и не пропустите FlashGamm, который пройдёт 4-5 декабря в Киеве (я там тоже буду).
Но сейчас не об этом. Выкладываю свою презентацию с CasualConnect Kiev 2010, а также код и небольшой пример как с ним работать.
Цель доклада - немного изменить подход к программированию ИИ персонажа. Иными словами - как задать персонажу сложное поведение во время игры, когда он выполняет большой набор действий и принимает новые решения. В качестве “умного” объекта могут быть не только бегающие в игре объекты. Это также может быть “окружающая среда” (например, уровень игры, который напускает на вас противников, когда вам легко играть или подкидывает аптечку, когда у вас мало жизней).
Традиционно алгоритм ИИ задавался через цепочку if…else…if...
Долгое время я и сам только так и делал. На событие ENTER_FRAME вызывалась громадная функция, которая проверяла что сейчас делает персонаж и принимала какие-то решения. Смена действий обычно требовала установки “флагов” (переменные типа Boolean которые в условии разрешают или запрещают что-то делать). Это нормальный способ и он имеет свои плюсы. Например, запрограммировать что-то простое так гораздо быстрее. Но если кода становится много, а поведение персонажа сложным, то вы рискуете запутаться в длинной цепочке условий. По мере роста сложности игры, может наступить момент, когда уже сложно уследить за логикой приложения (особенно если код написан не идеально, а мы-то знаем, что идеально не пишет никто 
).
Поэтому я предлагаю вам немного изменить своё отношение к программированию и начать мыслить Задачами. Однажды люди уже шагнули навстречу объектно-ориентированному программированию и возвращаться к процедурному сейчас никто не хочет. Здесь нечто похожее: мы начнём мыслить задачами и, надеюсь, программировать вам станет проще.
В этом случае подход следующий: все поведение персонажа разбивается на задачи (в программном понимании задачи - это обычные функции). Например, дровосек из игры Warcraft может: 1)стоять; 2)идти; 3)рубить дрова; 4)защищаться от противников; 5)умирать. Мы должны обеспечить переключение между ними и создать последовательность задач если нужно. На каждую из этих задач нужно написать функцию, которая будет вызываться каждый кадр, пока задача не будет выполнена. Это очень важный момент - фактически это инструмент для нелинейного развития событий. Мы не можем предсказать заранее, сколько времени нужно дровосеку чтобы дойти до дерева и нарубить дров, так как во время ходьбы может измениться рельеф и придётся искать новый путь, противник может нас отвлечь или сама цель может смещаться в пространстве. Поэтому задача-функция просто будет вызываться каждый кадр пока не выполнится.
Самое сложное здесь - обеспечить выполнение задач друг за дружкой. Тот же дровосек должен пойти к дереву, нарубить дров, вернуться назад (попутно меняя свою анимацию и скорость ходьбы). Тут нам поможет класс TaskManager (э-ге-гей!!!). Он имеет следующие функции:
- addTask() - добавить задачу в конец очереди
- addUrgentTask() - добавить задачу в начало очереди
- addInstantTask() - добавить задачу, которая выполнится всего 1 раз в конец очереди
- addUrgentInstantTask() - добавить одноразовую задачу в начало очереди
- addPause() - добавить паузу в конец очереди (в кадрах)
- removeAllTasks() - удалить все задачи из очереди
Синтаксис работы с классом TaskManager показан на слайде 6. Каждой задаче можно передавать необходимое количество параметров. Объекты TaskManager можно и нужно создавать для каждого отдельного юнита в игре. Тогда вы сможете наделить любого вашего персонажа уникальным поведением.
Принцип работы менеджера задач достаточно прост: вы создаёте объект TaskManager и задаёте ему задачи которые нужно выполнить. Менеджер САМ, внутри себя, запустит обработку события ENTER_FRAME и будет каждый кадр вызывать текущую задачу (первая в очереди) до тех пор, пока задача-функция не вернёт true. Как только вернула истину, удаляем задачу из очереди и переходим к следующей задаче, и так пока не выполнится вся очередь. Это стековый режим работы.
Существует ещё циклический режим работы. Есть 2 способа его включить: создать объект TaskManager с параметром true при старте либо изменить в любое время его свойство cycle, соответственно на true. В этом режиме отработанные задачи не удаляются, а переносятся в конец очереди. Это очень удобно, если противник должен постоянно слоняться по карте или патрулировать местность, или дровосек должен всё время бегать за дровами пока не закончится лес… Тут всё просто, если свойство cycle==true, то задача переносится в конец очереди, иначе - удаляется.
На 9-м слайде характерный пример циклического режима. Зомби выбирает случайную точку на карте и идёт к ней пока не приблизится на расстояние, меньшее чем его скорость (всего одна задача). Потом он ждёт одну секунду - я реализовал это через добавление паузы только чтобы показать как она работает, но лучше для ожидания создать отдельную задачу, которая будет проверять, нет ли рядом чего вкусненького. Попутно отрабатываются мгновенные задачи (instantTask), которые переводят графику в нужное состояние.
Очень часто бывает полезно изменить свойство в нужный момент времени. Я не стал добавлять отдельных методов для этого, так как считаю что способ показанный на 11-м слайде решает эту проблему и позволяет при этом производить необходимые проверки. На 12-м слайде видно как это работает - скорость дровосека меняется когда он несёт груз.
С этим как бы всё ясно, но это ещё не всё. Настоящий потенциал класса TaskManager раскрывается когда мы добавляем задачи на лету, то есть когда события в игре меняются. В любое время мы можем добавить задачу в начало или в конец (как одноразовую, так и исполняемую каждый кадр). Более того, если у нас циклический режим, мы можем добавлять задачи, которые выполнятся всего один раз (необязательный параметр ignoreCycle:Boolean). Принцип действия на 15-м слайде - как только зомби встречает дровосека, он добавляет себе в начало очереди новую задачу “Атаковать”. Теперь эта задача будет выполняться пока дровосек не отойдёт в мир иной и тогда зомби продолжит свой маршрут.
Тут важно понять, кто и как принимает решение выполнять новые действия. Это делают сами задачи! Например, задача_идти_в_случайную_точку кроме того что смещает персонажа, ещё и выполняет проверку на близость дровосека. И как только он оказывается рядом, добавляет атакующее действие. То есть расширяем немного сознание: задачи-функции не просто выполняют какое-то действие, но и проверяют, не нужно ли добавить новых задач в очередь.
Кому-то может будет удобнее стирать весь текущий список задач (метод removeAllTasks() ) и записывать новый. Можно создать для этого отдельные функции и вызывать их из разных мест.
Ещё раз скажу, что для запуска менеджера ничего делать не нужно. Он сам запускается как только вы добавили ему задачу (но выполняться начнёт только со следующего кадра). Если нужно его приостановить, можно использовать свойство pause (загонять в него true или false). TaskManager остановится сам когда выполнит все задачи или если вызвать метод removeAllTasks(). Ещё можно вручную перейти к следующей задачи не дожидаясь её выполнения - метод nextTask() - но это так, на всякий случай
Теперь где и как хранить задачи? У меня есть 2 варианта:
- Мы выстраиваем грамотную цепочку наследования для классов юнитов, например: BaseUnit -> StaticUnit -> DynamicUnit -> Hero или Enemy(дальше идут параллельно). Все задачи-функции тут грамотно распределены внутри этих классов - соответственно идти, стоять - будет в DynamicUnit, а рубить дрова в Hero. Общие для юнитов задачи выносим в общие для них классы.
- Хранить функции-задачи во внешних классах как статические, но тогда нужно в качестве параметра передавать и ссылку на сам объект которым можно управлять. Такие классы легко переносить из проекта в проект, но методы должны знать что умеет делать юнит.
Всё.
Эта тема очень интересна для меня, так как я использую TaskManager почти в каждом проекте (и не только в играх), поэтому открыт для предложений по улучшению или оптимизации этого класса.
Сам код класса и небольшой пример патрулирования местности в архиве ниже:
TaskManagerExample (22.1 KB, 1,498 hits)
Интересно на 56%
Почему бы не использовать в качестве задач объекты, вместо функций?
Например делаем класс Task с единственным методом execute и интерфейсом ITask и TaskManager работает с задачей как с интерфейсом, а все задачи являются наследниками Task. Таким образом можно будет типизировать задачи и использовать их для совершенно разных персонажей, даже если они не имеют общего предка, к тому же, можно будет сделать пул задач, который снимет нагрузку с GC.
Идея хорошая, но возникает вопрос о наследовании TaskManager от Sprite. Зачем ему куча лишнего функционала, только ради ENTER_FRAME?
Да, Sprite только ради ENTER_FRAME
Идея с Task хорошая и с точки зрения ООП правильная, но как быть со свойствами? Чтобы задачи были легко переносимыми они должны знать о нужных свойствах у объекта. Тоже через интерфейсы, типа эта задача может быть выполнена для объекта типа ITralivali?
Ну для ENTER_FRAME, можно передать stage или непостредственно ссылку на персонажа, если он является отображаемым объектом.
Насчет свойств, задаче все равно прийдется передавать ссылку на персонажа (например). В принципе если свойство специфичное, то можно, так сказать, объяснить задаче с каким объектом она работает (соответсвенно она потеряет универсальность). Если свойство распространенное, то тут уже можно и интерфейс применить или приводить объект к базовому объекту если он содержит нужные свойства, тут уже фантазия не ограничена ничем.
На счёт передачи ссылки нужно подумать. Хочется сделать его как можно проще в использовании. А как сильно Sprite загрузит память и процессор в сравнени с обычным Object?
А где-бы посмотреть на конвейер Потапенко? Все ссылки что я нашел ведут на несуществующий сайт.
Я сам искал и не нашёл. Когда-то давно он у меня был, но с очередной сменой компа куда-то делся.
передавать ссылку на stage, думаю стоило бы, например, чтобы указывать паузу можно было бы в секундах =)
Не вижу связи между stage и паузой в секундах.
Но я умышленно делаю паузу в кадрах, так как обычно у меня в игре всё завязано на ENTER_FRAME, да и анимация в кадрах считается. Вызвать задачу после проигрывания анимации, если пауза в секундах - не всегда точно попадает, особенно если флешка притормаживает.
Ну, это я так, к слову=)
А связь вот:
if (pauseCount >= t * this._stage.frameRate)
А что касается оптимизации, могу только предложить заменить tasks.push на tasks[tasks.length]. Где-то видел, что работает быстрее второй способ)
Очень интересные идеи, спасибо!!!
Это как раз то что мне нужно!!!) Спасибо огромнейшее!!!
Интересный и хошо иллюстрированный подход. Спасибо!
Хорошая статья! ИИ во флеше не редкая вещь, но прежде чем найти что-то стоящее успеешь уже бросить затею. На мой взгляд пример с лесорубами и зомби как нельзя кстати подходит для игр с “живущим” миром. Так держать!
нашел у себя конвеер Потапенко
http://dl.dropbox.com/u/1036911/potapenko.zip
супер статья =)
П.С.
на 4 слайде грам. ошибка.
“откуда ноги рАстут”
Stormit,
вопрос кстати, как срабатывает отслеживание самообороны чуваков? (15 слайд)
догадываюсь что, добавляешь в начало очереди чувака функцию “перейти на кадр атаки”.
но как ты определяешь кто противник?
М-да, наконец-то что то появилось, после долгого ожидания, но качественное. Не зря столько времени ушло
.
Да, зомби переводится в анимацию атаки и запускается задача “бить” которая каждый раз снимает немного здоровья у противника. Сами противники определяются легко: есть 2 массива, для зомби и лесорубов. Зомби пока идёт вызывает функцию checkForMan(), где проверяет есть ли рядом лесоруб. Если есть, на чинает его атаковать и, чтобы было меньше проверок, вызывает у лесоруба метод “защищайся” (он тоже переводит его в анимацию атаки и каждый кадр отнимает здоровье у противника). Просто проверку выполняет только зомби.
А насчёт ошибки, кто его знает как правильно? Вот есть имя Ростислав (Рости славным) - пишется через О. Так что может я и прав…
Stormit, Помоги!
Я знаю только основы actionscript, и никогда не слышал о TaskManager, скажи может я чего то не понимаю, чтоб работать с TaskManager, что для этого нужно AS2 или AS3? какие то дополнительные файлы или ещё что нибудь, так как у меня
такие функции как addTask() flash’ем не воспринимаются!
Это AS3.
А флеш подсвечивает только свои, встроенные классы. Именно поэтому опытные разработчики пишут AS3 в сторонних редакторах. Мне нравится FlashDevelop. Скачать его можно тут.
Спасибо
жаль as3 я не знаю и изучать пока не планирую, надо вначале as2 изучить хорошо
круто но не совсем понятно в разборе кода
Stormit, вопрос не по теме: Мне нужно сделать программу(во flash на AS1&2 ), в которой есть текстовое поле и если туда ввести “4*(6+3)”, то он выведет ответ “36″, то есть чтобы он воспринимал текст как функцию, или что-то типа того.
Так сделать можно?
Можно, БОГДАН. Загоняешь в переменную текст этого поля, например var str:String=t.text, теперь ты можешь обратиться к любому символу как str[0], str[1] и т.д. В цикле проверяешь знаки… и т.д.
Прочел с год назад весь сайт, от и до - спасибо за посты. Потом был перерыв и вот Гуру вернулся!
К делу.
Отличный шаблонный подход к реализации ИИ по задачам (шаблонам)
Но дам один совет по оптимизации:
Видимо AS3 еще нов и штампы AS2 дают о себе знать. Зачем вешать все на ЕнтерФрейм?
В презентации прокликать 20-30 раз Add Zombi и ужаснуться ушедшему в 100% процессору и еще ползающей в браузере мышь
Есть же прерывания, а не только ЕнтерФрейм.
Делаем свои прерывания и вешаем слушателя. Стукнулся зомби с дровосеком, тогда и прерывание, которое это обработает.
При этом вечный цикл нужен. Но не каждый же кадр, а хоть раз в 1-2 сек. Вешаем на таймер. Можно потом протестить на той же флашке и увидеть, как она обрабатывает колво зомбей, приводящие к завису в текущей реализации.
Так же согласен с наследованием от Спрайта, можно без него, лучше от EventDispatcher
он как раз пустой и прерывания умеет ловить.
Но для удобства можно и от спрайта, по сути тут свои плюсы и по своему это даже вернее.
Это визуальный объект со своим поведением и контентом, но если он сам и есть объект, а не просто так вызван сбоку. Так что, тоже верный подход.
А разве получится избежать тормозов если использовать не ENTER_FRAME, а таймер?
Ведь прерывание на столкновение не произойдёт если само столкновение не проверить. И смещаться персонажи должны постоянно. Если уж на то пошло, то можно проверять столкновения каждый третий-пятый кадр. Наверное это личное предпочтение как делать - энтерфреймом или таймером, но мне с первым работать удобнее.
ENTER_FRAME - сердце флеш-приложения, куда ж без него
Если в ЕнтерФрей делать проверку не каждую итерацию, а делить на число кадров в сек или половину от них. То все будет гут.
При этом, еще добавить ранд() в это дело, чтоб 100 юнитов “думали” не в одну секунду, а размазано во времени.
Что быстрее таймер или кадры? Нужно тестить. Я как-то делал для себя и свой таймер на кадрах, раз уже был обработчик повешен.
Но скорее всего таймер все же быстрее (причем в разы).
Дело в том, что ресурс жрется на саму обработку прерывания, даже пустого, а таймер его плодит сильно реже. Но если говорить о случае, что прерывание нужно все равно (на движение), то тут выигрыша нет, достаточно сделать проверку не каждый тик.
В общем, тест все расставит по местам - простой тест, на 100 зобмях.
До и после.
Спасибо большое за ваш великолепный блог… давно его нашел и тогда загорелся флешем. Раньше было сложно многое понять из того что написано) теперь же довольно таки просто все… Какраз с неделю назад думал о том что не знаю как делается ИИ и залез сюда) а тут уже и статейка… Да и вправду при 100+ юнитов на сцене проц топится. как-то облегчить мыслительный процесс возможно???
Тормоза при 100 зомбях только из-за того, что процессору приходится отрисовывать почти всю сцену каждый кадр (так как зомби векторные и тень полупрозрачная). Расчёт ИИ на эти тормоза никак не влияет (влияет на несколько порядков меньше чем графика). Так что не заморачивайтесь
Да, я тоже об этом подумал, задача как уменьшить нагрузку 100 зомби, во время отображения на экране… и вопрос, как сильно грузит проц, ротатион?
Уменьшить нагрузку можно так: Картинки обгоняют вектор
но увеличится вес, а может как то в оперативку все это засунуть)
Сейчас век анлима… Так что вес не играет уже такой большой роли… Сейчас главное производительность, ибо не у каждого стоят 4х-яйцевые процы. Так что правильно, растр хелп аз!
Хорошая статья, но хотелось бы поподробнее осветить вопрос, как TaskManager взаимодействует с объектом ? как выстраивается очередь ? можно пример в студию ?
Если не хочется наследоваться от Sprite, но нужен ENTER_FRAME, можно сделать статический спрайт и на него подписываться.
static var mc:Sprite = new Sprite();
…
protected function start():void
{
…
mc.addEventListener(Event.ENTER_FRAME, step, false, 0, true);
…
}
как у вас устроена функция отвечающая за то что зомби “видит” дровосека и начинает его бить?
В общем, тест все расставит по местам - простой тест, на 100 зобмях.
Любопытно, что оказалось быстрее, ЕнтерФрей или таймер? Или статический спрайт? Или пойти самому всё сделать…
Здоровский сайт! Уникальный по передаче информации! Очень комфортно читаются статьи. Автор молодец=) Сколько лет пытаюсь взяться за АС3 все никак основательно не могу сесть, читал много статей, но ваши самые дружеские!
Замечание по коду в TaskManager.as:
protected function step(e:Event):void {
var curTask:Object = tasks[0] as Object;
if(curTask) {
result = (curTask.func as Function).apply(this, curTask.params);
//Пусть ваша текущая задача одноразовая (curTask.isInstant==true)
//и внутри curTask.func вы очистили очередь команд и добавили новые (юнит
//резко поменял поведение)
//Тогда следующее условие выполнено:
if(curTask.isInstant || result) {
// и в этом месте tasks[0] уже новая задача, которую еще не трогали
// в результате выполнения nextTask она будет потеряна
nextTask(curTask.ignoreCycle);
// я выкрутился вставив дополнительное условие if (curTask==tasks[0])
}
} …
Не уверен, что предыдущее решение хорошее. В качестве альтернативы можно добавить addPause(1); в конец функции removeAllTasks().
Благодарю за найденный баг.
По-моему решение вполне нормальное.
Обновил архив.
Спасибо за блог, содержание статей не всегда показывает оптимизированный код, но вот от чего я просто фанатею, так это от графики в примерах, вот действительно сила художника, такое впечатление что это готовые игры. Крута!
Есть над чем подумать
Когда я делал ИИ дял игры Раш (которую так и не купили увы) там был тихий ужас. Десяток булевых переменных, куча ИФов и ЭЛСЕв. Хотя в конечном итоге конечно работало. Да так что сам не мог вынести своих же ботов иногда )))))
Спасибо за идею, будем пробовать.
Кстати не задумываешься над созданием какого-нибудь 2.5д движка, но не совсем изометрического? Я вот себе уже голову сломал чтобы придумать как сделать пошустрее )))
Сразу видно, что автор поста не программист. Ну как можно сделать, чтобы уровень был объектом игры?! может быть у вас еще и меню отвечает за управление игровым объектом
Я больше программист чем художник. Под уровнем я подразумеваю основной класс, который отвечает за логику в игре. Это такой же игровой объект (экземпляр класса), только абстрактный и задачи у него другие: кроме перемещения персонажей и обеспечения их взаимодействия, могут быть и другие задачи, например, добавлять расходники или противников на сцену. Это уже вопросы гейм-дизайна, но такой класс тоже может выступить в роли носителя AI
Это просто чудо а не сайт! Спасибо! Побольше бы таких в рунете
Вау! Круто! Суперская темпка про AI!
Вопрос частично не в тему: если создовать банер, где два мувика пошагово перемещаются, надо ли, и если да, то что надо изменить в коде AI?
Ну и совсем не в тему: как сделать пошаговый сброс хода? типа сделал 1 действие, переход хода?
function потрясающийСайт ():void {
честьИхвала = честьИхвала + 1;
}
А я проверила.
Timer быстрее + можно настроить скорость.
Нет потери в работоспособности (правда, я графику оптимизировала, сжимала и кодировала =))
Спасибо