데드 레커닝 - 온라인 게임의 이동처리 기법

현재 3D 온라인 게임 프로젝트에서 게임서버를 제작하면서 미처 예상하지 못한 부분에서 많은 문제들이 있다 그 중 캐릭터의 이동처리 부분이고 해결해 나가면서 큰 도움이 되고 있다. 
사용자가 키보드를 이용한 방향키 입력으로 이동 패킷을 서버에 보내주고 그것을 서버에서는 브로드캐스트로 뿌려주는
가장 기본적이고 간단한 방법이 있지만 60프레임으로 돌아가는 게임이라고 한다면 1초에 60번이나 이동에 대한 패킷을 보내고 받게 됨으로 엄청난 서버 부하를 가져오게 된다.

이를 해결하기 위해선 기존 상태를 계속 유지하고 있다면 일정한 규칙을 가진 행동을 반복하고 있을테니 패킷을 보내지 않고 같은 처리를 계속 하도록 하고, 상태의 변화가 있을때만 패킷을 보내서 상태변화를 알리게 되면 서버는 이를 브로드캐스트하여 다른 클라이언트들도 해당 유저의 상태를 갱신해줌으로써 송수신 횟수를 엄청나게 줄일수 있게 된다.
예를들어 오른쪽 방향키를 입력하여 캐릭터를 이동시키고 있다고 가정하자. 일정한 이동속도로 캐릭터를 계속 이동시키면서 이를 1초에 60번씩 계속 서버에 알리고 서버는 이를 똑같이 1초에 60번씩 브로드캐스트 하게 된다. 이동 정지에 대한 패킷은 따로 없고 패킷이 가지 않는다면 그게 바로 정지한것이 될 것이다.

다른 방법으로는 오른쪽 방향키를 처음 입력하여 캐릭터를 이동시키기 시작했을때만 패킷을 보내는거다. 서버는 이를 브로드캐스트 하여 해당 유저가 이동을 시작하였다고 알리면 각 클라이언트는 자체적으로 정해진 이동속도로 캐릭터를 이동시키며 1초에 60번씩 화면을 갱신한다. 해당 유저가 방향키에서 손을 떼어서 키가 올라갔다면 캐릭터 이동 정지 패킷을 보내고 서버는 이를 브로드캐스트하여 해당 유저가 정지했다고 알린다. 그러면 또 각 클라이언트는 계산을 멈추고 해당 유저를 정지시킬거다.

위의 두가지 방법을 비교하자면 첫번째 방법은 10초동안 이동하는 클라이언트가 서버로 600번 이동패킷을 보내고 서버는 접속해있는 10명에게 600번씩 전송하여 합 6000번 패킷을 전송하고 서버는 총 6600번의 송수신을 하게 된다.
두번째 방법은 이동하는 클라이언트가 이동 시작시 서버로 이동시작 패킷을 보내고 서버는 접속해있는 10명에게 한번씩 이동 시작 패킷을 보내게 되고 서버는 총 11번의 송수신을 하게 된다.
두가지 방법은 6589번의 송수신 횟수가 차이 난다.

데드레커닝이란 계속하여 패킷을 받아 위치를 갱신하여야 되지만 처음 한번만 이동정보를 받아서 패킷이 오지 않는 동안에는 처음에 받은 이동정보를 이용하여 다음 위치를 추측하여 이동시키는 것이다. 여기서 상태 변화가 올때만 패킷을 다시 보내냐 아니면 일정 주기마다 패킷을 다시 보내냐 일정주기마다 보내는 것이면 10프레임마다 보내냐 아니면 1초마다 보내냐 이런것들은 정답이 없기 때문에 각자의 서버 상태나 혹은 게임 종류에 따라서 자기에게 알맞게 정하면 된다.

단점으론 여러가지 부가적으로 처리해줘야 하는 부분들이 있다. 송수신에 있어서는 지연 시간이 발생할 수 밖에 없다. 이동을 요청한 유저가 보낸 패킷이 서버에 도착하기까지 걸리는 시간과 서버가 다른 유저에게 다시 뿌려주는데 걸리는 시간, 그리고 다른 유저가 그 패킷을 받아서 처리하기까지의 지연시간이 있다. 그 지연시간동안 클라이언트는 기존 계산되던 방식으로 계속 해당 유저의 위치나 상태를 갱신시키고 있기 때문에 도착한 정보와의 오차가 발생하고 이 오차만큼 캐릭터가 워프되거나 하는 문제가 생긴다. 눈으로 확실히 식별되지 않을정도의 작은 오차라면 큰 문제가 되지 않을거다. 
다들 한번씩 온라인게임을 하면서 경험했을거다. 잘 걸어가던 캐릭터가 갑자기 뒤로 확 와지거나 일자로 걸어가다 다른방향으로 방향을 확 틀었는데 순식간에 위치가 워프되듯이 건너뛰거나 하는등 지연시간이 길어질수록 오차값이 커지게 되고 이런 문제들이 생기게 된다. 이런 경우 최대한 어색하지 않고 자연스럽게 새로운 방향으로 이동시켜야 유저들의 불만이 없을거다. 어떻게하면 자연스럽게 이동할수 있을까 하는 방법이 필요하다. 지연시간을 없앨수 있는 방법은 절대 없다. 그러니 오차가 있어도 이것을 어떻게 극복하여 유저들의 눈을 속여서 자연스럽게 이동하게 할수있나 심각하게 고려햐여야 한다.

