階層型ステートマシンによるステートデザインパターン

今回は、ゲームプログラミングの中でもとても重要なデザインパターン、ステートデザインパターンについて紹介しようかと思います。

通常、クラスというものは「属性」と「振る舞い」の二種類の要素を兼ね備えています。
一般に、データとインターフェースと呼ばれるものですね。

クラスは自身の状態を保持し、きっとカプセル化されたデータに応じて要求された操作に対し適切な振る舞いをすることでしょう。
そのようなコードは列挙体とswitch-caseで簡単に表現できます。

例として、村によくいる住人のオブジェクトを考えます。
住人は、走ったり、歩いたり、或いは居眠りをする挙動を考えます。

class NPC {
  enum class State {
    WALK,
    RUN,
    SLEEP
  }

/*-----適当な実装-----*/

  void update(float deltaTime);
  void changeState();

  private:
    State _state;
    float _elapsedTime;

    static constexpr float CHANGE_STATE_TIME = 50;
};

void NPC::update(float deltaTime) {
  _elapsedTime += deltaTime;
  if(_elapsedTime >= CHANGE_STATE_TIME) {
    _elapsedTime -= CHANGE_STATE_TIME;
    changeState();
  }

  switch(_state){
    case State::WALK:
    //歩きます
    break;
    case State::RUN:
  //走ります
    break;
    case State::SLEEP:
    //眠ります
    break;
  }
}

void NPC::changeState() {
  switch(_state){
    case State::WALK:
    _state = State::SLEEP; //歩き疲れたので眠ります
    break;
    case State::RUN:
  _state = State::WALK; //走り疲れたので歩きます
    break;
    case State::SLEEP:
    _state = State::RUN; //眠って元気が出たので走ります
    break;
  }
}

この程度のコードならまあ、これでいいんでしょうが、あまりにも拡張性に欠けます。
状態(State)は今3つだけですが、当然追加が発生することもありますし、遷移の順番も変わるかもしれません。

さらに、状態というものはネストすることがあります。例えば、「機嫌が良い/悪い」という状態が加わったらどうでしょう。「歩いている」と「機嫌が良い」は同時に発生しうる状態であり、両方とも別変数で管理し、switch-caseをネストさせて条件分岐させなくてはなりません。

//地獄のswitch-caseのネスト
switch(_state1){
    case State1::WALK:
    switch(_state2) {
        case State2::FeelBad:
        /*...*/
        break;
        case State2::FeelGood:
        /*...*/
    }
    break;
    /*...*/
  }

そんなswitch-caseのコードのメンテナンスをしていると、とんでもないことになります(なりました)。

具体的にどうするべきかというと、「状態」というものをクラスにしカプセル化しましょう。
NPCクラス自身が次の状態は何か、今どうするべきかを判断する構造は良くないです。

class StateBase {
  StateBase():_next(nullptr){}
  virtual StateBase* update(float deltaTime) = 0;
  /* --- 適当な実装 --- */
  private:
  StateBase* _next;
};

class Walk : public StateBase {
  StateBase* update(float deltaTime) override {
    /* ある条件下で_nextを更新 */
    return _next;
  }
};

class Run : public StateBase {
  //同様
};

class Sleep : public StateBase {
  //同様
};

class NPC {
void update(float deltaTime);
private:
  StateBase* _current;
};

void NPC::update(float deltaTime) {
  auto next = _current->update();
  if(next) {
   changeState(next); 
  }
}

NPCクラスが呼び出すのはStateのupdateだけ。
あとは勝手に状態遷移をやってくれそうな感じです。

ステートデザインパターンとしてはまだまだ実装すべき項目がありますが、コンセプトとしてはこの方針で問題なさそうです。

私が作成するステートマシンの基本要件は以下。

 

ステートマシンクラス

      1. ステートマシンは必ず「現在のステート」を持つ

