Что такое конечные автоматы и как их использовать в разработке игр

Польза и область применения.

На конференции DevGAMM 2018 в Москве с докладом о пользе конечных автоматов выступила Алёна Пономаренко, программист в Social Quantum. Она рассказала, как в играх используются конечные автоматы (Finite-State Machine) — особые алгоритмы, отвечающие за состояние внутриигровых объектов и персонажей. С их помощью можно не только управлять поведением ИИ, но и задавать модели функционирования интерфейсов. Мы выбрали из выступления главное.

Реальный мир устроен так, что все процессы протекают параллельно друг с другом. Например, человек может одновременно дышать, слушать доклад и обдумывать определённую мысль. К этому добавляются ещё и процессы, происходящие вне текущего контекста: ожидание ответа на СМС — наглядный пример.

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

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

Для эмулирования реальности необходимо использовать специальные инструменты. Конечные автомат — один из таких инструментов.

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

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

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

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

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

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

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

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

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

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

#опыт