사용자 도구

사이트 도구


kb:stackbasedstatemachine

차이

문서의 선택한 두 판 사이의 차이를 보여줍니다.

차이 보기로 링크

kb:stackbasedstatemachine [2014/11/08 14:07] (현재)
줄 1: 줄 1:
 +====== Stack-based State Machine ======
 +일반적인 FiniteStateMachine의 약점 중 하나가, 한 순간에 하나의 상태만을 유지할 수 있다는 점이다. 이 때문에 상태 변환이 일어나는 경우, 이전 상태에 대한 정보가 모두 사라진다.
 +
 +상태 변환시, 이전 상태를 깡그리 잊어버리고 새로운 상태로 변환하는 것이 아니라, 스택을 이용하여 이전 상태를 저장해두면,​ 현재 상태에 대한 처리가 끝난 후에, 이전 상태로 되돌아갈 수 있다. ​
 +
 +이를 통해 패트롤하다가 플레이어를 발견하면 공격하고,​ 플레이어가 시야에서 사라지면 다시 패트롤하러 가는 NPC 같은 것을 쉽게 만들 수 있다.
 +
 +구현 자체는 그렇게 어렵지 않다. 기존의 FiniteStateMachine의 상태 변환하는 부분에다가 현재 상태를 치환해버리는 부분에다가,​ 스택 연산을 집어넣으면 된다.
 +
 +
 +====== 샘플 ======
 +===== State Machine =====
 +<code cpp>
 +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();​ }
 +};
 +</​code>​
 +
 +===== Driver =====
 +<code cpp>
 +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;
 +}
 +</​code>​
 +
 +===== Output =====
 +<​code>​
 +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)
 +</​code>​
 +
 +
 +====== 링크 ======
 +  * [[http://​www.gamecode.org/​article.php3?​no=1588&​page=1&​current=0&​field=tip | NPC 인공지능 처리 기본 구성]]
 +
 +----
 +  * see also [[FiniteStateMachine]]
  
kb/stackbasedstatemachine.txt · 마지막으로 수정됨: 2014/11/08 14:07 (바깥 편집)