15. 空间拓扑与动态扩容

// 文件：BigWorld-Engine-14.4.1/programming/bigworld/server/cellappmgr/bsp_node.hpp（简化）
enum BSPNodeType
{
    BSP_NODE_HORIZONTAL,   // 水平分割线（沿 X 轴分割）
    BSP_NODE_VERTICAL,     // 垂直分割线（沿 Z 轴分割）
    BSP_NODE_LEAF          // 叶子节点 = Cell
};

class BSPNode : public WatcherProvider
{
public:
    virtual void balance(const BW::Rect& range, float loadSafetyBound,
        bool isShrinking) = 0;
    virtual void updateRanges(const BW::Rect& range) = 0;
    virtual float updateLoad() = 0;
    virtual float avgLoad() const = 0;
    virtual float totalSmoothedLoad() const = 0;

    const BW::Rect& range() const { return range_; }
    const EntityBoundLevels& entityBoundLevels() const { return entityBoundLevels_; }

protected:
    BW::Rect range_;                         // 节点管理的空间范围
    EntityBoundLevels entityBoundLevels_;    // 实体在各层级的边界数据
    BW::Rect chunkBounds_;                   // 地形块边界
    int numRetiring_;                        // 正在退休的 Cell 数
    float areaNotLoaded_;                    // 未加载面积
};

// 文件：BigWorld-Engine-14.4.1/programming/bigworld/server/cellappmgr/internal_node.hpp（简化）
class InternalNode : public BSPNode
{
public:
    InternalNode(BSPNode* pLeft, BSPNode* pRight,
        bool isHorizontal, float position);

    // 负载均衡核心
    void balance(const BW::Rect& range, float loadSafetyBound,
        bool isShrinking);
    BalanceDirection doBalance(float loadSafetyBound);
    void balanceChildren(float loadSafetyBound, BalanceDirection balanceDir);

    float updateLoad();
    float avgLoad() const;

    // 分割线管理
    void position(float newPos) { position_ = newPos; }
    float position() const { return position_; }
    bool isHorizontal() const { return isHorizontal_; }

    BSPNode* pLeft() const { return pLeft_; }
    BSPNode* pRight() const { return pRight_; }

private:
    enum BalanceDirection
    {
        BALANCE_LEFT,     // 左子树负载更重，分割线应该左移
        BALANCE_NONE,     // 两边均衡
        BALANCE_RIGHT     // 右子树负载更重，分割线应该右移
    };

    BSPNode* pLeft_;          // 左/下子树
    BSPNode* pRight_;         // 右/上子树
    bool isHorizontal_;       // 分割方向
    float position_;          // 分割线位置
    float balanceAggression_; // 平衡激进度
};

// 文件：BigWorld-Engine-14.4.1/programming/bigworld/server/cellapp/space.hpp（简化）
// SpaceBranch 是 CellApp 侧维护的 BSP 节点视图
class SpaceBranch
{
    bool isHorizontal_;       // 分割方向
    float position_;          // 分割线位置

    SpaceNode* pLeft_;        // 左/下子树
    SpaceNode* pRight_;       // 右/上子树

    void visitRect(const BW::Rect& rect, CellInfoVisitor& visitor);
    const CellInfo* pCellAt(float x, float z) const;
};

// 文件：BigWorld-Engine-14.4.1/programming/bigworld/server/cellappmgr/internal_node.cpp（简化）
InternalNode::BalanceDirection InternalNode::doBalance(float loadSafetyBound)
{
    const float leftAvgLoad = pLeft_->avgLoad();
    const float rightAvgLoad = pRight_->avgLoad();
    const float nodeAvgLoad = this->avgLoad();

    // 计算负载差异（带符号：正数=左重，负数=右重）
    float loadDiff = (leftAvgLoad > rightAvgLoad) ?
        fabs(leftAvgLoad - nodeAvgLoad) :
        -fabs(rightAvgLoad - nodeAvgLoad);

    // 从负载差异推导平衡方向
    BalanceDirection balanceDir = this->dirFromLoadDiff(loadDiff);

    // 检查是否应该移动分割线
    bool shouldMove = (balanceDir != BALANCE_NONE) &&
        (pFromNode->maxLoad() < loadSafetyBound);

    if (shouldMove)
    {
        // 计算分割线应该移动多远
        float entityLimit = this->entityLimitInDirection(balanceDir,
            loadDiff * balanceAggression_);

        // 可选：限制在地形块（chunk）边界上移动
        float chunkLimit = shouldLimitToChunks ?
            this->chunkLimitInDirection(balanceDir) : entityLimit;

        // 取最近的限制
        newPos = this->closestLimit(position_, entityLimit,
            chunkLimit, balanceDir);
    }

    position_ = newPos;  // 移动分割线
    return balanceDir;
}

void InternalNode::balanceChildren(float loadSafetyBound,
    BalanceDirection balanceDir)
{
    // 递归到子节点继续均衡
    if (balanceDir == BALANCE_LEFT || balanceDir == BALANCE_NONE)
        pLeft_->balance(range_, loadSafetyBound, isShrinking);

    if (balanceDir == BALANCE_RIGHT || balanceDir == BALANCE_NONE)
        pRight_->balance(range_, loadSafetyBound, isShrinking);
}

