N Tutorial A - Collision Detection and Response
table of contents
SECTION 0: General Introduction
SECTION 1: SAT
SECTION 2: SAT for AABBs
SECTION 3: SAT for Circles
SECTION 4: SAT for Points
SECTION 5: Fast-Moving Objects
SECTION 6: Conclusion / Source Code
FOOTNOTES
APPENDIX A : Basic Geometry
SECTION 0: General Introduction
Collision Detection in Games
일반적으로, 게임에서의 충돌 탐지는 두 단계로 수행된다:
- 도형들의 어떤 쌍들이 충돌을 위해 테스트될 필요가 있는지 결정한다 (broad phase)
- step (1)에서 인식된 각 쌍에 대해 충돌 결과를 결정한다 (narrow phase)
N에서, step (1)은 사각형 셀의 균일한 "loose" grid를 사용하여 구현된다; 각 도형은 셀에 저장되는데, 그 셀은 그것의 중심부를 포함한다. 그리고 각 도형은 그것의 현 재 셀에서 어떤 도형과 충돌한다. 또는 현재 cell에 닿는 8개의 셀들.
나중 튜토리얼에서 좀 더 세부적을 이 시스템을 설명할 것이다; 이 튜토리얼은 N에서 step (2)가 어떻게 구현되었는지를 설명할 것이다.
이 단계를 다루기 위해 우리가 사용했던 알고리즘은 간단한 boolean result를 제공하는 것 이상으로 빠른 충돌탐지를 요구하는 어떤 게임에 든지 유용하다.
Collision Response via Projection
충돌 탐지를 어떻게 할 지에 대해 생각하기 이전에, 우리는 처음에 충돌하는 두 오브젝트에게 무엇이 발생해야 하는지를 생각해야 한다. 오브젝트들 a와 b가 서로 겹친다는 사실만이 주어진다면, 간단한 반응은 하나 또는 두 개의 오브젝트들을 파괴하거나 하나 또는 두 개를 그것들의 이전 위치로 움직이는 것이다. 이것이 몇 가지 오브젝트들의 유형에 충분한 것일지도 모르지만, 우리는 또한 좀 더 현실적인 방식으로 행동하는 물리적으로 재현된 오브젝트를 원할 것이다. 이 특징을 지원하기 위해, 우리는 "a와 b가 겹치고 있다"라는 정보보다 좀 더 많은 정보가 필요할 것이다. 특히, 중복의 특징에 대한 정보가 필요하다.
Projection은 겹치는("관통하는") 오브젝트를 다루는 물리적으로 그럴듯한 방법이다. 그 기본 아이디어는 가장 작은 가능한 displacement를 사용하여 관통한 오브젝트들을 움직이는 것이다. 그러고나서 충돌을 해결하는 것은 가능한 짧은 거리로 두 오브젝트들을 관통에서 빠져나오게 하는 vector v를 찾는 것과 동일하게 된다.
충돌을 다루는 몇 가지 다른 방법들은 penalty-force or impulse-based methods를 사용한다. Penalty methods는 충돌에서 오브젝트들을 당기기 위해 spring forces를 사용한다. Impulse based methods는 오브젝트들이 서로 관통하는 것을 막기 위해 즉각적인 충격(속도의 변화)를 사용한다.
다른 충돌-반응 방법을 보는 또 다른 방식은 오브젝트의 위치 관점에서 이다. Projection은 오브젝트의 위치를 직접 수정한다; impulse-based methods는 그 위치의 첫 번째 도함수 (즉, 속도)를 바꾸고, penalty-methods는 위치의 2차 도함수를 바꾼다(즉, 가속도, 스프링 힘으로부터 온 원인) - 모든 이 세 가지 방식들은 오브젝트들을 어떤 타겟 위치를 움직이려고 하는 것이다.
이 경우에, 우리는 그것들이 서로 관통하지 않도록 그 오브젝트를 움직이고 싶어한다. 모든 세 개의 충돌 반응 방식들은 우리가 구현했던 충돌 탐지 방법과 함께 사용될 수 있다; 우리는 projection을 사용하는 것을 선택했다. 왜냐하면 그것이 가장 간단한 방법이기 때문이고, 테스트 케이스에서 잘 작동하는 것처럼 보였기 때문이다.
그래서, 우리는 우리의 collision detection routines의 boolean result가 필요할 뿐만 아니라, 우리는 또한 projection vector가 필요하다. 이 projection vector가 (unit, 단위) 방향 벡터와 (scalar) penetration depth로 묘사되어질 수 있다는 것에 주목해라.
Bounce and Friction
우리가 우리의 두 오브젝트들을 그것들이 더 이상 충돌하지 않도록 움직이게 한다면, 우리는 "bounciness"와 마찰같은 물리적 현상을 모델링하기 위해 그것들의 속도를 바꾸고 싶다.
N에서 사용된 그 모델은 꽤 간단하고 현실적이지 않지만, 우리는 또한 마찰이 있는 bouncy objects를 위한 좀 더 현실적인 모델을 개발했었다. - 우리는 그리고 이 현실적인 모델이 간단한 모델 처럼 재미있는 느낌이 아니라는 것을 발견했다.
우리의 collision response method는 다음과 같았다:
- 충돌에 벗어나도록 움직여라
- 속도 벡터를 두 개의 컴포넌트들로 나누어라 : collision surface와 평행한 것과 수직인 것.
- perpendicular component를 사용하여 bounce를 계산하고,
- parallel component를 사용하여 마찰을 계산해라.
Note
소스코드를 이해하기 위해 너가 알아볼 필요가 있는 2D 기하에 대한 몇 가지 컨셉에 대해 간단한 리뷰를 위해, Appendix A를 참조해라. 우리는너가 벡터가 무엇이고, 벡터를 어떻게 스케일링하고, 덧셈 하는지를 그리고 내적이 무엇인지를 안다고 가정할 것이다; 그것이 너가 알아야 할 필요가 있는 모든 것이다.
SECTION 1: SAT
summary of SAT
SAT는 두 개의 볼록 도형이 주어지고, 만약 우리가 두 도형을 사영시킨 것이 중복하지 않은 축을 발견할 수 있다면 그 도형들이 겹치지 않는다는 것을 말해준다. 그 정리의 깊은 검사를위해 Eberly를 보아라.
2D에서, 이러한 잠재적인 분리 축들의 각각은 각 도형의 faces (edges) 중의 하나에 수직이다.
그래서 일반적으로, 우리는 일련의 1D queries를 사용하여 2D overlap query를 해결하고 있는 것이다. 각 query는 두 도형들이 주어진 축에 따라 겹치는지를 테스트한다. 만약 우리가 오브젝트들이 겹치지 않는 축을 발견한다면, 우리는 나머지축들을 계속해서 테스트 할 필요가 없다: SAT 덕분에, 우리는 오브젝트들이 겹치지 않는 다는 것을 안다.
이것이 SAT-type 접근법의 중요한 강점이다: 대부분의 게임에서, 두 오브젝트들이 겹치기 보다는 겹치지 않을 가능성이 더 크다. 그래서 이 "early-out (빠른 종료)" 능력을 속도를 좋게 상승시킨다.
calculating the projection vector
만약 그 오브젝트들이 가능한 분리 축에 따라서 모두 겹친다면, 그것들은 명백히 서로 겹치고 있는 중이다; 우리가 충돌을 발견했다는 것이다. 이것은 우리가 projection vector를 결정할 필요가 있는 것을 의미한다. 그 projection vector는 두 오브젝트를 떨어지게 밀어낸다.
이 점에서, 우리는 이미 대부분의 작업을 해왔다: 각 축은 우리가 그 오브젝트를 project할 수 있는 잠재적인 방향이다. 그래서 우리가 할 필요가 있는 모든 것은 두 오브젝트 사이의 중복의 양이 가장 작은 축을 찾는 것이다. - 그 projection vector의 방향이 axis direction과 같고, projection vector의 길이는 그 축을 따라 겹치는 크기와 동일하다.
그래서, 우리는 이제 충돌 탐지에 대해 우리의 일반적인 접근법을 가진다: 한 쌍의 오브젝트들에 대해, 각 잠재적인 분리 축을 테스트하고, 만약 분리되어있는 것을 발견하면 멈추어라. 그 축들어느것도 분리되어있지 않다면, projection vector를 생성하기 위해 가장 작은 overlap의 axis를 사용해라.
SECTION 2: SAT for AABBs
움직이는 물체들을 나타내기 위해, 2D 게임들에서 사용되는 흔한 도형은 axis-aligned bounding box, or AABB이다. AABB는 position p와 한쌍의 width and vectors xw and yw로 정의된다. 그리고 이것은 그 world 축들을 따라 박스의 사이즈를 정의한다.
halfwidth는 반지름의 개념과 비슷하다. 모든 방향 대신에 특정한 방향으로 정의된 것 말고는.
이제, 이 AABB와 또 다른 도형 사이의 충돌 탐지를 수행하기 위해, 우리는 간단히 우리의 SAT-type method를사용할 필요가 있고, x와 y (그 AABB의 두 개의 잠저잭인 분리 축들)을 따라 간단히 검사할 필요가있다. 뿐만아니라 그 다른 도형의 다른 잠재적인 분리축들도.
triangles
우리는 이미 위에서 두 AABB로 이 방법을 어떻게 사용하는지를 보았다; non-axis-aligned shapes는 어떤가?
N에서 사용된 삼각형 타일들은 world axes에 평행한 두 개의 변을 가지고 있다; 이것은 AABB와 triangular tile을 테스트하기 위해서, 우리고 한 다른 축을 따라서 검사할 필요 있다는 것을 의미한다 - 삼각형의 빗변에 수직인 축.
빗변의 수직 (즉, 그 빗변에 수직인 단위 방향 행렬)은 미리 계산되어질 수 있고, 그 도형을 회전시키거나 바꾸지 않는 삼각형들을 위해 저장되어질 수 있다.
round shapes
우리는 이제 AABB와 convex polyhedral shapes를 다룰수 있지만, 우리가 원형의 도형을 원하면 어떨까?
원들은 직접적으로 SAT에서 다뤄지지 않는다. 왜냐하면 그것들이 본질적으로 무한 개의 분리축을 가지고 있기 때문이다 - 어떤 방향이든지 그것들의 면에 수직이다.
우리의 방식을 적용하기 위해서, 그러한 원형의 도형을 적절히 나타내기 위해 (AABB로부터 생성된 world axes외에도) 어떤 축을 테스트해야할지 결정할 필요가 있다. 운 좋게도, 그 답은 간단하다: 만약 원의 중심인 한 점 p를 고려하고, AABB의 중심인 한 점 b를 고려한다면,
그 부가적인 분리 축은 p에서 b로 가는 벡터에 평행한 ㅜㄱ이다.
N의 collision system에서, "텅빈" circular sections으로 만들어진 타일들은 concave(오목) 타일들로 불려진다. 그러한 "solid" circular sections으로 만들어진 그 타일들은 covex(볼록)이라고 불려진다.
위에 있는것은 다소 심한 과장인 것을 주목해라: 특히, 우리가 완전한 원에 대해 AABB를 충돌시키길 원한다면 올바를 것이지만, 우리는 1/4원 부분에만 관심이 있기 때문에, 우리는 그 박스가 같은 사분면에 포함되었다면 circular axis를 우리가 관심있는circular section으로만 고려한다. 만약 그렇지 않다면, 우리는 이 축을 projection의 가능한 후보로 고려하지 않는다; 이것은위의 다이어그램에서 보여질 수 있다.
SECTION 3: SAT for Circles
2D 오브젝트들을 움직이게 하는 또 다른 공통된 충돌 도형은 원이다.
이전 섹션에서 우리의 SAT같은 방식과 호환되기 위해서 둥근 도형이 특별한 처리를 요구하는 것을 보았다; 이 섹션에서, 우리는 원과 다양한 다른 도형들 사이의 충돌을 다루기 위해서 그러한 아이디어들을 어떻게 확장시키는지 볼 것이다.
AABB에 대해서, minimum projection의 방향은 항상 AABB의 변 들 중 하나에 수직일 것이다(즉, 그 world axes들 중 하나와 함께); 원과 함께, 우리는 도형의 변 뿐만 아니라 그것의 정점들도 고려할 필요가 있다; 예를들어, 한 원과 한 box에 대한 잠재적 분리 축의 집합은 그 박스의 edges에 수직인 두 개의 축이고, 그 원에 평행한 4개의 축들이다 - box vertex vector들이다. 합리적으로 잠재적인 분리 축으로 고려되어질 수 있는 단일의 정점이 있다는 것이 명백하다: 원의 중심에 가장 가까운 vertex
한 도형에 있는 모든 정점들을 고해야만 하는 것은 많은 추가 계산을 더할 것이다; 그러나 위의 예제에서, 일반적으로 그 원의 각각에 에서, 즉 vertex axes들이 분리 축이 될 수 있지만, 그 원의 어떤 특정한 위치에 대해,
그러나 우리가 어떻게 어떤 정점이 가장 가까운지를 결정할 수 있는가? 각 정점에 Naively하게 거리를 테스트하는것은 가장 가까운 정점을 찾는 것을 손상시킬 것이다. 그리고 이것은 다른 정점들을 자명하게 거절할 것이다. 비싼 거리 연산 없이. voronoi regions의 유용한 개념이 사용될 수 있다.
voronoi regions
한 도형의 voronoi regions(VR)은 간단히 그 도형 주이의 공간의 지역이다. 그리고 그것은 polygon feature과 가장 가까운 모든 점을 포함한다. 한 polygon의 feature는 그 폴리곤의 edge or vertex이다.
소스코드를 이해하기 위해 너가 알아볼 필요가 있는 2D 기하에 대한 몇 가지 컨셉에 대해 간단한 리뷰를 위해, Appendix A를 참조해라. 우리는너가 벡터가 무엇이고, 벡터를 어떻게 스케일링하고, 덧셈 하는지를 그리고 내적이 무엇인지를 안다고 가정할 것이다; 그것이 너가 알아야 할 필요가 있는 모든 것이다.
SECTION 1: SAT
summary of SAT
SAT는 두 개의 볼록 도형이 주어지고, 만약 우리가 두 도형을 사영시킨 것이 중복하지 않은 축을 발견할 수 있다면 그 도형들이 겹치지 않는다는 것을 말해준다. 그 정리의 깊은 검사를위해 Eberly를 보아라.
2D에서, 이러한 잠재적인 분리 축들의 각각은 각 도형의 faces (edges) 중의 하나에 수직이다.
그래서 일반적으로, 우리는 일련의 1D queries를 사용하여 2D overlap query를 해결하고 있는 것이다. 각 query는 두 도형들이 주어진 축에 따라 겹치는지를 테스트한다. 만약 우리가 오브젝트들이 겹치지 않는 축을 발견한다면, 우리는 나머지축들을 계속해서 테스트 할 필요가 없다: SAT 덕분에, 우리는 오브젝트들이 겹치지 않는 다는 것을 안다.
이것이 SAT-type 접근법의 중요한 강점이다: 대부분의 게임에서, 두 오브젝트들이 겹치기 보다는 겹치지 않을 가능성이 더 크다. 그래서 이 "early-out (빠른 종료)" 능력을 속도를 좋게 상승시킨다.
calculating the projection vector
만약 그 오브젝트들이 가능한 분리 축에 따라서 모두 겹친다면, 그것들은 명백히 서로 겹치고 있는 중이다; 우리가 충돌을 발견했다는 것이다. 이것은 우리가 projection vector를 결정할 필요가 있는 것을 의미한다. 그 projection vector는 두 오브젝트를 떨어지게 밀어낸다.
이 점에서, 우리는 이미 대부분의 작업을 해왔다: 각 축은 우리가 그 오브젝트를 project할 수 있는 잠재적인 방향이다. 그래서 우리가 할 필요가 있는 모든 것은 두 오브젝트 사이의 중복의 양이 가장 작은 축을 찾는 것이다. - 그 projection vector의 방향이 axis direction과 같고, projection vector의 길이는 그 축을 따라 겹치는 크기와 동일하다.
그래서, 우리는 이제 충돌 탐지에 대해 우리의 일반적인 접근법을 가진다: 한 쌍의 오브젝트들에 대해, 각 잠재적인 분리 축을 테스트하고, 만약 분리되어있는 것을 발견하면 멈추어라. 그 축들어느것도 분리되어있지 않다면, projection vector를 생성하기 위해 가장 작은 overlap의 axis를 사용해라.
SECTION 2: SAT for AABBs
움직이는 물체들을 나타내기 위해, 2D 게임들에서 사용되는 흔한 도형은 axis-aligned bounding box, or AABB이다. AABB는 position p와 한쌍의 width and vectors xw and yw로 정의된다. 그리고 이것은 그 world 축들을 따라 박스의 사이즈를 정의한다.
halfwidth는 반지름의 개념과 비슷하다. 모든 방향 대신에 특정한 방향으로 정의된 것 말고는.
이제, 이 AABB와 또 다른 도형 사이의 충돌 탐지를 수행하기 위해, 우리는 간단히 우리의 SAT-type method를사용할 필요가 있고, x와 y (그 AABB의 두 개의 잠저잭인 분리 축들)을 따라 간단히 검사할 필요가있다. 뿐만아니라 그 다른 도형의 다른 잠재적인 분리축들도.
triangles
우리는 이미 위에서 두 AABB로 이 방법을 어떻게 사용하는지를 보았다; non-axis-aligned shapes는 어떤가?
N에서 사용된 삼각형 타일들은 world axes에 평행한 두 개의 변을 가지고 있다; 이것은 AABB와 triangular tile을 테스트하기 위해서, 우리고 한 다른 축을 따라서 검사할 필요 있다는 것을 의미한다 - 삼각형의 빗변에 수직인 축.
빗변의 수직 (즉, 그 빗변에 수직인 단위 방향 행렬)은 미리 계산되어질 수 있고, 그 도형을 회전시키거나 바꾸지 않는 삼각형들을 위해 저장되어질 수 있다.
round shapes
우리는 이제 AABB와 convex polyhedral shapes를 다룰수 있지만, 우리가 원형의 도형을 원하면 어떨까?
원들은 직접적으로 SAT에서 다뤄지지 않는다. 왜냐하면 그것들이 본질적으로 무한 개의 분리축을 가지고 있기 때문이다 - 어떤 방향이든지 그것들의 면에 수직이다.
우리의 방식을 적용하기 위해서, 그러한 원형의 도형을 적절히 나타내기 위해 (AABB로부터 생성된 world axes외에도) 어떤 축을 테스트해야할지 결정할 필요가 있다. 운 좋게도, 그 답은 간단하다: 만약 원의 중심인 한 점 p를 고려하고, AABB의 중심인 한 점 b를 고려한다면,
그 부가적인 분리 축은 p에서 b로 가는 벡터에 평행한 ㅜㄱ이다.
N의 collision system에서, "텅빈" circular sections으로 만들어진 타일들은 concave(오목) 타일들로 불려진다. 그러한 "solid" circular sections으로 만들어진 그 타일들은 covex(볼록)이라고 불려진다.
위에 있는것은 다소 심한 과장인 것을 주목해라: 특히, 우리가 완전한 원에 대해 AABB를 충돌시키길 원한다면 올바를 것이지만, 우리는 1/4원 부분에만 관심이 있기 때문에, 우리는 그 박스가 같은 사분면에 포함되었다면 circular axis를 우리가 관심있는circular section으로만 고려한다. 만약 그렇지 않다면, 우리는 이 축을 projection의 가능한 후보로 고려하지 않는다; 이것은위의 다이어그램에서 보여질 수 있다.
SECTION 3: SAT for Circles
2D 오브젝트들을 움직이게 하는 또 다른 공통된 충돌 도형은 원이다.
이전 섹션에서 우리의 SAT같은 방식과 호환되기 위해서 둥근 도형이 특별한 처리를 요구하는 것을 보았다; 이 섹션에서, 우리는 원과 다양한 다른 도형들 사이의 충돌을 다루기 위해서 그러한 아이디어들을 어떻게 확장시키는지 볼 것이다.
AABB에 대해서, minimum projection의 방향은 항상 AABB의 변 들 중 하나에 수직일 것이다(즉, 그 world axes들 중 하나와 함께); 원과 함께, 우리는 도형의 변 뿐만 아니라 그것의 정점들도 고려할 필요가 있다; 예를들어, 한 원과 한 box에 대한 잠재적 분리 축의 집합은 그 박스의 edges에 수직인 두 개의 축이고, 그 원에 평행한 4개의 축들이다 - box vertex vector들이다. 합리적으로 잠재적인 분리 축으로 고려되어질 수 있는 단일의 정점이 있다는 것이 명백하다: 원의 중심에 가장 가까운 vertex
한 도형에 있는 모든 정점들을 고해야만 하는 것은 많은 추가 계산을 더할 것이다; 그러나 위의 예제에서, 일반적으로 그 원의 각각에 에서, 즉 vertex axes들이 분리 축이 될 수 있지만, 그 원의 어떤 특정한 위치에 대해,
그러나 우리가 어떻게 어떤 정점이 가장 가까운지를 결정할 수 있는가? 각 정점에 Naively하게 거리를 테스트하는것은 가장 가까운 정점을 찾는 것을 손상시킬 것이다. 그리고 이것은 다른 정점들을 자명하게 거절할 것이다. 비싼 거리 연산 없이. voronoi regions의 유용한 개념이 사용될 수 있다.
voronoi regions
한 도형의 voronoi regions(VR)은 간단히 그 도형 주이의 공간의 지역이다. 그리고 그것은 polygon feature과 가장 가까운 모든 점을 포함한다. 한 polygon의 feature는 그 폴리곤의 edge or vertex이다.
따라서, 만약 우리가 어떤 VR이 그 원의 중점을 포함하는지 안다면, 우리는 어떤 feature가 그 원에 가장 가까운지를 안다. 그리고 따라서, 우리는 그 원과 vertex를 테스트 해야하는지를 알 뿐만 아니라 어떤 정점을 테스트 할 지도 안다.
VR의 아름다운은, world axes를따라서 그 테스트의 결과를 봄으로써, 우리는 더 연산을 수행하는 것 없이 AABB의 어떤 VR이 그 원을 포함하는지 추론할 수 있다. 이 아이디어는 Arvo에서 처음으로 나타난다.
other shapes
원과 직각삼각형 그리고 convex/concave circular sections과 같은 다른 도형들을 충돌시키는 것은 AABB에서 했던 것과 같은 방식으로 이루어질 수 있다. 위의 다이어그램에서 만약 그 원이 다른 도형의 voronoi regions주으이 하나 안에 있다면 부가적인 축이 고려되어야 한다는 것을 제외하고.
SECTION 4: SAT for Points
우리가 그 위의 아이디어들을 점과 다양한 타일 도형들에 테스팅하기 위해 적용할 수 있을지라도, 그 결과는 보통 만족스럽지 않을 것이다. 이것은 우리의 collision detection routines 때문이 아니라, 대신에 projection을 통해서 충돌들을 다루는 우리의 결정 때문이다.
가장 짧은 가능한 벡터를 따라서 항상 projecting하는 것의 문제는 그것이 항상 "옳은" 벡터가 아니라는 것이다.특정하게도, 너가 기대하는 방식으로 보이거나 또는 행동하는 벡터가 아닐것이다.
예를들어, AABB-AABB 경우를 고려하자; 그 projection vector는 가끔씩 한 축에서 다른 축으로 갑자기 "뛰어가버린다". 이것은 너가 한 AABB가 다른 것의 아래로 들어가는동안, 그것이 왼쪽 또는 오른쪽으로 (위로 가는 것 대신에) 밀어지는것을 의미한다. 왜냐하면 그것이 한프레임에 얼마나멀리 움직이는 가 때문에, left/right direction은 더 작은 projection vector를만든다.
이 문제는 collision response의 projection method의 피할 수 없는 부분이다. 그리고 만약 world에 있는 그 오브젝트가 한 프레임에 너무 멀리 움직인다면 발생한다. 한 오브젝트가 더 작을수록, 그것은 더욱 빨리 움직이고, 이 문제가 일어날 가능성이 더 높다.
그러나, 비록 point-tile query에 의해 반환된 projection info가 너가 원하는게 아닐지라도, 실제 boolean result는 항상 옳을 것이라는 것을 명심해라. 그래서 우리의 SAT-like 방식은 간단히 AABB-tile code를사용하고, xw와 yw를 0으로 설정하고 (또는 간단히 그것들을 제외하고), 그리고 projection-vector calculations를 건너뛰어서 매우 빠른 점-tile boolean queries를 위해 사용되어질 수 있다.
N에서, homing-rocket vss tilemap collision은, point-tilemap queries를 사용하여 구현된다; 우리는 점프 또는 슬라이딩과 같은 벽 상호작용을 allow/disallow하기 위해 빠르게 그 닌자가 벽에 가까이 있는지를 결정하기 위해 또한 point-tilemap queries를 사용한다.
SECTION 5: Fast-Moving Objects
위에서 언급되었듯이, 작은 and/or fast-moving 오브젝트들은 static collision test를 사용할 때 문제를 만들 수 있다. 그러한 오브젝트들을다루기 위해 취해질 수 있는 몇 가지 접근법들이 있다 - 가장 간단한 것은 너의 게임 설계를 그러한 오브젝트들이 필요하지 않도록 제한하는 것이다.
만약 너가 절대적으로 그것들을 가져야 한다면, small and/or fast-moving 오브젝트들을 다룰 두 가지 공통된 방법들이 있다:
swept-collision tests and multisampling
sweep tests
두 개의 정적인 도형들 사이의 교차를 테스팅하는 대신에, 우리는 원래의 도형을 그것들의 trajectory(궤도)를 따라서 sweeping하여 대신에 새로운 도형을 만들 수 있다. 그리고 이러한 swept된 도형들 사이의 교차를 테스트 한다.
기본 아이디어는 circle-circle and AABB-AABB sweep tests에 대해 [Gomez]에서 묘사된다.
multisampling
swept tests에 대한 좀 더 간단한 대안은 multisample이다; 그 오브젝트의 새로운 위치에서 단일의 정적 테스트를 수행하는 대신에, 그 오브젝트의 이전과 새로운 위치 사이에 위치한 몇 가지 위치에서 몇 가지 테스트를 수행하라.
만약 너가 그 샘플들이 항상 그 오브젝트의 반지름보다 더 작은 거리에 공간에 있게 할 수 있다면, 이것은 훌륭한 결과들을 만들어 낼 것이다. 우리의 구현에서, 우리는 최대 샘플 갯수를 제한한다. 그래서 매우 높은 속도는 가끔씩 문제를 만들어 낼 것이다; 이것은 너의 특정한 프로그램을 기반으로 조정되어질 수 있다.
SECTION 6: Conclusion / Source Code
운 좋게도,이것은 2D에서 어떻게 충돌 탐지와 반응을 구현할지에 대해 너에게 몇 가지 아이디어들을 준다. 우리는 우리의 방법이 가장 빠르고 또는 가장 우아한 솔루션이 아니지만 우리가 사용한 것이 잘 작동하다는 것은 확신할 수 있다.
확실히, 충돌에 대한 위의 접근법은 다양한 방법들로 확장되어질 수 있다 - 예를들어, 임의의 삼각형들 같은 다른 도형은 tile shapes로 구현되어질수 있거나 dynamic shpaes로 구현되어질 수 있다. 정말 dynamic object shapes로서 그 타일 모양의 어떤 것이든 구현가능한 것이다. 만약 너가 위의 접근법으로 어떤 주어진 모형을 사용하고 싶다면, 너가 할 수 있을 필요가 있는 모든 것은 주어진 축에 사영될 때 그 도형의 halfwidth를 결정하는 것이다. 만약 스피드가 정말 중요하다면 (actionscript에서 처럼), 그러면 그 트릭은 이러한 halfwidth가 미리 계산된거나 또는 쉽게 계산될 수 있는 도형들을 사용하는 것이다.
댓글 없음:
댓글 쓰기