Skip to content

AOI Broadcast and Message Deduplication ​

The Core Problem ​

When an entity moves, all players in its view must be notified of the entity's state change.

Scenario: a monster moves from point A to point B
      M moves →

Must notify:
- all players in the monster's view: the monster's new position
- also tell the players: which monsters entered/left the view

1. Broadcast Types ​

1. Enter broadcast ​

cpp
// 玩家进入地图时 (when a player enters the map)
onPlayerEnter(Player* player) {
    // 1. 获取玩家视野内的所有实体 (1. get all entities in the player's view)
    auto entities = aoi.getEntitiesInPlayerView(player);

    // 2. 通知玩家:这些实体在你视野内 (2. notify the player: these entities are in your view)
    for (Entity* e : entities) {
        player->send(EntityAppearMsg(e));  // "怪物X出现在(x,y)" ("monster X appears at (x,y)")
    }

    // 3. 通知视野内玩家:有一个新玩家来了 (3. notify players in the view: a new player has arrived)
    for (Entity* e : entities) {
        if (e->isPlayer()) {
            e->send(PlayerEnterMsg(player));
        }
    }
}

2. Leave broadcast ​

cpp
// 玩家离开时 (when a player leaves)
onPlayerLeave(Player* player) {
    auto viewers = aoi.getViewers(player);  // 谁能看到我 (who can see me)

    // 通知所有能看到我的玩家:我离开了 (notify all players who can see me: I'm leaving)
    for (Entity* viewer : viewers) {
        viewer->send(EntityLeaveMsg(player));
    }
}

3. Move broadcast (the most complex) ​

cpp
// 玩家/怪物移动时 (when a player/monster moves)
onEntityMove(Entity* entity, Position oldPos, Position newPos) {
    // 1. 计算旧的视野和新的视野 (1. compute the old view and the new view)
    auto oldViewers = getEntityViewers(oldPos);
    auto newViewers = getEntityViewers(newPos);

    // 2. 找出差异 (2. find the differences)
    auto enterViewers = newViewers - oldViewers;  // 新看到的玩家 (players newly seeing it)
    auto leaveViewers = oldViewers - newViewers;  // 丢失视野的玩家 (players who lost sight of it)
    auto stayViewers   = oldViewers & newViewers;  // 一直看到的玩家 (players seeing it all along)

    // 3. 分发消息 (3. dispatch the messages)
    for (auto viewer : leaveViewers) {
        viewer->send(EntityLeaveMsg(entity));
    }

    for (auto viewer : enterViewers) {
        viewer->send(EntityAppearMsg(entity));
    }

    for (auto viewer : stayViewers) {
        viewer->send(EntityMoveMsg(entity, oldPos, newPos));  // 增量更新 (incremental update)
    }
}

2. Message Deduplication Strategies ​

Problem: message storms ​

100 players moving simultaneously in one grid cell
→ each player notifies 99 other players
→ 100 * 99 = 9900 messages
→ network explosion!

Option 1: Interest List ​

Each entity maintains a list of who is watching me:

cpp
struct Entity {
    std::unordered_set<Entity*> viewers;  // 谁在看我 (who is watching me)
    std::unordered_set<Entity*> watchees; // 我在看谁 (whom I am watching)
};

void updateViewers(Entity* entity) {
    auto newViewers = aoi.getViewers(entity);  // O(9格) (O(9 cells))
    auto oldViewers = entity->viewers;

    // 新增的观察者 (newly added watchers)
    for (auto v : newViewers - oldViewers) {
        entity->viewers.insert(v);
        v->send(EntityAppearMsg(entity));
    }

    // 离开的观察者 (departing watchers)
    for (auto v : oldViewers - newViewers) {
        entity->viewers.erase(v);
        v->send(EntityLeaveMsg(entity));
    }
}

Advantages:

  • computed only when the view changes; incremental updates
  • avoids walking the whole 3×3 grid on every move

Option 2: 3×3 grid cross-deduplication ​

