FiniteStateMachine

Лучший способ помочь другим, поделиться своими находками.

FiniteStateMachine

Сообщение _Disa_ 11 авг 2012, 01:41

Для нужд сообщества и для тестирования класса (ну или в обратном порядке :D ).

Конечный автомат (мб детерминированный, мб вероятностный), основанный на делегатах и строках.

Тянем с гитхаба:
https://github.com/IslamovDenis/Csharp-FSM-

Сразу прошу прощения - README писал ночью, там скорее всего ошибки и мб не очень все ясно изложено. Завтра днем переделаю. В общем-то с экзамплом должно быть ясно что происходит.

Пока example - консольное приложение, в ближайшем будущем сделаю package для Юньки.

Огромная просьба, всем пользующимся - по возможности напишите багрепорт на почту (ошибку и схему действий, которая к ней привеля):
islamov.denisсабакаgmail.com

Я весь день тестил, вроде все окей.
ArShift
_Disa_
UNIт
 
Сообщения: 97
Зарегистрирован: 07 мар 2012, 09:07
Откуда: Нерезиновая
Skype: islamov_denis
  • Сайт

Re: FiniteStateMachine

Сообщение Syberex 11 авг 2012, 03:24

_Disa_ писал(а):Для нужд сообщества и для тестирования класса (ну или в обратном порядке ).

Нужно было в раздел Исходники ложить.

_Disa_ писал(а):Пока example - консольное приложение, в ближайшем будущем сделаю package для Юньки.

Если экземпл это файл Main.cs, то там видно только пример описания конечного автомата с ипользованием класса FiniteStateMachine, а примера использования описанного автомата нет, но хотелось бы :)
Аватара пользователя
Syberex
Адепт
 
Сообщения: 2292
Зарегистрирован: 14 янв 2011, 20:35
Откуда: Кострома
  • Сайт

Re: FiniteStateMachine

Сообщение _Disa_ 12 авг 2012, 00:06

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

Концептуально - делегат описывает состояние и вызывается после того как происходит событие связывающие его с предыдущим состоянием или переходом ("finish transition"). Чтоб можно было видеть весь граф, можно сохранить весь КА в формат .dot и открыть прогой от ATundT (там же, в ридми описано).

То есть например, хотим чтоб что-то крутилось по кругу:

Синтаксис:
Используется cpp
public void Rotate()
{
  // крутим-вертим что-то
}

void Start()
{
 // инициализируем КА (fsm.AddState, fsm.AddTransition, fsm.AddEvent)
}

void Update()
{
  // вызываем event (EventHappen) который приводит к State связанному с Rotate и
  // EventHappen("finish transition") если еще было переходное состояние в случае его окончания (например, какая-то функция таймер).
}


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

Обращайте внимание на ексепшены - нельзя добавлять существующие элементы или связывать не существующие, иначе ломается структура КА.

Так же думал про сигнатуру делегатов, имеет ли смысл добавлять параметр ref object или params object[] arg(буду благодарен, если скажите нужно ли указывать ref тут) в аргументе. Лично мне это не нужно, т.к. буду использовать КА только в скриптах и там все переменные в общем-то можно вызывать без передачи в функцию. Но с другой стороны хочется сделать хорошую абстракцию, и учитывая контравариантность делегатов, то можно было бы передать любые параметры.
ArShift
_Disa_
UNIт
 
Сообщения: 97
Зарегистрирован: 07 мар 2012, 09:07
Откуда: Нерезиновая
Skype: islamov_denis
  • Сайт

Re: FiniteStateMachine

Сообщение AndreyMust19 12 авг 2012, 13:24

Не совсем понял что делает ваш класс, то что он реализует конечный автомат - понятно по названию. Тогда если State - это состояние (A), Transition - переход (A1 -> A2), то что такое событие (Event)? Входной сигнал? А где тогда выходной?
Или вместо выходного сигнала вызывается функция, указанная при добавлении правила перехода в новое состояние? Такт автомата происходит при вызове EventHappen, где указывается входной сигнал, т. е. ваш автомат асинхронный и выполняет переход как только появится входной сигнал.
Зачем нужны функции удаления состояний, переходов и вх. сигналов? Уж если создали автомат, то предполагается что его структура не изменится. Иначе может возникнуть неопределенное состояние вроде разбиения автомата на 2 несвязанных графа или отсутствие возможности попасть в какое-то состояние, куда можно было перейти только при возникновении удаленного события.

Если я не ошибся, то все правила вы записываете в виде текста в формате "X -> Y" и сделано это наверняка для того чтобы можно было менять логику работы автомата. Почему вы не решили описывать автомат матрицей переходов и матрицей выходных функций, а кол-во вх. сигналов, состояний и вых. сигналов указывать при создании автомата?
И если у вас есть SaveToFile то почему не сделали LoadFromFile? При условии что все файлы с описаниями автоматов грузились в память процесса на стадии запуска, то чтение автомата из памяти намного бы ускорило его создание по сравнению с многочисленными вызовами Add-методов. Или вы сохраняете в файл только для отладки?
Нужна помощь? Сами, сами, сами, сами, сами... делаем все сами
AndreyMust19
Адепт
 
Сообщения: 1119
Зарегистрирован: 07 июн 2011, 13:19

Re: FiniteStateMachine

Сообщение _Disa_ 13 авг 2012, 00:11

1) Ответы на половину ваших вапросов есть в README. Если плохо знаете англицкий (хотя я писал на таком чукотском, что можно понять даже не зная), то вот:

