Простой пример конечного автомата в C #? - PullRequest
237 голосов
/ 08 мая 2011

Обновление:

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

Разве приведенные в настоящее время примеры, насколько я понимаю их и конечных автоматов, не являются лишь половиной того, что мы обычно понимаем под конечным автоматом?
В том смысле, что примеры меняют состояние, но это представлено только изменением значения переменной (и разрешением разных изменений значения в разных состояниях), в то время как обычно конечный автомат должен также изменять свое поведение, а поведение не (только) в смысл разрешения различных изменений значений для переменной в зависимости от состояния, но в смысле разрешения выполнения различных методов для разных состояний.

Или у меня неправильное представление о конечных автоматах и ​​их общем использовании?

С наилучшими пожеланиями


Оригинальный вопрос:

Я нашел это обсуждение о конечных автоматах и ​​блоках итераторов в c # и инструментах для создания конечных автоматов, а не в C #, так что я нашел много абстрактных вещей, но в качестве нуба все это немного сбивает с толку.

Так что было бы замечательно, если бы кто-то мог предоставить пример исходного кода C #, который реализует простой конечный автомат с, возможно, 3,4 состояниями, просто чтобы понять его суть.


Ответы [ 18 ]

391 голосов
/ 08 мая 2011

Давайте начнем с этой простой диаграммы состояний:

simple state machine diagram

Имеется:

  • 4 состояния (Неактивно, Активно, Пауза и Выход)
  • 5 типов переходов между состояниями (команда «Начало», «Команда конца», «Команда паузы», «Команда возобновления», «Команда выхода»).

Вы можете преобразовать это в C # внесколько способов, таких как выполнение оператора switch для текущего состояния и команды или поиск переходов в таблице переходов.Для этого простого конечного автомата я предпочитаю таблицу переходов, которую очень легко представить с помощью Dictionary:

using System;
using System.Collections.Generic;

namespace Juliet
{
    public enum ProcessState
    {
        Inactive,
        Active,
        Paused,
        Terminated
    }

    public enum Command
    {
        Begin,
        End,
        Pause,
        Resume,
        Exit
    }

    public class Process
    {
        class StateTransition
        {
            readonly ProcessState CurrentState;
            readonly Command Command;

            public StateTransition(ProcessState currentState, Command command)
            {
                CurrentState = currentState;
                Command = command;
            }

            public override int GetHashCode()
            {
                return 17 + 31 * CurrentState.GetHashCode() + 31 * Command.GetHashCode();
            }

            public override bool Equals(object obj)
            {
                StateTransition other = obj as StateTransition;
                return other != null && this.CurrentState == other.CurrentState && this.Command == other.Command;
            }
        }

        Dictionary<StateTransition, ProcessState> transitions;
        public ProcessState CurrentState { get; private set; }

        public Process()
        {
            CurrentState = ProcessState.Inactive;
            transitions = new Dictionary<StateTransition, ProcessState>
            {
                { new StateTransition(ProcessState.Inactive, Command.Exit), ProcessState.Terminated },
                { new StateTransition(ProcessState.Inactive, Command.Begin), ProcessState.Active },
                { new StateTransition(ProcessState.Active, Command.End), ProcessState.Inactive },
                { new StateTransition(ProcessState.Active, Command.Pause), ProcessState.Paused },
                { new StateTransition(ProcessState.Paused, Command.End), ProcessState.Inactive },
                { new StateTransition(ProcessState.Paused, Command.Resume), ProcessState.Active }
            };
        }

        public ProcessState GetNext(Command command)
        {
            StateTransition transition = new StateTransition(CurrentState, command);
            ProcessState nextState;
            if (!transitions.TryGetValue(transition, out nextState))
                throw new Exception("Invalid transition: " + CurrentState + " -> " + command);
            return nextState;
        }

        public ProcessState MoveNext(Command command)
        {
            CurrentState = GetNext(command);
            return CurrentState;
        }
    }


    public class Program
    {
        static void Main(string[] args)
        {
            Process p = new Process();
            Console.WriteLine("Current State = " + p.CurrentState);
            Console.WriteLine("Command.Begin: Current State = " + p.MoveNext(Command.Begin));
            Console.WriteLine("Command.Pause: Current State = " + p.MoveNext(Command.Pause));
            Console.WriteLine("Command.End: Current State = " + p.MoveNext(Command.End));
            Console.WriteLine("Command.Exit: Current State = " + p.MoveNext(Command.Exit));
            Console.ReadLine();
        }
    }
}

В порядке личных предпочтений мне нравится конструировать свои конечные автоматы с помощью *Функция 1020 * для возврата следующего состояния детерминистически и функция MoveNext для изменения конечного автомата.

70 голосов
/ 10 мая 2011

