필자는 2D게임에 대한 개발 경험이 있으므로 이 글에서 언급되는 충돌 알고리즘은 2d가 기준이 된다.
충돌처리는 많은 부분에서 쓰인다. 하지만 게임에서는 더더욱 빠질 수 없는 부분이다.
흔히 충돌을 감지할때는 서로의 영역(Range)안에 서로가 겹쳐(Overlab)되어 있는 여부를 확인함으로써 충돌(Collision)인지를 검출한다.
이 중에 Range에 관해서는 크게 2가지로 나눌 수 있다.
1. 사각형
이것은 가장 일반적인 영역으로 4변의 직각으로 이루어진 도형을 말한다.
사각형은 2가지로 표현 될 수 있는데 각 점을 x1, y1, x2, y2로 봤을 경우
Rect(x1, y1, x2, y2) 와
width = x2 - x1 , height = y2 - y1으로 생각한
Rect(x1, y1 , width ,height)가 있다.
다만, 충돌연산에서는 전자가 편리할 수 있다.
이제 충돌을 감지할 때는 2개의 영역이 필요하므로
R1 (x1, y1, x2, y2) 와 R2 (x3, y3, x4, y4)가 있다고 가정하면
> x1은 left y1은 top x2는 right y2는 bottom으로 matting된다.
R1.left < R2.right && R1.right > R2.left
&& R1.top < R2.bottom && R1.bottom > R2.top
으로 생각할 수 있다. 위 식을 만족하는 경우 R1과 R2는 충돌했다 볼 수 있다.
다음은 다른 도형이다.
2. 원
원의 장점은 사각형보다 빠른 연산을 할 수 있는 점이다.
물론, 원도 역시 2개가 충돌한 경우를 살펴보면
C1 (x1, y1, r1) 과 C2(x2, y2, r2)
sqrt( (x2 - x1)^2 + (y2 - y1)^2 ) < abs( r2 - r1 ) 인 경우이다(반지름과 두 점과의 거리를 살펴봄)
>1. < 인 경우는 내접
>2. = 인 경우는 충돌시작
>3. > 인 경우는 외접(충돌 X)
이다. =의 유무는 필요에 따라 다르다.
일반적으로 사각형과 원 가운데 무엇을 선택할 지는 개발자의 몫이다.
이어서.. 충돌이 일어났다는 감지(Collision)뿐만 아니라 충돌된 영역 (Collision Range)를 구하는 방법도 알아보자.
> 이것은 장애물(Object)와의 충돌시 해당 영역을 보상할 때 필요하다.
> ex) 맵에서 바닥에 들어갔을 때 관통되지 않는 Object라면 Object위에 그대로 서 있어야 하는 경우.
'알고리즘' 카테고리의 다른 글
| 더블 버퍼링 (0) | 2015.02.12 |
|---|---|
| 임의의 순서로 이루어진 순열 얻기 (0) | 2015.02.10 |
| 현재 화면에 맞춰 이미지 크기 변경 (0) | 2015.02.10 |
| XOR 교체 알고리즘 (0) | 2015.01.29 |
| 오브젝트를 생성하고 삭제하는 문제 (0) | 2015.01.08 |