StackBasedStateMachine

UserPreferences

1. 개요
2. 샘플
1. State Machine
2. Driver
3. Output
3. 링크

1 개요

일반적인 FiniteStateMachine의 약점 중 하나가, 한 순간에 하나의 상태만을 유지할 수 있다는 점이다. 이 때문에 상태 변환이 일어나는 경우, 이전 상태에 대한 정보가 모두 사라진다.

상태 변환시, 이전 상태를 깡그리 잊어버리고 새로운 상태로 변환하는 것이 아니라, 스택을 이용하여 이전 상태를 저장해두면, 현재 상태에 대한 처리가 끝난 후에, 이전 상태로 되돌아갈 수 있다.

이를 통해 패트롤하다가 플레이어를 발견하면 공격하고, 플레이어가 시야에서 사라지면 다시 패트롤하러 가는 NPC 같은 것을 쉽게 만들 수 있다.

구현 자체는 그렇게 어렵지 않다. 기존의 FiniteStateMachine의 상태 변환하는 부분에다가 현재 상태를 치환해버리는 부분에다가, 스택 연산을 집어넣으면 된다.

2 샘플

2.1 State Machine

template <typename DERIVED, int ErrorState=-1>
class cStackStateMachine : private cNoncopyable
{
public:
    static const int s_ErrorState = ErrorState;

    class cEventObject
    {
    private:
        int m_EventID;

    public:
        cEventObject(int ID) : m_EventID(ID) {}
        virtual ~cEventObject() {}
        int GetEventID() const { return m_EventID; }
        void SetEventID(int ID) { m_EventID = ID; }
    };


private:
    typedef void (DERIVED::*ACTION)(const cEventObject*);
    typedef void (DERIVED::*POLLER)();

    enum StackOperation
    {
        OP_PUSH,
        OP_POP,
        OP_REPLACE
    };

    struct STATE;

    struct TRANSITION
    {
        STATE*         To;
        StackOperation Operation;
        ACTION         Action;

        TRANSITION(STATE* t, StackOperation op, ACTION a) 
            : To(t), Operation(op), Action(a) {}
    };

    struct STATE : public stdext::hash_map<int, TRANSITION>
    {
        int    ID;
        POLLER Poller;
        ACTION Enter;
        ACTION Leave;

        STATE(int s, POLLER p, ACTION e, ACTION l) 
            : ID(s), Poller(p), Enter(e), Leave(l) {}

        void AddTransition(int eventid, STATE* to, StackOperation op, ACTION action) 
        {
            iterator itr(find(eventid));
            Assert(itr == end());
            insert(value_type(eventid, TRANSITION(to, op, action)));
        }

        const TRANSITION& OnDispatch(DERIVED* pDerived, const cEventObject* pEvent)
        {
            iterator itr(find(pEvent->GetEventID()));
            Assert(itr != end());

            const TRANSITION& t = itr->second;
            if (t.Action != NULL) (pDerived->*(t.Action))(pEvent);

            return t;
        }

        void OnEnter(DERIVED* pDerived, const cEventObject* pEvent)
        {
            if (Enter != NULL) (pDerived->*(Enter))(pEvent);
        }

        void OnLeave(DERIVED* pDerived, const cEventObject* pEvent)
        {
            if (Leave != NULL) (pDerived->*(Leave))(pEvent);
        }
    };

    void DefaultPoller() {}


private:
    typedef stdext::hash_map<int, STATE*> STATES;
    typedef stack<STATE*> STACK;

    STATES m_States;
    STACK  m_Stack;


public:
    cStackStateMachine() {}
    virtual ~cStackStateMachine() { DESTROY_ALL_OBJECT(m_States); }


public:
    void AddState(int state, POLLER poller=DefaultPoller, ACTION enter=NULL, ACTION leave=NULL)
    {
        Assert(state != ErrorState);
        Assert(poller != NULL);

        STATES::iterator itr(m_States.find(state));
        Assert(itr == m_States.end());

        m_States.insert(
            STATES::value_type(state, new STATE(state, poller, enter, leave)) );
    }

    void AddPushTransition(int from, int eventid, int to, ACTION action)
    {
        STATES::iterator f(m_States.find(from));
        STATES::iterator t(m_States.find(to));

        Assert(f != m_States.end());
        Assert(t != m_States.end());

        f->second->AddTransition(eventid, t->second, OP_PUSH, action);
    }

    void AddPopTransition(int from, int eventid, ACTION action)
    {
        STATES::iterator f(m_States.find(from));

        Assert(f != m_States.end());

        f->second->AddTransition(eventid, NULL, OP_POP, action);
    }

    void AddReplaceTransition(int from, int eventid, int to, ACTION action)
    {
        STATES::iterator f(m_States.find(from));
        STATES::iterator t(m_States.find(to));

        Assert(f != m_States.end());
        Assert(t != m_States.end());

        f->second->AddTransition(eventid, t->second, OP_REPLACE, action);
    }

    void SetInitialState(int state) 
    { 
        Assert(state != ErrorState);
        Assert(m_Stack.empty());

        STATES::const_iterator itr(m_States.find(state));
        Assert(itr != m_States.end());

        STATE* pState = itr->second;
        m_Stack.push(pState);

        cEventObject dummy(ErrorState);
        pState->OnEnter(static_cast<DERIVED*>(this), &dummy);
    }


public:
    int GetCurrentState() const 
    { 
        Assert(!m_Stack.empty());
        return m_Stack.top()->ID; 
    }

