Самые простые конечные автоматы или стейт-машины в три шага

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

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

Вскоре я наткнулся на эту статью, которая подтвердила отсутствие удобных решений.

Что сделал тогда?

Так как задачу требовалось решить быстро (ну как обычно), то мой конечный автомат был реализован с помощью словарей, то есть:

• есть список состояний (Enum)
• список сигналов (замена классическому входному алфавиту)
• словарь (map): состояние-сигнал-состояние

Таким образом, в нужном месте функция «издает сигнал» и, в зависимости от текущего состояния и сигнала, происходит переход (устанавливается следующее состояние)

Но что дальше?

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

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

Спустя год разработки...

Графический редактор

Реализован на wpf с использованием ReactiveUI.

Тут у нас структура конечного автомата в виде графа и в виде таблицы переходов.
Накидываем узлы, соединяем их и сохраняем в xml файл.

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

Для тех, кому неохота клацать на ссылку (лень переходить в репозиторий)

Возможности

Две темы

Два представления конечного автомата:

• в виде графа
• в виде таблицы переходов

Валидация

• уникальные имена для состояний и переходов
• отсутствие достижимых состояний (состояний без переходов)

Добавление узлов и соединений

Отмена действий

Сворачивание и перемещение узлов

Масштабирование

Выделение элементов

Наименования для состояний и переходов

Перемещение переходов

Удаление переходов

Импорт/Экспорт из/в xml

<?xml version="1.0" encoding="utf-8"?>
<StateMachine>
  <States>
    <State Name="Start" Position="37, 80" IsCollapse="False" />
    <State Name="State 1" Position="471, 195.54" IsCollapse="False" />
    <State Name="State 2" Position="276, 83.03999999999999" IsCollapse="False" />
  </States>
  <StartState Name="Start" />
  <Transitions>
    <Transition Name="Transition 2" From="State 2" To="State 1" />
    <Transition Name="Transition 1" From="Start" To="State 2" />
  </Transitions>
</StateMachine>

Сохранение схемы в PNG/JPEG

Библиотека

Реализуем конечный автомат в три шага:

1. Создаем конечный автомат и инициализируем его структуру сохраненным из редактора файлом.
   
   

   StateMachine stateMachine = new StateMachine("scheme.xml");

2. Основную логику описываем в методах, которые затем «навешиваем» на события, которых предоставляется достаточно.
   
   

   stateMachine.GetState("State1").OnExit(Action1);
   stateMachine.GetState("State2").OnEntry(Action2);
   stateMachine.GetTransition("Transition1").OnInvoke(Action3);
   stateMachine.OnChangeState(Action4);

3. Запускаем.
   
   

   stateMachine.Start(parameters);

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

А что с переходами?

Для перехода внутри функции, которая обрабатывает Entry/Exit в состояние, вызываем:

StateMachine.InvokeTransition("Transition1", parameters);

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

Что есть ещё?

• Параметры для переходов и состояний.
• Data — словарь с данными, которые хранятся внутри StateMachine и используются для обмена данными между состояниями.

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

Для тех, кому неохота клацать на ссылку (лень переходить в репозиторий)

Возможности:

• Начальное состояние
• События входа и выхода для состояния
• Событие выполнение для перехода
• Параметры для перехода
• Параметры для входа/выхода состояния
• Событие изменения состояния
• Данные для обмена между состояниями
• Событие изменения данных
• Импорт/Экспорт из/в xml
• Логирование

Будущее проекта

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

Библиотека. Возможные улучшения:

1. Асинхронность
2. Таймеры
3. Вложенные конечные автоматы
4. Магия работы с элементами из схемы

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

И работа с ними происходит так:

stateMachine.GetState("State1");

А хотелось бы так

stateMachine.State1;

Сразу скажу, что dynamic не подойдет так как все равно нужно помнить название.
Тут наверное нужна какая-то кодо-генерация, но решение пока что не нашел.

Графический редактор. Возможные улучшения:

1. Локализация
2. Шейдеры для отрисовки элементов схемы.
3. Вложенные конечные автоматы
4. Автораспределение узлов
   — волшебная кнопка автокомпоновки элементов на канвасе
5. Кроссплатформенность
   — Перевод проекта на AvaloniaUI

Выводы

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

Ссылки

Графический редактор, исходники на GitHub: SimpleStateMachineNodeEditor
Библиотека, исходники на GitHub: SimpleStateMachineLibrary