1. 나는 그냥 프로그래머고 게임 프로그래밍을 하는 사람은 아닌데 그냥 2D 게임을 만들어 보려고 생각 중이다.

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

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

---

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

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

즉, 슈팅 게임에 나오는 '플레이어가 조종하는 캐릭터 하나와 다수의 적들의 관계' 정도를 생각하면 된다. 다시 말해,

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

이런 경우에는 그냥 상대 객체의 수만큼(적의 수만큼) 체크를 반복하면 된다. 그렇게까지 연산 횟수가 많이 늘어나지 않아

(상대 객체가 100이면 100번만 하면 되니까) 이렇게 해도 사실 큰 무리가 없어 보인다.

---

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

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

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

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

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

---

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

이 있다면 어떤 방법이 있을까? 그리고 일반적인 2D 게임들은 어떤 방법을 이용하는 것일까? 그것이 궁금하다.

---

구체적인 구현 방법에 대해서 설명하지 않아도 개괄적으로 이런 방식이 효율적이다 정도만 제시해 줘도 충분히 구현 할 수 있을 거 같은데

어디 그런 거 물어볼 데가 없다. 저번에 보니까 영역을 여러개로 나눠서 각 영역 내에 있는 것들끼리만 연산한다던데, 그러면 경계면에 있는

두 객체는 연산이 안되거나 하는 문제가 발생할 수 있지 않나? 거기에 뭐 이진탐색 같은 걸 활용한다는 거 같기도 하고 여튼 모르겠다.

누구 좀 잘 가르쳐 줄 사람 없을까?