Возможно, вы захотите использовать один из существующих конечных автоматов с открытым исходным кодом.Например, bbv.Common.StateMachine находится по адресу http://code.google.com/p/bbvcommon/wiki/StateMachine.. Он имеет очень интуитивный свободный синтаксис и множество функций, таких как действия входа / выхода, действия перехода, охранники, иерархическая, пассивная реализация (выполняется в потокевызывающая программа) и активная реализация (собственный поток, в котором выполняется fsm, события добавляются в очередь).

На примере Джульетта определение конечного автомата становится очень простым:

var fsm = new PassiveStateMachine<ProcessState, Command>();
fsm.In(ProcessState.Inactive)
   .On(Command.Exit).Goto(ProcessState.Terminated).Execute(SomeTransitionAction)
   .On(Command.Begin).Goto(ProcessState.Active);
fsm.In(ProcessState.Active)
   .ExecuteOnEntry(SomeEntryAction)
   .ExecuteOnExit(SomeExitAction)
   .On(Command.End).Goto(ProcessState.Inactive)
   .On(Command.Pause).Goto(ProcessState.Paused);
fsm.In(ProcessState.Paused)
   .On(Command.End).Goto(ProcessState.Inactive).OnlyIf(SomeGuard)
   .On(Command.Resume).Goto(ProcessState.Active);
fsm.Initialize(ProcessState.Inactive);
fsm.Start();

fsm.Fire(Command.Begin);

Обновление : Местоположение проекта перемещено в: https://github.com/appccelerate/statemachine

48 голосов
/ 08 мая 2011

Вот пример очень классического конечного автомата, моделирующего очень упрощенное электронное устройство (например, телевизор)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace fsm
{
class Program
{
    static void Main(string[] args)
    {
        var fsm = new FiniteStateMachine();
        Console.WriteLine(fsm.State);
        fsm.ProcessEvent(FiniteStateMachine.Events.PlugIn);
        Console.WriteLine(fsm.State);
        fsm.ProcessEvent(FiniteStateMachine.Events.TurnOn);
        Console.WriteLine(fsm.State);
        fsm.ProcessEvent(FiniteStateMachine.Events.TurnOff);
        Console.WriteLine(fsm.State);
        fsm.ProcessEvent(FiniteStateMachine.Events.TurnOn);
        Console.WriteLine(fsm.State);
        fsm.ProcessEvent(FiniteStateMachine.Events.RemovePower);
        Console.WriteLine(fsm.State);
        Console.ReadKey();
    }

    class FiniteStateMachine
    {
        public enum States { Start, Standby, On };
        public States State { get; set; }

        public enum Events { PlugIn, TurnOn, TurnOff, RemovePower };

        private Action[,] fsm;

        public FiniteStateMachine()
        {
            this.fsm = new Action[3, 4] { 
                //PlugIn,       TurnOn,                 TurnOff,            RemovePower
                {this.PowerOn,  null,                   null,               null},              //start
                {null,          this.StandbyWhenOff,    null,               this.PowerOff},     //standby
                {null,          null,                   this.StandbyWhenOn, this.PowerOff} };   //on
        }
        public void ProcessEvent(Events theEvent)
        {
            this.fsm[(int)this.State, (int)theEvent].Invoke();
        }

        private void PowerOn() { this.State = States.Standby; }
        private void PowerOff() { this.State = States.Start; }
        private void StandbyWhenOn() { this.State = States.Standby; }
        private void StandbyWhenOff() { this.State = States.On; }
    }
}
}
20 голосов
/ 15 октября 2012

Некоторая бесстыдная самореклама здесь, но некоторое время назад я создал библиотеку под названием YieldMachine , которая позволяет описать конечный автомат ограниченной сложности очень простым и понятным способом. Например, рассмотрим лампу:

state machine of a lamp

Обратите внимание, что этот конечный автомат имеет 2 триггера и 3 состояния. В коде YieldMachine мы пишем единый метод для всего поведения, связанного с состоянием, в котором мы совершаем ужасное злодеяние использования goto для каждого состояния. Триггер становится свойством или полем типа Action, украшенным атрибутом с именем Trigger. Я прокомментировал код первого состояния и его переходы ниже; следующие состояния следуют той же схеме.

public class Lamp : StateMachine
{
    // Triggers (or events, or actions, whatever) that our
    // state machine understands.
    [Trigger]
    public readonly Action PressSwitch;

    [Trigger]
    public readonly Action GotError;

    // Actual state machine logic
    protected override IEnumerable WalkStates()
    {
    off:                                       
        Console.WriteLine("off.");
        yield return null;

        if (Trigger == PressSwitch) goto on;
        InvalidTrigger();

    on:
        Console.WriteLine("*shiiine!*");
        yield return null;

        if (Trigger == GotError) goto error;
        if (Trigger == PressSwitch) goto off;
        InvalidTrigger();

    error:
        Console.WriteLine("-err-");
        yield return null;

        if (Trigger == PressSwitch) goto off;
        InvalidTrigger();
    }
}