State состояние, Transition тот же state, для перехода которому требуется Event - finish state. Пример использования:
У персонажа 2а состояния - ничего не делать и кипятить чайник. Для выполнения обоих нужно сделать переходное состояние - налить воду, вариант реализации:
Добавляем персонажу состояние наливания воды и соответствующий сигнал его начала и завершения.
Либо добавляем transition и просто говорим finish transition когда вода налита. Это сделано для того чтоб автомат не разростался и был менее разряжен чем мог бы быть.

т. е. ваш автомат асинхронный и выполняет переход как только появится входной сигнал.

Именно так. Состояние переходит из одного в другое в любой момент, если инициализирован соответствующий эвент. Выходной сигнал описывает функция делегат, на то она и передается в событие или переход.

Зачем нужны функции удаления состояний, переходов и вх. сигналов?


Маштабируемость. Если на написал автомат на 200 событий и тут мне потребовалась его реализация на такие же 180 - инициализировать заново?

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

Пока да, это у меня в TODO (запрет разбитие на несвязанный граф)

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

Какой именно матрицей? Инцидентности или смежности? Я знаю что граф обычно описывают ими, но для понимания логики они не очень удобны, как только у вас появляется более 20ти вершин графа. Напишите такую матрицу и потом посмотрите сколько времени у вас займет восстановление ее с ручкой и бумажкой в видел графа на бумаге.

Удобно наверное было бы сделать State отдельным объектом и хранить в каждом State структуру в которой хранился бы указатель на смежную вершину и указатель на функцию делегат (или сам делегат, я не знаю как это делает шарп, в плюсах точно был бы указатель), но я там наворотил бы ошибок которых правил бы еще месяц. И вообще стараюсь придерживатся правила не использовать ссылки и указатели без лишней надобности. Мб есть какой-то мизерный прирост памяти и скорости, но учитывая что это сделанно для игрового 3d движка, где почти все ресурсы сожрет графика - это похоже на идиотизм. Это примерно как если бы вы у плешивой собаки стали мыть лечебным шампунем только конец хвоста.

PS: Нотацию a->b украл у *.dot формата, уж больно понравилась.

LoadFromFile?

Если мне кто-то скажет, что можно как-то загрузить описание делегата из файла, я буду признателен. А то получится кучу состояний, которые ничего не делают и их все равно нужно потом инициализировать.
ArShift
_Disa_
UNIт
 
Сообщения: 97
Зарегистрирован: 07 мар 2012, 09:07
Откуда: Нерезиновая
Skype: islamov_denis
  • Сайт

Re: FiniteStateMachine

Сообщение seaman 13 авг 2012, 07:36

Делал я как-то такое (см подпись). Однако мне не понравилась такая реализация. Нужно писать редактор FSM желательно графический, иначе достаточно быстро начинаешь путаться. И transition не помогут.
ЗЫ: в Antares Univers есть FSM с редактором.
seaman
Адепт
 
Сообщения: 8352
Зарегистрирован: 24 янв 2011, 12:32
Откуда: Самара

Re: FiniteStateMachine

Сообщение _Disa_ 13 авг 2012, 09:11

Это как раз следующая стадия - сделать граф. редактов в Юньке, в начале отображение (это халява), потом и редактирование (пока просто не писал плагины, поэтому не знаю).
ArShift
_Disa_
UNIт
 
Сообщения: 97
Зарегистрирован: 07 мар 2012, 09:07
Откуда: Нерезиновая
Skype: islamov_denis
  • Сайт

Re: FiniteStateMachine

Сообщение AndreyMust19 13 авг 2012, 13:10

_Disa_
Какой именно матрицей?

Для матрицы переходов - первый индекс это вх. сигнал, второй - состояния. Элементы массивы содержат новые состояния.
Если автомат Мили, то таблица выходных сигналов заполняется так же (только вместо новых состояний храняться выходные сигналы). Если Мура, то достаточно одномерного массива.
И еще надо знать количество входных сигналов, выходных сигналов и состояний, а также начальное состояние. Это просто другой способ задания ЦА (не графом).
Напишите такую матрицу и потом посмотрите сколько времени у вас займет восстановление ее с ручкой и бумажкой в видел графа на бумаге.

Зачем? Ведь в виде текста все читабельно, а матрицы - это конечные данные, с к-ми удобно работать программе. При создании автомата вы передаете программе этот текст, а из него она сама создает конечные данные (т. е. переводит из человеческой формы в машинную). В вашем случае структура автомата остается на человеческом языке.
Нужна помощь? Сами, сами, сами, сами, сами... делаем все сами
AndreyMust19
Адепт
 
Сообщения: 1119
Зарегистрирован: 07 июн 2011, 13:19

Re: FiniteStateMachine

Сообщение _Disa_ 13 авг 2012, 21:51

Жестко налажал в двух местах, сейчас правлю. В консоли по прежнему работает, а в Юньки нужно было сделать "синхронизацию" с апдейтом. Забыл что все будет все время в цикле крутиться и eventHappen тоже.

Поботаю сейчас про матрицы - подумаю, мб и вправду лучше. Я просто автоматы кодил только для работы со строками и там либо матрицы графов, либо все делалось связными списками (что удобнее т.к. графы часто разряженные).
Позор мне! Про Мили и Мура не знал :(
ArShift
_Disa_
UNIт
 
Сообщения: 97
Зарегистрирован: 07 мар 2012, 09:07
Откуда: Нерезиновая
Skype: islamov_denis
  • Сайт

Re: FiniteStateMachine

Сообщение _Disa_ 15 авг 2012, 15:01

Вроде поправил. Клонируем репозиторий с Github'а.

Буду очень признателен тем, кто найдет время найти ошибки и написать мне о них.
ArShift
_Disa_
UNIт
 
Сообщения: 97
Зарегистрирован: 07 мар 2012, 09:07
Откуда: Нерезиновая
Skype: islamov_denis
  • Сайт


Вернуться в Исходники (Копилка)

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3