Создание искусственного интеллекта для игр — от проектирования до оптимизации

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

Создание искусственного интеллекта для игр

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

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

Принятие решений

Основным принципом, лежащим в основе работы ИИ, является принятие решений. Для выбора при принятии решений система должна влиять на объекты с помощью ИИ. При этом такое воздействие может быть организовано в виде «вещания ИИ» или «обращений объектов».
 
В системах с «вещанием ИИ» система ИИ обычно изолирована в виде отдельного элемента игровой архитектуры. Такая стратегия зачастую принимает форму отдельного потока или нескольких потоков, в которых ИИ вычисляет наилучшее решение для заданных параметров игры. Когда ИИ принимает решение, оно передается всем участвующим объектам. Такой подход лучше всего работает в стратегиях реального времени, где ИИ анализирует общий ход событий во всей игре.

Системы с «обращениями объектов» лучше подходят для игр с простыми объектами. В таких играх объекты обращаются к системе ИИ каждый раз, когда объект «думает» или обновляет себя. Такой подход отлично подходит для систем с большим количеством объектов, которым не нужно «думать» слишком часто, например в шутерах. Такая система также может воспользоваться преимуществами многопоточной архитектуры, но для нее требуется более сложное планирование (подробные сведения см. в статье Ориона Гранатира Многопоточный ИИ).

Базовое восприятие

Чтобы искусственный интеллект мог принимать осмысленные решения, ему необходимо каким-либо образом воспринимать среду, в которой он находится. В простых системах такое восприятие может ограничиваться простой проверкой положения объекта игрока. В более сложных системах требуется определять основные характеристики и свойства игрового мира, например возможные маршруты для передвижения, наличие естественных укрытий на местности, области конфликтов.
При этом разработчикам необходимо придумывать способ выявления и определения основных свойств игрового мира, важных для системы ИИ. Например, укрытия на местности могут быть заранее определены дизайнерами уровней или заранее вычислены при загрузке или компиляции карты уровня. Некоторые элементы необходимо вычислять на лету, например карты конфликтов и ближайшие угрозы.

Системы на основе правил

Простейшей формой искусственного интеллекта является система на основе правил. Такая система дальше всего стоит от настоящего искусственного интеллекта. Набор заранее заданных алгоритмов определяет поведение игровых объектов. С учетом разнообразия действий конечный результат может быть неявной поведенческой системой, хотя такая система на самом деле вовсе не будет «интеллектуальной».
Классическим игровым приложением, где используется такая система, является Pac-Man. Игрока преследуют четыре привидения. Каждое привидение действует, подчиняясь простому набору правил. Одно привидение всегда поворачивает влево, другое всегда поворачивает вправо, третье поворачивает в произвольном направлении, а четвертое всегда поворачивает в сторону игрока. Если бы на экране привидения появлялись по одному, их поведение было бы очень легко определить и игрок смог бы без труда от них спасаться. Но поскольку появляется сразу группа из четырех привидений, их движения кажутся сложным и скоординированным выслеживанием игрока. На самом же деле только последнее из четырех привидений учитывает расположение игрока.


Наглядное представление набора правил, управляющих привидениями в игре Pac-Man, где стрелки представляют принимаемые «решения»

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

В более сложных и разумных системах в качестве основы используются последовательности условных правил. В тактических играх правила управляют выбором используемой тактики. В стратегических играх правила управляют последовательностью строящихся объектов и реакцией на конфликты. Системы на основе правил являются фундаментом ИИ.

Конечные автоматы в качестве ИИ

Конечный автомат (машина с конечным числом состояний) является способом моделирования и реализации объекта, обладающего различными состояниями в течение своей жизни. Каждое «состояние» может представлять физические условия, в которых находится объект, или, например, набор эмоций, выражаемых объектом. Здесь эмоциональные состояния не имеют никакого отношения к эмоциям ИИ, они относятся к заранее заданным поведенческим моделям, вписывающимся в контекст игры.


Схема состояний в типичном конечном автомате, стрелки представляют возможные изменения состояния

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

Адаптивный ИИ

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

Предсказание

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

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

Восприятие и поиск путей

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

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

Как ИИ воспринимает окружающий мир

Зрение

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

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

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

