ここでは、ロボットの行動を表現するときに状態遷移を使う方法を説明します。

状態遷移とは

状態遷移とは、何かのイベントに基づいて出力を変えるときに利用できる仕組みです。例えば「ロボットが適当に移動しながら、ゴミを検出して片付ける」というタスクを考えてみます。このロボットの動作を書き出してみると、例えば以下のようになります。

向きを変更する。
一定の距離だけ直進しながら、ゴミがないかを確認する。
- ゴミを検出したら、ゴミを片付ける処理を行う。
- 一定の距離だけ移動してもゴミが検出できなければ、向きを変更する。
- 移動できなくなったら、向きを変更する。

この状態遷移は、以下のように記述できます。

以降では、この状態遷移をプログラムでどう実現するのかについて、説明します。

C++ と Lua スクリプトでの状態遷移の実現

ここでは、「ゲーム AI プログラミング」(O'REILLY) で紹介されている手法を説明します。簡単に要約すると、"向きを変更する" などの実際の処理は C++ で実装し、"ゴミを検出したら状態を遷移させる" といったフローの管理を Lua スクリプトで記述します。

ロジックを Lua スクリプトで記述するのは、ロジック部分の変更を行ってもプログラムをコンパイルレスを実現するためです。コンパイルレスが実現できると

コンパイル時間がなくなることで、開発時のストレスが減る。
C++ のプログラマでなくても、ロジックが記述できるようになる。

といったメリットがあります。

仕組み

C++ で処理を記述し Lua スクリプトでロジックを記述するために luabind を利用します。C++ でロボットのクラスを作成し、luabind を用いて C++ から Lua スクリプト内で記述した処理を呼び出します。

以下に、この処理を実装したファイルのリストを示します。

robot_ai_example.cpp

main() 関数が含まれるプログラムです。
ロボットの制御で使う C++ 関数を Lua スクリプトで利用できるようにするための関数を最初に呼び出しています。また、このサンプルでは、状態遷移の処理を数回行うのみにしています。

#include <cstddef>
#include "geometry_bind.h"
#include "Lua_handler.h"
#include "Cleaner_robot.h"
using namespace hrk;
int main(int argc, char *argv[])
{
    static_cast<void>(argc);
    static_cast<void>(argv);
    Cleaner_robot robot;
    // Lua スクリプトから C++ の関数が使えるようにする
    lua_State* lua = Lua_handler::pointer();
    geometry_bind(lua);
    // 状態遷移の処理を数回繰り返している
    // 実際のロボットプログラムでは、無限ループにしてもよい
    enum { Action_times = 15 };
    for (size_t i = 0; i < Action_times; ++i) {
        robot.update();
    }
    return 0;
}

robot_ai.lua

ロボットのロジックを定義した Lua スクリプトです。
"Enter" で定義される Lua 関数は、その状態に遷移するときに１回のみ評価されます。また "Execute" で定義される Lua 関数は C++ の Cleaner_robot::update() が呼ばれる度に評価されます。最後に "Exit" で定義される Lua 関数は "Enter" の逆で、その状態から別の状態に遷移するときの評価されます。

A の状態の実行後、B という状態に遷移するときに呼び出される関数は、以下のようになります。

A の Execute
A の Exit
B の Enter

また、この Lua スクリプト内の change_state() の関係をパースして生成した状態遷移図を示します。

Lua スクリプトをパースして生成した状態遷移の図

-- 「適当に移動しながら、ゴミを検出して片付けるロボット」の AI
robot_start_state = {} -- state: Start
robot_start_state["Enter"] =
   function(robot)
   end
robot_start_state["Execute"] =
   function(robot)
      print("== in robot_start state.")
      robot:change_state("robot_change_direction_state")
   end
robot_start_state["Exit"] =
   function(robot)
   end
robot_change_direction_state = {} -- state: 向きを変更する
robot_change_direction_state["Enter"] =
   function(robot)
      -- ランダムな向きを向かせることにする
      local degree = 360 * math.random()
      -- 向きの変更を指示する
      print("turn_direction(" .. (degree - degree % 1.0).. " [deg])")
      robot:turn_direction(deg(degree))
   end
robot_change_direction_state["Execute"] =
   function(robot)
      print("== in change_direction state.")
      if robot:is_stable() then
         -- 向きの変更が完了したら、次の状態に遷移させる
         print("is_stable() return true")
         robot:change_state("robot_go_straight_state")
      end
   end
robot_change_direction_state["Exit"] =
   function(robot)
   end
robot_go_straight_state = {} -- state: 一定の距離だけ直進する
robot_go_straight_state["Enter"] =
   function(robot)
      -- 直進させる
      print("go straight()")
      robot:go_straight()
   end
robot_go_straight_state["Execute"] =
   function(robot)
      print("== in go_straight state.")
      if robot:is_obstacle_detected() or robot:is_straight_moved() then
         -- 障害物を検出したら、向きを変える
         -- 一定の距離だけ移動したら、向きを変える
         print("obstacle detected or moved enough")
         robot:change_state("robot_change_direction_state")
      elseif robot:is_trash_detected() then
         -- ゴミを検出したら、片付ける
         print("trash is detected.")
         robot:change_state("robot_handle_trash_state")
      end
   end
robot_go_straight_state["Exit"] =
   function(robot)
      -- ロボットの移動を停止させる
      robot:stop()
   end
robot_handle_trash_state = {} -- state: ゴミを片付ける
robot_handle_trash_state["Enter"] =
   function(robot)
      print("clean()")
      robot:clean()
   end
robot_handle_trash_state["Execute"] =
   function(robot)
      print("== in handle_trash state.")
      if robot:is_cleaned() then
         -- ゴミを片付けたら、移動を再開させる
         print("cleaned !")
         robot:change_state("robot_change_direction_state")
      end
   end
robot_handle_trash_state["Exit"] =
   function(robot)
   end

robot_ai_example.cpp を実行したときの出力結果

% ./robot_ai_example
== in robot_start state.
turn_direction(302 [deg])
== in change_direction state.
is_stable() return true
go straight()
== in go_straight state.
== in go_straight state.
== in go_straight state.
obstacle detected or moved enough
turn_direction(120 [deg])
== in change_direction state.
is_stable() return true
go straight()
== in go_straight state.
trash is detected.
clean()
== in handle_trash state.
== in handle_trash state.
cleaned !
turn_direction(199 [deg])
== in change_direction state.
is_stable() return true
go straight()
== in go_straight state.
== in go_straight state.
obstacle detected or moved enough
turn_direction(184 [deg])
== in change_direction state.
is_stable() return true
go straight()
== in go_straight state.
== in go_straight state.

実行結果より、状態遷移が Clean_robot.cpp と clean_robot_ai.lua の実装通りに行われていることが確認できます。

Cleaner_robot.h

ロボットが行う処理を実装した C++ クラスです。

#ifndef CLEANER_ROBOT_H
#define CLEANER_ROBOT_H
/*
  「適当に移動しながら、ゴミを検出して片付けるロボット」の例
*/
#include <memory>
#include <luabind/luabind.hpp>
#include "Entity.h"
namespace hrk
{
    class Angle;
}
class Cleaner_robot : public hrk::Entity
{
 public:
    Cleaner_robot(void);
    ~Cleaner_robot(void);
    void update(void);
    void change_state(const char* state_name);
    bool is_stable(void);
    void stop(void);
    void turn_direction(const hrk::Angle& direction);
    void go_straight(void);
    bool is_obstacle_detected(void);
    bool is_straight_moved(void);
    bool is_trash_detected(void);
    void clean(void);
    bool is_cleaned(void);
 private:
    Cleaner_robot(const Cleaner_robot& rhs);
    Cleaner_robot& operator = (Cleaner_robot& rhs);
    struct pImpl;
    std::auto_ptr<pImpl> pimpl;
};
#endif

Cleaner_robot.cpp

今回はサンプルの提示ということで、具体的な処理は実装されていません。

/*
  \example Cleaner_robot.cpp
  「適当に移動しながら、ゴミを検出して片付けるロボット」の例
*/
#include "Angle.h"
#include "luabind_initializer.h"
#include "Lua_handler.h"
#include "Scripted_state_machine.hpp"
#include "Cleaner_robot.h"
using namespace hrk;
using namespace luabind;
namespace
{
    typedef Scripted_state_machine<Cleaner_robot> State_machine;
}
struct Cleaner_robot::pImpl
{
    lua_State* lua_;
    State_machine state_machine_;
    int is_stable_called_times_;
    int is_straight_moved_called_times_;
    int is_cleaned_called_times_;
    pImpl(Cleaner_robot* parent)
        : lua_(luabind_initializer()), state_machine_(parent, lua_),
          is_stable_called_times_(0), is_straight_moved_called_times_(0),
          is_cleaned_called_times_(0)
    {
        // AI スクリプトの読み込み
        Lua_handler::dofile(lua_, "robot_ai.lua");
        // 状態遷移の初期化
        bind_class(lua_);
        state_machine_.set_current_state("robot_start_state");
    }
    void bind_class(lua_State* lua)
    {
        module(lua)
            [
             class_<Cleaner_robot>("Cleaner_robot")
             .def("change_state", &Cleaner_robot::change_state)
             .def("is_stable", &Cleaner_robot::is_stable)
             .def("stop", &Cleaner_robot::stop)
             .def("turn_direction", &Cleaner_robot::turn_direction)
             .def("go_straight", &Cleaner_robot::go_straight)
             .def("is_obstacle_detected", &Cleaner_robot::is_obstacle_detected)
             .def("is_straight_moved", &Cleaner_robot::is_straight_moved)
             .def("is_trash_detected", &Cleaner_robot::is_trash_detected)
             .def("clean", &Cleaner_robot::clean)
             .def("is_cleaned", &Cleaner_robot::is_cleaned)
             ];
    }
};
Cleaner_robot::Cleaner_robot(void) : pimpl(new pImpl(this))
{
    // ロボットの位置を、原点の X 軸の正の方向に初期化する
    // !!! 実装しない
}
Cleaner_robot::~Cleaner_robot(void)
{
}
void Cleaner_robot::update(void)
{
    pimpl->state_machine_.update();
}
void Cleaner_robot::change_state(const char* state_name)
{
    pimpl->state_machine_.change_to(state_name);
}
bool Cleaner_robot::is_stable(void)
{
    // ロボットの動作が安定したら true を返す
    // 今回は、ロボットの向きを変える動作が完了したかの判定に利用している
    // !!! １回ほど呼び出されると、その次には true を返すようにする
    enum { Retry_simulate_times = 1, };
    if (++pimpl->is_stable_called_times_ >= Retry_simulate_times) {
        pimpl->is_stable_called_times_ = 0;
        return true;
    }
    return false;
}
void Cleaner_robot::stop(void)
{
    // ロボットを停止させる
    // !!! 実装しない
}
void Cleaner_robot::turn_direction(const Angle& direction)
{
    (void)direction;
    // 指定された角度の方向にロボットの向きを変える
    // !!! 実装しない
}
void Cleaner_robot::go_straight(void)
{
    // ロボットの向いている方向に直進する
    // !!! 実装しない
}
bool Cleaner_robot::is_obstacle_detected(void)
{
    // !!! 3/10 の確率で障害物に阻まれることにする
    return ((1.0 * rand() / RAND_MAX) < 0.3) ? true : false;
}
bool Cleaner_robot::is_straight_moved(void)
{
    // !!! ５回ほど呼び出されると、その次には true を返すようにする
    enum { Retry_simulate_times = 5, };
    if (++pimpl->is_straight_moved_called_times_ >= Retry_simulate_times) {
        pimpl->is_straight_moved_called_times_ = 0;
        return true;
    }
    return false;
}
bool Cleaner_robot::is_trash_detected(void)
{
    // !!! 4/10 の確率でゴミを見付けることにする
    return ((1.0 * rand() / RAND_MAX) < 0.4) ? true : false;
}
void Cleaner_robot::clean(void)
{
    // ゴミを片付ける
    // !!! 実装しない
}
bool Cleaner_robot::is_cleaned(void)
{
    // !!! ２回ほど呼び出されると、その次には true を返すようにする
    enum { Retry_simulate_times = 2, };
    if (++pimpl->is_cleaned_called_times_ >= Retry_simulate_times) {
        pimpl->is_cleaned_called_times_ = 0;
        return true;
    }
    return false;
}

Scripted_state_machine.hpp

状態遷移を実現するための、参考文献で紹介されている C++ テンプレートです。
詳細は、書籍をご覧下さい。

#ifndef HRK_SCRIPTED_STATE_MACHINE_HPP
#define HRK_SCRIPTED_STATE_MACHINE_HPP
#include <iostream>
#include <luabind/luabind.hpp>
namespace hrk
{
    template <class T>
    class Scripted_state_machine
    {
    public:
        Scripted_state_machine(T* owner, lua_State* lua)
            : owner_(owner), lua_(lua)
        {
        }
        void set_current_state(const std::string& state_name)
        {
            luabind::object global = luabind::globals(lua_);
            luabind::object state = global[state_name];
            check_state_is_table(state, state_name);
            previous_state_ = current_state_;
            current_state_ = state;
            current_state_name_ = state_name;
        }
        luabind::object change_to_previous(void) const
        {
            return previous_state_;
        }
        bool update(void)
        {
            if (!current_state_.is_valid()) {
                return false;
            }
            if (luabind::type(current_state_["Execute"]) != LUA_TFUNCTION) {
                std::string state_name = current_state_name_ + "['Execute']";
                std::cerr << "Not found function: " << state_name << std::endl;
                return false;
            }
            current_state_["Execute"](owner_);
            return true;
        }
        bool change_to(const std::string& next_state_name)
        {
            if (current_state_.is_valid()) {
                if (luabind::type(current_state_["Exit"]) != LUA_TFUNCTION) {
                    std::cerr << "Not found function: "
                              << current_state_name_ << "['Exit']"
                              << std::endl;
                    return false;
                }
                current_state_["Exit"](owner_);
            }
            // 直前の状態を保持しておく
            previous_state_ = current_state_;
            current_state_name_ = next_state_name;
            luabind::object global = luabind::globals(lua_);
            luabind::object next_state = global[next_state_name];
            check_state_is_table(next_state, next_state_name);
            current_state_ = next_state;
            if (luabind::type(current_state_["Enter"]) != LUA_TFUNCTION) {
                std::cerr << "Not found function: "
                          << next_state_name << "['Enter']" << std::endl;
                return false;
            }
            current_state_["Enter"](owner_);
            return true;
        }
    private:
        void check_state_is_table(const luabind::object& state,
                                  const std::string& state_name)
        {
            if (luabind::type(state) != LUA_TTABLE) {
                std::cerr << "'" << state_name
                          << "' variable is not table." << std::endl;
                if (luabind::type(state) == LUA_TNIL) {
                    std::cerr << "'" << state_name << "' is nil." << std::endl;
                }
            }
        }
        T* owner_;
        lua_State* lua_;
        luabind::object current_state_;
        luabind::object previous_state_;
        std::string current_state_name_;
    };
}
#endif

状態遷移は、このような AI に近い処理以外にも、いろいろな用途に利用できます。
無理のない範囲での利用をお勧めします。

また luabind は便利ですが、これを利用したソースコードのコンパイル時間は長くなってしまうため、ソースコードの構成は必要に応じて工夫が必要です。