我让 DeepSeek 实现的 C++ aoi 算法库.

README.md

ccaoi — C++ AOI (Area of Interest) 模块

概述

二维地图实体视野管理，C++11 单头文件，零依赖（仅 STL）。提供两种实现：

实现	算法	适用场景
ccaoi_normal	全表扫描 O(N)	N < 300, 简单场景
ccaoi_grid	九宫格 O(1)	N ≥ 300, 生产环境

快速开始

#include "ccaoi.h"

// 1000×1000 地图, 视野半径 50, 实体 ID 用 std::string
ccaoi_range_t<double> r{0, 1000, 0, 1000};
ccaoi_grid<> aoi(r, 50);

// 进入
aoi.enter("player_1", 100, 200);

// 移动 + 视野通知
void on_see(const ccaoi_entity_t<double,std::string> &e, void *ud) {
    auto *sess = static_cast<Session*>(ud);
    sess->send(e.eid, e.x, e.y);
}
aoi.move("player_1", 105, 205, on_see, &session);

// 查询
if (auto *e = aoi.find("player_1")) {
    printf("pos: %.1f, %.1f\n", e->x, e->y);
}

// 离开
aoi.leave("player_1", on_see, &session);

公共类型

ccaoi_entity_t<POSITION, EID>

字段	类型	说明
x	POSITION	X 坐标
y	POSITION	Y 坐标
eid	EID	实体标识

ccaoi_range_t<POSITION>

字段	类型	说明
min_x, max_x	POSITION	X 轴范围
min_y, max_y	POSITION	Y 轴范围

模板参数默认值

参数	默认值
POSITION	double
EID	std::string

CCAOI_CALLBACK

using CCAOI_CALLBACK = void(*)(const ENTITY& entity, void* userdata);

公共接口

ccaoi_normal 和 ccaoi_grid API 完全一致，可互换。

构造

explicit ccaoi_xxx(RANGE range, POSITION radius);

参数	说明
range	地图有效范围
radius	视野半径（grid 中也是格子边长）

enter — 实体进入

bool enter(const EID &eid, POSITION x, POSITION y,
           CCAOI_CALLBACK cb = nullptr, void *udata = nullptr) noexcept;

• 实体在 (x, y) 进入地图
• 若 cb 非空，通知该实体视野内所有已有实体
• 返回 false：坐标越界或实体已存在

move — 实体移动

bool move(const EID &eid, POSITION x, POSITION y,
          CCAOI_CALLBACK cb = nullptr, void *udata = nullptr) noexcept;

• 实体移动到 (x, y)
• 若 cb 非空，通知该实体其新旧位置并集范围内所有实体
• 返回 false：目标越界或实体不存在

leave — 实体离开

bool leave(const EID &eid,
           CCAOI_CALLBACK cb = nullptr, void *udata = nullptr) noexcept;

• 实体离开地图
• 若 cb 非空，通知该实体离开前视野内所有实体
• 返回 false：实体不存在

find — 实体查询

const ENTITY* find(const EID &eid) const noexcept;

• 返回实体指针，不存在返回 nullptr
• O(1)

复杂度

操作	ccaoi_normal	ccaoi_grid
enter (无 cb)	O(1)	O(1)
enter (有 cb)	O(N)	O(实体密度) ≈ O(1)
move (无 cb)	O(1)	O(log G + 1)
move (有 cb)	O(N)	O(实体密度) ≈ O(1)
leave (无 cb)	O(1)	O(log G + 1)
leave (有 cb)	O(N)	O(实体密度) ≈ O(1)
find	O(1)	O(1)

• N = 实体总数
• G = 非空格子数

grid 退化条件

• 小步移动（位移 ≪ radius）：始终 3×3 格，严格 O(1)
• 传送（位移 ≫ radius）：lower_bound 只访问非空格，最多 O(N)
• 密度 ≈ 1.0（每格恰好 1 实体）：常数因子最大值，但仍 ≤ O(N)

性能测试

g++ -std=c++11 -O2, radius=50, 单位 μs/move.

小步移动（Δ≈5，游戏常态）

W       N     每格实体  normal    grid    grid/normal
------  -----  --------  --------  --------  -----------
  1000   2000       5.0      28.1       6.0      0.2×  ★
  2000   4000       2.5      51.0       3.1      0.1×  ★
  4000   8000       1.2     121.7      11.3      0.1×  ★
  8000  16000       0.6     542.1      20.2      0.0×  ★

• normal 严格 O(N)，grid 近乎平直
• N=16000 时 grid 快 27 倍

传送场景（grid 最坏情况）

W       N     每格实体  normal    grid    grid/normal
------  -----  --------  --------  --------  -----------
  1000   2000       5.0      21.5      20.7      1.0×  ★
  2000   4000       2.5      65.6      39.5      0.6×  ★
  4000   8000       1.2     190.2      56.2      0.3×  ★
  8000  16000       0.6     806.4     246.6      0.3×  ★

• lower_bound 优化使 grid 在传送场景仍不差于 normal
• N≥8000 时 grid 仍快 3.3 倍

