C / raylib
Advanced
C99 / raylib
O(N^2) 브루트포스 충돌을 O(N)으로 가속하는 C 언어 2D 공간 분할 해시 그리드
화면을 고정 크기 셀(Cell) 그리드로 분할하고 해시 함수를 통해 같은 셀 내에 존재하는 객체끼리만 충돌을 검사하여 수천 개 오브젝트를 초당 60프레임으로 처리하는 아키텍처.
#C #SpatialHashing #Collision #Optimization #DataStructure
핵심 개념물체가 $N$개일 때 이중 루프로 모든 쌍을 검사하면 연산 횟수는 $\frac{N(N-1)}{2}$로 기하급수적으로 폭증합니다. 월드 공간을 $64 \times 64$ 크기의 셀로 나누고, 물체의 좌표 $(x, y)$를 해시 키로 변환해 버킷에 삽입하면 인접한 셀의 물체들만 검사하므로 평균 시간 복잡도가 $O(N)$으로 수렴합니다.
1. 공간 해시 키 계산 및 버킷 구조
#define CELL_SIZE 64
#define HASH_BUCKETS 1024
typedef struct {
int id;
float x, y;
} Entity;
// 소수를 곱해 충돌을 최소화하는 2D 정수 해시 함수
int HashPosition(int cellX, int cellY) {
return ((cellX * 73856093) ^ (cellY * 19349663)) % HASH_BUCKETS;
}
void InsertEntity(Entity* e) {
int cellX = (int)(e->x / CELL_SIZE);
int cellY = (int)(e->y / CELL_SIZE);
int bucket = HashPosition(cellX, cellY);
// 버킷 링크드 리스트에 추가...
}