1. Рассчитайте вектор между агентом и нужным объектом путем вычитания положения цели из положения агента.
2. Вычислите угол между этим вектором и направлением взгляда агента.
3. Если абсолютное значение угла превышает заданный угол поля зрения агента, то ваш агент не видит объект.

В более сложных играх нужно учитывать, что игрок или другие объекты могут находиться за каким-либо укрытием. Для таких игр может потребоваться построить бегущие лучи (так называемый метод ray casting), чтобы узнать, не загорожена ли возможная цель чем-либо. Построение бегущих лучей — это математический способ проверить, пересекается ли луч с какими-либо объектами, начиная с одной точки и двигаясь в заданном направлении. Если хотите узнать, как именно это делается на конкретном примере, ознакомьтесь со статьей Одна голова хорошо, а две лучше.

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

Слух

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

Как и в случае со зрением, сначала нужно получить список находящихся рядом объектов. Для этого можно снова просто проверить дистанцию, но выборка нужных объектов из этого списка происходит уже совсем иначе.

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

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

Базовая функциональность, необходимая для придания вашим агентам зрения и слуха, может использоваться и для имитации других органов чувств. Например, обоняния. (Возможность отслеживания игроков интеллектуальными агентами по запаху существует в современных играх, таких как Call of Duty 4*). Добавление обоняния в игру не вызывает особенных трудностей: достаточно назначить каждому игровому объекту отличительный номер запаха и его интенсивность. Интенсивность запаха определяет два фактора: радиус запаха и силу запаха следа, который остается позади. Активные объекты игроков часто отслеживают свои предыдущие положения по ряду причин. Одной из таких причин может быть использование объектов с запахом. С течением времени сила запаха следа уменьшается, след «остывает». Когда данные агента о запахе изменяются, он должен проверить наличие запаха точно так же, как наличие звука (с учетом радиуса и препятствий). Успешность обоняния вычисляется на основе интенсивности запаха и силы обоняния агента: эти значения сравниваются с объектом и его следом.
Осязание в играх поддерживается изначально, поскольку в любой игре уже есть система автоматической обработки столкновений объектов. Достаточно добиться того, чтобы интеллектуальные агенты реагировали на события столкновений и повреждения.

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

Временные объекты

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

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

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

Укрытие

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


Художники из Penny Arcade* сатирически описывают проблему ИИ противника и укрытий

Эта проблема на самом деле состоит из двух задач: во-первых, нужно правильно распознать укрытия на основе геометрии окружающего мира; во-вторых, нужно правильно распознать укрытия на основе объектов окружающего мира (как показано в приведенном выше комиксе). Чтобы определить, способно ли укрытие защищать от атак, можно просто один раз сравнить размер граничной рамки агента с размерами возможного укрытия. Затем следует проверить, сможет ли ваш объект поместиться за этим укрытием. Для этого нужно провести лучи от различий в положениях вашего стрелка и укрытия. С помощью этого луча можно определить, свободно ли место, находящееся за укрытием (если смотреть со стороны стрелка), а затем пометить это место как следующую цель перемещения агента.


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

Навигация ИИ

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

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

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

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

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

1. Двигайтесь в направлении цели.
2. Если путь разветвляется, выберите одно из возможных направлений.
3. Если путь приводит в тупик, возвращайтесь к последнему разветвлению и выберите другое направление.
4. Если все возможные пути пройдены безрезультатно, отказывайтесь от дальнейшего поиска.

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

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

Поиск путей

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

Поиск путей можно считать уже давно и успешно решенной проблемой в разработке игр. Даже в таких старых играх, как первая версия легендарной игры Starcraft* (Blizzard Entertainment*), огромные количества игровых объектов могли определять пути движения по крупным и сложным картам.

Для определения путей движения используется алгоритм под названием A* (произносится э-стар). С его помощью можно находить оптимальный путь между двумя любыми точками в графе (в данном случае — на карте). Простой поиск в Интернете выдает чистый алгоритм, использующий крайне «понятные» описательные термины, такие как F, G и H. Сейчас я попробую описать этот алгоритм более удобопонятным образом.

Сначала нужно создать два списка: список узлов, которые еще не проверены (Unchecked), и список уже проверенных узлов (Checked). Каждый список включает узел расположения, предполагаемое расстояние до цели и ссылку на родительский объект (узел, который поместил данный узел в список). Изначально списки пусты.

Теперь добавим начальное расположение в список непроверенных, не указывая ничего в качестве родительского объекта. Затем вводим алгоритм.

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