2. ステートマシンは階層構造になっており、ステートマシンには親ステートマシンや子ステートマシンが存在する場合がある

3. ステートマシンは特定の間隔(ゲームであるならば、毎フレームが望ましい)でステートに次の遷移先ステートを問い合わせ、状態が更新される

4. 遷移先ステートが同一である場合、遷移は行わないと定義する(本来ステートマシンの元となる有限オートマトンにおいては、この操作は「自己遷移」と呼ばれるものだが、省略する)

5. ステートの遷移が行われた場合、遷移前のステートのイグジット処理と、遷移後のステートのエントリー処理を実行する

6. ステートマシンはイベントの通知を受けた時、現在のステートに処理すべきかどうか問い合わせる。この操作は、イベント処理するステートが見つかるまで子ステートマシンより再帰的に行われる

ステートクラス

      1. ステートは「次のステート」を持つ

2. ステートは「イベント」と「アクション/トランジション」のマップを持つ。ステートマシンより問い合わせが来た時、該当するイベントアクションが存在する場合、実行する

3. アクションは関数の実行、トランジションは遷移の発生である。ただし、拡張性のため、トランジションにはファクトリデザインパターンを採用する

 

そんなこんなで、実装したステートマシンが以下.
(業務のために本格的に作成したものですので、少し大規模になっています)

//HFStateMachine.hpp
#include "StateInterface.hpp"
#include "StateMachineUtils.hpp"
#include <memory>
#include <vector>
#include <map>

/* ステートマシンのベースクラスです ContextTypeは継承したクラスを渡します */
template <class ContextType, class Event>
class HFStateMachine : public std::enable_shared_from_this<HFStateMachine<ContextType, Event>>
{
public:
    typedef ContextType context_t;
    typedef HFStateBase<context_t, Event> state_t;
    typedef SMUtils<context_t, Event> Utils;
    typedef actionInterface<context_t> action_t;
    typedef factoryInterface<context_t> factory_t;
    friend std::shared_ptr<context_t>;
    
/*ステートマシンの生成はこの関数を使います(コンストラクタは不可)*/
    static std::shared_ptr<context_t> create(state_t* firstState) {
        auto context = std::make_shared<context_t>(new typename Utils::start);
        context->changeState(std::shared_ptr<state_t>(firstState));
        return context;
    }
    
    void setParent(std::shared_ptr<context_t> parent) {
        _parent = parent;
    }
    
    void addChild(std::shared_ptr<context_t> child) {
        child->setParent(derived());
        _children.push_back(child);
    }
    
    std::weak_ptr<context_t>& getParent() {
        return _parent;
    }
    
    const std::vector<std::shared_ptr<context_t>>& getChildren() {
        return _children;
    }
    
    const std::shared_ptr<state_t>& getState() {
        return _current;
    }
    
    void removeFromParent() {
        for(auto &&child: _children) {
            child->removeFromParent();
        }
        if(!_parent.expired()) {
            _parent.lock()->removeChild(derived());
        }
    }
    
    void removeChild(std::shared_ptr<context_t> child) {
        auto removeIt = std::find(_children.begin(), _children.end(), child);
        if(removeIt != _children.end()) {
            _children.erase(removeIt);
        }
    }
    
    void removeChildren() {
        _children.clear();
    }
    
/* このupdate関数は外側から呼び出してください */
    void update(float deltaTime)
    {
/* ステートに問い合わせします */
        const auto& _next = _current->update(deltaTime);
        changeState(_next);
        for(auto &&child: _children) {
            child->update(deltaTime);
        }
    }
    
    void changeState(const std::shared_ptr<state_t>& destState)
    {
        if(!destState) {
            return;
        }
        /* 自己遷移は何もしません */
        if( _current == destState ) {
            return;
        }
        /* ステートの遷移を行います */       
        _current->exit();
        _current->setNext(nullptr);
        
        removeChildren();
        
        destState->setNext(destState);
        destState->setContext(derived());
        
        _current = destState;
        
        destState->entry(derived());
    }
    
