47、STL与游戏开发：游戏对象管理、碰撞检测、路径查找中的STL应用

游戏开发，说白了就是跟一堆对象打交道。你想想看，一个游戏里有多少东西要管？角色、怪物、子弹、道具、特效……每个都得创建、更新、销毁。我早年刚入行时，还傻乎乎地自己写链表来管理这些对象。后来发现，STL 早就把这些脏活累活干好了。

今天我们就聊聊，STL 在游戏开发里到底能怎么用。我会结合自己踩过的坑，给你讲讲对象管理、碰撞检测、路径查找这三个核心场景。

游戏对象管理：vector 和 list 的选择

游戏对象管理，最基础的就是容器选择。我个人习惯用 std::vector 作为默认容器。为什么？因为游戏对象通常是连续创建的，遍历频率远高于插入删除。

核心原则：遍历多就用 vector，频繁增删中间元素就用 list。

举个例子，管理所有子弹对象：

#include <vector>
#include <memory>

class Bullet {
public:
    void update(float dt);
    bool isAlive() const;
private:
    float lifetime_;
};

class BulletManager {
    std::vector<std::unique_ptr<Bullet>> bullets_;
public:
    void addBullet(std::unique_ptr<Bullet> b) {
        bullets_.push_back(std::move(b));
    }

    void updateAll(float dt) {
        for (auto& b : bullets_) {
            b->update(dt);
        }
        // 移除死亡的子弹
        bullets_.erase(
            std::remove_if(bullets_.begin(), bullets_.end(),
                [](const auto& b) { return !b->isAlive(); }),
            bullets_.end()
        );
    }
};

这里用了 std::remove_if 配合 erase，这是 STL 里经典的「移除-擦除」惯用法。我在项目中遇到过一个问题：如果直接用 erase 在循环里删除元素，性能会急剧下降。因为每次 erase 都会导致后续元素向前移动。而 remove_if 先把要删除的元素移到末尾，再一次性擦除，效率高得多。

小技巧：如果子弹数量很大（比如上万颗），可以考虑用 std::deque 替代 vector。deque 在头部和尾部插入删除都是 O(1)，而且内存碎片更少。

碰撞检测：空间划分与 STL 算法

碰撞检测是游戏开发里的性能杀手。最简单的做法是两两检测，复杂度 O(n²)。1000 个对象就要检测 50 万次，这谁顶得住？

我常用的优化手段是空间划分。比如网格法：把游戏世界分成格子，每个格子用一个 std::vector 存储该格子内的对象。

#include <vector>
#include <unordered_map>

class SpatialGrid {
    int cell_size_;
    std::unordered_map<int, std::vector<int>> grid_; // cell_id -> object_ids

    int getCellId(float x, float y) const {
        int cx = static_cast<int>(x / cell_size_);
        int cy = static_cast<int>(y / cell_size_);
        return cx * 10000 + cy; // 简单的哈希
    }

public:
    void addObject(int id, float x, float y) {
        int cell = getCellId(x, y);
        grid_[cell].push_back(id);
    }

    // 只检测相邻格子内的对象
    void checkCollisions() {
        for (auto& [cell, objects] : grid_) {
            // 只检测当前格子内的对象
            for (size_t i = 0; i < objects.size(); ++i) {
                for (size_t j = i + 1; j < objects.size(); ++j) {
                    // 检测 objects[i] 和 objects[j] 是否碰撞
                }
            }
        }
    }
};

这里用了 std::unordered_map 来存储格子数据。为什么不用 map？因为 unordered_map 的查找是 O(1) 平均，而 map 是 O(log n)。游戏里每帧都要频繁查找格子，unordered_map 更合适。

注意：unordered_map 的哈希函数如果设计不好，会导致大量冲突，性能反而下降。我建议用简单的乘法哈希，或者直接用 std::hash 的默认实现。

另外，STL 的 std::sort 在碰撞检测里也很有用。比如做「扫描线算法」时，先把对象按 x 坐标排序，然后只检测 x 轴重叠的对象。这样能把 O(n²) 降到接近 O(n log n)。

