游戲AI(二)—行為樹優化之記憶體優化

上一篇我們講到了AI架構之一的行為樹，本篇文章和下一篇文章我們將對行為樹進行優化，在本篇文章中我們講到的是記憶體優化

問題

上一篇中我們設計的行為樹由於直接採用new進行動態記憶體分配，沒有自己進行管理。因此行為樹各節點的存儲位置會散佈在記憶體空間的各處，行為樹在不同節點中切換時會導致Cache頻繁失效。
通過記憶體管理改變行為樹節點的記憶體分佈，可以顯著提高行為樹的記憶體性能。

解決辦法

我們可以在BehaviorTree中引入一組記憶體分配的API來保證各節點儘量分配在連續的記憶體上，代碼如下

BehaviorTree(Behavior*InRoot):Root(InRoot),
Buffer(new uint8_t[MaxBehaviorTreeMemory]),Offset(0){}
~BehaviorTree(){ delete[] Buffer; }
    
template<typename T>
        T* Allocate()
        {
            T* Node = new((void*)((uintptr_t)Buffer + Offset)) T;
            Offset += sizeof(T);
            assert(Offset < MaxBehaviorTreeMemory);
            return Node;
        }

我們在BehaviorTree中引入一個Allocate函數用來負責所有節點的記憶體分配。
當行為樹被構造時，一塊用於保存節點的記憶體空間Bufffer會隨之分配，Allocate函數通過Placement new在Buffer上進行記憶體分配，通過Offset記錄分配已分配記憶體的偏移地址。
通過這種方式我們可以讓節點分配在連續的記憶體上，同時通過控制分配節點的順序（如深度遍歷廣度遍歷等），我們可以進一步減少行為樹遍歷時產生的Cache失效，提高記憶體性能。）

複合節點

除了對節點分配進行優化，我們還可以改變複合節點的記憶體佈局，進一步提升性能。

class Composite :public Behavior
    {
    public:
        friend class BehaviorTree;
        virtual void AddChild(Behavior* InChild) override
        { 
            assert(ChildrenCount < MaxChildrenPerComposite);
            ptrdiff_t p = (uintptr_t)InChild - (uintptr_t)this;
            assert(p < std::numeric_limits<uint16_t>::max());
            Children[ChildrenCount++] = static_cast<uint16_t>(p);
        }   

        Behavior* GetChild(size_t index)
        {
            assert(index < MaxChildrenPerComposite);
            return (Behavior*)((uintptr_t)this + Children[index]);
        }

        size_t GetChildrenCount()
        {
            return ChildrenCount;
        }

protected:
        uint16_t Children[MaxChildrenPerComposite];
        uint16_t ChildrenCount = 0;
    };

在如上代碼中，我們通過靜態數組代替vector，避免在存儲時vector所產生的額外堆操作，通過用保存子節點相對於複合節點的偏移地址來代替直接保存子節點指針以節省記憶體空間。由於更換了子節點的存儲方式，我們需要通過getchild（）函數來根據複合節點地址和子節點偏移地址獲得子節點指針。

總結

以上，就是關於行為樹的記憶體優化方式，當然凡事無絕對，究竟如何構造行為樹應當根據實際情況選擇，下一篇我們將講述另一種行為樹優化方法。
[gihub鏈接][1]