При разработке нам понадобился простой конечный автомат, желательно уже реализованный. Из списка реализаций, который предложил гугл, выбрали этот, за простоту и компактность. Используем у себя, в целом FSM неплох. Далее под катом перевод оригинальной статьи автора из Греции Tasos Giannakopoulos. Я не переводчик, поэтому я старался передать смысл, иногда объясняя суть своими словами, за что извиняюсь перед перфекционистами.
Конечный автомат является популярным шаблоном проектирования, который используются разработчиками игр для реализации поведения, к примеру поведения юнитов или каких-то сложных объектов.
Конечный автомат (Finite state machine или FSM в буржуйской терминологии) легко описывается диаграммами и потом программируется, что позволяет использовать его для реализации широкого круга поведений.
По определению сайта AI-depot.com (лучший сайт по AI по мнению автора оригинальной статьи), конечный автомат состоит из четырёх основных элементов:
— состояний, которые определяют поведение и могут производить действия
— переходов состояний, которые определяют переход от одного состояния к другому
— правил и условия, которые должны быть выолнены для перехода
— входных состояний, полученных извне или изнутри, которые могут согласно правилам привести к переходу состояний
Я не буду вдаваться в теорию конечных автоматов, кому надо — есть интернет с кучей подробных статей, а так же есть несколько ссылок в конце статьи.
Чтобы реализовать поведение главного героя, в проекте над которым я сейчас работаю, я использовал FSM. Реализация на C#. На данный момент код далёк от своего конечного вида, но имеет базовый функционал, чего достаточно для объяснения принципа работы FSM.
— Инициализация конечного автомата и набора переходов, определяющего поведение персонажа
— Когда приходят события ввода, делается попытка перевести FSM в соответсвующее состояние
— Если переход возможен, то состояние меняется и вызывается callback для соотсветсвующего перехода
В общем, я хотел что-то, что позволит мне реализовать следующую схему, определяющую поведение персонажа игрока. Кроме того, хотелось бы, чтобы система была расширямой и можно было легко добавить новые состояния и переходы.
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/97e/f08/6e4/97ef086e43b41767a558704e994af27d.png)
Я тут посмотрел, подумал, и решил что на C# эту задачу лучше решать с помощью делегатов. Делегаты в C# — это указатели на функции, что позволяет вызвать функцию из любого места. Они простые в использовании, гибкие, а главное быстро работают (это почти что прямой вызов функции).
![](https://habrastorage.org/r/w780q1/getpro/habr/post_images/696/68f/cc6/69668fcc6a85687fb09dbd3c14c37c86.jpg)
В диаграмме классов выше вы можете увидеть StateTransition которые реализуется через интерфейс IEquatable и FiniteStateMachine, собственно сам интерфейс конечного автомата. Оба класса представляют собой шаблоны, позволяющие пользователю определять состояние. Я использую их с перечислениями (enums), которые позволяют определить список возможных состояний.
StateTransition по сути это C# кортеж (tuple), где в качестве ключа генерится значение по двум состояниям. После того, как я уже реализовал, я узнал что можно сделать проще — реализовать через System.Collections.Generic.KeyValuePair<K, V>, где K и V — возможные состояния. Но так как я не уверен что переход с кортежа на KeyValuePair даст прирост скорости, решил оставить всё как есть.
В конце статьи вы найдёте ссылку на исходники моей реализации. Просто распакуйте, и используйте, как в примере, приведённом ниже. Я уже говорил, что FSM далека от завершения, но она обеспечивает базовую функциональность, и может быть отправной точкой для других проектов.
Для начала создайте перечислиние всех состояний вашего объекта и передайте их в FiniteStateMachine.
Вы должны создать кучу функций, которые реализуют поведение вашего объекта, у меня к примеру это Run(), Idle(), IdleJump() и другие. Затем с помощью AddTransition() добавьте желаемые переходы между состояниями. При соблюдении определённых условий, вы вызываете Advance() для того, чтобы попытаься переключиться в нужное состояние. Если переход из текущего состояние возможен, то вызывается функция, определённая пользователем.
Приведённый ниже код реализует часть поведения моего персонажа. Этого фрагмента кода достаточно для понимания, как использовать FSM.
Исходник FSM
https://en.wikipedia.org/wiki/Finite-state_machine
http://ai-depot.com/FiniteStateMachines/FSM.html
http://jessewarden.com/2012/07/finite-state-machines-in-game-development.html
http://unitygems.com/fsm2/
Автор оригинальной статьи: Tasos Giannakopoulos.
Что такое Конечный автомат?
Конечный автомат является популярным шаблоном проектирования, который используются разработчиками игр для реализации поведения, к примеру поведения юнитов или каких-то сложных объектов.
Конечный автомат (Finite state machine или FSM в буржуйской терминологии) легко описывается диаграммами и потом программируется, что позволяет использовать его для реализации широкого круга поведений.
По определению сайта AI-depot.com (лучший сайт по AI по мнению автора оригинальной статьи), конечный автомат состоит из четырёх основных элементов:
— состояний, которые определяют поведение и могут производить действия
— переходов состояний, которые определяют переход от одного состояния к другому
— правил и условия, которые должны быть выолнены для перехода
— входных состояний, полученных извне или изнутри, которые могут согласно правилам привести к переходу состояний
Я не буду вдаваться в теорию конечных автоматов, кому надо — есть интернет с кучей подробных статей, а так же есть несколько ссылок в конце статьи.
Зачем всё это?
Чтобы реализовать поведение главного героя, в проекте над которым я сейчас работаю, я использовал FSM. Реализация на C#. На данный момент код далёк от своего конечного вида, но имеет базовый функционал, чего достаточно для объяснения принципа работы FSM.
— Инициализация конечного автомата и набора переходов, определяющего поведение персонажа
— Когда приходят события ввода, делается попытка перевести FSM в соответсвующее состояние
— Если переход возможен, то состояние меняется и вызывается callback для соотсветсвующего перехода
В общем, я хотел что-то, что позволит мне реализовать следующую схему, определяющую поведение персонажа игрока. Кроме того, хотелось бы, чтобы система была расширямой и можно было легко добавить новые состояния и переходы.
![](https://habrastorage.org/getpro/habr/post_images/97e/f08/6e4/97ef086e43b41767a558704e994af27d.png)
Проектирование и реализация
Я тут посмотрел, подумал, и решил что на C# эту задачу лучше решать с помощью делегатов. Делегаты в C# — это указатели на функции, что позволяет вызвать функцию из любого места. Они простые в использовании, гибкие, а главное быстро работают (это почти что прямой вызов функции).
![](https://habrastorage.org/getpro/habr/post_images/696/68f/cc6/69668fcc6a85687fb09dbd3c14c37c86.jpg)
В диаграмме классов выше вы можете увидеть StateTransition которые реализуется через интерфейс IEquatable и FiniteStateMachine, собственно сам интерфейс конечного автомата. Оба класса представляют собой шаблоны, позволяющие пользователю определять состояние. Я использую их с перечислениями (enums), которые позволяют определить список возможных состояний.
StateTransition по сути это C# кортеж (tuple), где в качестве ключа генерится значение по двум состояниям. После того, как я уже реализовал, я узнал что можно сделать проще — реализовать через System.Collections.Generic.KeyValuePair<K, V>, где K и V — возможные состояния. Но так как я не уверен что переход с кортежа на KeyValuePair даст прирост скорости, решил оставить всё как есть.
В конце статьи вы найдёте ссылку на исходники моей реализации. Просто распакуйте, и используйте, как в примере, приведённом ниже. Я уже говорил, что FSM далека от завершения, но она обеспечивает базовую функциональность, и может быть отправной точкой для других проектов.
Как использовать
Для начала создайте перечислиние всех состояний вашего объекта и передайте их в FiniteStateMachine.
// Add the possible states here
public enum eCharacterState
{
IDLE,
RUN,
// ...
};
public class CharacterFSM : FiniteStateMachine<eCharacterState> {};
Вы должны создать кучу функций, которые реализуют поведение вашего объекта, у меня к примеру это Run(), Idle(), IdleJump() и другие. Затем с помощью AddTransition() добавьте желаемые переходы между состояниями. При соблюдении определённых условий, вы вызываете Advance() для того, чтобы попытаься переключиться в нужное состояние. Если переход из текущего состояние возможен, то вызывается функция, определённая пользователем.
Приведённый ниже код реализует часть поведения моего персонажа. Этого фрагмента кода достаточно для понимания, как использовать FSM.
public class Player : CatGameItem
{
// ...
public CharacterFSM mFSM;
void Start ()
{
mFSM = new CharacterFSM();
// Add state transitions here
mFSM.AddTransition(eCharacterState.IDLE, eCharacterState.RUN, Run);
mFSM.AddTransition(eCharacterState.RUN, eCharacterState.IDLE, Idle);
// This calls the Run() function while on run state.
// I will probably replace it with with a state callback or something similar sometime in the future to avoid calling TryGetValue all the time.
mFSM.AddTransition(eCharacterState.RUN, eCharacterState.RUN, Run);
// ...
}
// FSM Delegates
void Run()
{
//Debug.Log("RUN!");
float curMoveSpeed = Controller.GetGroundSpeed();
AnimationController.SetSpeed("Cat_Run", curMoveSpeed/RunSpeed);
AnimationController.Play("Cat_Run");
}
void Idle()
{
AnimationController.Play("Cat_Idle_Breath");
}
// ...
void UpdateInput()
{
mCurAxisInput.x = Input.GetAxis("LeftAxisH"); // Get Horizontal axis (XBox360 xAxis OR 'A', 'D')
mCurAxisInput.y = Input.GetAxis("LeftAxisV"); // Get Vertical axis (XBox360 yAxis OR 'W', 'S')
}
void UpdateStateMachine()
{
// Based on the input events, advance to desired state
// Run, Idle
if (mCurAxisInput.magnitude > 0)
mFSM.Advance(eCharacterState.RUN);
else
mFSM.Advance(eCharacterState.IDLE);
// ...
}
void FixedUpdate()
{
// Update the state machine here
UpdateStateMachine();
}
void Update ()
{
// Update user input
UpdateInput();
UpdateCharacterMovement();
}
}
Исходник FSM
Ссылки на статьи по теме:
https://en.wikipedia.org/wiki/Finite-state_machine
http://ai-depot.com/FiniteStateMachines/FSM.html
http://jessewarden.com/2012/07/finite-state-machines-in-game-development.html
http://unitygems.com/fsm2/
Автор оригинальной статьи: Tasos Giannakopoulos.