浅析游戏编程中的空间分区概念

空间分区的设计广泛应用于游戏引擎的底层以及游戏玩法的实现中，本文仅简单介绍其概念以便形成基本的认识，以引出一些较为成熟的空间分区方案

发表于 2025/05/17 更新于 2025/05/17

作者 WhythZ

23 分钟阅读

浅析游戏编程中的空间分区概念

参考文章：http://gameprogrammingpatterns.com/spatial-partition.html

一、空间分区的设计动机

1.1 敌人搜索

我们常常需在游戏世界的空间里从某类的全部对象中找到一些特殊的目标对象，对他们执行某些操作或拿取某种信息，例如一个防御塔要执行攻击，那么最粗暴的方式就是遍历场上的所有敌人找到最合适的目标进行攻击，实现大致如下

  
Enemy* Tower::FindTargetEnemy()
{
    Enemy* _target = nullptr;
    EnemyPool _enemyPool = EnemyManager::Instance()->GetEnemyPool();

    //在攻击范围内的敌人中，应当优先攻击最靠近家门口的那个
    double _maxProcess = -1;
    for (Enemy* _enemy : _enemyPool)
    {
        //确保敌人在攻击半径范围内
        if ((_enemy->GetPosition() - this->position).Length() <= fireRadius)
        {
            //不断遍历更新最大完成度，最终得到路径完成度最大的怪物，其距离家门口最近
            double _newProcess = _enemy->GetRouteProcess();
            if (_newProcess > _maxProcess)
            {
                _target = _enemy;
                _maxProcess = _newProcess;
            }
        }
    }

    //返回目标敌人指针
    return _target;
}

void Tower::OnUpdate(double _delta)
{
    fireTimer.OnUpdate(_delta);
    animCurrent->OnUpdate(_delta);

    //如果处于可开火的状态，则准备更新相关数据并开火
    if (canFire)
    {
        //更新子弹的属性数据，需在FindTargetEnemy()前更新，因该函数内使用了索敌半径数据
        static TowerManager* _tm = TowerManager::Instance();
        fireCooldown = _tm->GetFireCooldownOf(type);
        fireRadius = _tm->GetFireRadiusOf(type);
        bulletDamage = _tm->GetBulletDamageOf(type);
        //std::cout << "FireRadius=" << fireRadius << "\n";

        //如果暂时未找到可攻击目标，则无需进行后续更新浪费资源
        Enemy* _target = FindTargetEnemy();
        if (_target == nullptr)
            return;

        //向目标敌人开火
        OnFireBullet(_target);

        //重置可开火状态，然后重置计时器，经冷却后canFire被回调函数重新赋值为true
        canFire = false;
        fireTimer.SetWaitTime(fireCooldown);
        fireTimer.Restart();
    }
}

void TowerManager::OnUpdate(double _delta)
{
    for (Tower* _tower : towerList)
        _tower->OnUpdate(_delta);
}

上述实现的每轮循环，都需遍历所有防御塔与所有敌人（双重循环），耗费指数级别的$O(mn)$时间复杂度，而我们实际上只需遍历每个防御塔四周一定范围内的敌人即可，这就需要对游戏世界的空间进行分区，需用额外的空间来记录分区信息、维护分区内对象的更新
- 先考虑一维空间
  - 将所有对象按照其位置排序在一条轴线上
  - 可以用二分查找等方法快速按区域查询敌人
- 推广到更高维度，二分查找可对应2D的四叉树、3D的八叉树等
  - 将一组在空间中拥有位置信息的对象按照其位置存储某种空间数据结构中
  - 当对象位置改变时，更新空间数据结构
  - 用户可查询在某块区域内的所有对象

1.2 适用情况

空间分区的思想可用于存储活跃的可移动游戏对象、静态美术、世界地理等，在复杂的游戏中，不同的内容通常有不同的空间分区
对于位置可发生变化的对象，除了空间分区数据结构所需的额外空间复杂度外，我们还需额外花费时间复杂度来根据其移动维护不同分区内的对象，所以只有当世界越大、可移动对象越多的情况下，维护空间分区的收益才会越大，所以在在使用空间分区时，需要考虑以你的游戏规模，使用空间分区是否值得

二、空间分区的实现思路

2.1 固定网格示例

固定网格的空间分区本质上是连续的桶排序

2.1.1 游戏内单位对象