路径查找：A* 算法与 STL 容器

路径查找，最经典的就是 A* 算法。A* 需要两个核心数据结构：开放列表（open list）和关闭列表（closed list）。

关闭列表用 std::unordered_set 最合适，因为只需要快速判断一个节点是否已经处理过。开放列表则需要一个优先队列，STL 的 std::priority_queue 正好派上用场。

#include <queue>
#include <unordered_set>
#include <vector>
#include <functional>

struct Node {
    int x, y;
    float g, h; // 实际代价 + 启发式代价
    Node* parent;

    float f() const { return g + h; }
};

// 优先队列需要自定义比较
struct CompareNode {
    bool operator()(const Node* a, const Node* b) {
        return a->f() > b->f(); // 小顶堆
    }
};

std::vector<Node> findPath(int startX, int startY, int endX, int endY) {
    std::priority_queue<Node*, std::vector<Node*>, CompareNode> openList;
    std::unordered_set<int> closedList; // 用 (x*1000 + y) 作为 key

    // 起点入队
    Node* start = new Node{startX, startY, 0, heuristic(startX, startY, endX, endY), nullptr};
    openList.push(start);

    while (!openList.empty()) {
        Node* current = openList.top();
        openList.pop();

        int key = current->x * 1000 + current->y;
        if (closedList.count(key)) continue;
        closedList.insert(key);

        if (current->x == endX && current->y == endY) {
            // 找到路径，回溯
            std::vector<Node> path;
            while (current) {
                path.push_back(*current);
                current = current->parent;
            }
            std::reverse(path.begin(), path.end());
            return path;
        }

        // 扩展邻居节点（略）
    }

    return {}; // 没找到路径
}

这里有个坑：std::priority_queue 默认是大顶堆（最大元素在顶部），而 A* 需要小顶堆（最小 f 值在顶部）。所以必须自定义比较器，把大于号改成小于号的效果。

我的经验：如果地图很大（比如 1000x1000），用 std::priority_queue 的 push/pop 操作会频繁分配内存。这时候可以考虑用 std::vector 手动维护堆，配合 std::push_heap 和 std::pop_heap，能减少内存分配次数。

STL 在游戏中的其他妙用

除了上面三个场景，STL 还有很多实用组件：

  • std::string：处理 UI 文本、日志输出。别自己写字符串拼接，std::ostringstream 比 sprintf 安全得多。
  • std::map：做配置表、状态机。比如用 std::map<std::string, std::function<void()>> 实现状态分发。
  • std::algorithm：排序、查找、洗牌。比如用 std::shuffle 实现抽卡逻辑。
  • std::chrono：精确计时，控制帧率。比 clock() 靠谱多了。

我曾经接手过一个项目，里面全是手写的链表和数组。光是一个碰撞检测模块就有 2000 行，bug 还特别多。后来我用 STL 重构了一遍，代码量砍到 600 行，性能反而提升了 30%。嗯，这就是 STL 的魅力——你不需要重复造轮子，轮子早就被造好了，而且比你造的强。

知识体系总览

下面这张图总结了 STL 在游戏开发中的核心应用场景：

STL 在游戏开发中的应用 游戏对象管理 容器选择 vector：遍历多，连续存储 list：频繁增删中间元素 deque：头尾操作多 碰撞检测 空间划分 + 算法 unordered_map：格子管理 sort：扫描线排序 remove_if：惰性删除 路径查找 A* 算法核心 priority_queue：开放列表 unordered_set：关闭列表 push_heap/pop_heap：手动堆 核心思想 选择合适的容器 + 善用算法 = 高效、可维护的游戏代码 不要重复造轮子，STL 的轮子比你造的强

STL 不是银弹，但它能帮你解决 80% 的通用问题。剩下的 20%，比如内存池、对象池、ECS 架构，才需要你手写优化。但那是另一个话题了。

一句话总结：STL 是游戏开发的基石。用好它，你的代码会更简洁、更高效、更不容易出 bug。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →