Как и обещал в прошлом посте, здесь я рассмотрю вопрос реализации менеджера игровых состояний и подробно разберу концепцию конечного автомата (КА), являющуюся ключевой в этом вопросе. Для начала я опишу КА с точки зрения математики, а затем рассмотрю возможность его применения для управления игровыми состояниями.
Конечные автоматы в математической логике
Так что же из себя представляют КА? Для начала посмотрим на то, какие функции они выполняют.
Конечный автомат – это некое умозрительное устройство, которое в любой момент времени может находиться в одном конкретном состоянии (которые можно представить как, например, пронумерованные загорающиеся строго по одному индикаторы). У этого агрегата имеется также устройство ввода (традиционно представляемое как лента, разделенная на ячейки, в которых записаны буквы – КА при этом рассматривает ячейки по очереди и считывает записанную в ячейку букву).
При считывании очередной буквы (можно назвать ее управляющим символом) автомат переходит в какое-то другое состояние, причем это новое состояние однозначно определяется парой (считанная буква, старое состояние).
Некоторые из состояний являются выделенными – имеется одно начальное и несколько конечных. Подразумевается, что когда КА начал считывать буквы с ленты, он находился в начальном состоянии; если после считывания последней переданной ему буквы он оказался в одном из конечных – это «хорошо», если нет – «плохо».
Больше ничем начальное и конечные состояния не примечательны – в процессе своей работы автомат может сколько угодно раз побывать в любом из них. Строго говоря, что он делает между началом и окончанием чтения записанных на ленту символов, никого не волнует.
Из всего вышесказанного можно заключить, что конечный автомат – это некий распознаватель, главная задача которого – отвечать на вопрос, ведет ли последовательность символов, записанная на ленте, в одно из конечных состояний, или нет. Иначе – распознает ли он эту последовательность, или нет.
Поскольку для любой последовательности символов (слов) КА может сказать, распознает ли он ее, то с каждым конечным автоматом сопоставляют распознаваемый им язык (совокупность всех слов, которые он распознает).
Теперь рассмотрим, как (почти) строго задать конечный автомат. Пусть имеется некоторое конечное множество Q, которое мы назовем множеством состояний (а его элементы – состояниями). Выберем из этого множества элемент q0, который назовем начальным состоянием, а также подмножество F – множество конечных состояний.
Возьмем также некоторое конечное множество ∑, которое назовем алфавитом. На декартовом произведении Q*Σ зададим всюду определенную функцию δ, принимающую значения на множестве Q – функцию перехода. Пятерку (Q, ∑, δ, q0, F) называют полным детерминированным конечным автоматом (ПДКА).
Нетрудно убедиться, что данный объект работает так же, как и описанный ранее: имеется множество состояний, множество символов, которые могут быть на ленте, правило, по которому из каждого конкретного состояния при считывании каждого конкретного символа выбирается вполне определенное следующее состояние, а также начальное и конечное состояния.
Помимо ПДКА существуют и другие разновидности конечных автоматов. Одна из них – неполный ДКА – отличается тем, что функция перехода на нем не является всюду определенной. Считается, что если автомат должен выполнить не определенный переход, то вместо этого он заканчивает свою работу, сигнализируя при этом, что слово не было распознано.
Нетрудно убедиться, что полные и неполные ДКА эквивалентны друг другу в том смысле, что распознают один и тот же класс языков (т.е. если для какого-то языка существует распознающий его ПДКА, то существует распознающий его неполный ДКА, и наоборот). В самом деле, полный автомат – это частный случай неполного, так что в одну сторону эквивалентность очевидна.
Однако, для всякого неполного автомата можно построить эквивалентный ему полный – достаточно ввести новое «мусорное» состояние, и доопределить функцию перехода так, чтобы вместо завершения из-за отсутствующего перехода она отправляла автомат в это мусорное состояние. Тогда единожды попав в него, он больше не сможет из него выйти, никогда не придет в конечное состояние, и не распознает полученное слово.
Если же при считывании слова он и не должен был совершить неопределенный переход, то в модифицированном виде автомат будет вести себя так же, как раньше, не замечая появления нового состояния. При этом он уже будет полным.
Есть также другие типы КА, например, недетерминированный конечный автомат (НКА) и ε-НКА (они оба эквивалентны ДКА), но здесь я их рассматривать не буду. Они оказываются удобны в некоторых задачах, но для рассмотрения вопроса о реализации менеджера игровых состояний лучше подходят детерминированные автоматы. Впрочем, в полной мере их будет недостаточно, и придется упомянуть также т.н. конечные автоматы с магазинной памятью, которые распознают более широкий класс языков, нежели ПДКА.
Применение автоматов к построению менеджера состояний
Теперь, рассмотрев такое математическое понятие, как КА, можно начать проводить параллели с нашей реальной прикладной задачей создания менеджера состояний.
Очевидно, что идеология конечных автоматов не противоречит основным требованиям к управлению поведением игры, обозначенным в прошлом посте. А именно: в каждый момент времени игровое приложение находится строго в одном состоянии, а переход между ними осуществляется по определенной схеме, зависящей от текущего состояния и некоторого управляющего ввода (например, реакции пользователя или сигнала о завершении загрузки ресурсов).
Не менее важным, однако, является вопрос об эффективной реализации процесса перехода из одного состояния в другое. Самый примитивный вариант – выбирать следующее состояние на основе текущего, а также управляющего сигнала конструкциями типа if/switch – обладает рядом серьезных недостатков. В их числе громоздкость кода, а также трудности при его изменении, добавлении новых состояний или удалении старых. Попробуйте-ка по несколько раз поменять структуру КА с десятью состояниями и пятью управляющими символами, и при этом ничего не забыть и не перепутать! Особенно если логика размазана по нескольким участкам кода, между которыми очень неудобно то и дело скакать.
Однако при работе с конечными автоматами естественным образом возникает такая система, как таблица переходов, лишенная все этих недостатков. С математической точки зрения она представляет собой табличное задание функции δ: Q*Σ → Q. С программистской – двумерный массив, индексами которого являются номер текущего состояния и управляющий символ.
Так, КА для отслеживания текущего состояния какого-нибудь боевого юнита в игре, можно реализовать примерно таким кодом (оставляем за кадром все вопросы реализации, не связанные с альтернативой «if/switch» vs «таблица переходов»):
enum State { stIdle = 0, stWalk, stShoot, stShootWalking, stDead }; enum Command { comGo = 0, comStand, comShoot, comDie }; State Transition[5][4] = { {stWalk, stIdle, stShoot, stDead}, {stWalk, stIdle, stShootWalking, stDead}, {stShootWalking, stShoot, stShoot, stDead}, {stShootWalking, stShoot, stShootWalking, stDead}, {stDead, stDead, stDead, stDead} }; State NextState(State currState, Command receivedCommand) { returnTransition[currState][receivedCommand]; }
Ради интереса вы можете попробовать реализовать ту же логику с помощью обычных условных переходов. Затем для более полного эффекта добавьте одно-два состояния на ваш выбор. А потом – удалите какое-то одно.
При работе с таблицей перехода естественным образом возникает возможность использовать data-driven подход (когда данные управляют бизнес-логикой). Если при использовании if/switch мы получаем напрочь захардкоженную логику, то помещение правил перехода в массив позволяет легко настраивать их под текущие задачи, менять прямо во время работы приложения, загружать из файла и т.п.
Итак, семантика конечного автомата вполне подходит для управления игровыми состояниями, а таблица переходов предоставляет удобную и эффективную реализацию этой идеи в виде кода.
Классические КА – не наш выбор
Однако, присмотревшись повнимательнее к математической концепции конечных автоматов, нетрудно заметить, что она мало помогает реализовать настоящий менеджер игровых состояний.
Сразу оговорюсь, что это вовсе не повод отказываться от автоматов вовсе – нужно лишь адаптировать их под нашу задачу. КА используются во многих приложениях, но очень редко – в первозданном виде. Немного отвлекусь от темы и приведу простой пример.
Самая естественная область для конечных автоматов – работа со строками, одна из самых частых задач в алгоритмах на строках – поиск вхождения подстроки (с указанием позиции). Один из алгоритмов, Ахо-Корасик, заключается в построении специального ПДКА (т.н. бор, англ. trie), который распознает необходимые подстроки; затем целевой текст скармливается этому автомату, и мы за чистое время O(n) (не считая времени на построение бора) находим все вхождения всех строк (их может быть не одна, а сразу очень много) в текст.
Но даже здесь мы не можем обойтись классическим конечным автоматом –успех тут определяется не состоянием КА после прочтения всего текста, а фактом прихода его где-то посередине работы в состояние, означающее конец одной из подстрок.
Такие состояния (регистрирующие) помечаются специальным образом, и после каждого перехода мы проверяем, не пришли ли мы в регистрирующее состояние, и если да, то добавляем в список вхождений соответствующей ему подстроки еще одно. При этом регистрирующее состояние также хранит длину своей подстроки, мы всегда знаем номер текущего символа текста, так что вычисление позиции очередного вхождения подстроки не составляет труда.
Итак, даже в таком сравнительно тривиальном и близком к основе основ КА случае мы были вынуждены добавить дополнительные информацию и логику работы к автомату. Для создания менеджера игровых состояний придется поступить похожим образом, правда изменения будут более существенными.
Так какие же все-таки моменты не дают нам использовать КА в нашей задаче?
Первое, что бросается в глаза – это то, что в мат.логике состояния автомата являются некими атомарными объектами без внутренней структуры. Это просто элементы некоторого множества, с которыми можно сопоставить разве что некий номер. В игровом же приложении состояние – это сразу и логика, выраженная в коде, и данные, описывающие игровой мир или загруженные к настоящему моменту ресурсы.
Это приводит нас к тому соображению, что неплохо бы использовать в качестве состояний не их номера, а целые классы (унаследованные от некоторого общего класса GameState). К слову, здесь можно провести параллель с паттерном проектирования State. Однако, в данном паттерне логика переходов зашита внутри каждого отдельного состояния, нам же хочется использовать более гибкую структуру, основанную на таблице переходов.
Следующий момент заключается в том, что описанные ПДКА (и другие эквивалентные им разновидности конечных автоматов) в каждый момент времени находятся строго в одном состоянии и не могут ничего помнить о своем прошлом. Однако, представим себе, что находясь в основном игровом состоянии мы хотим перейти в главное меню (игра при этом должна поставиться на паузу), поменять какие-то настройки, после чего возобновить игру.
В классическом случае при переходе из основного состояния в состояние меню мы безвозвратно потеряли бы «все, что нажито непосильным трудом», и при возвращении из меню вынуждены были довольствоваться в лучшем случае последним сохранением, так как мы фактически заново создаем объект класса CommonGameState.
Конечно, если мы не храним в классах игровых состояний никаких данных вообще (а некоторые данные мы точно храним за пределами этих классов – например ресурсы, которые сначала в одном из них загружаются, а в другом используются), то проблем с потерями не возникнет. Но не факт, что для этих классов будет естественным полное отсутствие каких-либо данных. А искусственно выносить их вовне – плохая идея.
Однако, есть и другой момент. Допустим, в главное меню мы можем попасть как при запуске игры, так и по нажатию клавиши Escво время игрового процесса. Но если находясь в этом меню мы опять нажмем Esc – то что должно произойти? Возврат в игру (если мы до этого были в главном игровом состоянии) или просто игнорирование нажатия (если игра только что запущена)?
Определить ответ на этот вопрос, исходя только из знаний о том, в котором состоянии мы сейчас находимся, и какой управляющий сигнал пришел на вход, невозможно. Так что если мы хотим оставаться в рамках подхода, основанного на конечном автомате, и не жульничаем с записыванием где-то в сторонке дополнительных данных – у нас ничего не выйдет.
Однако, есть способ не нарушать идеологии «все зависит только от состояний и управляющих сигналов». Для этого нам придется в некоторых случаях «запоминать» предыдущие состояния, а именно – помещать их в стек. Тогда после возврата из перекрывающего состояния мы можем извлечь их из стека в том же виде, в котором поместили, и снова передавать им управление.
Проще говоря, при вызове из игры главного меню мы кладем текущее состояние в стек, а управление передаем состоянию меню. Тем самым внутреннее устройство игрового состояния «замораживается» до тех пор, пока оно снова не станет текущим. Сделав все дела в главном меню, мы говорим игре, что готовы вернуться куда-то назад, и поскольку стек действительно не пуст, приложение нас правильно понимает, уничтожает состояние меню, извлекает игровое состояние из стека и передает ему управление. Если бы в стеке ничего не было – команду возврата назад вежливо бы проигнорировали.
Кстати, применение стека дает нам возможность построить целую цепочку состояний, в которые можно будет последовательно вернуться. Хотя вот так навскидку я все же не могу придумать адекватный пример, где это было бы действительно необходимо.
Вообще тонкости организации работы менеджера состояний при наличии стека я рассмотрю в следующем посте, когда буду подробно описывать его реализацию с чисто практической точки зрения. Пока лишь отмечу, что сочетание ПДКА и стека состояний перекликается с т.н. автоматами с магазинной памятью (АМП). Такие автоматы уже не являются эквивалентными ДКА, и распознают более широкий класс языков (например, язык сбалансированных скобок, который не является автоматным/регулярным, то есть ПДКА не распознается).
Еще один момент, отдаляющий нас от чисто математических автоматов, заключается в способе передачи системе управляющих сигналов. В классическом случае мы просто последовательно считывали входную строку и каждый символ передавали на вход КА. Естественно, что в игровом приложении происхождение и природа управляющих сигналов будет существенно иной.
Подходящим вариантом организации передачи управляющих команд менеджеру состояний является пересылка сообщений/событий. При этом сообщение является объектом класса, производного от некоего базового класса сообщения/события и может содержать какие-либо дополнительные данные. При этом то, в какое состояние перейдет игровое приложение, определяется только типом сообщения (грубо говоря, кодом его типа), а дополнительные данные предназначены только для объекта класса-состояния, в которое переходит приложение (например, это может быть имя файла, из которого нужно загрузить данные).
Здесь уместно будет рассмотреть идеи, заложенные в паттерны проектирования Command или Subscriber. Припомним также систему сигналов/слотов, реализованную в Qt, Boost, etc. Конечно, точное копирование здесь будет малополезным, но это хорошая отправная точка при проектировании работы менеджера состояний.
И еще один чисто технический момент заключается в том, что коль скоро для менеджера состояний более естественным будет использование неполного ДКА, то возникает вопрос с интерпретацией неправильного ввода (т.е. попытки выполнить неопределенный переход).
Автомат-распознаватель обычно должен заканчивать свою работу и сообщать о неудаче распознавания; в некоторых задачах естественным будет возвращаться в начальное состояние и продолжать работу как ни в чем не бывало. В нашем же случае неверный ввод как правило можно просто игнорировать.
Таковы вкратце идеи, положенные мной в основу менеджера состояний моей игры. Подробно его структуру я опишу в следующем посте, к тому моменту я также планирую провести экспериментальную их проверку и написать простую игру с использованием менеджера состояний.