float 安全性

• _cell_coord 显式 double 强转后再 floor，消除 int 型 POSITION 的截断问题
• ccaoi_in_range 使用 IEEE 754 标准比较，边界 ±1 ULP 误差与 ccaoi_normal 完全一致
• 已通过 nextafter 边界测试、500×0.1 累积误差测试、负坐标测试

内存安全性

• _map RAII 拥有所有 ENTITY
• _grid 存储 const ENTITY* 非拥有指针
• 析构顺序（_grid 先于 _map）由成员声明顺序保证
• 空 cell 自动清理，无残留

ccaoi.h

#pragma once

#include <cstdint>
#include <cmath>
#include <map>
#include <string>
#include <unordered_set>

#include <algorithm>
#include <unordered_map>

#define CCAOI_POSITION_TEMPLATE   template<typename POSITION = double>
#define CCAOI_ENTITY_TEMPLATE     template<typename POSITION = double, typename EID = std::string>
#define CCAOI_BASIC_TEMPLATE      CCAOI_ENTITY_TEMPLATE

CCAOI_ENTITY_TEMPLATE
struct ccaoi_entity_t {
  POSITION x, y;
  EID eid; // 实体`ID`(玩家/NPC/其他...)
};

CCAOI_POSITION_TEMPLATE
struct ccaoi_range_t { /* 当前二维地图的有效区间 */
  POSITION min_x, max_x;
  POSITION min_y, max_y;
};

/* note: return `true` when x between r.min_x ~ r.max_x, y between r.min_y ~ r.max_y. */
CCAOI_POSITION_TEMPLATE
inline bool ccaoi_in_range(const ccaoi_range_t<POSITION> &r, POSITION x, POSITION y) noexcept
{
  return (r.min_x <= x and r.max_x >= x) and (r.min_y <= y and r.max_y >= y);
}

CCAOI_POSITION_TEMPLATE
inline bool ccaoi_in_around(const ccaoi_range_t<POSITION> &r, POSITION x, POSITION y) noexcept
{
  return ccaoi_in_range(r, x, y);
}

CCAOI_POSITION_TEMPLATE
inline void ccaoi_wrap_around(ccaoi_range_t<POSITION> &r, POSITION x1, POSITION x2, POSITION y1, POSITION y2, POSITION radius) noexcept
{
  r.min_x = std::min(x1, x2) - radius; r.max_x = std::max(x1, x2) + radius;
  r.min_y = std::min(y1, y2) - radius; r.max_y = std::max(y1, y2) + radius;
}

/* ── ccaoi_normal: O(n) 全表扫描实现 ── */
CCAOI_BASIC_TEMPLATE
class ccaoi_normal
{
  using ENTITY = struct ccaoi_entity_t< POSITION, EID >;
  using MAP = std::unordered_map< EID, ENTITY >;
  using RANGE = struct ccaoi_range_t< POSITION >;
  public:
    using CCAOI_CALLBACK = void(*)(const ENTITY&, void*);
  private:
    MAP      _map;    // 实体表
    POSITION _radius; // 半径长度
    RANGE    _r;      // aoi范围
    void _find_around(const ENTITY &self, const RANGE &r, CCAOI_CALLBACK cb, void *udata) noexcept
    {
      for (auto &iter : _map)
      {
        const auto &val = iter.second;
        if (&val == &self) continue;
        if (ccaoi_in_around<POSITION>(r, val.x, val.y))
          cb(val, udata);
      }
    }
  public:
    explicit ccaoi_normal(RANGE r, POSITION radius): _radius(radius), _r(r) {}

    const ENTITY* find(const EID &eid) const noexcept
    {
      auto it = _map.find(eid);
      return it != _map.end() ? &it->second : nullptr;
    }
    /* 进入 */
    bool enter(const EID &eid, POSITION x, POSITION y, CCAOI_CALLBACK cb = nullptr, void *udata = nullptr) noexcept
    {
      if (!ccaoi_in_range(_r, x, y))
        return false;

      auto result = _map.emplace(eid, ENTITY{x, y, eid});
      if (!result.second)
        return false;

      if (cb) {
        RANGE r; ccaoi_wrap_around(r, x, x, y, y, _radius);
        _find_around(result.first->second, r, cb, udata);
      }
      return true;
    }

    /* 移动 */
    bool move(const EID &eid, POSITION x, POSITION y, CCAOI_CALLBACK cb = nullptr, void *udata = nullptr) noexcept
    {
      if (!ccaoi_in_range(_r, x, y))
        return false;

      auto iter = _map.find(eid);
      if (iter == _map.end())
        return false;

      ENTITY &e = iter->second;
      if (cb) {
        RANGE r; ccaoi_wrap_around(r, e.x, x, e.y, y, _radius);
        _find_around(e, r, cb, udata);
      }

      e.x = x; e.y = y;
      return true;
    }