Когда объект достигает поля цели, можно построить путь, отследив родительские узлы вплоть до узла, у которого нет родительского элемента (это начальный узел). При этом мы получаем оптимальный путь, по которому может перемещаться объект.
Этот процесс работает, только когда агент получает приказ или самостоятельно принимает решение о движении, поэтому здесь можно с большой выгодой использовать многопоточность. Агент может отправить запрос в поток поиска пути, чтобы получить обнаруженный путь, не влияя на производительность ИИ. В большинстве случаев система может быстро получить результаты. При загрузке большого количества запросов путей агент может либо подождать, либо, не дожидаясь выдачи путей, просто начать двигаться в нужном направлении (например, по алгоритму «Столкнуться и повернуть»). На очень больших картах можно разделить систему на области и заранее вычислить все возможные пути между областями (или точки маршрута).
В этом случае модуль поиска путей просто находит наилучший путь и немедленно возвращает результаты. Поток карты путей может просто отслеживать изменения на карте (например, когда игрок строит стену), а затем снова запускает проверку путей по мере необходимости. Поскольку этот алгоритм работает в собственном потоке, он может адаптироваться, не влияя на производительность остальной игры.

Многопоточность может повысить производительность даже внутри подсистемы поиска путей. Этот подход широко применяется во всех стратегиях в реальном времени (RTS) и в системах с большим количеством объектов, каждый из которых пытается обнаружить потенциально уникальный путь. В разных потоках можно одновременно находить множество путей. Разумеется, система должна отслеживать, какие пути обнаруживаются. Каждый путь достаточно обнаружить только один раз.

Пример кода

Вот пример алгоритма А*, реализованного на языке С. Ради упрощения я убрал из этого примера поддерживающие функции.
Этот пример основывается на игровой карте в виде прямоугольной координатной сетки, каждое поле которой может быть проходимым либо непроходимым. Приведенный алгоритм поддерживает только перемещение на соседнее поле, но с незначительными изменениями его можно будет использовать и для перемещения по диагонали, и даже в играх, где карты уровней состоят из шестиугольных полей.

/*Get Path will return -1 on failure or a number on distance to path
 if a path is found, the array pointed to by path will be set with the path in Points*/
