[FSM vs Behavior Tree] Part.2 - FSM 의 구현

FSM 의 구현

 

Part.1 에서 FSM 의 개념에 대해서 보았습니다. 

이번에는 FSM 을 구현하기위해 먼저 UML 로 컨셉을 보겠습니다. 

FSM Concept UML

우선, 핵심부분은 상태머신이 상태 인터페이스에대한 콜렉션을 가지고있고, 현재 상태에 따라 상태의 로직을 수행한다는 것입니다. 

 

해당 컨셉을 좀더 자세히보면, 

 

IState 인터페이스는 enum 타입의 명령종류에 대해 열거하고있으며, 실행가능 여부를 따지고(CanExecute) 실행할 수 있습니다(Execute()).  Iterating 을 하기위한 MoveNext() 를 가지고있고, 해당 상태가 종료되어야할때 Machine이 중단시킬 수 있도록 Stop() 을 추상화해놓고있습니다.  

 

IState<T> 인터페이스는 해당 상태가 Machine입장에서 어떤 상태에 수행되어야 하는 인터페이스인지 명시하기위한 타입을 넣을 수 있도록 Generic 으로 구현되어있으며, 주로 Enum 타입을 사용할 수 있습니다. 하위 상태들에 대해 Machine이  DIP(의존성 역전의 원칙)을 고수하기위한 인터페이스입니다. Workflow() 는 해당 인터페이스의 현재 명령종류에 따른 로직을 수행하는 함수이며, 반환값으로 전환해야하는 다음 상태를 반환합니다.

즉,

① MoveState 가  Attack 을 반환

② Machine 이 AttackState의 CanExecute 확인

③ 실행가능시 Machine 이 MoveState의 Stop() 호출 및 AttackState의 Execute() 호출

④ Mahine 의 Current 가 AttackState 로 전환됨

 

위 컨셉을 실제 C# 로 구현한다면 다음처럼 할 수 있습니다. 

 

● IState

-> 추상컨셉에서와 마찬가지로 멤버들이 구현되어있고 추가로 해당 상태가 바쁜지, 끝났는지, 에러에 걸렸는지 등을 체크하기위한 getter 를 가지고있습니다.

public interface IState
{
    public enum Commands
    {
        Idle,
        Prepare,
        WaitUntilPrepared,
        Cast,
        WaitUntilCasted,
        OnAction,
        Finish,
        WaitUntilFinished,
        Finished,
        Error,
        WaitUntilErrorCleared
    }
    bool IsBusy { get; }
    bool IsFinished { get; }
    bool IsError { get; }
    bool CanExecute { get; }
    Commands Command { get; }
    void Execute();
    void Stop();
    void MoveNext();
}

● IState<T>

-> 다음 상태를반환하는 Workflow() 를 구현하고 있으며, 반환한 상태가 현재상태와 같다면 Machine 은 상태전환 없이 로직을 수행할 것입니다.

using System;
public interface IState<T> : IState where T : Enum
{
    T Workflow();
}

● StateBase<T>

-> 생성자에서 파라미터로 Machine 기준 상태, Machine , 전환 조건, 다음 상태로 전환하기위한 조건과 종류를 가지고있습니다. 그래서 Machine 이 State들을 생성할 때에, 각 State 마다 모든 조건과 종류에 대해 생성하고 인자로 넘겨주어야합니다. 

Workflow() 에서 Finished 명령 case 를 보면 다음 상태를 반환하기위한 모든 조건을 순회하고있습니다. 

using System;
using System.Collections.Generic;

/// <summary>
/// Base for generic state machine's sub state
/// </summary>
public abstract class StateBase<T> : IState<T> where T : Enum
{
    public bool IsBusy
    {
        get => Command > IState.Commands.Idle || 
               Command < IState.Commands.Finished;
    }

    public bool IsFinished
    {
        get => Command == IState.Commands.Finished;
    }

