?

Log in

No account? Create an account

Разработка AI в стратегических компьютерных играх II - Не кинокритик. Не палеонтолог.

авг. 11, 2007

10:22 am - Разработка AI в стратегических компьютерных играх II

Previous Entry Поделиться Next Entry

Продолжение, начало здесь.

Пара комментариев к предыдущей части.

Во-первых, ку. В абстрактных "мы", упоминаемых в истории "Silent Storm", я составляю довольно маленький процент. Основную работу над AI провел Игорь Фаломкин (не знаю, есть ли у него ЖЖ), ну а автор многих концепций - учитель и джедай _foreseer. Также ку хочется выразить bandures'у, который провел основную работу над AI в "Ночном Дозоре", подтвердив многие предположения.

Во-вторых, комментарий по поводу "зависаний AI", аналога которым, якобы, нет в RTS. На самом деле аналог такой ситуации существует, и, более того, она возможна даже и не в играх. Именно, если действие, которое выбрано как наилучшее, на деле оказывается невыполнимым, и это выясняется мгновенно, то в "наивной" реализации то же самое действие сразу выбирается повторно. Это приводит либо к зависанию физическому (вечный цикл, переполнение стека и тп), либо, если код написан чуть безопаснее - к логическому (AI просто ничего не делает до тех пор, пока ситуация не изменится).

Способ избежать этого, который мы с bandures'ом изобрели для "Дозора", состоит в том, что выбирается не одно возможное действие, а сразу несколько, и им назначаются приоритеты. После чего, даже если вмешается грубая реальность (например, самое высокоприоритетное действие окажется запрещенным), в запасе останутся другие варианты. Подробнее я писал об этом здесь.

Анализ архитектурных ошибок

Допустим, мы можем классифицировать основные проблемы. Но почему они возникают вновь и вновь? Конечно, можно объяснить их банальным недостатком людей, времени или денег на разработку и тестирование AI (и игры в целом). Но это неконструктивная позиция, т.к. ресурсов не хватает никогда и никому. Вместо этого можно выявить явные архитектурные ошибки и ошибки, связанные с неверно организованной технологической цепочкой. Сначала поговорим об архитектурных ошибках и о том, как они влияют на качество итогового продукта.

1. Отношение между «состоянием», «реакцией», «логикой» etc. и игровым персонажем выбирается ошибочно.Например, в Silent Storm и в Blitzkrieg подобные сущности относились друг к другу как «один к одному», что кажется естественным: в каждый момент времени между персонажем (боевой единицей) и его AI-состоянием («логикой», «реакцией») существует взаимно-однозначное соответствие. На самом деле следует с самого начала реализовать это отношение как «многие к одному» (то есть, одна и та же логика или реакция может управлять несколькими персонажами). Тогда не может возникнуть проблем с реализацией совместных действий. 2007: На самом деле, с учетом того, что логики иерархические - «многие к многим». В Нивале игры делались под РС, и память управлялась автоматически, при помощи счетчиков ссылок. В проектах, в которых память управляется вручную, корректно реализовать отношение «многие к многим» - та еще задача. Хотя оно того стоит, но считайте, что я вас предупредил.

2. Неверно организуется иерархия «планов». Если назвать реакцию, логику и отдельное действие одним словом «план», то мы увидим, что в нашем случае дерево планов, управляющее персонажами, сначала имело глубину 0, затем глубину 1 и в конце разработки глубину 2. Естественно продолжить эту тенденцию: вообще не разделять реакции, логики и действия, и сделать структуру дерева планов гибкой. То есть, любой план может передать управление любому «младшему» плану, причем количество уровней вложенности заранее не ограничивается. Действительно, в адд-оне Silent Storm: Sentinels мы столкнулись с тем, что двух уровней вложенности уже не хватает для описания некоторых вариантов поведения.

Два предыдущих примера в той или иной степени специфичны для наших проектов. Однако можно найти и третью, более глобальную ошибку, которую допускают практически все, и которая всегда приводит к серьезным потерям качества и усложнению разработки. Вот она:

3. При создании AI описываются его действия, а не его задачи. А все потому, что к такому программированию мы привыкли. Почти любой язык программирования и почти любая среда разработки предназначены для описания детерминированных последовательностей действий. (2007: ну это я, конечно, черезчур мощно обобщил)

