階層型有限状態機械（Hierarchical Finite State Machine）の実装

C++

前回有限状態機械（Finite State Machine:FSM）の実装 - while( c++ );の続きです。

参考サイト


以下のような階層化されたステートマシンを実装します。

現在の状態 イベント 次の状態 アクション
start state_0
state_0 event_0 state_3 action_0
state_1 event_1 state_0
state_0 event_2 end

※現在の状態でイベントが処理できない場合は、親の状態に渡されます。


  • start --> state_0
    • state_4::entry()
    • state_0::entry()
  • state_0 -- event_0/action_0 --> state_3
    • state_0::exit()
    • state_1::entry()
    • state_2::entry()
    • state_3::entry()
  • state_1(3) -- event_1 --> state_0
    • state_3::exit()
    • state_2::exit()
    • state_1::exit()
    • state_0::entry()
  • state_0 -- event_2 --> end
    • state_0::exit()
    • state_4::exit()

使い方

まずは使い方を見て、最低限必要なものを確認しましょう。

  • 1.state_machine<>を継承したクラスを作ります。ここではhfsmとしました。
  • 2.イベントを整数値で用意します。
  • 3.state_t（state_interface<>）とsingleton<>を継承した状態クラスを用意します。その際、必要に応じてentry()、exe()、exit()をオーバーライドします。
  • 4.状態遷移時にアクションを実行する場合は、action_t（action_interface<>）の実装クラスを用意します。
  • 5.コンストラクタでステート階層と状態遷移テーブルを作成します。
  • 6.初期状態をセットします。
class hfsm
    : public state_machine< hfsm >
{
    //
    //イベント
    //
public:
    enum event_id
    { event_0, event_1, event_2 };

    //
    //ステート
    //
public:
    class state_0
        : public state_t
        , public singleton< state_0 >
    {
        friend class singleton< state_0 >;
        state_0() : state_t( _T( "state_0" ) ){}
    public:
        void entry(){ _tcout << _T( "state_0::entry\n" ); }
        void exit(){ _tcout << _T( "state_0::exit\n" ); }
    };
    class state_1
        : public state_t
        , public singleton< state_1 >
    {
        friend class singleton< state_1 >;
        state_1() : state_t( _T( "state_1" ) ){}
    public:
        void entry(){ _tcout << _T( "state_1::entry\n" ); }
        void exit(){ _tcout << _T( "state_1::exit\n" ); }
    };

    /*...*/

    class state_4
        : public state_t
        , public singleton< state_4 >
    {
        friend class singleton< state_4 >;
        state_4() : state_t( _T( "state_4" ) ){}
    public:
        void entry(){ _tcout << _T( "state_4::entry\n" ); }
        void exit(){ _tcout << _T( "state_4::exit\n" ); }
    };

    //
    //アクション
    //
public:
    class action_0
        : public action_t
        , public singleton< action_0 >
    {
    public:
        void exe( context_t* /*context*/ ){ _tcout << _T( "action_0\n" ); }
    };

    //
    //hfsm
    //
public:
    hfsm()
    {
        //
        //ステート階層
        //
        state_4::get_instance()->set_parent( 0, this );
            state_0::get_instance()->set_parent( state_4::get_instance(), this );
            state_1::get_instance()->set_parent( state_4::get_instance(), this );
                state_2::get_instance()->set_parent( state_1::get_instance(), this );
                    state_3::get_instance()->set_parent( state_2::get_instance(), this );

        //
        //状態遷移テーブル
        //
        add_transition( state_0::get_instance(), event( event_0 ), state_3::get_instance(), action_0::get_instance() );
        add_transition( state_1::get_instance(), event( event_1 ), state_0::get_instance(), 0 );
        add_transition( state_0::get_instance(), event( event_2 ), end::get_instance(), 0 );

        change_state( state_0::get_instance() );
    }
};

以上で階層型ステートマシンを使う準備が整いました。


では、実際に使ってみましょう。

int _tmain(int argc, _TCHAR* argv[])
{
    hfsm state;

    while( !state.is_end() )
    {
        _TCHAR a;
        _tcin >> a;
        state.update();
        if( a == _T( 'z' ) )state.process_event( event( hfsm::event_0 ) );
        if( a == _T( 'x' ) )state.process_event( event( hfsm::event_1 ) );
        if( a == _T( 'c' ) )state.process_event( event( hfsm::event_2 ) );
    }
    return 0;
}