    std::shared_ptr<ContextType> derived()
    {
        return std::static_pointer_cast<ContextType>(this->shared_from_this());
    }
    
    bool dispatchEvent(const Event& e) {
        bool isSwallowed = false;
        /* 子ステートマシンに先にイベントを伝播します */
        if(!_children.empty()){
            for(auto &&child: _children){
                isSwallowed |= child->dispatchEvent(e);
            }
        }
        /* 子ステートマシンでイベントが処理されなかった場合 */
        if(!isSwallowed) {
            return _current->processEvent(e);
        }
        return false;
    }
    
    void end() {
        _current->setNext(new struct Utils::end);
    }
    
protected:
    std::shared_ptr<state_t> _current;
    std::weak_ptr<context_t> _parent;
    
    std::vector<std::shared_ptr<context_t>> _children;
    
    HFStateMachine(state_t* firstState)
    : _current(firstState)
    {
        
    }
    virtual ~HFStateMachine() {
        _current->exit();
    }
};

//StateInterface.hpp

#include "../SpiralLibrary/Utility/TupleUtils.hpp"
#include <map>
#include <memory>
#include <type_traits>

/* アクションはこのインターフェースを継承します */
template <class ContextType>
class actionInterface;

template <class ContextType>
class actionInterface {
public:
    virtual void exe(const std::shared_ptr<ContextType>& context) = 0;
};

/* トランジションはこのインターフェースを継承します */
template <class ContextType>
class factoryInterface {
public:
    virtual std::shared_ptr<typename ContextType::state_t> create(const std::shared_ptr<ContextType>& context) = 0;
};

/* トランジションが単純create関数の場合はこのヘルパを使います */
template<class ContextType, class State, bool hasDefaultConstructor, class... Args>
class _factoryDefault;


template<class ContextType, class State, class... Args>
using factoryDefault = _factoryDefault<ContextType, State, std::is_default_constructible<State>::value, Args...>;

/* デフォルトコンストラクタ版 */
template<class ContextType, class State, class... Args>
class _factoryDefault<ContextType, State, true, Args...> : public factoryInterface<ContextType>{
public:
    std::shared_ptr<typename ContextType::state_t> create(const std::shared_ptr<ContextType>& context) {
        return std::make_shared<State>();
    }
};

/* ユーザーコンストラクタ版 */
template<class ContextType, class State, class... Args>
class _factoryDefault<ContextType, State, false, Args...> : public factoryInterface<ContextType>{
public:
    _factoryDefault(Args... args) : _arguments(std::tie(args...)){}
    std::shared_ptr<typename ContextType::state_t> create(const std::shared_ptr<ContextType>& context) {
        return libspiral::tupleVariadicApply(static_cast<std::shared_ptr<State> (&)(Args&...)>(std::make_shared<State>), _arguments);
    }
    std::tuple<Args...> _arguments;
};

/* イベントはこのベースクラスを継承します */
template<class Enumration>
class EventBase {
public:
    EventBase(Enumration value) : _value(value) {}
    
    bool operator==(EventBase const& lhs)const;
    bool operator<(EventBase const& lhs)const;
    
private:
    Enumration _value;
};

template<class Enumration>
bool EventBase<Enumration>::operator==(EventBase const& lhs)const{
    return _value == lhs._value;
}

template<class Enumration>
bool EventBase<Enumration>::operator<(EventBase const& lhs)const{
    return _value < lhs._value;
}

/* ステートのベースクラスです */
template < class ContextType, class Event >
class HFStateBase : public std::enable_shared_from_this<HFStateBase<ContextType, Event>>
{
public:
    typedef ContextType context_t;
    typedef HFStateBase state_t;
    typedef actionInterface<ContextType> action_t;
    typedef factoryInterface<ContextType> factory_t;
    typedef std::map<Event, std::shared_ptr<factory_t>> transition_map;
    typedef std::map<Event, std::shared_ptr<action_t>> action_map;
    