    /* 离开 */
    bool leave(const EID &eid, CCAOI_CALLBACK cb = nullptr, void *udata = nullptr) noexcept
    {
      const auto iter = _map.find(eid);
      if (iter == _map.end())
        return false;

      if (cb) {
        const ENTITY &e = iter->second;
        RANGE r; ccaoi_wrap_around(r, e.x, e.x, e.y, e.y, _radius);
        _find_around(e, r, cb, udata);
      }

      _map.erase(eid);
      return true;
    }
};

/* ── ccaoi_grid: 九宫格 O(1) 空间索引实现 ──
 * 格子内存储 const ENTITY* 而非 EID，消除 _find_around 的二次 hash 查找。
 * enter/move/leave 时只搜索目标实体周围 3×3 格子内的实体，
 * 再通过 ccaoi_in_around 精确过滤，与 ccaoi_normal 语义完全一致。
 */
CCAOI_BASIC_TEMPLATE
class ccaoi_grid
{
  using ENTITY = struct ccaoi_entity_t< POSITION, EID >;
  using MAP = std::unordered_map< EID, ENTITY >;
  using RANGE = struct ccaoi_range_t< POSITION >;
  public:
    using CCAOI_CALLBACK = void(*)(const ENTITY&, void*);
  private:
    using cell_key_t = std::pair<int64_t, int64_t>;
    using cell_set_t = std::unordered_set<const ENTITY*>;
    using grid_t = std::map<cell_key_t, cell_set_t>;

    MAP      _map;
    POSITION _radius;
    RANGE    _r;
    grid_t   _grid;

    int64_t _cell_coord(POSITION v) const noexcept
    {
      return static_cast<int64_t>(std::floor(
        static_cast<double>(v) / static_cast<double>(_radius)));
    }

    cell_key_t _cell_of(POSITION x, POSITION y) const noexcept
    {
      return {_cell_coord(x), _cell_coord(y)};
    }

    void _grid_add(const ENTITY &e) noexcept
    {
      _grid[_cell_of(e.x, e.y)].insert(&e);
    }

    void _grid_remove(const ENTITY &e) noexcept
    {
      auto it = _grid.find(_cell_of(e.x, e.y));
      if (it != _grid.end()) {
        it->second.erase(&e);
        if (it->second.empty())
          _grid.erase(it);
      }
    }

    void _find_around(const EID &eid, const RANGE &r, CCAOI_CALLBACK cb, void *udata) noexcept
    {
      int64_t min_cx = _cell_coord(r.min_x);
      int64_t max_cx = _cell_coord(r.max_x);
      int64_t min_cy = _cell_coord(r.min_y);
      int64_t max_cy = _cell_coord(r.max_y);

      auto lo = _grid.lower_bound({min_cx, min_cy});
      auto hi = _grid.upper_bound({max_cx, max_cy});
      for (auto it = lo; it != hi; ++it) {
          if (it->first.second < min_cy || it->first.second > max_cy) continue;
          for (const auto *val : it->second) {
              if (val->eid == eid) continue;
              if (ccaoi_in_around<POSITION>(r, val->x, val->y))
                cb(*val, udata);
            }
        }
    }

  public:
    explicit ccaoi_grid(RANGE r, POSITION radius): _radius(radius), _r(r) {}

    const ENTITY* find(const EID &eid) const noexcept
    {
      auto it = _map.find(eid);
      return it != _map.end() ? &it->second : nullptr;
    }

    bool enter(const EID &eid, POSITION x, POSITION y, CCAOI_CALLBACK cb = nullptr, void *udata = nullptr) noexcept
    {
      if (!ccaoi_in_range(_r, x, y))
        return false;
      auto result = _map.emplace(eid, ENTITY{x, y, eid});
      if (!result.second)
        return false;
      _grid_add(result.first->second);

      if (cb) {
        RANGE r; ccaoi_wrap_around(r, x, x, y, y, _radius);
        _find_around(eid, r, cb, udata);
      }
      return true;
    }

    bool move(const EID &eid, POSITION x, POSITION y, CCAOI_CALLBACK cb = nullptr, void *udata = nullptr) noexcept
    {
      if (!ccaoi_in_range(_r, x, y))
        return false;
      auto iter = _map.find(eid);
      if (iter == _map.end())
        return false;

      ENTITY &e = iter->second;
      POSITION old_x = e.x, old_y = e.y;

      if (cb) {
        RANGE r; ccaoi_wrap_around(r, old_x, x, old_y, y, _radius);
        _find_around(eid, r, cb, udata);
      }

      _grid_remove(e);
      e.x = x; e.y = y;
      _grid_add(e);
      return true;
    }

    bool leave(const EID &eid, CCAOI_CALLBACK cb = nullptr, void *udata = nullptr) noexcept
    {
      const auto iter = _map.find(eid);
      if (iter == _map.end())
        return false;

      const ENTITY &e = iter->second;
      if (cb) {
        RANGE r; ccaoi_wrap_around(r, e.x, e.x, e.y, e.y, _radius);
        _find_around(eid, r, cb, udata);
      }

      _grid_remove(e);
      _map.erase(eid);
      return true;
    }
};