Русский
Русский
English
Статистика
Реклама

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

image

Привет, Хабр!

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


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


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


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


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


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

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


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


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


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


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


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


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


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


image


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


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

Возможности


Две темы


image


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


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

Валидация


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

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


image


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


image


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


image


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


image


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


image


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


image


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


image


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


image


Импорт/Экспорт из/в 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


image


Библиотека


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


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

    StateMachine stateMachine = new StateMachine("scheme.xml");<br>
    
  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

Источник: habr.com
К списку статей
Опубликовано: 01.07.2020 18:14:54
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Net

C

Программирование

State machine

Simplestatemachine

Finite state machine

Категории

Последние комментарии

© 2006-2020, personeltest.ru