    void DispatchEvent(const cEventObject* pEvent)
    {
        AssertPtr(pEvent);
        Assert(!m_Stack.empty());

        STATE* pCurrent = m_Stack.top();
        pCurrent->OnLeave(static_cast<DERIVED*>(this), pEvent);

        const TRANSITION& t = 
            pCurrent->OnDispatch(static_cast<DERIVED*>(this), pEvent);

        STATE* pNext = t.To;

        switch (t.Operation)
        {
        case OP_PUSH:
            m_Stack.push(pNext);
            pNext->OnEnter(static_cast<DERIVED*>(this), pEvent);
            Assert(m_Stack.size() <= m_States.size());
            break;
        case OP_POP:
            m_Stack.pop();
            Assert(!m_Stack.empty());
            break;
        case OP_REPLACE:
            m_Stack.pop();
            m_Stack.push(pNext);
            pNext->OnEnter(static_cast<DERIVED*>(this), pEvent);
            break;
        default:
            break;
        }
    }

    void DispatchEvent(int eventid)
    {
        cEventObject e(eventid);
        DispatchEvent(&e);
    }

    void Poll()
    {
        Assert(!m_Stack.empty());
        POLLER poller = m_Stack.top()->Poller;
        Assert(poller != NULL);
        ((static_cast<DERIVED*>(this))->*poller)();
    }
    
    size_t GetStackSize() const { return m_Stack.size(); }
};





2.2 Driver

class cGuard : public cStackStateMachine<cGuard>
{
private:
    enum 
    {
        STATE_IDLE,
        STATE_PARTOL,
        STATE_SEARCH,
        STATE_COMBAT
    };

    enum 
    {
        EVENT_TIME,
        EVENT_HEAR,
        EVENT_SEE,
        EVENT_BANISH
    };


public:
    cGuard() : cStackStateMachine() 
    {
        AddState(STATE_IDLE, &cGuard::WhileIdle);
        AddState(STATE_PARTOL, &cGuard::WhilePartol);
        AddState(STATE_SEARCH, &cGuard::WhileSearch);
        AddState(STATE_COMBAT, &cGuard::WhileCombat);
    
        AddPushTransition(STATE_IDLE, EVENT_TIME, STATE_PARTOL, &cGuard::OnTime);
        AddPushTransition(STATE_IDLE, EVENT_HEAR, STATE_SEARCH, &cGuard::OnHear);
        AddPushTransition(STATE_IDLE, EVENT_SEE, STATE_COMBAT, &cGuard::OnSee);
        AddPushTransition(STATE_PARTOL, EVENT_HEAR, STATE_SEARCH, &cGuard::OnHear);
        AddPushTransition(STATE_PARTOL, EVENT_SEE, STATE_COMBAT, &cGuard::OnSee);
        AddPopTransition(STATE_PARTOL, EVENT_TIME, &cGuard::OnTime);
        AddPushTransition(STATE_SEARCH, EVENT_SEE, STATE_COMBAT, &cGuard::OnSee);
    
        AddPopTransition(STATE_COMBAT, EVENT_BANISH, &cGuard::OnBanish);
        AddPopTransition(STATE_SEARCH, EVENT_BANISH, &cGuard::OnBanish);
    
        SetInitialState(STATE_IDLE);
    }
    

public:
    void Heartbeat() { Poll(); }


public:
    void WhileIdle() 
    {
        cout << "Idle...(StackSize:" << GetStackSize() << ")" << endl;
        
        if ((rand() % 100) < 50)
            DispatchEvent(EVENT_TIME);
    }
    
    void WhilePartol() 
    {
        cout << "Patroling...(StackSize:" << GetStackSize() << ")" << endl;
    
        if ((rand() % 100) < 50)
            DispatchEvent(EVENT_HEAR);
        else if ((rand() % 100) < 50)
            DispatchEvent(EVENT_TIME);
    }
    
    void WhileSearch()
    {
        cout << "Searching...(StackSize:" << GetStackSize() << ")" << endl;
    
        if ((rand() % 100) < 50)
            DispatchEvent(EVENT_SEE);
        else
            DispatchEvent(EVENT_BANISH);
    }
    
    void WhileCombat()
    {
        cout << "Engaging...(StackSize:" << GetStackSize() << ")" << endl;
    
        if ((rand() % 100) < 50)
            DispatchEvent(EVENT_BANISH);
    }
    
    void OnTime(const cEventObject* pEvent) {
        cout << ">>> It's time to switch." << endl;
    }
    
    void OnHear(const cEventObject* pEvent) { 
        cout << ">>> I heard something!" << endl; 
    }
    
    void OnSee(const cEventObject* pEvent) { 
        cout << ">>> There he is! Die, fucker!" << endl; 
    }
    
    void OnBanish(const cEventObject* pEvent) { 
        cout << ">>> W, Where is him?" << endl; 
    }
};

int main(int argc, char* argv[])
{
    cGuard g;

    while (true)
    {
        g.Heartbeat();
        Sleep(1000);
    }
    
    return 0;
}




2.3 Output

Idle...(StackSize:1) 
Idle...(StackSize:1) 
>>> It's time to switch. 
Patroling...(StackSize:2) 
>>> I heard something! 
Searching...(StackSize:3) 
>>> There he is! Die, fucker! 
Engaging...(StackSize:4) 
>>> W, Where is him? 
Searching...(StackSize:3) 
>>> There he is! Die, fucker! 
Engaging...(StackSize:4) 
Engaging...(StackSize:4) 
Engaging...(StackSize:4) 
>>> W, Where is him? 
Searching...(StackSize:3) 
>>> W, Where is him? 
Patroling...(StackSize:2) 
Patroling...(StackSize:2) 
>>> It's time to switch. 
Idle...(StackSize:1) 

3 링크

• NPC 인공지능 처리 기본 구성
  

• see also FiniteStateMachine
  

• CategoryAppProgramming, CategoryAiProgramming