以2D的空间为例，我们将其划分为固定大小的网格区域，通过横纵索引访问每个网格

我们先定义游戏世界内的角色单位（例如小兵等）如下
- 自身同时作为双向链表节点，记录前向和后向节点指针（此处手写链表仅仅是为了方便演示原理，实际应用时直接使用STL等即可）
- 提供构造函数，指定自身所属区块、自身所处坐标位置
- 提供Move方法，通过调用所属区块的Move方法进行移动

  
//模拟游戏对象实例（例如敌人单位）
class Unit
{
    //给网格提供权限
    friend class Chunk;

private:
    Chunk* owner;      //指向所属网格
    double x, y;       //记录自身位置

    Unit* prev;        //双向链表中的前方对象节点
    Unit* next;        //双向链表中的后方对象节点

public:
    Unit(Chunk*, double, double);

    void Move(double, double);
};

Unit::Unit(Chunk* _chunk, double _x, double _y)
    :owner(_chunk), x(_x), y(_y), prev(nullptr), next(nullptr)
{
    owner->Add(this);
}

void Unit::Move(double _x, double _y)
{
    owner->Move(this, _x, _y);
}

2.1.2 区块与晶胞网格

然后定义游戏世界的区块，区块内包含小的晶胞网格单位
- 提供添加新Unit*对象指针到区块内的Add方法
- 提供Move函数以移动区块内所属对象

  
//一个区块，内部依据尺寸划分出小网格（Cell），每个网格以链表存储一批游戏对象
class Chunk
{
public:
    static const int cellNum = 10;     //共享的静态变量，表示网格数量
    static const int cellSize = 20;    //共享的静态变量，表示网格尺寸

private:
    Unit* cells[cellNum][cellNum];     //以双向链表，挂载各网格内的游戏对象单位

public:
    Chunk();

private:
    void Add(Unit*);                   //往网格内添加新的游戏对象
    void Move(Unit*, double, double);  //移动网格内的游戏对象
};

Chunk::Chunk()
{
    //清空网格上挂载的Unit对象
    for (int x = 0; x < cellNum; x++)
    {
        for (int y = 0; y < cellNum; y++)
            cells[x][y] = nullptr;
    }
}

void Chunk::Add(Unit* _unit)
{
    //根据对象坐标，检测它应当在哪个网格中
    int _cellX = (int)(_unit->x / cellSize);
    int _cellY = (int)(_unit->y / cellSize);

    //加到网格的游戏对象链表前端
    _unit->prev = NULL;
    _unit->next = cells[_cellX][_cellY];
    cells[_cellX][_cellY] = _unit;

    if (_unit->next != NULL)
        _unit->next->prev = _unit;
}

void Chunk::Move(Unit* _unit, double _x, double _y)
{
    //看看它现在在哪个网格中
    int _oldCellX = (int)(_unit->x / cellSize);
    int _oldCellY = (int)(_unit->y / cellSize);

    //根据传入的目标地点，判断目标地点属于哪个网格
    int _cellX = (int)(_x / cellSize);
    int _cellY = (int)(_y / cellSize);

    //更新单位位置
    _unit->x = _x;
    _unit->y = _y;

    //若未跑出原网格，则无需执行后续更改
    if (_oldCellX == _cellX && _oldCellY == _cellY) return;

    //否则进入新的网格，将它从老网格的链表中移除
    if (_unit->prev != nullptr)
        _unit->prev->next = _unit->next;
    if (_unit->next != nullptr)
        _unit->next->prev = _unit->prev;
    //如果它是链表的头，将他从cells数组中更新掉
    if (cells[_oldCellX][_oldCellY] == _unit)
       cells[_oldCellX][_oldCellY] = _unit->next;

    //加到新网格的对象链表末尾，Add函数内会自动判断所属网格
    Add(_unit);
}

2.1.3 单位对象间交互

在上述基础上，我们为Unit增加交互功能（离散的坐标值的确可能重合，但浮点数坐标用==判断完全重合是几乎不可能的，所以下面使用了范围半径来判断交互）
我们发现，此处的交互代码实现在最外层是一层遍历所有网格的循环，内部则是交互双方的各一层循环，总共三层循环，而不使用空间分区优化直接遍历全局对象只需内部两层循环，所以若我们的世界规模较小，则过度的分区可能会导致操作的时间复杂度不降反增

  
class Chunk
{
public:
    static const int cellNum = 10;
    static const int cellSize = 20;

private:
    Unit* cells[cellNum][cellNum];

public:
    Chunk();