int GetPath(int sx,int sy,int gx,int gy,int team,Point *path,int pathlen)
{
 int u,i,p;
 memset(&Checked,0,sizeof(Checked));
 memset(&Unchecked,0,sizeof(Unchecked));
 Unchecked[0].s.x = sx;
 Unchecked[0].s.y = sy;
 Unchecked[0].d = abs(sx - gx) + abs(sy - gy);
 Unchecked[0].p.x = -1;
 Unchecked[0].p.y = -1;
 Unchecked[0].used = 1;
 Unchecked[0].steps = 0;

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

 do
 {
 u = GetBestUnchecked();
 /*add */
 AddtoList(Checked,Unchecked[u]);
 if((Unchecked[u].s.x == gx)&&(Unchecked[u].s.y == gy))
 {
 break;
 }

Приведенный выше фрагмент кода анализирует узел из списка непроверенных, ближайший к цели. Функция GetBestUnchecked() проверяет расчетное расстояние каждого узла до цели. Если данное поле является целью, цикл разрывается, процесс завершен.

Ниже видно, как вычисляется расстояние: берем предполагаемые значения расстояния до цели в направлениях X и Y и складываем их. При этом может возникнуть желание использовать теорему Пифагора (сумма квадратов катетов равна квадрату гипотенузы), но это излишне. Нам нужно получить лишь относительное значение расстояния, а не его точную величину. Процессоры обрабатывают сложение и вычитание во много раз быстрее, чем умножение, которое, в свою очередь, работает гораздо быстрее, чем деление. Этот фрагмент кода запускается по много раз в каждом кадре, поэтому во главу угла ставим оптимизацию.

/*tile to the left*/
 if((Unchecked[u].s.x - 1) >= 0)/*first, make sure we're on the map*/
 {
 if((IsInList(Unchecked,Unchecked[u].s.x - 1,Unchecked[u].s.y,NULL) == 0)&&(IsInList(Checked,Unchecked[u].s.x - 1,Unchecked[u].s.y,NULL) == 0))
	 /*make sure we don't repeat a search*/
 {
 if(TileValid(Unchecked[u].s.x - 1,Unchecked[u].s.y,team))
 NewtoList(Unchecked,Unchecked[u].s.x - 1,Unchecked[u].s.y, Unchecked[u].s.x, Unchecked[u].s.y, abs((Unchecked[u].s.x - 1) - gx) + abs(Unchecked[u].s.y - gy), Unchecked[u].steps + 1);
 }
 }

В приведенном выше разделе функция анализирует поле слева от текущего узла. Если это поле пока отсутствует в списках «Проверенные» или «Непроверенные», функция попытается добавить его в список. TileValid() — еще одна функция, которую нужно приспособить для игры. Если она передает проверку TileValid(), то она вызовет NewToList() и новое расположение будет добавлено в список непроверенных. В следующих фрагментах кода повторяется этот же процесс, но в других направлениях: справа, сверху и снизу.

/*tile to the right*/
 if((Unchecked[u].s.x + 1) < WIDTH)/*first, make sure we're on the map*/
 {
 if((IsInList(Unchecked,Unchecked[u].s.x + 1,Unchecked[u].s.y,NULL) == 0)&&(IsInList(Checked,Unchecked[u].s.x + 1,Unchecked[u].s.y,NULL) == 0))
	 /*make sure we don't repeat a search*/
 {
 if(TileValid(Unchecked[u].s.x + 1,Unchecked[u].s.y,team))
 NewtoList(Unchecked,Unchecked[u].s.x + 1,Unchecked[u].s.y, Unchecked[u].s.x, Unchecked[u].s.y, abs((Unchecked[u].s.x + 1) - gx) + abs(Unchecked[u].s.y - gy), Unchecked[u].steps + 1);
 }
 }
 /*tile below*/
 if((Unchecked[u].s.y + 1) < HEIGHT)/*first, make sure we're on the map*/
 {
 if((IsInList(Unchecked,Unchecked[u].s.x ,Unchecked[u].s.y + 1,NULL) == 0)&&(IsInList(Checked,Unchecked[u].s.x,Unchecked[u].s.y + 1,NULL) == 0))
	 /*make sure we don't repeat a search*/
 {
 if(TileValid(Unchecked[u].s.x,Unchecked[u].s.y + 1,team))
 NewtoList(Unchecked,Unchecked[u].s.x,Unchecked[u].s.y + 1, Unchecked[u].s.x, Unchecked[u].s.y, abs(Unchecked[u].s.x - gx) + abs((Unchecked[u].s.y + 1) - gy), Unchecked[u].steps + 1);
 }
 }
 /*tile above*/
 if((Unchecked[u].s.y - 1) >= 0)/*first, make sure we're on the map*/
 {
 if((IsInList(Unchecked,Unchecked[u].s.x ,Unchecked[u].s.y - 1,NULL) == 0)&&(IsInList(Checked,Unchecked[u].s.x,Unchecked[u].s.y - 1,NULL) == 0))
	 /*make sure we don't repeat a search*/
 {
 if(TileValid(Unchecked[u].s.x,Unchecked[u].s.y - 1,team))
 NewtoList(Unchecked,Unchecked[u].s.x,Unchecked[u].s.y - 1, Unchecked[u].s.x, Unchecked[u].s.y, abs(Unchecked[u].s.x - gx) + abs((Unchecked[u].s.y - 1) - gy), Unchecked[u].steps + 1);
 }
 }
 memset(&Unchecked[u],0,sizeof(PNode));

Последнее, что осталось сделать в этой итерации, — удалить текущий узел из списка непроверенных. Нет необходимости еще раз анализировать это поле.

 }
 while(1)
;

Заключительный фрагмент кода выстраивает путь из списка проверенных путем возвращения к исходному положению. Путь к исходному расположению всегда можно найти, поскольку каждый узел на пути отслеживает свой родительский узел. Затем возвращается итоговый путь (с помощью ссылки). Функция возвращает длину нового пути.

 IsInList(Checked,Unchecked[u].s.x,Unchecked[u].s.y,&u);
 p = Checked[u].steps;
 if(path != NULL)
 {
 for(i = (p - 1);i >= 0;i--)
 {
 path[i].x = Checked[u].s.x;
 path[i].y = Checked[u].s.y;
 IsInList(Checked,Checked[u].p.x,Checked[u].p.y,&u);
 }
 }
 return p;
}

