服务端-9宫格场景

前言

场景同步在游戏里已经有很成熟的处理方式，9宫格、十字链、灯塔、4叉树、8叉树….
一般分为这些方面：
- 地图制作
- 区域划分
- 地图管理
- 对象管理
- 视野同步
- 碰撞检测
对于服务端来说压力主要在视野同步、碰撞检测，一个涉及数据广播，一个涉及数据检查
前段时间重构了一个2DMMO游戏的场景相关内容，使用的9宫格方式做视野管理，只是2D碰撞检测就只使用了bits标记方式，没有引入4叉树、8叉树这种
记录一下备忘

名词

cell 可站立的最小单位，一般也是场景对象的(x, y)坐标：下图涂黄、绿的小格子
area 9宫格的一个单位，x, y 标记表示横纵各占用多少个 cell：下图黄、绿标记的块
eyesight 视野区域半径(3*3的9宫格，这里就是 1, 1)：下图蓝色、红色框示意的块，其中蓝色是客户端屏幕视野，红色是服务端管理视野，一般服务端是比客户端大的，也就是服务端先于客户端将数据同步到客户端，这样在玩家视野切换的时候表现更流畅
flag 配置来的静态属性(阻挡点、安全区、自由攻击….)、运行中的动态属性(栅栏、场景事件….)
worldpoint 一些大世界游戏会用到的概念，更小粒度的坐标点，比如4个worldpoint组成一个cell，也可以直接把这个概念简化为 cell，配合 4叉树处理碰撞问题

对象、格子管理

场景维护所在场景的对象（场景对象）
场景对象持有所在地图 uuid，cell 信息

视野同步是以 area 为单位的，碰撞检测以 cell 为单位，那么对象挂在 cell、area 哪里更合适呢？

两者发生的频率上视野同步更高：例如场景对象每次有动作(移动、坐下)都需要做视野同步，但是坐下这个动作不需要做碰撞检测
假设对象挂在 area 上，视野同步只需要遍历9个 area 就好
碰撞检测只是对单个格子占用信息的检查，需要的数据只是格子的占用标记 flag
结论：场景对象挂在 area 结构上，cell 对象生增加 flag 标记就好

1 2	using entity_handles = std::unordered_set<entity_handle>; std::vector<entity_handles> _area_entitys; // 视野格子对象列表


// 格子标记，做细节一点，但是匿名联合体、结构体都不是个好的习惯
struct cell_flag {
    union {
        int _flag = 0;
        struct {
            bool _barrier : 1;         // 占用阻挡（如果非下面的特有占用，标记这个通用值）
            bool _player_barrier : 1;  // 特有：玩家占用（如果占用的是玩家，标记这个值）
            bool _monster_barrier : 1; // 特有：怪物占用（如果占用的是怪物，标记这个值）
            bool _item_barrier : 1;    // 特有：道具占用（如果占用的是道具，标记这个值）

            bool _block : 1;           // 物理阻挡
        };
    };

    cell_flag() = default;

    bool is_block() const {
        return _block;
    }
};

struct barrier_mark {
    const bool is_mark = false;  // 标记判断是否占用格子

    // test 值和 cell_flag 一一对应
    union {
        int flag = 0;
        struct {
            bool test_barrier : 1;    // 是否检查其他占用
            bool test_player : 1;     // 是否检查玩家类型的占用
            bool test_monster : 1;    // 是否检查怪物类型的占用
            bool test_item : 1;       // 是否检查道具类型的占用

            bool test_block : 1;      // 是否检查物理阻挡
        };
    };

    barrier_mark() = default;
    barrier_mark(bool _0, bool _1, bool _2, bool _3, bool _4, bool _5)
        : is_mark(_0)
        , test_barrier(_1)
        , test_player(_2)
        , test_monster(_3)
        , test_item(_4)
        , test_block(_5) {
    }
};

static const barrier_mark barrier_mark_none(false, false, false, false, false, true);  // 不占格子，检查物理阻挡（比如用于透明场景对象）
static const barrier_mark barrier_mark_slack(true, true, false, false, false, true);   // 占格子，松弛的，穿人、穿怪、穿道具
static const barrier_mark barrier_mark_default(true, true, true, true, false, true);   // 占格子，默认的，不穿人、不穿怪、穿道具
static const barrier_mark barrier_mark_item(true, true, false, false, true, true);     // 占格子，场景道具的，穿人、穿怪、不穿道具

point 都是2维级别，为了简化转换成1维

1	std::vector<cell_flag> _cells; // 格子

cell, area 坐标系单位不一样，虽然都是 (x, y)，为了干净需要一个 cell_point, area_point

/**
    * \brief 横纵
    */
struct point {
    uint32_t x = 0;
    uint32_t y = 0;
};

/**
    * \brief struct cell point (world point)
    */
struct cell_point {
    uint32_t cx = 0;
    uint32_t cy = 0;

    bool operator == (const cell_point& right) const {
        return this->cx == right.cx
            && this->cy == right.cy;
    }
};
/**
    * \brief invalid cell point
    */
static const cell_point invalid_cell = cell_point{ 0x7FFFFFFF, 0x7FFFFFFF };

/**
    * \brief struct area point
    */
struct area_point {
    uint32_t ax = 0;
    uint32_t ay = 0;

