Практическое руководство по AI

Содержание

Введение
Автоматы
  Конечные автоматы
  Использование конечных автоматов
  Конечные автоматы в играх
  Гибкость
Юниты
  Анатомия
  Построение
  Разбиение на группы
  Приемущества группирования
  Большое хранилище
  Один из многих
  Разум толпы
  Собираем все воедино
Заключение
AI
  Перемещение
  Патрулирование
  Обход препятствий
  Прицеливание
  Преследование
Заключение
Список ссылок

Введение

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

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

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

Дискуссия и примеры будут относиться к стратегиям в реальном времени (Real-Time Stragedy), однако, некоторые концепции могут быть использованы для других типов игр. Примеры будут иллюстрироваться в формате языка Си.

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

Автоматы

Конечные автоматы

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

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

Использование конечных автоматов

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

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

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

Конечные автоматы в играх

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

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

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

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

Гибкость

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

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

Юниты

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

Анатомия

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

А теперь некоторые пояснения:

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

animDir, animAction и animNum отвечают за состояние анимации юнитов, которые выводятся на экран.

Переменные rank и health в объяснении не нуждаются и легко догадаться, для чего они нужны.

Переменная num - номер боевой единицы в главном массиве юнитов. Позже, запрашивая информацию о юните из его группы, иногда полезно выяснить, какой это юнит, не получая адрес структуры в ОЗУ.

group определяет, к какой группе боевая единица принадлежит, поскольку почти всегда любой юнит принадлежит к какой-нибудь группе. Юнит не принадлежит

style и animObj содержат дополнительную информацию о том, как спрайт юнита должен быть нарисован.

Построение

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

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

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

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

Разбиение на группы

Группировать или не группировать?

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

А хотите ли вы, чтобы юниты действовали согласованно?

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

Приемущества группирования

1. Информация о перемещениях юнитов хранится в общем списке. Плюс здесь состоит в том, что не нужно каждый раз, когда меняются пункты назначения и цели, копировать одни и те же данные каждому юниту. Все они получают ее из одного общего источника - источника группы.
2. Взаимодействие нескольких боевых единиц в таких вещах, как постройка сооружения. При этом юниты сразу же занимают определенное место на карте, а не перебирают всевозможные позиции по отношению к другим юнитам, путаясь до тех пор, пока не найдут подходящее положение.
3. Группы могут быть таким образом организованы, что отдача приказов между юнитами будет занимать столько же времени и данных, сколько отдача приказа отдельному юниту. Очень важно, чтобы данными можно было легко обмениваться. Пересылать информацию между 25 юнитами (или более того) от каждого к каждому - довольно рутинная работа, если не иметь то, что объединяет их всех.
4. В зависимости от того, как группа сформирована, алгоритм обхода и обнаружения препядствий можно упростить и уменьшить время нахождения пути в лабиринте. Иначе это может стать серьезной проблемой при работе с большим количеством юнитов.

Большое хранилище

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

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

Это значит, что юниты сами по себе не обладают информацией о том, куда идут, что делают, как происходит анимация, где они находятся. Юнит ВСЕГДА должен быть в группе, до тех пор, пока он передвигается и что-то делает. Если юнит один, он должен принадлежать к группе из одного.

Один из многих

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

Пояснения:

unitNum - номер юнита в группе. Если максимальное число юнитов в группе равно 10, тогда 10 мест в группе доступно. Первый юнит будет с номером 0, и так далее до 8.

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

waypoint - массив. Он содержит все области, на которые юниту прийдется передвинуться в порядке очереди. Все действия и точки-координаты (waypoints) определены только в структуре GroupUnit, если группа не самостоятельное образование, и юнитам нужно передвигаться самостоятельно.

Массив action содержит список действий, привязаных к движениям по точкам-координатам, это цепочка команд. Юниты могут, к примеру, красться по одной территории, затем бежать по другой. Действия игрока становятся более стратегическими и продуманными.

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

Переменныеrun, walk, sneak…отвечают за различные состояния, в которых находится юнит. Это не анимация, а состояния поведения, которые могут переключаться легко или даже работать вместе.

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

Разум толпы

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

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

Флажок formation определяет построение юнитов в группе. Они могут быть построенны в шеренгу и т.п. если изменить значение этой переменной. При этом юниты изменяют свое положение соответствующим образом.

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

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

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

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

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

По названиям переменных sentry(защита) and aiState (состояние интеллекта) понятно, что они содержат информацию о защите и более подробные данные о структуре и модели интеллекта.

Собираем все воедино

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

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

Заключение

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

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

Вы никогда не построите копию существующей реальности. Это факт. Поэтому создайте свой собственный мир.

AI

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

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

Перемещение

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

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

Патрулирование

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

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

Обход препятствий

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

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

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

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

Если возникает необходимость в более продвинутых алгоритмах поиска пути, попробуйте A*. Это довольно популярное решение для нахождения кратчайшего пути в лабиринтах. Есть варианты предпотчительнее A*, алгоритмы управления для постепенного прохождения через препятствия и для других жестко запрограммированых ситуации, таких как создание funneling intersections, которые можно использовать для того, чтобы добраться к отдельным областям карты.

Прицеливание

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

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

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

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

Преследование

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

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

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

Хотя данный алгоритм упускает из виду много возможностей, все же это разумная ответная реакция в данной ситуации.

Заключение

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

Список ссылок

Статья "Алгоритмы поиска пути"
Статья "Алгоритмы, применяемые в играх"