ИСПОЛЬЗОВАНИЕ МЕТОДА КОНЕЧНЫХ АВТОМАТОВ ДЛЯ МОДЕЛИРОВАНИЯ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА В КОМПЬЮТЕРНЫХ ИГРАХ

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

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

Этот способ реализации искусственного интеллекта (ИИ) является наиболее популярным и использовался во многих известных играх:

• в игре Pac-Man поведение противников реализовано через метод конечных автоматов. Враги в этой игре имеют как минимум два состояния: преследование (обычное состояние) и избегание (когда, оппоненты убегали от вас, при съедании большого кружка).
• компьютерные игроки в таких играх, как Quake, UnrealTournament, и т.п.
• персонажи многих популярных стратегийи т.д.

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

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

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

В нашей игре существовало несколько видов НИП, простейшим из которых были дикие волки. Для программной реализации мы создали систему, состоящую из абстрактного класса, представляющего собой основу для всех возможных классов состояний, в которых было описано поведение существа и условия перехода в другие состояния. Согласно Тынченко В.В. и Цареву Р.Ю.  легче принимать решения с помощью двухуровневой перспективы [7]. Поэтому в нашей системе было 2 типа состояний: внешние и внутренние.

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

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

Как писали Журавлёв В.М. и Якунин Ю.Ю., в сложных организационных системах хорошо работает единая система управления [5]. Создать подобную систему управления нам помогло встраивание в систему состояний системы сообщений между НИП, таким образом, НИП могли оповещать союзников поблизости о появлении врага, формируя собой группу с общим информационным полем.

Так же важно рассмотреть саму структуру состояний. Каждое состояние состоит из 4 методов: Enter, Execute, Exit, OnMessage.

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

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

Метод Exit() вызывается при выходе из данного состояния. В нем, как правило, освобождаются задействованные состоянием ресурсы.

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

Рассмотрим реализацию данного метода на примере:

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

Таблица 1

Состояния и переходы

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

Метод Enter() будет содержать инициализацию области патрулирования (построение подробного графа для поиска кратчайшего пути в заданный участок карты)

Метод Execute() случайным образом выбирает точку в области патрулирования и следует к ней. Помимо этого он проверяет область вокруг текущего  НИП на наличие врагов и если они есть в области видимости НИП, то его он переходит в состояние «Бой».

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

Одним из простейших способов реализации адаптивного ИИ является запоминание решений принятых ранее и оценка их результата. Во время разработки сложных систем, как например систем ИИ, согласно работам Якунина Ю.Ю. следует оценивать трудоемкость, и распределить свои силы правильно[8, 9].

При создании игры мы использовали спиральную модель разработки программного обеспечения, о которой писали И. В. Евдокимов и М. Ю. Вахрушева [4]. Мы выбрали необходимое программное обеспечение, руководствуясь работой И. В. Ковалева и А. С. Кузнецова [6]. Также игра это особенный вид программного обеспечения и для его разработки мы адаптировали стандарты программных средств к нашему проекту по статье И. В. Евдокимова [2]. После разработки игры мы проверили показатели качества и надежности программного обеспечения, руководствуясь работами [1, 3].

Список литературы:

1. Вахрушева М.Ю., Евдокимов И.В. Показатели качества и надежности программного обеспечения // Труды Братского государственного университета. Серия: Экономика и управление. 2012. Т. 1. С. 155-158.
2. Евдокимов И.В. Адаптация стандартов программных средств к проектам в области информационных технологий // Труды Братского государственного университета. Серия: Экономика и управление. 2010. Т. 2. С. 97-101.
3. Евдокимов И.В. Проблема и показатели качества программного обеспечения // Труды Братского государственного университета. Серия: Экономика и управление. 2009. Т. 1. С. 121-124.
4. Евдокимов И.В., Вахрушева М.Ю. Разработка программного обеспечения на основе спиральной модели жизненного цикла // Труды Братского государственного университета. Серия: Экономика и управление. 2011. Т. 1. С. 90-91.
5. Журавлёв В.М., Якунин Ю.Ю. Подход к моделированию сложной организационной системы с субъектно-объектным управлением // В сборнике: Технические и программные средства систем управления, контроля и измерения Материалы конференции с международным участием. 2010. С. 466-474.
6. Ковалев И.В., Кузнецов А.С. Операционные системы и системное программное обеспечение // Федер. агентство по образованию, Краснояр. гос. техн. ун-т. Красноярск, 2005.
7. Тынченко В.В., Царев Р.Ю. Концепция двухуровневого принятия решений на основе близости к идеальной альтернативе // Фундаментальные исследования. 2015. № 7-4. С. 778-781.
8. Якунин Ю.Ю. Оценка трудоемкости разработки программной системы // Вестник Сибирского государственного аэрокосмического университета им. академика М.Ф. Решетнева. 2008. № 2 (19). С. 87-91.
9. Якунин Ю.Ю. Технологии разработки программного обеспечения // Учебное пособие; Федеральное агентство по образованию, Сибирский Федеральный ун-т. Красноярск, 2008. Сер. Учебно-методический комплекс дисциплины.