    public bool IsError
    {
        get => Command >= IState.Commands.Error;
    }
    public virtual bool CanExecute => StateConditions.Contains(Machine.CurrentType);
    
    public IState.Commands Command { get; protected set; }
    protected T StateType;
    protected List<T> StateConditions;
    protected List<KeyValuePair<Func<bool>, T>> Transitions;
    protected StateMachineBase<T> Machine;

    //==============================================================================
    //****************************** Public Methods ********************************
    //==============================================================================
    
    
    public StateBase(T stateType, StateMachineBase<T> machine, List<T> stateConditions, List<KeyValuePair<Func<bool>, T>> transitions)
    {
        StateType = stateType;
        Machine = machine;
        StateConditions = stateConditions;
        Transitions = transitions;
    }

    public virtual void Execute() => Command = IState.Commands.Prepare;
    public virtual void Stop() => Command = IState.Commands.Idle;
    public virtual void MoveNext() => Command++;

    public virtual T Workflow()
    {
        T next = StateType;
        switch (Command)
        {
            case IState.Commands.Idle:
                break;
            case IState.Commands.Prepare:
                MoveNext();
                break;
            case IState.Commands.WaitUntilPrepared:
                MoveNext();
                break;
            case IState.Commands.Cast:
                MoveNext();
                break;
            case IState.Commands.WaitUntilCasted:
                MoveNext();
                break;
            case IState.Commands.OnAction:
                MoveNext();
                break;
            case IState.Commands.Finish:
                MoveNext();
                break;
            case IState.Commands.WaitUntilFinished:
                MoveNext();
                break;
            case IState.Commands.Finished:
                {
                    foreach (var transition in Transitions)
                    {
                        if (transition.Key.Invoke())
                        {
                            next = transition.Value;
                            break;
                        }
                    }
                }
                break;
            case IState.Commands.Error:
                MoveNext();
                break;
            case IState.Commands.WaitUntilErrorCleared:
                break;
            default:
                break;
        }
        return next;
    }
}

● IStateMachine 

-> 머신의 기본 추상화 인터페이스이고 현재 상태와 현재 상태에 대한 로직을 수행하는 멤버를 가지고있습니다.

public interface IStateMachine
{
    IState Current { get; }
    void RunCurrentWorkflow();
}

● IStateMachine<T>

-> 상태의 종류를 명시하고 쓸 수 있도록 일반화시킨 인터페이스입니다. 현재 상태, 상태에대한 타입, 상태전환을 멤버로 가집니다.

using System;

public interface IStateMachine<T> : IStateMachine where T : Enum
{
    IState<T> Current { get; }
    T CurrentType { get; }
    bool ChangeState(T newStateType);        
}

● StateMachineBase<T>

-> IState<T> 에 대한 Dictionary를 가지고있어 상태를 변경할 때 원하는 상태에 대한 인터페이스를 인덱스 접근할 수 있습니다.  ChangeState(T) 를 보면, 전환하려는 상태가 변경되었는지, 해당상태로 전환가능한지를 확인하고 현재 상태를 정지시킨 후 다음 상태로전환해주고 있습니다. RunCurrentWorkflow() 를 보면, 현재 상태의 Workflow() 에서 반환된 다음 상태를 바로 ChangeState(T) 의 인자로 넘겨주면서 상태가 전환되어야하는지를 매 로직 마다 체크합니다.

InitStates() 에서는 구현할 때에 모든 State 들의 생성자를 호출하고 Dictionary 에 추가해주는 작업을 해 주면 됩니다.

아래 추가 주석은 각 세부 상태도 추상화해서 사용하려는 경우 (ex. StateMove<T>, StateAttack<T> ... ) Relfection 을 활용해서 InitStates() 의 하드코딩을 줄여줄 수 있도록 할 수 있는 예시입니다.

using System;
using System.Reflection;
using System.Collections.Generic;