Коротко и красиво, а!

Этот конечный автомат управляется просто отправкой ему триггеров:

var sm = new Lamp();
sm.PressSwitch(); //go on
sm.PressSwitch(); //go off

sm.PressSwitch(); //go on
sm.GotError();    //get error
sm.PressSwitch(); //go off

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

    protected override IEnumerable WalkStates()
    {
    off:                                       // Each goto label is a state

        Console.WriteLine("off.");             // State entry actions

        yield return null;                     // This means "Wait until a 
                                               // trigger is called"

                                               // Ah, we got triggered! 
                                               //   perform state exit actions 
                                               //   (none, in this case)

        if (Trigger == PressSwitch) goto on;   // Transitions go here: 
                                               // depending on the trigger 
                                               // that was called, go to
                                               // the right state

        InvalidTrigger();                      // Throw exception on 
                                               // invalid trigger

        ...

Это работает, потому что компилятор C # фактически создал конечный автомат для каждого метода, который использует yield return. Эта конструкция обычно используется для ленивого создания последовательностей данных, но в этом случае нас на самом деле не интересует возвращаемая последовательность (которая в любом случае равна нулю), а поведение поведения, которое создается внутри.

Базовый класс StateMachine делает некоторые размышления о конструкции для назначения кода каждому действию [Trigger], которое устанавливает элемент Trigger и перемещает конечный автомат вперед.

Но на самом деле вам не нужно понимать внутренности, чтобы иметь возможность его использовать.

10 голосов
/ 08 мая 2011

Вы можете закодировать блок итератора, который позволит вам выполнить блок кода организованным способом. То, как кодовый блок разбит на части, на самом деле не должно соответствовать чему-либо, просто то, как вы хотите его кодировать. Например:

IEnumerable<int> CountToTen()
{
    System.Console.WriteLine("1");
    yield return 0;
    System.Console.WriteLine("2");
    System.Console.WriteLine("3");
    System.Console.WriteLine("4");
    yield return 0;
    System.Console.WriteLine("5");
    System.Console.WriteLine("6");
    System.Console.WriteLine("7");
    yield return 0;
    System.Console.WriteLine("8");
    yield return 0;
    System.Console.WriteLine("9");
    System.Console.WriteLine("10");
}

В этом случае, когда вы вызываете CountToTen, на самом деле ничего еще не выполняется. Фактически вы получаете генератор конечных автоматов, для которого вы можете создать новый экземпляр конечного автомата. Вы делаете это, вызывая GetEnumerator (). Получающийся IEnumerator фактически является конечным автоматом, который вы можете использовать, вызывая MoveNext (...).

Таким образом, в этом примере при первом вызове MoveNext (...) вы увидите «1», записанное в консоль, а при следующем вызове MoveNext (...) вы увидите 2, 3, 4, а затем 5, 6, 7, а затем 8, а затем 9, 10. Как видите, это полезный механизм для организации того, как все должно происходить.

8 голосов
/ 11 мая 2011

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

Мой оригинальный ответ - классический, непостоянный код.Я думаю, что это довольно наглядно, поскольку код идет из-за массива, который делает визуализацию конечного автомата простой.Недостатком является то, что вы должны написать все это. Remos * Ответ 1004 * облегчает написание кода, но гораздо менее нагляден.Есть третья альтернатива;действительно рисует конечный автомат.

Если вы используете .NET и можете ориентироваться на версию 4 времени выполнения, тогда у вас есть возможность использовать действия конечного автомата рабочего процесса .По сути, они позволяют вам нарисовать конечный автомат (так же, как на диаграмме Джульетта ) и заставить среду выполнения WF выполнить его за вас.

См. Статью MSDN Создание машин состоянийс Windows Workflow Foundation для получения более подробной информации и этого сайта CodePlex для последней версии.

Это вариант, который я всегда предпочел бы при ориентации на .NET, поскольку его легко увидеть, изменитьи объяснить не программистам;картинки стоят тысячи слов, как говорится!

7 голосов
/ 08 мая 2011

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

Например, вы можете реализовать конечный автомат с функциями:

void Hunt(IList<Gull> gulls)
{
    if (gulls.Empty())
       return;

    var target = gulls.First();
    TargetAcquired(target, gulls);
}

void TargetAcquired(Gull target, IList<Gull> gulls)
{
    var balloon = new WaterBalloon(weightKg: 20);

    this.Cannon.Fire(balloon);

    if (balloon.Hit)
    {
       TargetHit(target, gulls);
    }
    else
       TargetMissed(target, gulls);
}

void TargetHit(Gull target, IList<Gull> gulls)
{
    Console.WriteLine("Suck on it {0}!", target.Name);
    Hunt(gulls);
}

void TargetMissed(Gull target, IList<Gull> gulls)
{
    Console.WriteLine("I'll get ya!");
    TargetAcquired(target, gulls);
}

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

Каждая функция соответствует каждому состоянию; начальное и конечное состояния (или accept ) не отображаются. Хотя там, вероятно, больше состояний, чем моделируется функциями. Например, после запуска воздушного шара машина действительно находится в другом состоянии, чем это было до нее, но я решил, что сделать это различие нецелесообразно.

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

6 голосов
/ 07 ноября 2013

Сегодня я глубоко в государстве шаблон проектирования. Я сделал и протестировал ThreadState, который равен (+/-) Threading в C #, как описано на рисунке из Threading в C #

enter image description here

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

Реализация и использование в: Реализация .NET ThreadState по шаблону проектирования состояний

5 голосов
/ 27 января 2014

Я еще не пробовал внедрять FSM в C #, но все это звучит (или выглядит) очень сложно по сравнению с тем, как я работал с FSM в прошлом на языках низкого уровня, таких как C или ASM.

Я считаю, что метод, который я всегда знал, называется чем-то вроде «Итеративного цикла». В нем, по сути, имеется цикл while, который периодически выходит на основе событий (прерываний), а затем снова возвращается в основной цикл.

В обработчиках прерываний вы должны передать CurrentState и вернуть NextState, который затем перезаписывает переменную CurrentState в главном цикле. Вы делаете это до бесконечности, пока программа не закроется (или микроконтроллер не перезагрузится).

То, что я вижу, другие ответы выглядят очень сложными по сравнению с тем, как, на мой взгляд, ФШМ должен быть реализован; Его красота заключается в его простоте, и FSM может быть очень сложным со многими, многими состояниями и переходами, но они позволяют легко разбивать и переваривать сложный процесс.

Я понимаю, что мой ответ не должен включать другой вопрос, но я вынужден спросить: почему эти другие предлагаемые решения кажутся такими сложными?
Похоже, они похожи на попадание маленького гвоздя гигантской кувалдой.

5 голосов
/ 19 апреля 2016

Нашел этот замечательный учебник в Интернете, и он помог мне разобраться с конечными автоматами.

http://gamedevelopment.tutsplus.com/tutorials/finite-state-machines-theory-and-implementation--gamedev-11867

Учебник не зависит от языка, поэтому его легко адаптировать к вашему C #необходимо.

Кроме того, используемый пример (муравей ищет еду) легко понять.


Из учебника:

enter image description here

public class FSM {
    private var activeState :Function; // points to the currently active state function

    public function FSM() {
    }

    public function setState(state :Function) :void {
        activeState = state;
    }

    public function update() :void {
        if (activeState != null) {
            activeState();
        }
    }
}


public class Ant
{
    public var position   :Vector3D;
    public var velocity   :Vector3D;
    public var brain      :FSM;

    public function Ant(posX :Number, posY :Number) {
        position    = new Vector3D(posX, posY);
        velocity    = new Vector3D( -1, -1);
        brain       = new FSM();

        // Tell the brain to start looking for the leaf.
        brain.setState(findLeaf);
    }

    /**
    * The "findLeaf" state.
    * It makes the ant move towards the leaf.
    */
    public function findLeaf() :void {
        // Move the ant towards the leaf.
        velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y);

        if (distance(Game.instance.leaf, this) <= 10) {
            // The ant is extremelly close to the leaf, it's time
            // to go home.
            brain.setState(goHome);
        }

        if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) {
            // Mouse cursor is threatening us. Let's run away!
            // It will make the brain start calling runAway() from
            // now on.
            brain.setState(runAway);
        }
    }

    /**
    * The "goHome" state.
    * It makes the ant move towards its home.
    */
    public function goHome() :void {
        // Move the ant towards home
        velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y);

        if (distance(Game.instance.home, this) <= 10) {
            // The ant is home, let's find the leaf again.
            brain.setState(findLeaf);
        }
    }

    /**
    * The "runAway" state.
    * It makes the ant run away from the mouse cursor.
    */
    public function runAway() :void {
        // Move the ant away from the mouse cursor
        velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y);

        // Is the mouse cursor still close?
        if (distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) {
            // No, the mouse cursor has gone away. Let's go back looking for the leaf.
            brain.setState(findLeaf);
        }
    }

    public function update():void {
        // Update the FSM controlling the "brain". It will invoke the currently
        // active state function: findLeaf(), goHome() or runAway().
        brain.update();

        // Apply the velocity vector to the position, making the ant move.
        moveBasedOnVelocity();
    }

    (...)
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...