游戏客户端架构 / 系统课时

优化空间查询

优化空间查询

当场景中的碰撞体增多时,逐对检测会迅速拖慢每一帧。本课用均匀网格先筛出可能相交的对象,再进入精确检测,并通过一个可运行的 C++ 示例验证候选组合确实减少。

学习目标

  • 理解空间查询中“粗检测”和“精确检测”的分工
  • 能将二维包围盒映射到均匀网格并生成候选对象对
  • 能根据对象尺寸与分布选择网格大小并处理重复组合

从全量配对到两阶段检测

若场景中有 NN 个对象,直接两两比较需要检查 N(N−1)/2N(N-1)/2 个组合。对象数量翻倍时,检测次数接近四倍,即使绝大多数对象相距很远,也会消耗时间。

均匀网格把世界划分为固定大小的单元格。每个碰撞体只登记到自身覆盖的格子中,查询时仅比较同一格子里的对象。这个步骤称为粗检测;它允许产生少量误报,但不能漏掉真正可能碰撞的组合。随后再用圆形、AABB 或其他算法完成精确检测。

均匀网格粗检测与精确检测关系

实现均匀网格查询

碰撞体可能跨越多个格子,因此要分别计算包围盒最小角和最大角所在的单元格,并登记到覆盖范围内的每个格子。不同格子可能生成同一对象对,示例使用 std::set 自动去重,并按编号稳定输出结果。

cpp
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <set>
#include <tuple>
#include <utility>
#include <vector>

struct Aabb {
    int id;
    float minX;
    float minY;
    float maxX;
    float maxY;
};

struct Cell {
    int x;
    int y;

    bool operator<(const Cell& other) const {
        return std::tie(x, y) < std::tie(other.x, other.y);
    }
};

bool overlaps(const Aabb& a, const Aabb& b) {
    return a.minX <= b.maxX && a.maxX >= b.minX &&
           a.minY <= b.maxY && a.maxY >= b.minY;
}

int toCell(float value, float cellSize) {
    // floor 能正确处理负坐标,直接转 int 会在负数区域产生错误格子。
    return static_cast<int>(std::floor(value / cellSize));
}

int main() {
    const float cellSize = 10.0f;
    const std::vector<Aabb> objects{
        {1, 1.0f, 1.0f, 3.0f, 3.0f},
        {2, 2.5f, 2.5f, 4.0f, 4.0f},
        {3, 12.0f, 1.0f, 14.0f, 3.0f},
        {4, 18.0f, 1.0f, 22.0f, 3.0f},
        {5, 21.0f, 2.0f, 23.0f, 4.0f}
    };

    std::map<Cell, std::vector<const Aabb*>> grid;
    for (const Aabb& object : objects) {
        const int minCellX = toCell(object.minX, cellSize);
        const int maxCellX = toCell(object.maxX, cellSize);
        const int minCellY = toCell(object.minY, cellSize);
        const int maxCellY = toCell(object.maxY, cellSize);

        // 跨格对象必须登记到全部覆盖格子,否则会漏掉边界附近的碰撞。
        for (int y = minCellY; y <= maxCellY; ++y) {
            for (int x = minCellX; x <= maxCellX; ++x) {
                grid[{x, y}].push_back(&object);
            }
        }
    }

    std::set<std::pair<int, int>> candidates;
    for (const auto& [cell, members] : grid) {
        for (std::size_t i = 0; i < members.size(); ++i) {
            for (std::size_t j = i + 1; j < members.size(); ++j) {
                candidates.emplace(
                    std::min(members[i]->id, members[j]->id),
                    std::max(members[i]->id, members[j]->id)
                );
            }
        }
    }

    std::cout << "候选对象对: " << candidates.size() << "\n";
    for (const auto& [leftId, rightId] : candidates) {
        const Aabb& left = objects.at(static_cast<std::size_t>(leftId - 1));
        const Aabb& right = objects.at(static_cast<std::size_t>(rightId - 1));
        if (overlaps(left, right)) {
            std::cout << "发生碰撞: " << leftId << " - " << rightId << "\n";
        }
    }
}

预期输出:

text
候选对象对: 3
发生碰撞: 1 - 2
发生碰撞: 4 - 5

示例中的五个对象原本需要检查十个组合,网格只生成三个候选组合;其中 3 - 4 是粗检测误报,最终被 AABB 精确检测排除。

选择网格大小与处理边界

网格边长通常接近场景中常见碰撞体的直径。格子过大时,同格对象过多,粗检测退化为接近全量比较;格子过小时,一个对象会跨越很多格子,登记和去重成本上升。对象尺寸差异很大时,可考虑分层网格、四叉树或动态包围盒树。

动态场景需要在对象移动后更新其格子成员关系。简单实现可以每帧清空并重建网格;对象数量较多时,应记录旧格子范围,只在跨格后增删成员。生产代码还应避免用连续数组下标查找对象编号,并根据世界范围选择哈希表或稀疏存储。

本课总结

  • 均匀网格用空间邻近性减少粗检测候选组合,再交给精确算法确认碰撞
  • 跨格登记和候选对去重是避免漏检与重复检测的两个关键点
  • 网格大小应匹配常见对象尺寸,并结合对象移动方式评估更新成本

下一课预告

下一课将把空间查询结果接入基础物理更新流程,处理碰撞响应、位置修正与速度变化。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

优化空间查询

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通