游戏中AOI(Area of Interest)通常用于逻辑事件触发，网络数据同步，优化逻辑计算。如触发NPC攻击进入视野玩家，计算手雷爆炸伤害范围等。常规的实现方式有网格和十字链表，十字链表的方式实现比较复杂，这里不讨论。我的实现是采用根据查询坐标定位数组下标的方式，这种实现方式比较简单，并且比较方便任意区域的查询.

主要接口有

void insert(objectid_t uid, float x, float y);
void update(objectid_t uid, float x, float y);
//width object视野宽度
//height object视野长度
//Handler：void(id). 查询结果回掉
void query(objectid_t uid, float width, float height, const Handler& callback);
void erase(objectid_t uid);

接口的实现非常简单,主要是增删改查。uid 表示一个AOI实体(玩家 NPC)的唯一ID。最核心的接口是query,许多逻辑操作都要通过这个接口完成。

进出视野主要是通过比较两次查询结果的差异来计算的。如 第一次查询得到集合 A,第二次查询得到集合 B, 比较两个集合: 一个对象B包含而A没有包含，就是进视野；一个对象B没有包含而A包含，就是出视野。

struct aoi_object_t
{
    float x;
    float y;
    int32_t handle;
};

using aoi_t = aoi< aoi_object_t>;

struct player
{
    //uid-version, version用于优化差异比较计算，通过2次遍历即可得出进出视野结果
    using entity_view_t = std::unordered_map<int32_t, int32_t>;
    int32_t version = 1;
    float view_w = 20.0f;//视野长宽
    float view_h = 20.0f;
    entity_view_t view;
};

void print_view_event(int32_t uid, const player& p)
{
    for (auto& v : p.view)
    {
        if (v.second == p.version)
        {
            //进入视野
            std::cout << "player " << v.first << " enter " << uid << "view" << std::endl;
        }
        else if (v.second != (p.version - 1))//出视野
        {
            std::cout << "player " << v.first << " leave " << uid << "view" << std::endl;
            //注意这里要从 p.view 删除已经出视野的玩家
        }
    }
}

void example()
{
    float length_of_area = 512.0f;
    aoi_t::rect rc(-length_of_area / 2.f, -length_of_area / 2.f, length_of_area, length_of_area);
    aoi_t aoi_(rc.x,rc.y, length_of_area,8);

    std::unordered_map<int32_t, player> players;

    auto insert = [&](int32_t uid, float x, float y) {
        aoi_.insert(uid, x, y);
        players.try_emplace(uid, player());
    };

    insert(1, 10.0f, 25.0f);
    insert(2, 10.0f, 20.0f);
    insert(3, 10.0f, 200.0f);
    insert(4, 100.0f, 200.0f);

    auto update = [&]()
    {
        for (auto& p : players)
        {
            p.second.version += 2;
            aoi_.query(p.first, p.second.view_w, p.second.view_h, [&p](int32_t id) {
                if (id == p.first)
                {
                    return;
                }
                auto res = p.second.view.try_emplace(id, p.second.version);//新进入玩家
                if (!res.second)//玩家已经在视野内
                {
                    res.first->second = p.second.version - 1;//更新已经在视野内玩家的版本号,比当前版本号小1
                }
            });
            print_view_event(p.first, p.second);//第一次遍历打印结果
        }
    };

    update();// 1 -><- 2;
    aoi_.update(3, 20, 35);
    update();// 1 -><- 3;
    aoi_.update(3, 25, 100);
    update();// 1 <--> 3; //离开
}

上面根据版本号**不相等**判断出视野，可能会造成AOI边缘处的玩家频繁进出视野，可以采用如下办法优化：
根据玩家的速度动态设置一个版本号的差值范围， 根据这个差值判断出视野。

下面是不同参数性能测试：

地图最小分割单元8，每次进行N次update,N次query, N = 实体数量

1.玩家较慢移动（speed = 2）,单次移动大概率不会跨越地图最小分割单元

结果：

2.玩家较快移动（speed = 10）,单次移动大概率会跨越地图最小分割单元

结果：

可见查询的性能主要受实体数量，和AOI视野范围影响；更新的新能主要受实体数量，和是否频繁跨域单元格影响。并且基本上是线性关系。可以多次测试调整地图最小分割单元，来满足自己情况。