// 文件：BigWorld-Engine-14.4.1/programming/bigworld/server/cellappmgr/entity_bound_levels.hpp（简化）
class EntityBoundLevels
{
public:
    void merge(const EntityBoundLevels& left, const EntityBoundLevels& right,
        bool isHorizontal, float position);

    float entityBoundForLoadDiff(float loadDiff, bool isHorizontal,
        bool isMax, float defaultPosition) const;

private:
    typedef BW::vector<BW::Rect> Rects;
    Rects entityBounds_;     // 实体边界矩形（用于计算分割线位置）
    Rects entityLoads_;      // 实体负载信息
};

// 文件：BigWorld-Engine-14.4.1/programming/bigworld/server/cellappmgr/cell_app_group.hpp（简化）
class CellAppGroup
{
public:
    void addCell();                                    // 扩容：添加新 Cell
    void checkForUnderloaded(float loadLowerBound);    // 缩容：检查是否需要移除 Cell
    float avgLoad(int ifNumRemoved = 0) const;         // 计算平均负载

    typedef BW::set<CellApp*> Set;
    Set set_;                                          // CellApp 集合
    float avgLoad_;                                    // 当前平均负载
};

// 文件：BigWorld-Engine-14.4.1/programming/bigworld/server/cellappmgr/cell_app_group.cpp（简化）
void CellAppGroup::checkForUnderloaded(float loadLowerBound)
{
    // 如果移除一个 CellApp 后平均负载仍然低于下界
    if (this->avgLoad(1) < loadLowerBound)
    {
        CellApp* pLeastLoaded = NULL;
        float leastLoad = FLT_MAX;

        // 找到负载最轻的 CellApp
        iterator iter = this->begin();
        while (iter != this->end())
        {
            if (!(*iter)->hasOnlyRetiringCells() &&
                (*iter)->smoothedLoad() < leastLoad)
            {
                pLeastLoaded = *iter;
                leastLoad = (*iter)->smoothedLoad();
            }
            ++iter;
        }

        // 让它退休所有 Cells
        if (pLeastLoaded)
            pLeastLoaded->retireAllCells();
    }
}

// 文件：BigWorld-Engine-14.4.1/programming/bigworld/server/cellapp/offload_checker.hpp（简化）
class OffloadChecker
{
public:
    void run();   // 执行迁移检查

    void addToOffloads(EntityPtr pEntity,
        CellAppChannel* pOffloadDestination);

private:
    void sendOffloads();
    void sendOffload(OffloadList::const_iterator iOffload);

    typedef std::pair<EntityPtr, CellAppChannel*> OffloadEntry;
    typedef BW::vector<OffloadEntry> OffloadList;

    Cell& cell_;
    OffloadList offloadList_;          // 待迁移的实体列表
    uint numGhostsDeleted_;            // 已删除的 Ghost 数量
};

// 文件：BigWorld-Engine-14.4.1/programming/bigworld/server/cellapp/offload_checker.cpp（简化）
void OffloadChecker::run()
{
    if (cell_.space().isShuttingDown())
        return;

    // 检查每个 real entity 是否需要迁移
    Cell::Entities::iterator iEntity = cell_.realEntities().begin();
    while (iEntity != cell_.realEntities().end())
    {
        EntityPtr pEntity = *iEntity;
        EntityGhostMaintainer entityGhostMaintainer(*this, pEntity);
        entityGhostMaintainer.check();
        ++iEntity;
    }

    // 发送待迁移的实体
    this->sendOffloads();
}

// 文件：BigWorld-Engine-14.4.1/programming/bigworld/server/baseapp/dead_cell_apps.cpp（简化）
class DeadCellApp
{
    static const int MAX_AGE = 10;   // 保留 10 秒
    Mercury::Address addr_;
    uint64 timestamp_;
};

class DyingCellApp
{
public:
    bool tick(const Bases& bases);   // 每 tick 恢复一批实体
    void onCompleted(Mercury::NetworkInterface& intInterface);

private:
    Mercury::Address addr_;
    BW::map<SpaceID, Mercury::Address> newDestinations_;  // Space → 新 CellApp
};

// 文件：kbe/src/server/cellapp/space.h
class Space : public Entity
{
    BASE_SCRIPT_HREADER(Space, Entity)
public:
    Space(ENTITY_ID id, const ScriptDefModule* pScriptModule);
    ~Space();
};

// 文件：kbe/src/server/cellapp/spacememory.h
class SpaceMemory
{
    // 每个 Space 只有一个 Cell
    Cell* pCell_;

    // 一个 CoordinateSystem 管理所有实体
    CoordinateSystem coordinateSystem_;

    // 实体列表
    SPACE_ENTITIES entities_;
};

// Cellapp 中的 teleport 机制
void Cellapp::reqTeleportToCellApp(Network::Channel* pChannel,
    MemoryStream& s)
{
    // 手动将实体从当前 CellApp 迁移到目标 CellApp
    // 通过脚本调用触发
}

// 文件：kbe/src/server/cellapp/spacememory.h
// 每个space最多只有一个cell
Cell* pCell_;

// 文件：kbe/src/server/cellapp/witness.cpp
// 当前这么做能解决问题，但是在space多cell分割的情况下将会出现问题