游戏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（）函数来根据复合节点地址和子节点偏移地址获得子节点指针。

总结

以上，就是关于行为树的内存优化方式，当然凡事无绝对，究竟如何构造行为树应当根据实际情况选择，下一篇我们将讲述另一种行为树优化方法。