어소트락게임아카데미안녕하세요. 어소트락 게임아카데미 입니다.
오늘은 게임내에서 꼭 필요한 충돌처리에 대한 내용에 대해서 글을 적어보려 합니다.
리그 오브 레전드, 오버워치 등 모든 게임에선 충돌처리를 해서 어떤 물체와 물체 사이에 부딪혔는지를 판단할 수 있는 기능을 만듭니다.
몬스터를 때리거나 부딪히거나 하는 등에 사용할 수 있는 것이죠.
이런 충돌처리는 다양한 기법이 있습니다. 구를 이용하는 방법, 상자를 이용하는 방법, 선을 이용하는 방법, 픽셀을 이용하는 방법 등 굉장히 많은 충돌처리 기법들이 있습니다.
오늘은 이런 충돌처리 기법을 언급하는 것이 아닌 물체들간에 충돌이 되었는지를 비교해볼 수 있는 로직 자체에 대한 내용에 대해서 얘기해보겠습니다.
간단한 예로 리그 오브 레전드를 예로 들어보겠습니다. 리그 오브 레전드라는 게임에는 플레이어 10명이 존재합니다. 10명은 각각 1개의 챔피언을 컨트롤 하는거죠. 그럼 이때 10개의 챔피언에 대한 충돌체가 필요할 것입니다.
그리고 미니언이라는 것이 있습니다. 일정 간격으로 6마리가 생기다가 특정 순간에 1마리가 더 추가되어 7마리가 생성되어 3개의 공격로를 갑니다. 그럼 1분에 6마리라고 하고 6마리 * 공격로3개 = 18마리의 미니언이 생성되게 됩니다.
이것만 해도 28개의 충돌체가 필요하죠. 그런데 정글에도 몬스터들이 존재합니다. 블루, 레드 모두 정글몬스터가 생기게 되기 때문에 여기에도 충돌체들이 생기게 될 것입니다. 이처럼 많은 충돌체들이 생성되면 이 충돌체들끼리 서로간에 충돌처리를 해주는 로직이 필요할 것입니다.
위의 그림을 보시면 저렇게 화면에 돌아다니는 모든 물체에 충돌체가 필요한 것입니다. 그것 뿐만 아니라 UI들도 충돌체들이 필요한 UI들도 있습니다.
이처럼 많은 충돌체를 어떻게 하면 효과적으로 적은 시간 내에 서로간에 충돌이 되었는지를 확인할 수 있는것이 핵심인데요.
일반적으로는 단순하게 충돌체가 100개가 있다면 첫번째와 2 ~ 100번째 충돌체를 모두 체크하고 두번째와 3 ~ 100번째 충돌체 .......... 99번째와 100번째 충돌체를 체크하는 방식으로 모두 체크를 하는 방법으로 활용을 하고 있을 것입니다.
하지만 이 경우 충돌체가 많아지면 많아질수록 그만큼 비교하는 횟수가 많아지게 되어 점점 느려지게 될 것입니다.
그렇다면 이런 충돌처리를 어떻게 하면 효과적으로 적은 횟수만으로 전체를 비교할 수 있는지를 알아보도록 해보겠습니다.
저희 어소트락 게임아카데미에서 사용하는 방법은 공간을 분할하는 방법입니다.
2D 게임, 3D 게임 상관 없이 전체 월드를 하나의 커다란 공간으로 보고 그 공간을 원하는 크기로 미리 분할을 해두는 것입니다.
2D게임이라면 단순히 평면 형태로 공간이 분할될 것이고 3D 게임이라면 육면체 형태로 분할될 것입니다.
위의 그림은 2D공간을 분할한것과 3D 공간을 분할한 것입니다. 분할된 공간은 다양한 충돌체들이 존재할 수 있게 되는 것이죠. 그럼 여기에서 하나의 의문을 가져볼 필요가 있습니다.
서로 다른 공간에 포함된 충돌체들이 충돌처리를 할 필요가 있는지 입니다.
답은 아니오 입니다. 서로 다른 공간에 있는 충돌체들은 서로 충돌할 필요가 없는것이죠.
100개의 충돌체가 존재한다면 물론 100개 모두 같은 공간에 포함되는 경우가 있을 수도 있을 것입니다.
이 경우라면 물론 99번, 98번, ...... 1번 까지 모두 더한 횟수가 나오게 되겠죠.
시간복잡도로 표현하자면 최악의 경우 100의 제곱이 나올 수 있습니다.
그런데 각각 다른 공간에 골고루 분포되어 있다고 가정을 할 경우 공간이 10개가 분할되어 있고 100개의 충돌체가 10개의 공간에 분포되어 있다고 가정할 경우 10개씩 10개의 공간이 존재하므로 한 공간에 9번, 8번, ..... 1번 시간복잡도로 표현하면 10의 제곱 * 10이 될것입니다.
100의 제곱은 10000입니다. 10의 제곰은 100이고 100 * 10을 하게 될 경우 1000이 나오게 됩니다.
즉, 10000번을 비교하는것과 1000번을 비교하는 것이 차이가 되는 것이죠.
물론, 이것은 최상의 경우 이렇게 될 것이며 편차는 존재할 것입니다.
하지만, 단순히 무조건 다 충돌처리를 할 경우 많은 충돌체에 대해서는 처리가 어려워지게 되므로 한꺼번에 모두 처리하는 것보다는 훨씬 좋은 성능을 보여줄 것입니다.
이렇게 공간분할을 이용할 경우 좀더 효율적으로 충돌처리 횟수를 줄여줄 수 있게 될 것입니다.
물론 여기에 다른 최적화 기법들이 더 포함되어 처리가 된다면 더 빠른 속도로 충돌처리를 할 수 있게 되겠죠.
충돌처리 최적화 공간분할에 대해서 알아봤습니다.