Между тем, разработку AI гораздо правильнее представлять себе как описание последовательностей задач и подзадач. Пока что различие между этими двумя методиками может быть для Вас неясным (вплоть до «какая разница, какими словами это называть, все равно это одно и то же программирование!»). Тем не менее, если пользоваться идеологией «описывай задачи», можно построить AI, знающий и учитывающий смысл, который вкладывается в те или иные задуманные Вами действия.

Нам хочется, чтобы AI следил за возникновением непредвиденных ситуаций (т.е. таких, возможность которых программист не учел при разработке плана), и мог адекватно на них реагировать, не совершать бессмысленных действий, и не повторять одну и ту же ошибку два раза подряд. Значит, нужен способ как-то описать, что такое «бессмысленное действие», что такое «непредвиденная ситуация», и что такое «ошибка».

Все эти понятия - производные от понятия «задача». Вот пример типичной задачи, и связанных с ее выполнением бессмысленных действий, ошибок и непредвиденных ситуаций.

Задача: сделай А, чтобы получить X. Когда условие Х выполняется, сделай В, чтобы получить Y
Бессмысленное действие: X или даже Y уже и так выполняется, но мы все-таки делаем А
Ошибка, непредвиденная ситуация: Действия А выполнены, но X не наступило; или: действия А выполнены, X наступило, мы выполняем B, но в этот момент X вновь перестает выполняться
В коде обычно пишут: Сделай А, затем сделай В.

Легко видеть, что такое описание естественным образом приводит и к бессмысленным действиям, и к ошибкам, и к беспомощности в непредвиденных ситуациях.

На самом деле, конечно, не все настолько плохо. Код, написанный подобным образом, затем тестируется, и в соответствующем поведении обнаруживаются ошибки. После их исправления код начинает выглядеть, например, так:

Если не (часть условия Х), делай А. Затем делай В.

Код опять тестируется, и через неделю-две случайно находятся новые ошибки в поведении. После их исправления код начинает выглядеть, например, так:

Если не (часть условия Х и еще одна часть условия Х), делай А. Затем делай В до тех пор, пока не (часть условия Y).

Итоговый код после нескольких таких итераций работает «почти всегда». Что в таком процессе плохого? Многое:

Как надо правильно описывать задачи в коде, мы и поговорим подробнее при разборе "идеальной архитектуры", к которому сейчас приступим.

Описание "идеальной" архитектуры


Слово "идеальная", конечно, является сильным преувеличением (2007: как и слово "архитектура" - это, скорее, набор принципов, на основе которых она должна быть построена). Все же в ней собраны идеи, проверенные на практике, и учтены многие известные ошибки.

Основные принципы.

А вот они же, подробнее:

Скрытие источников управления. Различия между человеком, удаленным входом (то есть, командами, приходящими от человека, играющего за другим компьютером), скриптом и AI должны быть локализованы на уровне небольшого общего интерфейса. Например, на уровне абстрактного класса "командир", или общей системы передачи команд. Команды пользователей, команды скрипта и команды AI должны передаваться в одинаковом формате, т.е. вид одной и той же команды не должен зависеть от того, кто ее отдает - input (игрок за данным компьютером), сеть (удаленный игрок), AI, скрипт. Так и было сделано в Silent Storm, и мы об этом ни разу не пожалели.

Понадобится древовидная структура «планов», каждый из которых относится к игровым персонажам по принципу «один к многим». Под «планом» здесь понимается некая сущность, обобщающая понятия «тактика», «стратегия», «тактический прием».

По ходу выполнения каждый план может выполнить одно или несколько из следующих действий:
- отдавать команды управляемым боевым единицам
- создать план-потомок, управляющий частью "подопечных" боевых единиц
- завершиться (вместе со всеми своими планами-потомками) и сообщить плану-предку результат: успешное или неуспешное завершение (2007: и если неуспешное, то с каким именно "кодом возврата")
- обрабатывать текущие изменения ситуации. Для этого, как правило, каждый план, получивший управление, по очереди передает его всем потомкам. На каждом такте управление вначале получает главный план, управляющий всеми войсками ("командир"). Затем управление по очереди переходит к каждому его потомку, и так по всему дереву. План может иметь нескольких «потомков», каждый из которых управляет работой части персонажей, управляемых планом-родителем. Эти части не пересекаются. Таким образом, каждому персонажу соответствует цепочка вложенных планов. Например, «сейчас я следую по пути Х (это план нижнего уровня, управляющий данным персонажем), потому что с другими персонажами еду окружать точку У (план среднего уровня, управляющий группой), потому что наша стратегия в данной игровой сессии - отрезАть противника от источников ресурсов (план высокого уровня, управляющий всеми)».
(2007: Изложенный способ при большом количестве персонажей, очевидно, вычислительно очень затратен: на каждый логический такт мы проходим по всей логике. Можно, пожертвовав простотой, организовать обработку изменений ситуации гораздо более эффективным образом. Я, если будет интересно, расскажу об этом отдельно)