보간 처리란?

게임에서 보간 처리(interpolation)는 주로 네트워크 지연을 해결하거나 더 매끄러운 애니메이션을 구현하기 위해 사용된다. 데드 레커닝 알고리즘을 사용하면 서버는 클라이언트가 보내는 이동 정보를 기반으로 각 플레이어의 미래의 위치를 예측하지만 클라이언트의 변경된 행동을 서버가 인지하는데 무조건 지연 시간이 발생하므로 완벽하지 않기 때문에 예측치와 실제 위치 사이의 차이를 처리해야 하는데 이 때 사용되는 것이 보간 처리다.

예를 들어, 서버는 플레이어 A가 현재 위치에서 일정한 방향과 속도로 움직일 것으로 예측할 수 있다. 그런데 예측과 실제 움직임 사이에 차이가 발생하면 사용자에게 최대한 자연스럽게 보일 수 있도록 보정하게 된다. 이 보정 과정이 바로 보간 처리다.

보간 처리의 종류

선형 보간

가장 간단한 형태의 보간 처리는 선형 보간(linear interpolation, 또는 lerp)이다. 선형 보간은 두 점 사이의 어떤 중간 점을 계산하는 방법으로 각 축에 대한 비율을 사용한다. 만약 두 점 A와 B 사이에서 중간 점을 찾으려면 다음과 같이 계산할 수 있다:

P = A + (B - A) * t

여기서 t는 0과 1 사이의 값으로, A와 B 사이의 비율을 나타낸다. t가 0이면 A를, 1이면 B를 반환한다. t가 0.5이면 A와 B 사이의 정중앙 지점을 반환한다. 이러한 선형 보간은 간단하고 효율적이지만, 속도 변화나 방향 변화 등이 자연스럽지 않을 수 있다.

고차 보간법?

선형 보간으로 처리하였을 때의 결과가 아쉽다면, 스플라인 보간(spline interpolation)이나 베지어 곡선(Bezier curve)과 같은 고급 보간 기법을 사용할 수 있다. 이러한 기법은 선형 보간에 비해 움직임이 더 부드럽고 자연스럽게 보이도록 해주는 대신 두 가지 방법 모두 계산 비용도 더 많이 든다는 단점이 있다.

베지어 곡선은 정의된 제어점의 수에 따라 차수가 결정된다. 제어점이 적으면(예: 2차 또는 3차 베지어 곡선), 계산 비용은 상대적으로 낮을 수 있다. 그러나 제어점이 많아질수록(즉, 차수가 높아질수록) 계산 비용은 급격히 증가하게 된다.

반면 스플라인 보간의 계산 비용은 사용하는 스플라인의 유형에 따라 다르다. 예를 들어 3차 스플라인 보간은 각 구간에 대해 3차 다항식을 계산해야 하므로 보간하려는 점의 수가 많을수록 계산 비용이 높아진다.

보간 처리를 어떻게 적용하지?

보간 처리를 통해 구한 값을 게임 캐릭터의 움직임에 적용하는 방법은 클라이언트 측에서 보간을 수행하는 방법과 서버 측에서 보간을 수행하는 방법이 있다.

1. 클라이언트 측에서 보간을 수행하는 경우

클라이언트 측에서 보간을 수행하는 경우 서버는 단순히 게임 상태의 업데이트를 주기적으로 클라이언트에게 보내고 클라이언트는 이 업데이트를 기반으로 보간을 수행하여 캐릭터의 위치를 계산한다. 예를 들어 선형 보간의 경우, 클라이언트는 두 시점 사이의 캐릭터 위치를 보간하여 캐릭터의 현재 위치를 결정한다.

2. 서버 측에서 보간을 수행하는 경우

서버 측에서 보간을 수행하는 경우 서버는 클라이언트의 입력을 받아 게임 상태를 업데이트 하고, 이 업데이트된 게임 상태를 보간하여 캐릭터의 위치를 결정한 다음 서버는 이 보간된 캐릭터 위치를 클라이언트에게 보낸다. 클라이언트는 이 위치 정보를 사용하여 캐릭터를 그린다.

보간을 수행하는 위치(클라이언트 또는 서버)는 여러 요인에 따라 달라진다. 예를 들어 네트워크 대기 시간이 긴 경우 클라이언트 측에서 보간을 수행하는 것이 더 효과적일 수 있다. 그러나 이 경우 클라이언트 간의 동기화가 문제가 될 수 있는 반면에 네트워크 대기 시간이 짧고 서버의 처리 능력이 충분한 경우 서버 측에서 보간을 수행하는 것이 더 효과적일 수 있습지만 이 경우 서버의 부하가 증가할 수 있다.

일반적으로 실시간 온라인 게임에서는 클라이언트 측에서 보간을 수행한다, 이 방법은 네트워크 대기 시간의 영향을 최소화하고 클라이언트의 프레임레이트를 최대한 유지할 수 있다.

 

출처 : https://cocoa106.tistory.com/entry/%EC%98%A8%EB%9D%BC%EC%9D%B8-%EA%B2%8C%EC%9E%84%EC%9D%98-%EC%9D%B4%EB%8F%99%EC%B2%98%EB%A6%AC-%EA%B8%B0%EB%B2%95-%EB%8D%B0%EB%93%9C-%EB%A0%88%EC%BB%A4%EB%8B%9D