    void UpdateCells();                //更新所有网格

private:
    void UpdateCellUnits(Unit*);       //更新网格内的游戏单位对象间的交互

    void Add(Unit*);
    void Move(Unit*, double, double);
    void Interact(Unit*, Unit*);       //交互函数
    
    double Distance(Unit*, Unit*);     //计算两点间距
};

void Chunk::UpdateCells()
{
    for (int _x = 0; _x < cellNum; _x++)
    {
        for (int y = 0; y < cellNum; y++)
            UpdateCellUnits(cells[x][y]);
    }
}

void Chunk::UpdateCellUnits(Unit* _unit)
{
    while (_unit != nullptr)
    {
        //与其在链表中的后方所有节点对象进行交互
        Unit* _other = _unit->next;
        while (_other != nullptr)
        {
            //如果相互间在交互范围内，则进行交互
            if (Distance(_unit, _other) < interactDitance)
                Interact(_unit, _other);
            _other = _other->next;
        }
        _unit = _unit->next;
    }
}

void Interact(Unit* _unit1, Unit* _unit2)
{
    std::cout << "(" << _unit1->x << "," << _unit1->y <<
        ") Interacts With (" << _unit2->x << "," << _unit2->y << ")\n";
}

double Distance(Unit* _unit1, Unit* _unit2)
{
    return sqrt((_unit1->x - _unit2->x) * (_unit1->x - _unit2->x)
        + (_unit1->y - _unit2->y) * (_unit1->y - _unit2->y));
}

2.1.4 跨网格交互半径

上述交互实现存在问题，UpdateCellUnits仅会处理单个网格内的游戏对象（链表节点）
- 这就会导致对于中心点位于不同网格内、但间距小于interactDitance的对象，其二者之间理应发生交互但却不会发生
- 为了解决这点，我们不仅需检测同一网格的游戏对象，还需比较邻近网格中的游戏对象

先前的UpdateCellUnits仅遍历自身对象，所有网格的该函数在UpdateCells中被统一调用，现在为了满足跨网格检测的需求，可将UpdateCellUnits删除，然后如下
- 新增UpdateUnits函数作为工具辅助
  - 传入的第一个指针在函数体内固定不变，而第二个指针则会不断向后取->next不断与第一个指针代表的对象进行交互检测，故该函数不仅可满足单个网格内的检测
    - 单个：传入网格对象链表头节点及其下一位UpdateUnits(head, head->next)
    - 多个：传入两个网格对象链表头节点UpdateUnits(head1, head2)
- 统一在UpdateCells函数综合管理网格内与网格间的对象交互检测
  - 如下代码中仅检测了周围一圈内的网格，这建立在最大攻击距离小于一个格子的基础上，若交互距离大于网格边长，会导致需要扫描几格开外的的邻格
  - 此处仅检测左上半的相邻网格，是为了防止对象间重复检测，若检查全部八个格子会导致以下情况
    - 检测对象A，在它右侧找到了B，进行一次A和B间的交互（第一次，正常）
    - 检测对象B，在它右侧找到了A，进行一次B和A间的交互（第二次，多余）

  
class Chunk
{
public:
    static const int cellNum = 10;
    static const int cellSize = 20;

    double interactDitance = 2;

private:
    Unit* cells[cellNum][cellNum];

public:
    Chunk();

    void UpdateCells(int, int);        //更新特定网格内游戏对象间的交互

private:
    void UpdateUnits(Unit*, Unit*);    //更新第一参数与第二参数节点及其后对象间的检测

    void Add(Unit*);
    void Move(Unit*, double, double);
    void Interact(Unit*, Unit*);

    double Distance(Unit*, Unit*);
};