    bool operator == (const area_point& right) const {
        return this->ax == right.ax
            && this->ay == right.ay;
    }
};
/**
    * \brief invalid area point
    */
static const area_point invalid_area = area_point{ 0x7FFFFFFF, 0x7FFFFFFF };

/**
    * \brief rect_point
    */
struct rect_point {
    uint32_t lx = 0;
    uint32_t ly = 0;
    uint32_t rx = 0;
    uint32_t ry = 0;
};

地图基础数据

/**
    * \brief base config
    */
struct base_config {
    cell_point cell;    // 地图格子数量
    area_point area;    // 视野块占格子数量
    point eyesight;     // 视野区域半径（3*3视野的话这里是 1, 1）
    point area_size;    // 整张地图多少个area（加载地图后计算得到）
};

视野

还是这个图，在服务端看，场景满载的同步量是: 12 * 8 * 9 = 864 (假设一个cell只有一个对象)

进出视野：假设一个对象从红色点移动到蓝色点，他的视野范围也就从左上角的 9 * area 变成了右下角的 9 * area

如图红色标记了相互离开的格子，蓝色标记了相互进入的格子，换到 area 就分别是 5 * area

视野列表，想要得到视野列表就需要先获得红蓝 area，简化图，看进出视野的相对关系

视图认为对象从 (0, 0) 移动到 (2, 2) 坐标点

上图已经用颜色标记了点和点相对的关系：

(-1, -1) <-> (3, 3) = (0, 0) - ( 1,  1) <-> (2, 2) + ( 1,  1)
(-1,  0) <-> (3, 2) = (0, 0) - ( 1,  0) <-> (2, 2) + ( 1,  0)
(-1,  1) <-> (3, 1) = (0, 0) - ( 1, -1) <-> (2, 2) + ( 1, -1)
( 0, -1) <-> (2, 3) = (0, 0) - ( 0,  1) <-> (2, 2) + ( 0,  1)
( 0,  0) <-> (2, 2) = (0, 0) - ( 0,  0) <-> (2, 2) + ( 0,  0)
( 0,  1) <-> (2, 1) = (0, 0) - ( 0, -1) <-> (2, 2) + ( 0, -1)
( 1, -1) <-> (1, 3) = (0, 0) - (-1,  1) <-> (2, 2) + (-1,  1)
( 1,  0) <-> (1, 2) = (0, 0) - (-1,  0) <-> (2, 2) + (-1,  0)
( 1,  1) <-> (1, 1) = (0, 0) - (-1, -1) <-> (2, 2) + (-1, -1)

from_point - (x, y) = to_point + (x, y)

这可能是全文最有价值的一段代码：（注意下面的拷贝是必要的，如果是list可以换成splice；因为会有原（临近）坐标force传送的情况，比如原地复活；如果客户端支持，可以标记force为false，否则会因为使用对称方式导致（视野内）对象先进入视野后离开视野的情况；根据需要选择合适的方式修改这种情况）

// 镜像关系
for (int32_t y = -_config.eyesight.y; y <= _config.eyesight.y; ++y) {
    for (int32_t x = -_config.eyesight.x; x <= _config.eyesight.x; ++x) {

        // 两个方向偏移后新点和目标点距离小于半径，用两圆相交的方式看待
        if (!force
            && std::abs(static_cast<int32_t>(from.ax) + x - static_cast<int32_t>(to.ax)) <= _config.eyesight.x
            && std::abs(static_cast<int32_t>(from.ay) + y - static_cast<int32_t>(to.ay)) <= _config.eyesight.y) {
            continue;
        }
        if (ok_from) {
            auto leas = entitys(area_point{ from.ax + x, from.ay + y }, nullptr);
            std::copy(leas.begin(), leas.end(), std::back_inserter(leaves));
        }
        if (ok_to) {
            auto ents = entitys(area_point{ to.ax - x, to.ay + y }, nullptr);
            std::copy(ents.begin(), ents.end(), std::back_inserter(enters));
        }
    }
}

25宫格

考虑这个问题是因为9宫格的范围毕竟太大了，想减少遍历的消耗
也想找到一种方式可以在对象多的场景优化一些性能
而且在服务端视野比客户端大的前提下，服务端其实是有优化空间的
如上格子满载的情况下，9格视野最多需要处理 12 * 8 * 5 (exit) + 12 * 8 * 5 (enter) = 960
5 * 5 宫格 area:(7, 5), 满载同步量: 7 * 5 * 25 = 875，格子范围并不影响客户端同步效果

从红格子跳到另一个红格子：满载需要处理的同步量: 7 * 5 * 9 (exit) + 7 * 5 * 9 (enter) = 630，相比960的数据量，少了1/3

简单压测的结果

思考

缩小 area 尺寸带来的问题:
- 最关键是同步变得频繁了；沿X轴单方向走，9宫格走12cell离开area，25宫格走7cell
为什么还考虑用这个方案：
- 同步频率提高了 40%，同步量减少了 30%，并且同步量是在非满载的情况下，收益是更差的，但是如果技能的命中范围是在 7 * 5 内的，对战斗目标的筛选是提高了很多的
- 进出视野会引发事件，单线程模型下，更少的进出视野可以减少1个逻辑周期程序的处理量
- 当前地图场景的设计，视野单位占格子数量和视野区域半径两个数值是配置项，可以每张地图都不同

样例代码

https://github.com/kinly/anything/blob/main/game_map.h