UE4やUnityのおかげで、すっかり普及した感のあるビヘイビアツリー。
基本的な実装方法や使用方法についての解説は、ネットを少し探せばたくさん見つかります。
今回は、より高速で効率的なビヘイビアツリーの実装について考えてみます。

ビヘイビアツリーとは

基本的な仕組みについては割愛。
下記のスライドが、非常に分かりやすいと思います。
https://www.slideshare.net/sindharta/behaviour-treeingriffon/

静的なツリーデータ

ビヘイビアツリーは、振る舞いを表す静的なデータとして表現することができます。
必要なのは、ノードの種類、ノード自身を表す属性、そして親子関係のみとなります。
そのため、ビヘイビアツリーを実行するインスタンス間でツリーデータを共有することができれば、メモリを大幅に節約することができます。
さらに、ツリーノードの巡回は深さ優先で行われるため、各ツリーノードのメモリ配置を深さ優先で連続したメモリに配置することで、実行時のキャッシュヒット率も上げられると考えられます。

インスタンスごとの実行時データ

ビヘイビアツリーの実行時に必要なデータは、各インスタンスごとにノード固有のデータが要求されます。
Sequenceノードであれば現在有効な子ノードのインデックス、Actionノードであれば関連するエンティティへのポインタなどです。

通常、ビヘイビアツリーを実行するインスタンスは、常にカレントの有効なノードにしか触りません。
これは、巨大なビヘイビアツリーであっても実行時に必要なデータ量というのはごく少量(数バイト～数十バイト程度)だと言うことです。
そのため、各インスタンスがカレントのノードを有効にする際に必要なメモリを確保し、ノードが結果を返すか中断されたらメモリを解放するようにすれば、実行時のメモリフットプリントを非常に小さくすることができます。
メモリの確保には小さなメモリを高速に割り当てられる bucket-based allocator などを用意すると良いでしょう。

ツリーデータと実行時データの分離

これはおおよそ機械的に、状態を持つパラメータとそうでないものを分けることで実現できます。

class Sequence : public Composite {
public:
    struct RuntimeData {
        uint8_t currentChild;  // 現在有効な子ノードのインデックス
    };
};

実行時データへのアクセス方法

実際にビヘイビアツリーの更新を行うためには、各ノードにおいて、インスタンスごとの実行時データ領域を取得する方法が必要になります。
1つの解決案としては、インスタンスとツリーノードにそれぞれユニークIDを持たせ、これらの値をキーとして実行時データ領域を取得できるようにすることです。

inline uint32_t makeRuntimeDataId(uint32_t entity, uint32_t uid) {
    // https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
    uint32_t ids[] = {entity, uid};
    return FNV(ids, sizeof(ids));
}

void BehaviorNode::execute(uint32_t behaviorTreeInstanceId) {
    uint32_t runtimeDataId = makeRuntimeDataId(behaviorTreeInstanceId, mUid);
    // mRuntimeDataManagerはノードの作成時に渡される
    // これは数百KBから数MB程度の小さなヒープを管理しており、渡されたハッシュ値をキーに実行時データのメモリ領域を管理している
    void* runtimeData = mRuntimeDataManager->find(runtimeDataId);
    if (!runtimeData) {
        runtimeData = mRuntimeDataManager->allocateRuntimeDataMemory(runtimeDataId);
        onInitialize(behaviorTreeInstanceId, runtimeData);
    }

    BehaviorStatus status = update(behaviorTreeInstanceId, runtimeData);

    if (status != BehaviorStatus::RUNNING) {
        onTerminate(behaviorTreeInstanceId, runtimeData);
        mRuntimeDataManager->deallocate(runtimeDataId);
    }
}

参考

Game AI Pro
http://www.gameaipro.com/

Game AI Pro Section 2: Architecture
6. The Behavior Tree Starter Kit, Alex Champandard, Philip Dunstan
http://www.gameaipro.com/GameAIPro/GameAIPro_Chapter06_The_Behavior_Tree_Starter_Kit.pdf

Amazon Lumberyard
Modular Behavior Tree
C++ Implementation: Runtime data
https://docs.aws.amazon.com/lumberyard/latest/userguide/ai-scripting-mbt.html