📄 SpatialGrid.cpp
#include <iostream>
#include <vector>
#include <map>
struct Entity {
int id;
float x, y;
float radius;
};
class SpatialGrid {
private:
float cellSize_;
// セル座標のハッシュ値 -> そのセルに属するエンティティIDリスト
std::map<int, std::vector<int> > grid_;
int getCellHash(int cellX, int cellY) const {
// 素数を用いた単純な2D空間ハッシュ関数
return cellX * 73856093 ^ cellY * 19349663;
}
public:
SpatialGrid(float cellSize) : cellSize_(cellSize) {}
void clear() {
grid_.clear();
}
void insert(const Entity& e) {
int cellX = static_cast<int>(e.x / cellSize_);
int cellY = static_cast<int>(e.y / cellSize_);
int hash = getCellHash(cellX, cellY);
grid_[hash].push_back(e.id);
}
void findPotentialCollisions(const std::vector<Entity>& entities) {
int checkCount = 0;
int hitCount = 0;
for (std::map<int, std::vector<int> >::iterator it = grid_.begin();
it != grid_.end(); ++it) {
const std::vector<int>& bucket = it->second;
// 同じバケットに入っている物体同士だけを判定
for (size_t i = 0; i < bucket.size(); ++i) {
for (size_t j = i + 1; j < bucket.size(); ++j) {
checkCount++;
const Entity& a = entities[bucket[i]];
const Entity& b = entities[bucket[j]];
float dx = a.x - b.x;
float dy = a.y - b.y;
float distSq = dx * dx + dy * dy;
float radSum = a.radius + b.radius;
if (distSq <= radSum * radSum) {
hitCount++;
std::cout << " 💥 衝突検知: ID " << a.id << " <-> ID " << b.id << std::endl;
}
}
}
}
std::cout << "[Grid統計] 判定実行回数: " << checkCount << " 回 (衝突: " << hitCount << " 件)" << std::endl;
}
};
int main() {
std::cout << "=== 空間グリッド衝突判定テスト ===" << std::endl;
std::vector<Entity> entities;
// 遠く離れた場所と密集した場所にオブジェクトを配置
Entity e1 = {0, 10.0f, 10.0f, 5.0f};
Entity e2 = {1, 12.0f, 11.0f, 5.0f}; // e1 と衝突
Entity e3 = {2, 500.0f, 500.0f, 5.0f}; // 遠く離れた位置
Entity e4 = {3, 502.0f, 501.0f, 5.0f}; // e3 と衝突
entities.push_back(e1);
entities.push_back(e2);
entities.push_back(e3);
entities.push_back(e4);
SpatialGrid grid(64.0f); // セルサイズ 64x64
for (size_t i = 0; i < entities.size(); ++i) {
grid.insert(entities[i]);
}
grid.findPotentialCollisions(entities);
return 0;
}