Тактический и стратегический ИИ

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

Тактический ИИ

Роль тактического ИИ состоит в координации усилий групп агентов в игре. Группы более эффективны, поскольку члены группы могут поддерживать друг друга, могут действовать как единое подразделение, обмениваться информацией и распределять действия по получению информации.
Принцип тактического ИИ построен вокруг динамики группы. Игра должна отслеживать различные группы объектов. Каждую группу необходимо обновлять отдельно от индивидуальных объектов. Для этого можно использовать выделенный модуль обновления, отслеживающий различные группы, их цели и их состав. Недостаток этого метода состоит в том, что требуется разработка отдельной системы для игрового движка. Поэтому я предпочитаю использовать метод командира группы.

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

Движение группы: поиск путей

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

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


В игре Overlord рядовые (красного цвета) действуют как одна команда и передвигаются строем по команде игрока (воин в броне)

Управлять строем очень просто, для этого достаточно несколько расширить сферу действий командира группы. Каждый юнит в строю выполняет определенную роль. При построении каждому члену группы назначается место в строю точно так же, как одному из юнитов назначается роль командира группы. Цель каждого юнита — сохранить свое место на относительном расстоянии до других членов группы.
Для примера возьмем рядовых в игре Overlord. Они передвигаются треугольным строем. На рисунке ниже по маршруту должен двигаться только командир группы (обозначенный буквой «С»). Юнит 1 следует за юнитом «С» с такой же скоростью сзади и немного левее. Юнит 2 следит и следует за юнитом 1, двигаясь немного в стороне. Юнит 3 делает то же самое, что и юнит 1, но следует за юнитом 1, а не за командиром. Все члены группы соблюдают этот порядок.


Порядок движения треугольным строем

Тактика групп

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


В игре Enemy Territory Quake Wars компаний Id Software* и Splash Damage, Ltd.* существует пять классов, которые выполняют разные роли в динамике группы

Кроме того, в группе может пригодиться еще один уровень анализа — анализ возможностей каждого члена группы. Командиру важно знать, в каких ситуациях группа может быть эффективна, когда группа получит преимущество, а когда группе следует отступить.
Например, в стратегии реального времени Starcraft* компании Blizzard существуют наземные войска и летающие войска. При этом не все виды наземных войск могут стрелять по летающим войскам. Группе важно знать о наличии такой возможности. Если в группе нет ни одного юнита, способного вести огонь по летающим юнитам, то при обнаружении летающего юнита лучше всего пуститься в бегство. Но если в группе есть юниты, способные поражать летающего противника, даже если таких юнитов и немного, лучше не отступать, а остановиться и обороняться (если в этой группе есть вспомогательные юниты, способные лечить тех, которые ведут огонь по воздушным целям).

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

Стратегический ИИ

Стратегический ИИ — это ИИ более высокого порядка, он управляет целой армией и вырабатывает оптимальные стратегии.
Стратегический ИИ обычно применяется в стратегиях в реальном времени, но в последнее время его все чаще реализуют и в тактических шутерах от первого лица. Управляемый игроком командир может представлять собой отдельную систему или может быть настроен как пустой объект, не имеющий места и графического изображения, но обновляемый и размышляющий.

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

Управление этим взаимодействием (или сражением) — вот где прежде всего работает ИИ. Командир должен изучить карту игры, чтобы обнаружить игрока, выявить основные области интереса, например узкие проходы, выстроить оборону и проанализировать оборону другого игрока. Как именно это сделать? Очевидного ответа на этот вопрос нет, но для упрощения можно использовать карты решений.
Карты решений
Карты решений представляют собой двухмерные массивы, приближенно соответствующие игровой карте. Каждая ячейка массива соответствует определенной области в игре и содержит важную информацию об этой области. Эти карты помогают стратегическому ИИ принимать грамотные решения относительно игры в целом.

Карты ресурсов

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

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

Карты целей

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

Карты конфликтов

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


Пример карты конфликта при наложении на карту местности. Чем больше красного цвета, тем больше конфликтов

Создание и применение карт

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

Впрочем, добиться быстрого обновления карт решений не так трудно. Достаточно поместить систему карт решений в отдельный поток. В идеале каждый игрок, управляемый искусственным интеллектом, должен располагать собственным потоком для обработки собственного набора карт решений. Значительный прирост производительности будет достигнут в том случае, если все объекты уже разделены на несколько потоков. Потоки с картами решений будут обрабатывать только запросы от сообщений обновления распараллеленных объектов.

