일반적으로 대상과 총알의 개수는 한정되어 있고 부딪히거나 말거나의 두가지 선택밖에 없기때문에,
이 경우 비교 작업은 복잡도가 그다지 높지 않으므로
특별히 신경쓰지 않으셔도 될겁니다.
대충 주저리 해보면..
적기가 20기 떠있고, 아군이 화면에 총알을 20발 뿌려도 400가지 경우지요.
아마도 사각형 두개가 충돌하는지를 검사하는데는 충돌 했을 경우(최악)에 4번 비교가 필요할거구요. 한 축으로 충돌 안했으면 아마도 2번... 아주 동떨어졌으면 1번도 가능하죠.
1000번 비교라고 대충 생각 했을 때... 비교는 빼서 return이니 ... 산술연산이구요... 어디 특별한 비용이 들 데가 없죠 ;
물론 최적화 시킬 방법이야 게임 특성에 맞추면 여러가지가 있을 수 있겠구요...
좌표에 따라 미리 정렬을 해놓고 처리하거나 하면 복잡도가 더 낮아지긴 하겠지만,
어쨌든 정렬 자체의 비용도 있으니 노력에 비해 별로 도움은 안될 듯 합니다.
뭐.. 충돌검사가 완전 사각형이고, 1대 다수의 상황이라면,
다수의 사각형의 꼭지점만으로 정렬해서 비교하는 방법도 있겠네요.
그래봤자 역시 비용은 비슷할 듯 하지만요 ;
복잡도는 n^3 정도 되지 않는다면
n이 100개 미만인 지금같은 경우에는 그냥 무시하셔도 될 정도이지요.
혹시 좋은 아이디어 가진 분들이 계실지도 모르겠습니다만...
-------------------------
The universe is run by the complex interweaving of three elements: matter, energy, and enlightened self-interest.
- G'kar, Babylon 5
저는 게임과는 거리가 멀다보니 게임을 만드시는 분들이 보통 어떤 방법을 채택하시는 지는 잘 모르겠지만, 그냥 문득 떠오르는 생각이 있어서...
총알이 진행하는 path를 초기치 (x1,y1)과 시간 t에 대해 특정한 방정식으로 모델링할 것이라는 가정하에서, 어차피 총알의 위치는 시간 t 에 대해 미리 계산이 가능하고, 비행기가 특정한 시간 t에 총알의 위치와 같은지 아닌지를 판별하기만 하면 될테니, 총알이 발사되는 순간에 미리 총알이 진행할 수 있는 위치를 (x,y,t)의 3차원 플레인에 미리 계산해두고 시간 t에서 비행기의 위치에 따라 한번 체크해보는 것은 어떨까요.
어차피 알고리즘은 time complexity와 space efficiency의 trade off같은 것이니 계산을 하는 대신 메모리를 써도 좋겠다는 단순한 생각입니다. :-)
총알의 숫자가 적다면 무식하게 그냥 돌려도 충분하겠죠. :) 근데, 많다면 어느 정도 구분을 해 두어야 합니다.
가장 간단한 방법으로는 일정한 영역으로 나누고, 총알 및 적기(개체라고 부르겠습니다.)의 위치를 영역별로 구분한 목록을 만들어 둡니다. ( 움직임에 따라, 영역 구분을 갱신해야 겠지요 ) 그리고나서, 충돌 판정할 때 같은 영역 및 인접 영역의 개체끼리만 검사하면 되겠지요 ?
음, 그리고 위에 분이 말씀하셨듯이 항상 정렬되어 있는 상태라면 복잡도는 매우 낮아집니다. 개체의 개수가 많아지면 정렬시키는 비용보다, 무식하게 개체의 충돌 판정을 하는 비용이 훨씬 더 비싸지게 됩니다. 이럴 때에는, 항상 정렬시켜 놓고 이분검색법 등으로 검색하는 것도 괜찮겠지요.
일반적으로 대상과 총알의 개수는 한정되어 있고 부딪히거나 말거나의 두가지
일반적으로 대상과 총알의 개수는 한정되어 있고 부딪히거나 말거나의 두가지 선택밖에 없기때문에,
이 경우 비교 작업은 복잡도가 그다지 높지 않으므로
특별히 신경쓰지 않으셔도 될겁니다.
대충 주저리 해보면..
적기가 20기 떠있고, 아군이 화면에 총알을 20발 뿌려도 400가지 경우지요.
아마도 사각형 두개가 충돌하는지를 검사하는데는 충돌 했을 경우(최악)에 4번 비교가 필요할거구요. 한 축으로 충돌 안했으면 아마도 2번... 아주 동떨어졌으면 1번도 가능하죠.
1000번 비교라고 대충 생각 했을 때... 비교는 빼서 return이니 ... 산술연산이구요... 어디 특별한 비용이 들 데가 없죠 ;
물론 최적화 시킬 방법이야 게임 특성에 맞추면 여러가지가 있을 수 있겠구요...
좌표에 따라 미리 정렬을 해놓고 처리하거나 하면 복잡도가 더 낮아지긴 하겠지만,
어쨌든 정렬 자체의 비용도 있으니 노력에 비해 별로 도움은 안될 듯 합니다.
뭐.. 충돌검사가 완전 사각형이고, 1대 다수의 상황이라면,
다수의 사각형의 꼭지점만으로 정렬해서 비교하는 방법도 있겠네요.
그래봤자 역시 비용은 비슷할 듯 하지만요 ;
복잡도는 n^3 정도 되지 않는다면
n이 100개 미만인 지금같은 경우에는 그냥 무시하셔도 될 정도이지요.
혹시 좋은 아이디어 가진 분들이 계실지도 모르겠습니다만...
-------------------------
The universe is run by the complex interweaving of three elements: matter, energy, and enlightened self-interest.
- G'kar, Babylon 5
저는 게임과는 거리가 멀다보니 게임을 만드시는 분들이 보통 어떤 방법을
저는 게임과는 거리가 멀다보니 게임을 만드시는 분들이 보통 어떤 방법을 채택하시는 지는 잘 모르겠지만, 그냥 문득 떠오르는 생각이 있어서...
총알이 진행하는 path를 초기치 (x1,y1)과 시간 t에 대해 특정한 방정식으로 모델링할 것이라는 가정하에서, 어차피 총알의 위치는 시간 t 에 대해 미리 계산이 가능하고, 비행기가 특정한 시간 t에 총알의 위치와 같은지 아닌지를 판별하기만 하면 될테니, 총알이 발사되는 순간에 미리 총알이 진행할 수 있는 위치를 (x,y,t)의 3차원 플레인에 미리 계산해두고 시간 t에서 비행기의 위치에 따라 한번 체크해보는 것은 어떨까요.
어차피 알고리즘은 time complexity와 space efficiency의 trade off같은 것이니 계산을 하는 대신 메모리를 써도 좋겠다는 단순한 생각입니다. :-)
실제로는 이런 경우를 어떻게 구현하는지 저도 참 궁금하군요.
제 생각엔 .. .. ..
총알의 숫자가 적다면 무식하게 그냥 돌려도 충분하겠죠. :) 근데, 많다면 어느 정도 구분을 해 두어야 합니다.
가장 간단한 방법으로는 일정한 영역으로 나누고, 총알 및 적기(개체라고 부르겠습니다.)의 위치를 영역별로 구분한 목록을 만들어 둡니다. ( 움직임에 따라, 영역 구분을 갱신해야 겠지요 ) 그리고나서, 충돌 판정할 때 같은 영역 및 인접 영역의 개체끼리만 검사하면 되겠지요 ?
음, 그리고 위에 분이 말씀하셨듯이 항상 정렬되어 있는 상태라면 복잡도는 매우 낮아집니다. 개체의 개수가 많아지면 정렬시키는 비용보다, 무식하게 개체의 충돌 판정을 하는 비용이 훨씬 더 비싸지게 됩니다. 이럴 때에는, 항상 정렬시켜 놓고 이분검색법 등으로 검색하는 것도 괜찮겠지요.
아니면 .. 트리구조를 활용해보는 것도 좋을 듯 합니다.
----
한 발자국, 한 발자국 - 언젠가는 도약하리라 ~
댓글 달기