    HFStateBase(){}
    virtual ~HFStateBase() = default;
    /* 遷移のエントリー処理です 必要に応じてオーバーライドしてください */
    virtual void entry(const std::shared_ptr<ContextType>& context){}
    
    /* 遷移のイグジット処理です 必要に応じてオーバーライドしてください */
    virtual void exit(){}
    
    /* 遷移先ステートの問い合わせです。また、経過時間を取得したい場合はこの関数をオーバーライドしますが、要件を満たすように記述してください */
    virtual std::shared_ptr<HFStateBase> update(float deltaTime) {
        if(_next) {
            return _next;
        }
        return this->shared_from_this();
    }
    
    void setContext(const std::shared_ptr<context_t>& context) {
        _context = context;
    }
    
    std::weak_ptr<context_t> getContext() {
        return _context;
    }
    
    void setNext(const std::shared_ptr<state_t>& state) {
        _next = state;
    }
    
   /* トランジションとイベントのペアを登録します */
    void addTransition(const Event& e, factory_t* factory) {
        _transition.insert(std::make_pair(e, std::shared_ptr<factory_t>(factory)));
    }

    /* アクションとイベントのペアを登録します */
    void addAction(const Event& e, action_t* act) { 
        _action.insert(std::make_pair(e, std::shared_ptr<action_t>(act)) ); 
    }
    
    /* イベントに対応するアクション、トランジションを追加します */
    bool processEvent(const Event& e) {
        auto itAction = _action.find(e);
        auto itTrans = _transition.find(e);
        
        if(itAction == _action.end() && itTrans == _transition.end()) {
            return false;
        }
        
        if(itAction != _action.end()) {
            itAction->second->exe(_context.lock());
        }
        if(itTrans != _transition.end()) {
            _next =  itTrans->second->create(_context.lock());
        }
        return true;
    }
    
    
    
protected:
    std::shared_ptr<state_t> _next;
    std::weak_ptr<context_t> _context;
    transition_map _transition;
    action_map _action;
    
};

//StateMachineUtils.hpp
#include "StateInterface.hpp"

template<class context_t, class event_t>
struct SMUtils {
    typedef actionInterface<context_t> action_t;
    typedef HFStateBase<context_t, event_t> state_t;
public:
    struct releaseChildMachines : public action_t {
        void exe(const std::shared_ptr<context_t>& context) {
            context->removeChildren();
        }
    };
    
    struct start : public state_t {
        
    };
    
    struct end : public state_t{
        void entry(const std::shared_ptr<context_t>& context) override{
            context->removeChildren();
            context->removeFromParent();
        }
    };
};

ステートマシンはupdate関数によってステートの状態を毎回チェックしています。
返ってきたステートが同一ではない場合、ステートの遷移を行います。
その際、ステートのentry関数とexit関数を実行します。

また、dispatchEvent関数によってイベントの処理を行います。
子ステートマシンに先に問い合わせた後、イベントが処理されるまで再帰的に実行されます。

また、メモリの安全性の考慮し、スマートポインタを使用します。

ステートクラスはアクションマップとトランジションマップを持ち、該当するイベントをprocessEvent関数によって実行します。
_nextメンバは次の遷移先ステートを表しており、update関数によって次のステートの問い合わせを受けた場合、_nextが存在するなら_nextを、存在しないならば自身を返します。

こんな感じで、実際にNPCが歩くだけのプログラムを作ってみました。
リポジトリを置いとくので、ステートマシンの使い方の参考がてらどうぞ!
cocos2dx v3.11が必要です。

https://github.com/Riyaaaaa/StateMachineSample

実行結果

ZjItNIl46X

こいつ…動くぞ!

素材提供者 直江ジャスティス様
(https://twitter.com/justicenaoe)

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です