Наибольшая эффективность ИИ: обработка потоков

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


В игре Starcraft* II компании Blizzard Entertainment одновременно работает ИИ огромного количества юнитов. Лучше всего использовать для этого многопоточную архитектуру

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

Распараллеливание задач

Простейший способ приспособить приложение к многопоточной архитектуре — разделить его на отдельные задачи.


Функциональное распараллеливание позволяет каждой подсистеме использовать собственный поток и ядро

Характерный пример — звуковая система игрового движка. Звуку не нужно взаимодействовать с другими системами: эта система занимается только одним — воспроизводит звуки и их сочетания по запросу. Функции обмена данными представляют собой вызовы для воспроизведения звуков и остановки воспроизведения. Благодаря этому звуковая система является автономной и идеально подходит для функционального распараллеливания.

В зависимости от потребностей игры может быть множество разных задач, каждой из которых можно предоставить отдельный поток. Здесь мы рассматриваем три такие задачи: поиск путей, стратегический ИИ и собственно система объектов.

Поиск путей

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

Любой объект, которому нужно найти путь, отправляет запрос на поиск путей и немедленно получает «квитанцию» от системы поиска путей. Эта квитанция представляет собой просто уникальный дескриптор, который система поиска путей может использовать для работы. После этого объект продолжает заниматься своими делами до следующего кадра в игровом цикле. Объект может проверить, обработана ли его квитанция. Если да, то объект получает рассчитанный путь; в противном случае объект продолжает заниматься своими делами в ожидании обработки пути.
В системе поиска путей квитанция используется для отслеживания запросов путей, пока система работает над ними, не влияя на производительность остальных компонентов. У такого подхода есть интересное преимущество — автоматическое отслеживание всех обнаруженных путей. Поэтому при поступлении запроса на найденный ранее путь система поиска путей может просто выдать квитанцию на уже существующий путь. Этот метод великолепно подходит для систем, где множество объектов запрашивают путь, поскольку все найденные пути с большой вероятностью будут запрошены многократно.

Стратегический ИИ

Как было упомянуто ранее, хорошо, если система ИИ, управляющая всем ходом игры в целом, будет работать в собственном отдельном потоке. Эта система сможет анализировать игровое поле и отдавать команды различным объектам, которые смогут получать и распознавать эти команды.
Система объектов в собственном потоке будет занята работой по сбору информации для карт решений. Полученная информация будет отправлена в систему стратегического ИИ в виде запросов на обновление карт решений. При обновлении стратегический ИИ будет анализировать эти запросы, обновлять карты решений и принимать решения. При этом не имеет значения, работают ли эти две системы (стратегический ИИ и объекты) синхронно: любая рассинхронизация будет незначительной и не повлияет на решения ИИ. (Речь идет о рассинхронизации в пределах 1/60 секунды, то есть, с точки зрения игрока, реакция ИИ не замедлится ни на один кадр.)

Распараллеливание данных

Функциональное распараллеливание очень эффективно и использует возможности систем с несколькими ядрами. Но, к сожалению, если в системе количество ядер превышает количество задач, то программа не использует всю доступную вычислительную мощность Поэтому переходим к распараллеливанию данных, при котором одна функция может воспользоваться всеми доступными ядрами


Распараллеливание данных

При функциональном распараллеливании мы брали автономный модуль и предоставляли ему отдельный поток. Теперь мы разделим одно задание на части и распределим их обработку между разными потоками. При этом производительность возрастает пропорционально количеству ядер в системе. В системе 8 ядер? Отлично! В системе 64 ядра? Еще лучше! Функциональное распараллеливание позволяет обозначать фрагменты кода как многопоточные, после чего эти фрагменты работают самостоятельно. При распараллеливании данных требуется дополнительная работа для согласования. Например, можно использовать один поток ядра (главный поток), чтобы отслеживать работу всех остальных потоков. Подчиненные потоки будут запрашивать «работу» в главном потоке, чтобы исключить дублирование выполнения одной и той же работы.

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

Реализация