/// <summary>
/// Base class for generic enum state machine 
/// </summary>
/// <typeparam name="T">enum state types</typeparam>
public abstract class StateMachineBase<T> : IStateMachine<T> where T : Enum
{
    public object Owner;
    public IState<T> Current { get; set; }
    public T CurrentType { get; protected set; }
    public IState.Commands CurrentCommand => Current.Command;
    IState IStateMachine.Current => Current;
    protected Dictionary<T, IState<T>> States = new Dictionary<T, IState<T>>();
    protected bool StateHasChanged;


    //==============================================================================
    //****************************** Public Methods ********************************
    //==============================================================================

    public StateMachineBase(object owner)
    {
        Owner = owner;
        InitStates();

        States[default(T)].Execute();
        Current = States[default(T)];
        CurrentType = default(T);
    }

    public virtual bool ChangeState(T newStateType)
    {
        if (StateHasChanged)
            return false;

        if (EqualityComparer<T>.Default.Equals(CurrentType, newStateType))
            return false;

        if (States[newStateType].CanExecute == false)
            return false;

        Current.Stop();
        CurrentType = newStateType;
        Current = States[CurrentType]; 
        Current.Execute();     

        StateHasChanged = true;
        return true;
    }
    
    public bool ChangeState(dynamic newStateType)
    {
        return ChangeState((T)newStateType);
    }

    public virtual void RunCurrentWorkflow()
    {
        ChangeState(Current.Workflow());
        StateHasChanged = false;
    }


    //==============================================================================
    //**************************** Protected Methods *******************************
    //==============================================================================

    protected abstract void InitStates();
    

/* ... 만약 StateBase<T> 를 상속받아 다른 상태들에 대한것들도 제네릭으로 구현한다고했을때
(ex, StateMove<T>, StateAttack<T> ... ) Reflection 을 활용해소 필요한 상태들을 정해주고 
Machine 이 알아서 상태들을 추가할 수 있도록 해 줄 수 있습니다.
*/	
    //protected void AddStates(List<T> stateTypes)
    //{        
    //    foreach (T stateType in stateTypes)
    //    {
    //        AddState(stateType);
    //    }
    //}

    //protected void AddState(T stateType)
    //{
    //    if (States.ContainsKey(stateType))
    //        return;
    //
    //    Assembly stateTypeAssembly = typeof(T).Assembly;
    //    Type stateExtendType = Type.GetType($"State{stateType}`1[[{typeof(T)},{stateTypeAssembly}]]");
    //
    //    if (stateExtendType == null)
    //        return;
    //
    //    ConstructorInfo constructorInfo = stateExtendType.GetConstructor(new Type[] { typeof(T),
    //                                                                                  typeof(StateMachineBase<T>),
    //                                                                                  typeof(List<T>),
    //                                                                                  typeof(List<KeyValuePair<Func<bool>, T>>)});
    //
    //    if (constructorInfo == null)
    //        return;
    //
    //    //StateBase<T> state = constructorInfo.Invoke(new object[] { stateType, 
    //																   exeuctionConditions,
    //                                                                 transitions,
    //    //                                                           this }) as StateBase<T>;
    //    States.Add(stateType, state);
    //}    
}

 

 

위와같이 StateMachine 관련해서 추상화를 시킬 수 있으며, StateMachine 과 State 를 실체화 해서 FSM 을 구현 할 수 있습니다. 

StateBase<T> 를 보면 알 수 있듯, FSM 의 단점은 해당 상태가 실행가능 조건에 해당하는 상태들과, 상태가 끝날때 전환해야하는 다음 상태에 대한 조건 및 종류들을 전부 가지고 있어야 하기 때문에 상태가 조금만 많아져도 StateMachineBase<T>.InitState() 내에서 해 주어야 할 내용이 매우 길어질 수 있습니다.

특정한 상황에서 이런 문제를 해결하기위해 보완하거나 대체할 수 있는 BehaviorTree 에 대해 다음 장에 이어서 다루도록 하겠습니다.