cpp
// 核心思想:每个格子维护自己的广播列表 (core idea: each grid cell maintains its own broadcast list)
class Grid {
    std::vector<Entity*> entities;

    // 本格子的实体需要广播给哪些格子? (which cells do this cell's entities need to be broadcast to?)
    std::unordered_set<Grid*> broadcastTargets;  // 需要通知的格子 (cells to notify)
};

void broadcastMove(Entity* mover, Grid* oldGrid, Grid* newGrid) {
    // 1. 收集需要通知的格子(去重) (1. collect the cells to notify (deduplicated))
    std::unordered_set<Grid*> targetGrids;

    for (auto* grid : oldGrid->broadcastTargets) {
        targetGrids.insert(grid);
    }
    for (auto* grid : newGrid->broadcastTargets) {
        targetGrids.insert(grid);
    }

    // 2. 向每个目标格子广播一次 (2. broadcast once to each target cell)
    for (auto* grid : targetGrids) {
        for (auto* entity : grid->entities) {
            if (entity != mover) {
                entity->send(EntityMoveMsg(mover));
            }
        }
    }
}

Option 3: Message Batching ​

cpp
// 批量发送,减少网络包数量 (send in batches to reduce the network packet count)
class MessageBatcher {
    struct PendingMessage {
        std::vector<EntityMoveData> moves;
        std::vector<EntityAppearData> appears;
        std::vector<EntityLeaveData> leaves;
    };

    std::unordered_map<Player*, PendingMessage> pending;

    void addMove(Player* receiver, Entity* mover, Pos from, Pos to) {
        pending[receiver].moves.push_back({mover->id, from, to});
    }

    void flush(int maxDelayMs) {
        // 定时批量发送 (batch-send on a timer)
        for (auto& [player, msg] : pending) {
            if (!msg.moves.empty()) {
                player->send(BatchMoveMsg(msg.moves));  // 一次包发多个移动 (multiple moves in one packet)
            }
        }
        pending.clear();
    }
};

// 使用:每50ms批量发送一次 (usage: batch-send once every 50ms)
MessageBatcher batcher;
timer.every(50ms, [&]() { batcher.flush(); });

3. Complete Broadcast Implementation ​

cpp
class AOIBroadcaster {
public:
    // 实体移动时的广播 (broadcast when an entity moves)
    void onMove(Entity* entity, Position from, Position to) {
        // 1. 计算视野变化 (1. compute the view change)
        ViewChange change = calculateViewChange(from, to);

        // 2. 处理离开视野的玩家 (2. handle players leaving the view)
        for (auto* leaver : change.leavers) {
            entity->removeWatcher(leaver);
            leaver->send(EntityLeave{entity->id});
        }

        // 3. 处理进入视野的玩家 (3. handle players entering the view)
        for (auto* enterer : change.enterers) {
            entity->addWatcher(enterer);
            enterer->send(EntityAppear{entity->id, to});
        }

        // 4. 处理一直在视野内的玩家(发送移动消息) (4. handle players who have been in view all along (send move messages))
        if (!change.stayers.empty()) {
            // 去重:同一帧内只发送一次 (dedup: send only once within the same frame)
            if (!entity->hasMoveFlagThisFrame()) {
                for (auto* stayer : change.stayers) {
                    stayer->send(EntityMove{entity->id, from, to});
                }
                entity->setMoveFlag();
            }
        }
    }

    // 定时清理标记(每帧清理) (periodically clear the flags (cleared every frame))
    void clearFlags() {
        for (auto* entity : allEntities) {
            entity->clearMoveFlag();
        }
    }

private:
    struct ViewChange {
        std::vector<Entity*> leavers;  // 离开视野的 (those leaving the view)
        std::vector<Entity*> enterers; // 进入视野的 (those entering the view)
        std::vector<Entity*> stayers;  // 一直在的 (those staying in view)
    };