Sample

eventクラス

class event
{
private:
    int value;

public:
    event( int value )
        : value( value )
    {}

    bool operator==( event const& e )const
    { return value == e.value; }
    bool operator<( event const& e )const
    { return value < e.value; }
};

action_interface

template < typename ContextType >
class action_interface
{
public:
    virtual void exe( ContextType* context ) = 0;
};

state_interface

template < typename ContextType >
class state_interface
{
    typedef ContextType context_t;
    typedef state_interface state_t;
    typedef action_interface< context_t > action_t;
    typedef std::map< event, state_t* > transition_map;
    typedef std::map< event, action_t* > action_map;

public:
    virtual void entry(){}
    virtual void exe(){}
    virtual void exit(){}

protected:
    context_t* context;
    state_t* parent;
    tstring name;	//デバッグ用
    transition_map transition;
    action_map action;

protected:
    state_interface( tstring const& name )
        : name( name )
    {}

public:
    void set_parent( state_t* parent, context_t* context )
    {
        this->parent = parent;
        this->context = context;
    }

    state_interface* get_parent()const
    { return parent; }

public:
    void add_transition( event const& e, state_t* state )
    { transition.insert( std::make_pair( e, state ) ); }

    bool transit( event const& e )
    {
        transition_map::iterator it = transition.find( e );
        if( it != transition.end() )
        {
            context->change_state( it->second, this );
            action_map::iterator it_action = action.find( e );
            if( it_action != action.end() )
                it_action->second->exe( context );
            return true;
        }
        return false;
    }

public:
    void add_action( event const& e, action_t* act )
    { action.insert( std::make_pair( e, act ) ); }
};

state_machine

template < typename ContextType >
class state_machine
{
protected:
    typedef ContextType context_t;
    typedef state_interface< context_t > state_t;
    typedef action_interface< context_t > action_t;

protected:
    //開始状態
    class start : public state_t, public singleton< start >
    {
        friend class singleton< start >;
        start() : state_t( _T( "start" ) ){}
    };
    //終了状態
    class end : public state_t, public singleton< end >
    {
        friend class singleton< end >;
        end() : state_t( _T( "end" ) ){}
    };

private:
    state_t* current;

public:
    state_machine()
        : current( start::get_instance() )
    {}

public:
    void update()
    {
        current->exe();
    }

    void change_state( state_t* dest_state, state_t* src_state = 0 )
    {
        if( src_state == 0 )src_state = current;

        //自己遷移
        if( src_state == dest_state )
        {
            src_state->exit();
            dest_state->entry();
            return;
        }

        typedef std::list< state_t* > state_list;
        //src_stateからrootまでの経路
        state_list src_top;
        for( state_t* s = src_state; s != 0; s = s->get_parent() )
            src_top.push_front( s );
        //dest_stateからrootまでの経路
        state_list dest_top;
        for( state_t* s = dest_state; s != 0; s = s->get_parent() )
            dest_top.push_front( s );

        //最も近い共通の親をrootから検索する
        state_t* parent = 0;
        state_list::iterator it_src = src_top.begin();
        state_list::iterator it_dest = dest_top.begin();
        while( it_src != src_top.end() && it_dest != dest_top.end() )
        {
            if( *it_src != *it_dest )break;
            ++ it_src;
            ++ it_dest;
        }
        //it_srcが先頭でない時の--it_srcが共通の親
        if( it_src != src_top.begin() )
        {
            -- it_src;
            parent = *it_src;
        }

        //退場動作
        for( state_t* s = current; s != parent; s = s->get_parent() )
            s->exit();

        //入場動作
        for( ; it_dest != dest_top.end(); ++ it_dest )
            ( *it_dest )->entry();

        current = dest_state;
    }

    context_t* derived()
    { return static_cast< context_t* >( this ); }

    void process_event( event const& e )
    {
        //イベントによるtransition
        //自分で処理できない場合は親に渡す
        state_t* s = current;
        while( s != 0 && !s->transit( e ) )
            s = s->get_parent();
    }

    void add_transition( state_t* current, event const& e, state_t* next, action_t* action )
    {
        current->add_transition( e, next );
        if( action )current->add_action( e, action );
    }

public:
    bool is_end()const
    { return current == end::get_instance(); }
};

雑感