Примерами планов, в порядке повышения уровня, являются:

При разработке конкретного плана сначала следует сформулировать ассоциированную логическую цепочку, а затем именно ее реализовать в коде.

Ассоциированная логическая цепочка – это некое промежуточное звено между идеей и кодом. Она все еще выражена человеческим языком (а потому понятна и программистам, и гейм-дизайнерам, и тестерам), но уже гораздо более подробна.

Вот достаточно простой пример. Предположим, мы хотим реализовать новый тактический прием - рейд, т.е. быстрое уничтожение противника, находящегося далеко от своих основных сил. Для этого первым делом (до начала всякого программирования) мы формулируем логическую цепочку - то есть, последовательность действий или дочерних планов, которые мы хотим реализовать, и условий, которые мы тем самым хотим выполнить. Для тактического приема «рейд» эта цепочка будет выглядеть примерно так:

«Управляемые войска едут по направлению к небольшой группе противников. Реализуем план «погоня». Все это время длина пути между управляемыми войсками и группой противников постепенно уменьшается, наши силы не уменьшаются, а размер группы противников не увеличивается. Не далее, чем через время Х, которое можно оценить заранее, управляемые войска вступают в бой с этой группой. Реализуем план «быстрый бой». Поскольку группа противника невелика по сравнению с управляемыми войсками, не более, чем через время Y, которое можно оценить заранее, группа противника уничтожена. Управляемые войска отступают на исходные позиции, так как они более защищенные по сравнению с текущими».

Несмотря на то, что она получилась столь громоздкой, видно, что она все еще неполная - ее можно расширить и уточнить. То, что итог будет еще более монструозным, нормально. Цепочка - промежуточное звено между замыслом и программным кодом, и ничего удивительного, что она, хоть и не достигает размеров второго, все же намного длиннее первого.

После того, как цепочка сформулирована, можно увидеть, что данный план может провалиться просто на любом своем пункте. Количество разнообразных непредвиденных обстоятельств, которые могут нарушить любое из условий, огромно. Возьмем, например, утверждение «все это время длина пути между управляемыми войсками и группой противников постепенно уменьшается, наши силы не уменьшаются, а размер группы противников не увеличивается». Мы могли ошибиться в оценках скорости; наши силы могли застрять на узком участке (например, на мосту, что встречается, по-моему, в любой RTS, где есть мосты); они могут подвергнуться бомбардировке, встретить на своем пути минное поле, попасть в непредвиденную стычку. Может помешать использование врагом какой-то военной хитрости (например, засады), скриптово-сценарное событие, использование «жульничества» со стороны игрока, и т.д. и т.п. Что же делать, ведь мы едва ли можем безошибочно учесть все заранее?

Ответ простой: реализовывать не только те части цепочки, которые говорят о действиях, но и те, которые говорят о целях и предположениях. В частности, мы должны описывать проверки тех условий, о которых в ней идет речь. Если условие, которое должно выполняться в данный момент, на самом деле не выполняется (например, по прошествии времени Х, управляемые войска так и не вступили в бой с противником), то план и все поддерево его планов-потомков сразу должны завершиться с результатом «провален», так как дальнейшее выполнение действий практически со 100% вероятностью будет бессмысленным и покажется пользователю глупым.

С другой стороны, если мы знаем цель неких действий, то прежде чем приступить к их выполнению, всегда можно проверить, а не была ли она уже достигнута сама собой? Если это так, можно (и нужно) сразу переходить к следующему условию.
Наконец, для всего плана целиком также можно сформулировать некоторые критические условия, по достижении которых он должен немедленно завершиться с результатом «провал». Например, «с момента начала выполнения плана прошло слишком много времени, значит, что-то пошло не так». Для плана «рейд» к нему можно добавить такое условие критического провала: «управляемая группа стала слабее преследуемой».