    ViewChange calculateViewChange(Position from, Position to) {
        ViewChange result;

        auto oldViewers = getViewers(from);  // 旧位置能看到谁 (whom the old position can see)
        auto newViewers = getViewers(to);    // 新位置能看到谁 (whom the new position can see)

        // 计算差集(去重关键) (compute the set differences (the key to dedup))
        for (auto* v : oldViewers) {
            if (newViewers.count(v) == 0) {
                result.leavers.push_back(v);
            } else {
                result.stayers.push_back(v);
            }
        }

        for (auto* v : newViewers) {
            if (oldViewers.count(v) == 0) {
                result.enterers.push_back(v);
            }
        }

        return result;
    }
};

4. High-Performance Optimization Techniques ​

1. Object pool to reuse message objects ​

cpp
// 避免频繁分配消息对象 (avoid frequently allocating message objects)
class MessagePool {
    std::vector<EntityMoveMsg*> freeList;

    EntityMoveMsg* acquire() {
        if (freeList.empty()) {
            return new EntityMoveMsg();
        }
        auto* msg = freeList.back();
        freeList.pop_back();
        return msg;
    }

    void release(EntityMoveMsg* msg) {
        msg->reset();
        freeList.push_back(msg);
    }
};

2. Area Broadcast ​

cpp
// 将地图划分为区域,区域内统一广播 (divide the map into areas and broadcast uniformly within an area)
class BroadcastArea {
    std::vector<Entity*> entities;

    void broadcast(const IMessage& msg) {
        for (auto* e : entities) {
            e->send(msg);
        }
    }
};

// 使用:相同区域的消息合并 (usage: merge messages for the same area)
area.broadcast(BatchMoveMsg{allMovesInThisArea});

3. Hierarchical AOI (multi-level 3×3 grids) ​

cpp
// 远距离用大格子,近距离用小格子 (large cells for long range, small cells for short range)
class HierarchicalAOI {
    NineGrid coarseGrid;  // 1000m × 1000m 粗粒度 (coarse granularity)
    NineGrid fineGrid;    // 100m × 100m  细粒度 (fine granularity)

    void broadcastMove(Entity* e, Pos from, Pos to) {
        // 远距离玩家:只通知大格子 (long-range players: notify only the large cells)
        coarseGrid.broadcastMove(e, from, to);

        // 近距离玩家:通知小格子 (nearby players: notify the small cells)
        fineGrid.broadcastMove(e, from, to);
    }
};

5. Message Format Optimization ​

Compressed message structure ​

cpp
// 优化前:每个移动50字节 (before optimization: 50 bytes per move)
struct MoveMsg_v1 {
    uint64_t entityId;   // 8字节 (8 bytes)
    float fromX, fromY;  // 8字节 (8 bytes)
    float toX, toY;      // 8字节 (8 bytes)
    uint32_t timestamp;  // 4字节 (4 bytes)
    // ... 共50字节 (... 50 bytes in total)
};

// 优化后:每个移动15字节(打包发送) (after optimization: 15 bytes per move (sent packed))
struct BatchMoveMsg {
    uint16_t count;      // 数量 (count)
    struct {
        uint32_t entityId : 24;  // 3字节(最多1600万实体) (3 bytes (up to 16 million entities))
        int16_t deltaX : 11;     // 2字节(-1024~1023,相对坐标) (2 bytes (-1024~1023, relative coordinates))
        int16_t deltaY : 11;     // 2字节 (2 bytes)
    } moves[100];  // 一次发送100个移动 (send 100 moves at once)

    // 100个移动 = 2 + 100*7 = 702字节 (100 moves = 2 + 100*7 = 702 bytes)
    // 平均每个 = 7字节 (7 bytes each on average)
};

Summary ​

ProblemSolution
Whom to broadcast tomaintain watcher lists, update incrementally
Message deduplicationbit-flag marking + interest lists
Performance optimizationbatch sending, object pools, message compression
Message stormsarea broadcast + hierarchical AOI

Core idea: notify only of changes, avoid duplication, send in batches

Released under the MIT License