В примере с системой поиска путей эта система хранит список запрошенных путей. Затем система циклически просматривает этот список и запускает функции поиска путей для отдельных запросов, сохраняя их в списке путей. Этот цикл можно распределить по потокам так, чтобы каждая итерация цикла разделялась на разные потоки. Эти потоки будут запускаться на первом же доступном ядре, что позволяет использовать всю доступную вычислительную мощность. Ядро процессора должно бездействовать только при отсутствии работы.
В таких системах есть возможность получения нескольких запросов на одно и то же задание. Если эти запросы разделены по времени, функция поиска путей автоматически проверяет, был ли уже обработан такой запрос ранее. При работе с распараллеливанием данных несколько запросов одного и того же пути может возникнуть одновременно. Это может привести к дублированию работы, в случае чего теряется весь смысл многопоточных вычислений.

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

• RequestPath(start, goal).Эта функция вызывается снаружи системы поиска путей для получения потока. Эта функция выполняет следующие задачи:
  
  • просматривает список выполненных запросов и определяет, был ли уже найден такой путь (или близкий путь), затем возвращает квитанцию на этот путь;
  • просматривает список активных запросов (если путь не был найден) для поиска этого пути; если путь в нем есть, функция возвращает квитанцию на рассчитываемый путь;
  • создает новый запрос и возвращает новую квитанцию (если поиск по обоим указанным выше спискам не дал результата).
• CheckPath(«ticket»). Используя квитанцию, эта функция просматривает список выполненных запросов и находит путь, для которого действует данная квитанция. Функция возвращает данные о том, был ли найден такой путь.
• UpdatePathFinder().Это управляющая функция, обрабатывающая издержки для потоков поиска путей. Эта функция выполняет следующие задачи.
  
  • Анализ новых запросов. Возможно одновременное создание разными ядрами нескольких запросов на один и тот же путь. Эта секция удаляет дублирующиеся запросы и назначает несколько квитанций (из разных запросов) одному и тому же запросу.
  • Циклический просмотр активных запросов. Эта функция просматривает все активные запросы и распределяет их по потокам. В начале и в конце каждого цикла код помечается как поток. Каждый поток:
    
    1. находит запрошенный путь;
    2. сохраняет его в списке готовых путей вместе с назначенными этому пути квитанциями;
    3. удаляет задание из списка активных заданий.

Устранение конфликтов

Возможно, вы обратили внимание, что при таком распределении работ могут возникнуть проблемы. Различным потокам нужно производить запись в очередь запросов; потокам данных нужно добавлять результаты в список готовых путей. Все это может привести к конфликтам записи, когда один поток записывает что-либо в ячейку А в то же самое время, когда другой поток записывает в эту же ячейку А что-то другое. Такой поток может привести к хорошо известному «состоянию состязания».

Чтобы избежать конфликтов, можно пометить некоторые части кода как особо важные. При выполнении особо важного кода только один поток сможет получить доступ к этой секции кода в один момент времени. Всем остальным потокам, которые собираются сделать то же самое (получить доступ к той же области памяти), придется подождать. Такое поведение может привести к СЕРЬЕЗНЕЙШИМ проблемам, таким как взаимная блокировка, возникающая, когда несколько потоков блокируют друг друга, препятствуя в получении доступа к памяти. Это решение позволяет избежать взаимной блокировки. Когда фактическая работа потока будет завершена, можно предоставлять доступ к важной области памяти сразу же по доступности без блокирования других секций, которые могут быть необходимы другим потокам.

Синхронизация

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

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

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

Заключение

Итак, задача искусственного интеллекта для игр состоит в имитации поведения объектов реального мира. И это совсем не сложно, если начать рассмотрение искусственного интеллекта с базовых компонентов — от низкоуровневых правил и алгоритмов поиска путей до более высокого уровня, на котором работает тактический и стратегический ИИ. При этом, следует добиться высокой эффективности работы системы ИИ, оптимизировать ее для использования на компьютерах с большим количеством вычислительных ядер. Возможности ИИ в системе должны ограничиваться только фактически наличными ресурсами оборудования, а не неспособностью использовать эти ресурсы. Только тогда мы сможем создать более интересных и сложных противников для игроков, которые будут с нетерпением ожидать продолжения игры.

Полный текст статей на русском языке

Создание искусственного интеллекта для игр (часть 1)
Создание искусственного интеллекта для игр (часть 2)
Создание искусственного интеллекта для игр (часть 3)
Создание искусственного интеллекта для игр (часть 4)