Нам часто понадобятся конструкции, реализующие логику «Пока не Х и не выполнены условия критического провала и возможно Y или Z, делай Y или Z. Если не Х, и ни Y, ни Z невозможны, то завершись с результатом «провал»». К сожалению, при реализации таких конструкций на С++ получаются существенно более громоздкий код, чем это можно было бы предположить исходя из того, как просто они формулируются на «естественном» языке. Если у вас так произойдет, не пугайтесь - увы, так и должно быть, С++ действительно для них не очень хорошо подходит.

Обработка нарушений логической цепочки («провала плана-потомка») внутри плана-родителя может вестись по крайней мере двумя способами:
1) если в коде AI существует только один тип плана, реализующий требуемый тактический прием, и этот план провалился, то и план верхнего уровня также считается проваленным.
2) если в коде AI существует несколько классов планов, реализующих требуемый тактический прием (например, «атаковать» часто можно многими способами), и экземпляр одного из этих классов провалился, то создается план следующего подходящего класса. Если провалились все - план верхнего уровня также считается проваленным.
Что происходит, если все планы, управляющие данной боевой единицей, провалены (то есть, остался только план самого верхнего уровня, который не может придумать для нее задачи)?

Для действий в этом случае нам понадобится некое «минимальное поведение». Какой бы сложной ни была ваша игра, для нее всегда найдется относительно простое поведение, которое не выглядит слишком глупо. Оно не будет использовать сложные тактические приемы, изощренные игровые возможности. Оно построено на нескольких очевидных правилах. Это поведение - тоже важный базовый элемент архитектуры. Именно оно и выполняется до тех пор, пока снова не станет возможно выполнение какого-либо более сложного и специализированного плана. Замечу, что, несмотря на простоту минимального поведения, его не просто надо тестировать, это надо делать в первую очередь. Именно от него в немалой степени зависит впечатление игрока от AI.
Вышеизложенного уже достаточно, чтобы при качественной реализациии избежать проблем "повторения глупых действий" и "применения логики в неподходящей ситуации".
Следующая часть архитектуры задумана для упрощения правильного «следования сценарию», а также для увеличения эффективности тестирования AI. Ее можно описать так:

Любой тип планов можно полностью запретить. Также любой план можно директивно установить (для заданной группы войск). Данная возможность доступна из скрипта, из настроек игровой карты и унифицирована для всех типов планов. Если план запрещен, то гарантируется, что его никто в данной группе не может использовать. Если же план установлен для некоторой группы, то на все время его действия она гарантированно выходит из-под управления всех остальных планов.

Если в Вашей игре эта возможность реализована, то поддержка сценария и требуемой скриптом логики поведения становится на порядки более простой. Кроме того, у Вас сразу появляется простой способ тестирования любой конкретной логики, включая и «минимальное поведение», что резко увеличивает скорость выявления ошибок.

Наконец, совсем вкратце, последняя идея: три вида обработки провала плана (не на уровне плана-родителя, где обработка может быть самой разной, а на глобальном уровне). Если план реализует то, что мы бы назвали «стратегией», то его провал запрещает планы этого класса вплоть до конца игровой сессии. Если план реализует то, что мы бы назвали «тактическим приемом», то вероятность его применения должна снизиться вплоть до конца игровой сессии. Если же план реализует какое-то базовое поведение (например, «атаковать»), то провал игнорируется. (2007: С тех пор так ни разу и не удалось проверить эту идею, так что, вполне возможно, она, хоть и выглядит логично, по какой-то причине "не работает")

Что мы теряем

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

Используя вышеописанные идеи, мы приобретаем контроль над поведением в тех ситуациях, которые не смогли предвидеть, даем дизайнерам миссий полный и прозрачный контроль над AI, и кардинально увеличиваем скорость и удобство исправления ошибок. Как ни странно, при этом мы не теряем ничего, кроме накладных расходов на создание такой системы. Но надо понимать: для того, чтобы затраченное время стоило получаемых преимуществ, игра должна быть большой, сложной, а для AI должны быть доступны разнообразные возможности. И надо понимать, что в таких условиях его реализация AI (как, впрочем, и всей игры) окажется довольно долгой.

2007: В исходном тексте дальше шли какие-то оценки масштаба проекта, для которого описанная система "окупится". Сейчас они кажутся мне абсурдно завышенными. Думаю, вообще в любой RTS или TBS при правильной реализации она "окупается" только за счет снижения времени bugfix'ов, даже если не считать сопутствующего повышения качества.

Tags: ,

Comments:

