1. 저는 평범한 프로그래머이고 게임 프로그래밍을 하는 사람은 아닙니다만, 2D 게임을 만들어 보려고 생각 중입니다.

2. 대부분의 게임에서 가장 본질적이고 핵심적인 부분이라고 할 수 있는 '충돌체크'에 대한 질문을 하고자 합니다.

 

3. 프로그래밍언어나 게임프로그래밍에 대한 기초적인 지식은 가지고 있으니 적당히 설명해 주면 알아 들을 수 있습니다.

---

자, 우선 저는 일반적으로 2D 게임에서 쉽게 통용되는 '두 사각형 객체 간의 충돌체크'에 대해서는 무리 없이 알고 있습니다.

이 경우는 객체 간의 관계가 '일대일'인 경우이고, 다음으로 생각해 봐야 하는 상황은 객체 간의 관계가 '일대다'인 경우입니다.

즉, 대부분의 슈팅 게임이 가진, '플레이어가 조종하는 '하나'의 캐릭터와 '다수'의 적들의 관계' 정도를 생각하시면 됩니다.

 

다시 말해 내 캐릭터와 적들 간의 충돌체크는 필요하지만, 적들 서로 간의 충돌체크는 필요하지 않은 그런 상황을 말하는 것입니다.

이런 경우에는 그냥 상대 객체의 수만큼(적의 수만큼) 체크를 반복하면 될거라 생각합니다. 상대 객체가 좀 많아도 그렇게까지

 

연산 횟수가 많이 늘어나지 않아 (상대 객체가 100이면 100번만 하면 되니까) 이렇게 해도 사실 큰 무리가 없어 보입니다.

 

---

문제는 객체 간의 관계가 '다대다'일 때입니다. 다시 말해, "적군과 아군이 30대 30으로 전투를 벌이는 게임"에서는 아군과 적군

사이의 충돌체크 뿐만 아니라, 아군과 아군 사이에서도 충돌체크가 필요합니다. (겹치면 안되니까) 다시 말해 화면 내에 있는

모든 객체들이 서로에 대한 충돌체크가 필요한 것입니다. 이런 경우에 위와 같은 방법을 적용하면 생각보다 많은 연산횟수가

필요하게 됩니다. 중복된 체크를 피하더라도 객체의 수 n에 따라 nC2라는 횟수로 증가하게 되는데, 제가 실제로 구현해보지

않은 상태라 이게 어느정도의 부하를 가져 올 지는 모르겠지만, 누가 생각해 봐도 결코 좋은 방법은 아닙니다.

---

그렇다면 결론적으로 "다수의 객체들이 실시간으로 자신을 제외한 모든 객체와 충돌체크를 할 수 있는 효율적인 알고리즘 혹은 그 방법"

이 있다면 어떤 방법이 있을까요? 그리고 일반적인 2D 게임들은 어떤 방법을 이용하는지 궁금합니다. 물론 이 부분은 2D 3D를 막론하고

 

공통된 사항이지만 말입니다.

---

아마 게임 프로그래밍을 전공으로 하는 학생이나, 게임업체에서 현역으로 활동하고 있는 프로그래머 분이라면 너무도 쉬운 부분이 아닐까 합니다.

 

아시는 분이 계신다면 간단하게나마 설명을 해주신다면 큰 도움이 되리라 생각합니다.