void Chunk::UpdateCells(int _xIdx, int _yIdx)
{
    //获取与传入索引对应的网格的游戏对象链表
    Unit* _head = cells[_xIdx][_yIdx];
    while (_head != nullptr)
    {
        //从_head开始，依次将其与后方所有节点对比检测交互
        UpdateUnits(_head, _head->next);

        //检测临近网格，只检测一半（此处是左上半），防止重复检测造成重复交互
        //将本网格对象（_head）与相邻网格对象（cells[_xIdx - 1][_yIdx - 1]）作比较检测
        if (_yIdx > 0)
            UpdateUnits(_head, cells[_xIdx][_yIdx - 1]);     //正上方相邻网格
        if (_xIdx > 0 && _yIdx > 0)
            UpdateUnits(_head, cells[_xIdx - 1][_yIdx - 1]); //左上方相邻网格
        if (_xIdx > 0)
            UpdateUnits(_head, cells[_xIdx - 1][_yIdx]);     //正左方相邻网格
        if (_xIdx > 0 && _yIdx < cellNum - 1)
            UpdateUnits(_head, cells[_xIdx - 1][_yIdx + 1]); //左下方相邻网格

        _head = _head->next;
    }
}

void Chunk::UpdateUnits(Unit* _unit1, Unit* _unit2)
{
    while (_unit2 !_ nullptr)
    {
        if (Distance(_unit1, _unit2) < interactDitance)
            Interact(_unit1, _unit2);
        //指向下一个
        _unit2 = _unit2->next;
    }
}

以上的所有代码仅作为设计思路示意，并未真正调试过功能，特此说明

2.2 其它设计考量

2.2.1 全局遍历

我们时常会有需要遍历全局所有对象的需求，如果所有对象只存储在分区内的话，那么我们若想遍历全部对象就需要先遍历所有分区，再遍历分区内的对象，这需要两层循环（且对于某些无对象的空分区，也需要对其进行遍历浪费时间）
如果我们多维护一个存储所有对象指针的大集合结构，那么就可直接通过该集合进行全局对象的遍历了（仅一层循环），代价是需要在新增和删除对象的时候对该集合进行额外的维护

2.2.2 层次划分

静态的固定空间划分（Flat Partition）：将整个世界空间划分为固定数量的网格
- 用于分区的内存大小固定、易于实现：添加新对象时不需要重新划分世界分区
- 更新对象所属分区更快、无需重新划分网格：若使用层次空间分区，则若对象移动到了新的区域内，若新空间为空则会导致此处需自上而下划分出新的层次分区结构，若原本空间少了它就变空了则原空间需要降级为更粗的层次分区（类比红黑树AVL树等，节点的变更会导致整个树需要自旋调整，这样会导致时间复杂度更高且更难维护）
动态的层次空间划分（Hierarchical Partition）：先将空间划分为几个大区域，递归地划分还包含较多对象的区域（其余区域无需继续拆分），直到每个子区域中的对象数量小于要求的上限数量
- 能更有效率地处理空区域：若固定划分网格，则如果世界空间的一半都是空的（不包含或包含较少的游戏对象），那么我们还需要为这些空区域划分空白格子，不仅浪费内存空间，在更新世界的时候还要浪费时间去遍历它们
- 能更有效率地处理密集对象空间：对于空间中的一群密集对象，若使用固定网格分区，则若网格尺寸选取不当，就容易导致大部分对象仍挤在某个网格中，导致跟没有划分差别不大

2.3 其它分区方法

参考毛星云先生写的游戏开发中的渲染加速算法总结

2.3.1 基于多叉树

四叉树（Quadtree）的分区方法融合了固定分区和层次分区的优点，其在最开始时将整个空间视为整体，若空间中的对象数量超过了临界值，空间就会被等分为四块，如此递归地对每个网格划分下去（其一般用于二维空间，其三维实现为八叉树）
- 若新增对象，则可能触发递归四分
- 若删除对象，若父网格内的对象计数低于临界值，会将子网格合并
- 若移动对象，则相当于原网格删除对象，新网格新增对象

2.3.2 基于搜索树

二叉空间划分（BSP, Binary Space Partitioning）
K-D树（K-Dimensional Tree）
层次包围盒（BVH, Bounding Volume Hierarchy）

游戏开发, 玩法相关

C++

本文由作者按照 CC BY-NC-SA 4.0 进行授权

一、空间分区的设计动机

1.1 敌人搜索

1.2 适用情况

二、空间分区的实现思路

2.1 固定网格示例

2.1.1 游戏内单位对象

2.1.2 区块与晶胞网格

2.1.3 单位对象间交互

2.1.4 跨网格交互半径

2.2 其它设计考量

2.2.1 全局遍历

2.2.2 层次划分

2.3 其它分区方法

2.3.1 基于多叉树

2.3.2 基于搜索树

热门标签