[User Picture]
From:vfocus
Date:Август 11, 2007 02:39 pm
(Link)
Любопытно. Есть несколько вопросов:
1. Каким способом AI выделяет группы юнитов на карте?
Т.е. как я понимаю, в принципе, для каждого отдельного кадра, достаточно легко выделить области "сгущения" юнитов.
Но во-первых, нужно достаточно четко выделить границы группы. Причем, в динамике, эти границы
меняются (юниты приезжают, уезжают, и т.д.), а группа остается.
И во-вторых, их надо классифицировать: опасны/ не опасны, кто они могут делать, и пр.

2. А как насчет DSL для AI? Мне кажется, это очень хороший подход. Как раз, в нем можно будет описывать планы,
правила поведения, и прочее.

3. Вы делали "вязкость AI"? Т.е. чтобы AI был бы ленивым, и не рыпался менять тактики из-за каких-то мелких изменений
обстановки.

4. Вы задумывались, а видит ли игрок все эти рейды, атаки, передислокации, и пр? ИМХО, когда я играю в стратегии,
для меня это не видно. Все, на что обычно я обращаю внимание, это копит ли враг на базе юниты, и атакует ли он меня.
Все остальное, для меня не имеет особое значение.
(Ответить) (Thread)
[User Picture]
From:plakhov
Date:Август 14, 2007 07:54 am
(Link)
Прошу прощения, что долго не отвечал.
Я отвечу на все это в следующей части, т.к. вопросы довольно типичные, а ответы в чем-то пересекаются с комментариями, которые я сам хотел сделать.
(Ответить) (Parent) (Thread)
[User Picture]
From:hedyn
Date:Август 17, 2007 11:24 am
(Link)
Ответ на первый вопрос: задача кластеризации, математика :)
Придумано достаточно алгоритмов для решения
(Ответить) (Parent) (Thread)
[User Picture]
From:fukanchik
Date:Август 17, 2007 12:17 am
(Link)
Прочитал обе ваши статьи.

Осталось впечатление, что просто прочитать учебники ИИ (того же Норвига) сильно облегчило бы вам жизнь и позволило бы значительно улучшить ИИ в играх.

Словарь оформился бы раньше - ведь прежде чем вы дали названия всем перечисленным понятиям, и соответственно выделили их из общей мешанины прошло много времени? А в книжках они уже названы и четко описаны.

Ваш механизм выбора поведения мало чем отличается от систем основанных на правилах. Существует значительное количество наработок с иерархией правил.

Уверен - знакомство с другими общепринятыми способами представления знаний (фреймы, семантические сети, логика), методами планирования, сопоставления с образцом, поиском - всё это не помешало бы. А вдь я перечислил вещи, которые появились в 60-70-х годах. И с тех пор прогресс не стоял на месте. И вы точно не пытались бы использовать в начале генетические алгоритмы и нейросети.

Расскажите - с тех пор вы познакомились с классическими методами ИИ (судя по вашему отношению к лиспу - да)? Насколько эти методы применимы в играх?

Кроме того - думаю, если вы всё это время продолжали программировать ИИ - ваше сегодняшний опыт гораздо интереснее.
(Ответить) (Thread)
[User Picture]
From:plakhov
Date:Август 17, 2007 06:40 am
(Link)
Не все так.

Я читал Норвига и часто его тут рекламирую. =)

"Общепринятую" терминологию здесь не старался использовать, поскольку из target аудитории с ней все равно мало кто знаком.

Генетические алгоритмы и нейросети мы использовать не пытались, а я был и против нечеткой логики, эксперименты с которой действительно проводились (но когда это решение принималось, я еще не обладал авторитетом, достаточным для участия в нем). Так что это предостережение для других.

И есть еще одна ловушка (собственно, она есть в восприятии любого большого текста), в которую, мне кажется, Вы рискуете попасть - переосмысление прочитанного в терминах привычного языка с отбрасыванием того, что на этот язык не переводится. Например, Вы увидели систему, основанную на иерархии правил, а человек, занимавшийся автоматным программированием, увидит стековый автомат. Можно интерпретировать и так, и так, но при каждой интерпретации что-то теряется.

Отвечать в комментарии очень долго. Я попробую более обстоятельно написать позже.
(Ответить) (Parent) (Thread)
[User Picture]
From:virtul
Date:Август 21, 2007 07:23 am
(Link)
Шикарно, спасибо :) Жду продолжения.
(Ответить) (Thread)