1. 저는 평범한 프로그래머이고 게임 프로그래밍을 하는 사람은 아닙니다만, 2D 게임을 만들어 보려고 생각 중입니다.
2. 대부분의 게임에서 가장 본질적이고 핵심적인 부분이라고 할 수 있는 '충돌체크'에 대한 질문을 하고자 합니다.
3. 프로그래밍언어나 게임프로그래밍에 대한 기초적인 지식은 가지고 있으니 적당히 설명해 주면 알아 들을 수 있습니다.
---
자, 우선 저는 일반적으로 2D 게임에서 쉽게 통용되는 '두 사각형 객체 간의 충돌체크'에 대해서는 무리 없이 알고 있습니다.
이 경우는 객체 간의 관계가 '일대일'인 경우이고, 다음으로 생각해 봐야 하는 상황은 객체 간의 관계가 '일대다'인 경우입니다.
즉, 대부분의 슈팅 게임이 가진, '플레이어가 조종하는 '하나'의 캐릭터와 '다수'의 적들의 관계' 정도를 생각하시면 됩니다.
다시 말해 내 캐릭터와 적들 간의 충돌체크는 필요하지만, 적들 서로 간의 충돌체크는 필요하지 않은 그런 상황을 말하는 것입니다.
이런 경우에는 그냥 상대 객체의 수만큼(적의 수만큼) 체크를 반복하면 될거라 생각합니다. 상대 객체가 좀 많아도 그렇게까지
연산 횟수가 많이 늘어나지 않아 (상대 객체가 100이면 100번만 하면 되니까) 이렇게 해도 사실 큰 무리가 없어 보입니다.
---
문제는 객체 간의 관계가 '다대다'일 때입니다. 다시 말해, "적군과 아군이 30대 30으로 전투를 벌이는 게임"에서는 아군과 적군
사이의 충돌체크 뿐만 아니라, 아군과 아군 사이에서도 충돌체크가 필요합니다. (겹치면 안되니까) 다시 말해 화면 내에 있는
모든 객체들이 서로에 대한 충돌체크가 필요한 것입니다. 이런 경우에 위와 같은 방법을 적용하면 생각보다 많은 연산횟수가
필요하게 됩니다. 중복된 체크를 피하더라도 객체의 수 n에 따라 nC2라는 횟수로 증가하게 되는데, 제가 실제로 구현해보지
않은 상태라 이게 어느정도의 부하를 가져 올 지는 모르겠지만, 누가 생각해 봐도 결코 좋은 방법은 아닙니다.
---
그렇다면 결론적으로 "다수의 객체들이 실시간으로 자신을 제외한 모든 객체와 충돌체크를 할 수 있는 효율적인 알고리즘 혹은 그 방법"
이 있다면 어떤 방법이 있을까요? 그리고 일반적인 2D 게임들은 어떤 방법을 이용하는지 궁금합니다. 물론 이 부분은 2D 3D를 막론하고
공통된 사항이지만 말입니다.
---
아마 게임 프로그래밍을 전공으로 하는 학생이나, 게임업체에서 현역으로 활동하고 있는 프로그래머 분이라면 너무도 쉬운 부분이 아닐까 합니다.
아시는 분이 계신다면 간단하게나마 설명을 해주신다면 큰 도움이 되리라 생각합니다.
충돌 검사는, 각 객체가 이동할 때 충돌체크를 하면 될 것 같습니다.
객체 이동 -> 이동할 좌표에 아무런 객체가 없으면 이동한다.
-> 만일 객체가 존재하면 -> 적인가? -- Yes ---> 데미지를 입는다.
-- No ---> 서로 자리를 바꾼다.
3D의 경우는 너무 경우가 복잡하다고 들었습니다. 부하도 많이 걸려서 효율적이면 겹치는 것도 허용한다고 하네요.
하지만 뭐 2D는 for문을 돌려도 어느정도는 커버가 되니깐요.
알고리즘 측면에서는 충돌된 횟수만큼 for문을 돌리는 것이 최선이죠.
근데 그 충돌된 횟수를 알려면 위치적으로 부딪혔다는 단서가 필요합니다.
다대다 전투에서 그 단서를 알려면 무작정 for문 돌리기에는 부담스럽긴 합니다.
그래서 아군 객체를 전체로 아우르는 영역을 하나 만듭니다. 이것을 아군 박스라고 말한다면...
적군 박스와 아군 박스가 부딪히는지 아닌지부터 확인합니다.
if( 아군박스와 적군박스의 충돌 == true)
{
아군박스의 어느 부분이 충돌이 났는가?
}
그래서 부딪히면, 아군 박스의 동 서 남 북 혹은 1사분면, 2사분면, 3사분면, 4사분면에 충돌이 일어났는지 확인합니다.
if ( 1사분면 == 충돌 )
{
1사분면 영역에 속하는 아군이 충돌났는지 조사한다.
충돌난 아군에게 flag == 충돌을 부여한다.
}
if ( 2사분면 == 충돌)
{
2사분면 영역에 속하는 아군이 충돌났는지 조사한다.
충돌난 아군에게 flag == 충돌을 부여한다.
}
이런식으로 나누고 정복하는 알고리즘으로 하면 괜찮을 것 같습니다.
더 좋은 방법이 있으면 저도 그 방법을 사용하고 싶습니다.
게임의 성향에 따라 틀리지만 x나 y중 한쪽만 먼저 확인후 범위안에있을시 나머지 한쪽을 검사하는식으로하면 그나마 부하를 줄일수있습니다
충돌은 물리의 영역에 속하는 데 "충돌체크"라는 용어를 쓰시는 분들은 "충돌 검출/판정/반응"이라는 개념을 보시게 되면서 물리엔진(2D건 3D건)으로 넘어가시게 되더군요.
사실 1980년대 게임 부터 물리영역은 존재했습니다. (마리오(8비트 컴퓨터 게임)가 땅을 밟고 점프하는 것도 충돌 검출/판정/반응 )이 일어나는 것이지요.
참고로 물리처리에서 충돌 검출할 객체를 공간 영역별로 나누는 알고리듬을 broad phase algorithm 이라고 하고
실제 충돌이 일어나는 객체간의 처리를 하는 알고리듬을 narrow phase algorithm이라고 합니다.
broad phase algorithm 으로 쓸 수 있는 알고리듬에는 quadtree/AABB/KDTree/BSP 등이 있고 이것은 충돌 검출 연산횟수를 획기적으로 줄이는 역할 을 합니다.
narrow phase algorithm 으로 쓸 수 있는 알고리듬에는 SAT, GJK, EPA, Chung Wang Axis Separation Algorithm 등이 있습니다. '두 사각형 객체 간의 충돌체크'에 대해서는 무리 없이 알고 게시다면 SAT같은 건 찾아보셨겠죠?
처음에 게임을 전공하는 학생 같으면 알지 않겠냐고 하셨는 데 국내 대학에서 이런 알고리즘(특히 narrow phase)을 가르치는 지는 잘 알려져 있지 않습니다.
워낙 교수 개개인의 연구분야에 좌우되는 지라 저런 것을 연구하는 교수님이 특정학교에 계신지는 직접 탐문조사하지 않으면 알길이 없을 겁니다.
이름만 대면 알만한 명문대학에도 안계실 수도 있고 커트라인이 낮은 학교에도 계실 수도 있는 것이죠.
다들 답변 감사합니다.
flag나 slot을 이용한 방식은 게임의 성향상 부적합할 거 같습니다만, 아군박스와 적군박스를 나눠서 처리하는 부분은 도움이 될 수도 있을거 같습니다.
그리고 충돌체크에 대한 다양한 알고리즘에 대해 말씀해 주셔서 찾아봤는데 확실히 많이 도움이 될 거 같네요. 다만 단순한 2D게임에 필요 이상으로
고차원적인 부분도 있는 거 같아서 적당히 절충안을 보는 것이 좋을 거 같습니다.
무엇보다 그냥 box2d 같은 좋은 엔진이 있네요... 그냥 이걸 이용하는 편이 가장 좋은 방책이 될거 같습니다. 다들 감사합니다. 좀더 공부해 봐야겠네요.
http://www.lameproof.com/index.php?listStyle=gallery&mid=neolith&page=2&document_srl=173210
여기에서 flag나 slot을 부여하는 방식으로 체크하는 방법을 추천하네요.
원하시는 것이 각 객체끼리 겹치지 않게 하는 것이라면 간단합니다.
맵을 슬롯화 시키는 거죠. 즉 창고에 있는 물건처럼 취급하면됩니다.
우리편 검사는 (0, 0)에 있습니다.
어 근데 우리편 궁수가 (0.0)에 오려고 합니다.
그런데 맵 슬롯은 딱 한개의 객체만 허용합니다.
그러면 궁수는 (0,0)에 들어오지 못하고 그자리에 멈춰섭니다.
퍼즐게임의 블록을 쌓는 느낌이면 되지 않을까 생각합니다.