【ゲーム制作】当たり判定の最適化｜四分木（Quadtree）をC++で実装する

// 総当たり：全部の組み合わせを調べる
for (size_t i = 0; i < objects.size(); ++i) {
    for (size_t j = i + 1; j < objects.size(); ++j) {
        if (Hit(objects[i], objects[j])) {
            // 当たった時の処理
        }
    }
}

#include <vector>
#include <memory>

// 矩形（中心x, 中心y, 半分の幅, 半分の高さ）
struct Rect {
    float cx, cy, hw, hh;

    // 点を含むか
    bool Contains(float x, float y) const {
        return x >= cx - hw && x <= cx + hw &&
               y >= cy - hh && y <= cy + hh;
    }

    // 他の矩形と重なるか（AABB判定）
    bool Intersects(const Rect& o) const {
        return !(o.cx - o.hw > cx + hw || o.cx + o.hw < cx - hw ||
                 o.cy - o.hh > cy + hh || o.cy + o.hh < cy - hh);
    }
};

struct GameObject {
    float x, y;
    int   id;
};

class Quadtree {
public:
    Quadtree(const Rect& boundary, int capacity = 4)
        : boundary_(boundary), capacity_(capacity), divided_(false) {}

    // オブジェクトを追加する
    bool Insert(const GameObject& obj) {
        // 自分の範囲外なら受け取らない
        if (!boundary_.Contains(obj.x, obj.y)) return false;

        // まだ余裕があるなら、ここで持つ
        if ((int)objects_.size() < capacity_ && !divided_) {
            objects_.push_back(obj);
            return true;
        }

        // 容量オーバーなら4分割する
        if (!divided_) Subdivide();

        // 子のどれかに入れてもらう
        if (nw_->Insert(obj)) return true;
        if (ne_->Insert(obj)) return true;
        if (sw_->Insert(obj)) return true;
        if (se_->Insert(obj)) return true;
        return false;
    }

private:
    void Subdivide() {
        float hw = boundary_.hw / 2.0f;
        float hh = boundary_.hh / 2.0f;
        float cx = boundary_.cx;
        float cy = boundary_.cy;

        nw_ = std::make_unique<Quadtree>(Rect{cx - hw, cy - hh, hw, hh}, capacity_);
        ne_ = std::make_unique<Quadtree>(Rect{cx + hw, cy - hh, hw, hh}, capacity_);
        sw_ = std::make_unique<Quadtree>(Rect{cx - hw, cy + hh, hw, hh}, capacity_);
        se_ = std::make_unique<Quadtree>(Rect{cx + hw, cy + hh, hw, hh}, capacity_);
        divided_ = true;

        // すでに持っていた分を子に配り直す
        for (const auto& o : objects_) {
            nw_->Insert(o) || ne_->Insert(o) || sw_->Insert(o) || se_->Insert(o);
        }
        objects_.clear();
    }

    Rect boundary_;
    int  capacity_;
    bool divided_;
    std::vector<GameObject> objects_;
    std::unique_ptr<Quadtree> nw_, ne_, sw_, se_;
};

    // 範囲内にいるオブジェクトを集める
    void Query(const Rect& range, std::vector<GameObject>& out) const {
        // 重なっていない区画は、中を見る必要すらない
        if (!boundary_.Intersects(range)) return;

        for (const auto& o : objects_) {
            if (range.Contains(o.x, o.y)) out.push_back(o);
        }

        if (divided_) {
            nw_->Query(range, out);
            ne_->Query(range, out);
            sw_->Query(range, out);
            se_->Query(range, out);
        }
    }

void UpdateCollision(std::vector<GameObject>& objects) {
    // 画面全体（640x480想定）で木を作り直す
    Quadtree tree(Rect{320.0f, 240.0f, 320.0f, 240.0f});
    for (const auto& o : objects) tree.Insert(o);

    std::vector<GameObject> nearby;
    for (const auto& o : objects) {
        nearby.clear();
        // 自分の周り32ピクセルだけを問い合わせる
        tree.Query(Rect{o.x, o.y, 32.0f, 32.0f}, nearby);

        for (const auto& other : nearby) {
            if (o.id == other.id) continue; // 自分自身は飛ばす
            // ここで実際の当たり判定
        }
    }
}