Q3: 什么是 AOI（Area of Interest）？有哪些实现方式？各有什么优缺点？

// 分层 AOI 设计
class LayeredAOI {
public:
    // 定义 AOI 层级
    enum Layer {
        LAYER_GLOBAL = 0,    // 全服范围（公会、世界BOSS）
        LAYER_REMOTE = 1,    // 远程范围（500m）
        LAYER_NORMAL = 2,    // 正常范围（100m）
        LAYER_NEARBY = 3,    // 近距离范围（20m）
        LAYER_COUNT
    };

    // 每层使用不同的数据结构
    struct LayerConfig {
        float viewRadius;           // 视野半径
        bool useGrid;               // 是否使用网格
        bool useTower;              // 是否使用兴趣索引
    };

    LayerConfig configs[LAYER_COUNT] = {
        {FLT_MAX, false, false},    // 全服：使用列表
        {500.0f,  true,  false},    // 远程：大网格
        {100.0f,  true,  true },    // 正常：网格 + 索引
        {20.0f,   true,  true }     // 近距离：小网格
    };

    // 实体可以属于多个层级
    struct EntityLayers {
        std::bitset<LAYER_COUNT> layers;
    };

    // 查询某个实体的可见实体
    std::vector<Entity*> queryVisible(Entity* entity) {
        std::vector<Entity*> result;
        auto& layers = getEntityLayers(entity);

        for (int i = 0; i < LAYER_COUNT; ++i) {
            if (layers.test(i)) {
                auto visible = queryInLayer(entity, i);
                result.insert(result.end(), visible.begin(), visible.end());
            }
        }

        return result;
    }
};

class GridAOI {
    struct Grid {
        std::unordered_set<Entity*> entities;
    };

    // 网格大小 = AOI 半径
    const float GRID_SIZE = 100.0f;
    int gridWidth, gridHeight;
    std::vector<std::vector<Grid>> grids;

    // 获取实体所在格子
    std::pair<int, int> getGridPos(float x, float y) {
        return {
            (int)(x / GRID_SIZE),
            (int)(y / GRID_SIZE)
        };
    }

    // 获取九宫格范围内的实体
    std::vector<Entity*> getVisibleEntities(Entity* entity) {
        auto [gx, gy] = getGridPos(entity->x, entity->y);
        std::vector<Entity*> result;

        // 遍历九宫格
        for (int dy = -1; dy <= 1; ++dy) {
            for (int dx = -1; dx <= 1; ++dx) {
                int nx = gx + dx;
                int ny = gy + dy;
                if (isValidGrid(nx, ny)) {
                    auto& grid = grids[ny][nx];
                    result.insert(result.end(),
                               grid.entities.begin(),
                               grid.entities.end());
                }
            }
        }

        return result;
    }

    // 移动实体
    void onEntityMove(Entity* entity, float newX, float newY) {
        auto [oldGx, oldGy] = getGridPos(entity->x, entity->y);
        auto [newGx, newGy] = getGridPos(newX, newY);

        if (oldGx != newGx || oldGy != newGy) {
            // 跨格子移动
            removeFromGrid(entity, oldGx, oldGy);
            addToGrid(entity, newGx, newGy);

            // 检查九宫格变化，触发进入/离开事件
            checkAOIChange(entity, oldGx, oldGy, newGx, newGy);
        }
    }
};

class CrossListAOI {
    struct Node {
        Entity* entity;
        Node* xPrev = nullptr;
        Node* xNext = nullptr;
        Node* yPrev = nullptr;
        Node* yNext = nullptr;
    };

    std::unordered_map<EntityID, Node*> nodes;

    // 获取 X 轴方向的可见实体
    std::vector<Entity*> getXAxisVisible(Entity* entity, float range) {
        std::vector<Entity*> result;
        Node* node = nodes[entity->id];

        // 向 X 正方向查找
        Node* p = node->xNext;
        while (p && p->entity->x - entity->x <= range) {
            if (abs(p->entity->y - entity->y) <= range) {
                result.push_back(p->entity);
            }
            p = p->xNext;
        }

        // 向 X 负方向查找
        p = node->xPrev;
        while (p && entity->x - p->entity->x <= range) {
            if (abs(p->entity->y - entity->y) <= range) {
                result.push_back(p->entity);
            }
            p = p->xPrev;
        }

        return result;
    }
};

class SpatialHashAOI {
    // 使用哈希表而非二维数组
    struct SpatialHash {
        std::unordered_map<uint64_t, std::unordered_set<Entity*>> buckets;

        // 空间坐标转哈希键
        uint64_t hash(int gx, int gy) {
            return (uint64_t)gx << 32 | (uint32_t)gy;
        }
    };
};

class QuadTreeAOI {
    struct Rect {
        float minX, minY, maxX, maxY;

        bool intersectsCircle(float x, float y, float radius) const;
        bool contains(float x, float y) const;
    };

    struct Node {
        Rect bounds;
        std::vector<Entity*> entities;
        std::unique_ptr<Node> nw;
        std::unique_ptr<Node> ne;
        std::unique_ptr<Node> sw;
        std::unique_ptr<Node> se;
        bool divided = false;
    };

public:
    std::vector<Entity*> queryCircle(float x, float y, float radius) {
        std::vector<Entity*> result;
        queryCircle(root_.get(), x, y, radius, result);
        return result;
    }

private:
    void queryCircle(Node* node, float x, float y, float radius,
                     std::vector<Entity*>& out) {
        if (node == nullptr || !node->bounds.intersectsCircle(x, y, radius)) {
            return;
        }

        for (auto* entity : node->entities) {
            if (distance(entity->x, entity->y, x, y) <= radius) {
                out.push_back(entity);
            }
        }

        if (!node->divided) {
            return;
        }

        queryCircle(node->nw.get(), x, y, radius, out);
        queryCircle(node->ne.get(), x, y, radius, out);
        queryCircle(node->sw.get(), x, y, radius, out);
        queryCircle(node->se.get(), x, y, radius, out);
    }

    std::unique_ptr<Node> root_;
};

class RTreeAOI {
    struct AABB {
        float minX, minY, maxX, maxY;
    };

    struct Entry {
        AABB box;
        Entity* entity;
    };

public:
    void insert(Entity* entity, const AABB& box) {
        // 插入到最合适的叶子，必要时分裂节点
    }

    std::vector<Entity*> queryRange(const AABB& range) {
        std::vector<Entity*> result;
        // 遍历与 range 相交的节点
        return result;
    }
};

class CellAppAOI {
    // 本 Cell 的 AOI 管理
    GridAOI localAOI;

    // Ghost 管理：跨边界的 Entity
    struct GhostEntity {
        Entity* original;       // 原始 Entity（在其他 Cell）
        Entity* ghost;          // 本 Cell 的只读拷贝
        CellApp* owner;         // 所属 CellApp
    };
    std::unordered_map<EntityID, GhostEntity> ghosts;

    // 获取玩家可见的所有 Entity
    std::vector<Entity*> getVisibleEntities(Player* player) {
        std::vector<Entity*> result;

        // 1. 本 Cell 内的可见 Entity
        auto local = localAOI.getVisibleEntities(player);
        result.insert(result.end(), local.begin(), local.end());

        // 2. 来自相邻 Cell 的 Ghost Entity
        for (auto& [id, ghost] : ghosts) {
            if (isInAOI(player, ghost.ghost)) {
                result.push_back(ghost.ghost);
            }
        }

        return result;
    }

    // 当玩家移动时
    void onPlayerMove(Player* player, float newX, float newY) {
        // 1. 更新本 Cell AOI
        auto oldVisible = localAOI.getVisibleEntities(player);
        localAOI.updatePosition(player, newX, newY);
        auto newVisible = localAOI.getVisibleEntities(player);

        // 2. 计算差异
        auto entered = difference(newVisible, oldVisible);
        auto left = difference(oldVisible, newVisible);

        // 3. 触发事件
        for (auto* e : entered) {
            player->onEnterAOI(e);
            e->onEnterAOI(player);
        }
        for (auto* e : left) {
            player->onLeaveAOI(e);
            e->onLeaveAOI(player);
        }

        // 4. 检查是否跨 CellApp 边界
        if (isCrossCellAppBoundary(newX, newY)) {
            handleCrossCellApp(player);
        }
    }
};

class GhostManager {
    // Ghost 管理
    struct GhostData {
        EntityID originalId;       // 原始 Entity ID
        Entity* ghost;             // 本 Cell 的只读拷贝
        CellApp* sourceCellApp;    // 来源 CellApp
        Vector3 lastPosition;      // 最后同步的位置
        uint64_t lastSyncTime;     // 最后同步时间
    };

    std::unordered_map<EntityID, GhostData> ghosts;

    // 创建 Ghost
    void createGhost(Entity* original, CellApp* targetCellApp) {
        GhostData ghost;
        ghost.originalId = original->id;
        ghost.sourceCellApp = original->ownerCellApp;
        ghost.lastPosition = original->position;
        ghost.lastSyncTime = now();

        // 创建只读拷贝
        ghost.ghost = new Entity();
        ghost.ghost->id = original->id;
        ghost.ghost->position = original->position;
        ghost.ghost->isGhost = true;
        ghost.ghost->readonly = true;

        ghosts[original->id] = ghost;

        // 通知目标 CellApp 创建 Ghost
        targetCellApp->addGhost(ghost.ghost);
    }

    // 同步 Ghost 数据
    void syncGhost(Entity* original) {
        auto it = ghosts.find(original->id);
        if (it == ghosts.end()) return;

        auto& ghost = it->second;

        // 同步关键数据
        ghost.ghost->position = original->position;
        ghost.ghost->rotation = original->rotation;
        ghost.ghost->health = original->health;
        ghost.ghost->mana = original->mana;

        // ... 其他需要同步的数据

        ghost.lastSyncTime = now();
    }

    // 检测边界并创建 Ghost
    void checkBoundaryAndCreateGhost(Entity* entity) {
        float boundaryMargin = entity->aoiRadius;

        // 检查是否接近边界
        if (isNearBoundary(entity, boundaryMargin)) {
            // 获取相邻的 CellApp
            auto neighbors = getNeighborCellApps(entity->position);

            for (auto* neighbor : neighbors) {
                EntityID id = entity->id;
                // 如果该 CellApp 没有这个 Entity 的 Ghost
                if (!neighbor->hasGhost(id)) {
                    createGhost(entity, neighbor);
                }
            }
        }
    }
};

class BoundaryManager {
    struct CellBoundary {
        float minX, maxX;
        float minY, maxY;
        CellApp* owner;
        CellApp* neighbor;  // 相邻的 CellApp（如果有）
    };

    std::vector<CellBoundary> boundaries;

    // 判断是否接近边界
    bool isNearBoundary(Entity* entity, float margin) {
        auto* cell = entity->ownerCell;
        auto bounds = getCellBounds(cell);

        return (entity->x - bounds.minX < margin ||
                bounds.maxX - entity->x < margin ||
                entity->y - bounds.minY < margin ||
                bounds.maxY - entity->y < margin);
    }

    // 判断是否跨过边界
    bool isCrossBoundary(Entity* entity, float newX, float newY) {
        auto* cell = entity->ownerCell;
        auto bounds = getCellBounds(cell);

        // 超出当前 Cell 的边界
        return (newX < bounds.minX || newX > bounds.maxX ||
                newY < bounds.minY || newY > bounds.maxY);
    }

    // 获取目标 CellApp
    CellApp* getTargetCellApp(float x, float y) {
        for (auto& boundary : boundaries) {
            if (x >= boundary.minX && x <= boundary.maxX &&
                y >= boundary.minY && y <= boundary.maxY) {
                return boundary.owner;
            }
        }
        return nullptr;
    }
};

class AOIOptimizer {
    // 不要每帧都检测所有 Entity
    void update() {
        // 分帧处理 Entity 移动
        int batchSize = entities.size() / 10;
        int start = (frameCount % 10) * batchSize;

        for (int i = start; i < start + batchSize && i < entities.size(); ++i) {
            checkAndUpdateAOI(entities[i]);
        }

        frameCount++;
    }
};

// 使用 R-Tree 或四叉树加速空间查询
class IndexedAOI {
    RTree rtree;

    std::vector<Entity*> query(float x, float y, float radius) {
        return rtree.queryCircle(x, y, radius);
    }
};

// 不要每个移动都发送事件，批量处理
class EventBatcher {
    struct PendingEvent {
        Entity* entity;
        EntityType type;
        std::vector<Entity*> entered;
        std::vector<Entity*> left;
    };

    std::vector<PendingEvent> pendingEvents;

    void flush() {
        for (auto& event : pendingEvents) {
            sendAOIChangeEvent(event);
        }
        pendingEvents.clear();
    }
};