게임 동기화 모델의 고민 흔적들 :: 게임제작[SSISO Community]

동기화 모델을 구현하기에 앞서 이런저런 고민 했던 것인데, 도움이 될까 하고 정리해 본다.

기본 정의

게임 오브젝트는 게임 세계에 존재하는 모든 것으로 보면 된다.

상태란 게임 세계에서 발생하는 이동, 공격등의 명령으로 게임 오브젝트의 속성 변화를 나타냄.

동기화란 Peer간에는 네트워크 지연, 하드웨어의 스펙 차이로인해 시간 차이가 발생하는데 이 시간차를 줄이는 방법이다.

대표적인 동기화 모델

스타크래프트가 이에 해당하며, 클라이언트 중 가장 느린 클라이언트에 시간이 맞춰진다.

또한, 느린 클라이언트에 맞춰지니 모두가 느려져 사용자들에게 짜증을 줄 수 있다.

LOL이 이에 해당하며, 클라이언트가 느리면 느린만큼 손해를 갖는 구조이고,

또한, 타 클라이언트가 느려진다고 모두가 느려지진 않지만, 서버가 느려지면 모두가 느려진다.

마지막으로 클라이언트가 먼저 계산하고, 서버와 오차를 보정해 나가며 동기화를 맞춘다.

FPS와 디아블로가 이에 해당하며, 빠른 반응성이 필요할 때 사용한다.

첫 번째 방법이었던 클라이언트끼리의 동기화는 나름 단순하다. 일명 Lock step으로 구현하면 된다.

여기서는 서버와 동기화를 맞추는 모델에 대해서 생각해 보겠다.

도표에서 사용한 용어 정의

고려할 갖 가지 상황

서버의 상태정보와 피어의 명령 전달은 ping 시간 만큼 걸린다.

서버 허락을 받아야 하는 구조.

P1의 S.T1 시점에 좌표 2,0으로 이동명령을 내리고 서버의 허락을 기다린다.

S의 S.T3에 P1의 명령이 도착하여 허락을 받게된 후, P1의 이동을 시작한다.

동시에 P2의 S.T1 시점에 P1 위치 0,0을 보고 창을 던지는 명령을 내리고 서버의 허락을 기다린다.

S의 S.T5에 P2의 명령이 도착하여 허락을 받게된 후, P2역시 창을 던지기 시작한다.

이 구조는 각 peer간에 처리되는 내용은 동일하지만, 과거 상태를 보며 행동하기 때문에. 느린 만큼 손해를 본다.

P1의 ping이 빠르기 때문에, P2보다는 기민하게 움직일 수 있다.

이에 비해 P2는 둔하기 때문에, P1을 창으로 맞추기가 어려워진다.

손해를 줄이기 위해 어느 정도의 과거까지 게임 진행에 무리가 없을지

서버 허락없이 클라이언트에서 명령을 먼저 처리하고 오차를 보간하는 구조

P1의 S.T1 시점에 좌표 2,0으로 이동명령을 내리고 서버 허락없이 이동하기 시작한다.

S의 S.T3에 P1 명령이 도착할 때에는 지연시간을 고려해 보간한다.

P2의 S.T1 시점에 P1 위치 0,0을 보고 창을 던지는 명령을 내리고 서버 허락없이 창을 던지기 시작한다.

S의 S.T5에 처리될 때에는 지연시간을 고려해 P1위치를 이전 시간으로 돌려 히트 판정을 시도한다.

P2 입장에서는 자연스럽겠지만, P1 입장에서는 갑자기 피격되는 상황이 벌어진다.

이 구조는 지연시간에 따른 시간 되돌기기가 사용되는데, 어느 정도까지 되돌릴 것인지 정한다.

서버에서 보내주는 정보가 일정하지 않거나 유실

P1의 S.T1 시점에 좌표 2,0으로 이동명령을 내리고, 다시 S.T2시점에 좌표 1,0으로 이동명령을 보냈다.

하지만, 두 번째 명령이 늦거나 유실되었다면, P1는 좌표 2,0까지 이동시켜야 한다.

이렇게 뒤 늦게 온 정보를 보간을 해야 하며, 이동시켜야 할 거리가 길다면, 워프시켜야 하겠지.

클라가 서버시간을 알아야 캐릭터 상태를 보간을 할 수 있는데, 서버시간 동기화가 필요하다. 하지만 ping이 고르지 않은 상황에서 서버시간 동기화를 어떻게 할까나.

클라이언트는 서버로 부터 받은 서버시간을 자체적으로 흘러가게 한다

또한, 서버시간 동기화 메시지를 받을 때마 클라이언트의 서버시간과 서버의 서버시간을 비교해 본다.

ping이 고정이면, 클라 자체적으로 흘려보낸 서버시간과 동일하며, ping만큼 서버 상태보다 과거를 본다.

ping이 길어지면, 클라의 서버시간이 더 빠르다.

아래 그림은 ping이 점점 길어져, 클라의 서버시간과 서버에서 받은 서버시간과 오차가 생기는 도표이다.

ping이 짧아지면, 클라의 서버시간이 더 느리다.

초반에는 네트워크 부하가 있었던지 느렸다가, 네트워크 상태가 원활하게 변경되어 빨라진 경우다.

서버의 상태 데이터와 오차가 줄면 좋은 것이니 클라의 서버시간을 당겨 주면 좋겠지.

아래 그림은 ping이 빨라지면서, 클라의 서버시간보다 받은 서버시간이 더 빨라지는 도표이다.

ping이 들쑥날쑥,

클라의 서버시간을 당기거나 늦춘다면, 천천히 부드럽게 하는게 좋지 않을까

일시적인거라면, 재빠르게 서버시간을 조정해도 부담이 없겠지만,

동기화를 구현한 예제

Array.prototype.clear = function() {
  while (this.length > 0) {
    this.pop();
  }
};

function clamp(value, min, max) {
    return Math.min(Math.max(value, min), max);
};

var http = require('http');
var WebSocketServer = require('websocket').server;

var port = process.env.port || 1337;
var httpServer = http.createServer(function (req, res) {
    res.writeHead(200, { 'Content-Type': 'text/plain' });
    res.end('Hello World\n');
});
httpServer.listen(port);

var wsServer = new WebSocketServer({
    httpServer: httpServer,
    // You should not use autoAcceptConnections for production
    // applications, as it defeats all standard cross-origin protection
    // facilities built into the protocol and the browser.  You should
    // *always* verify the connection's origin and decide whether or not
    // to accept it.
    autoAcceptConnections: false
});

const SERVER_TICK = 100;

const PID_LOGIN = 1;
const PID_ENTER_ANYONE = 2;
const PID_MOVEMENT = 3;
const PID_SYNC_SERVER_TIME = 4;
const PID_LEAVE_ANYONE = 5;
const PID_SHOOT_BULLET = 6;
const PID_HIT_ANYONE = 7;
const PID_DELETE_BULLET = 8;
const PID_REVIVE_CHARACTER = 9;

var CharacterState = function(){
return {
    'NOMAL':0,
    'DEATH':1    
    }
}();

var PF = require('pathfinding');
 var matrix = [
    [0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0],
];
 
var grid = new PF.Grid(5, 5, matrix);

var finder = new PF.AStarFinder();
 
function originIsAllowed(origin) {
  // put logic here to detect whether the specified origin is allowed.
  return true;
}

function broadcast(message, skipConn)
{
    wsServer.connections.forEach(function (conn) {
                if (skipConn == conn)
                    return

                conn.send(message);
            });
}

function lineDistance( point1, point2 )
{
  var xs = 0;
  var ys = 0;

  xs = point2.x - point1.x;
  xs = xs * xs;

  ys = point2.y - point1.y;
  ys = ys * ys;

  return Math.sqrt( xs + ys );
}

function setMovementGoalAtPoint(elem, start, goal)
{    
    elem.movement.limitTime = parseInt(lineDistance(start, goal)/elem.speed);
    elem.movement.sx = start.x;
    elem.movement.sy = start.y;
    elem.movement.ex = goal.x;
    elem.movement.ey = goal.y;
    elem.movement.elapsedTime = 0;
    elem.movement.startTime = globalMgr.elapsedTime;
}

function setMovementGoalWithPathFind(elem, x, y)
{    
    const TILE_SIZE = 100;
    var start = { x: parseInt(elem.movement.cx/TILE_SIZE), y: parseInt(elem.movement.cy/TILE_SIZE) };
    var goal = { x:parseInt(x/TILE_SIZE), y:parseInt(y/TILE_SIZE)};    
    goal.x = clamp(goal.x, 0, grid.width-1);
    goal.y = clamp(goal.y, 0, grid.height-1);

    elem.pathfind.path = [];
    elem.pathfind.cpath = 0;
    setMovementGoalAtPoint(elem, {x:elem.movement.cx, y:elem.movement.cy}, {x:clamp(x, 0, (grid.width-1)*TILE_SIZE), y:clamp(y, 0, (grid.height-1)*TILE_SIZE)});

    var gridBackup = grid.clone();
    var path = finder.findPath(start.x, start.y, goal.x, goal.y, gridBackup);
    if (path.length < 2)
        return;
    path = PF.Util.smoothenPath(gridBackup, path);
    if (path.length < 2)
        return;

    for(var i = 0; i < path.length; ++i)
    {
        path[i][0] *= TILE_SIZE;
        path[i][1] *= TILE_SIZE;
    }

    elem.pathfind.path = path;
    elem.pathfind.cpath = 2;
    setMovementGoalAtPoint(elem, {x:elem.movement.cx, y:elem.movement.cy}, {x:path[1][0], y:path[1][1]});
    return;
    
}

function setMovementGoalAsDirection(elem, x, y, length)
{
    var p1 = { x: elem.movement.cx, y: elem.movement.cy };
    var p2 = { x:x, y:y};
    
    var radian = Math.atan2(p2.y - p1.y, p2.x - p1.x);
    setMovementGoalAtPoint(elem, p1, {x:Math.cos(radian)*length+p1.x, y:Math.sin(radian)*length+p1.y});
}

function lerp(start, end, percent) {
    return start + ((end - start) * percent);
}

function inCircle (c1, c2) {
    var p1x = c1.movement.cx;
    var p1y = c1.movement.cy;
    var r1 = c1.radius;
    var p2x = c2.movement.cx;
    var p2y = c2.movement.cy;
    var r2 = c2.radius;
    var a = r1 + r2;
    var x = p1x - p2x;
    var y = p1y - p2y;
    
    if ( a > Math.sqrt( (x*x) + (y*y) ) ) {
        return true;
    }

    return false;
}

function move(elem, delta)
{           
    elem.movement.elapsedTime += delta;
    var timeLeft = elem.movement.limitTime-elem.movement.elapsedTime;
    
    if (timeLeft <= 0)    
    {
        elem.movement.cx = elem.movement.ex;
        elem.movement.cy = elem.movement.ey;
        elem.movement.elapsedTime = elem.movement.limitTime;
        return false;
    }
    
    var percentDone = 1 - timeLeft/elem.movement.limitTime;
    
    elem.movement.cx = lerp(elem.movement.sx, elem.movement.ex, percentDone) ;
    elem.movement.cy = lerp(elem.movement.sy, elem.movement.ey, percentDone) ;
    return true;
    
}



function GlobalMgr()
{
    this.updateTime = new Date().getTime();
    this.elapsedTime = 0;
    this.protocolHandler = [];
    this.inputQueue = [];
    this.userIDCounter = 0; 
    this.characters = [];
    this.connections = [];
    this.bullets = [];
    this.bulletIDCounter = 0;

    this.protocolHandler[PID_LOGIN] = onLoginReq;
    this.protocolHandler[PID_MOVEMENT] = onMovementReq;
    this.protocolHandler[PID_LEAVE_ANYONE] = onLeaveAnyoneReq;
    this.protocolHandler[PID_SHOOT_BULLET] = onShootBulletReq;
    this.protocolHandler[PID_DELETE_BULLET] = onDeleteBulletReq;
    this.protocolHandler[PID_REVIVE_CHARACTER] = onReviveCharacterReq;
}

var globalMgr = new GlobalMgr();


function updateState()
{
    var currentTime = new Date().getTime();
    var delta = currentTime-globalMgr.updateTime;
    globalMgr.elapsedTime += delta;

    var syncTimeProtocol = {id:PID_SYNC_SERVER_TIME, time:globalMgr.elapsedTime};
    broadcast(JSON.stringify(syncTimeProtocol), null); 
    
    var cloneInputQueue = globalMgr.inputQueue.slice(0);
    globalMgr.inputQueue.clear();    

    cloneInputQueue.forEach(function(e){
        var msg = e;
        var connection = e.connection;        
        
        globalMgr.protocolHandler[msg.id](connection, msg);
        
    });
    
    globalMgr.characters.forEach(function(elem){
        
        if (false == move(elem, delta))
        {
            if (elem.pathfind.cpath < elem.pathfind.path.length)
            {
                var start = {x:elem.movement.cx, y:elem.movement.cy};
                var goal = {x:elem.pathfind.path[elem.pathfind.cpath][0], y:elem.pathfind.path[elem.pathfind.cpath][1]};
                ++elem.pathfind.cpath;
                
                setMovementGoalAtPoint(elem, start, goal);
                sendUpdatePathMovement(elem);
            }
        }
    });

    globalMgr.bullets.forEach(function(elem){
        
        var movable = move(elem, delta);

        globalMgr.characters.forEach(function(character){
        
            if (elem.owner_id == character.id)
                return;

            if (true == inCircle(character, elem))
            {
                hitAnyone(character, elem);
            }
        
        });

        if (movable == false)
        {
            postDeleteBullet(elem.id);
        }
        
    });
    
    globalMgr.updateTime = currentTime;
    
}

setInterval(updateState, SERVER_TICK);

function createCharacter(connection)
{
    var id = ++globalMgr.userIDCounter;
    var myJSONObject = {
        movement:{cx:0, cy:0, sx:0, sy:0, ex:0, ey:0, limitTime:0, elapsedTime:0, startTime:globalMgr.elapsedTime},
                        hp:10,
                        speed:0.1,
                        radius:50,
                        state:CharacterState.NOMAL,
                        pathfind:{path:[], cpath:0},
                        id:id
                       };
    
    
    globalMgr.characters[id] = myJSONObject;
    globalMgr.connections[id] = connection;
    return myJSONObject;
}

function createBullet(owner)
{
    var id = ++globalMgr.bulletIDCounter;

    var myJSONObject = {
        movement:{cx:owner.movement.cx, cy:owner.movement.cy, sx:owner.movement.cx, sy:owner.movement.cy, ex:0, ey:0, limitTime:0, elapsedTime:0, startTime:globalMgr.elapsedTime},
                        dmg:1,
                        speed:0.3,
                        radius:5,
                        owner_id:owner.id,
                        id:id
                       };
    
    
    globalMgr.bullets[id] = myJSONObject;
    
    return myJSONObject;
}

function postDeleteBullet(id)
{
    postProtocolToInputQueue({id:PID_DELETE_BULLET, bullet_id:id});
}

function postProtocolToInputQueue(protocol, delay)
{
    if (delay == 0)
    {
        globalMgr.inputQueue.push(protocol);
    }
    else
    {
        setTimeout(function(){
            globalMgr.inputQueue.push(protocol);
        }, delay);
    }    
}

function hitAnyone(victim, bullet)
{
    victim.hp -= bullet.dmg;
    if (victim.hp <= 0)
    {
        if (victim.state != CharacterState.DEATH)
        {
            victim.state = CharacterState.DEATH;
            var revivePlace = {x:Math.floor((Math.random() * 300) + 1), y:Math.floor((Math.random() * 300) + 1)};
            postProtocolToInputQueue({id:PID_REVIVE_CHARACTER, characterID:victim.id, x:revivePlace.x, y:revivePlace.y, hp:10}, 5000);
        }
        victim.hp = 0;
    }

    var protocol = {id:PID_HIT_ANYONE, time:globalMgr.elapsedTime, victim:victim.id, bullet_id:bullet.id, dmg:bullet.dmg};
    broadcast(JSON.stringify(protocol), null);

    postDeleteBullet(bullet.id);
}

function onLoginReq(connection, msg)
{
    
    var newCharacter = createCharacter(connection);
    connection.userid = newCharacter.id;

    var loginProtocol = {id:PID_LOGIN, me:newCharacter, members:[], bullets:[]};

    var memberCount = 0;
    globalMgr.characters.forEach(function(e){
        if (globalMgr.userIDCounter == e.id)
            return;

        loginProtocol.members[memberCount] = e;
        memberCount++;
    });

    memberCount = 0;
    globalMgr.bullets.forEach(function(e){
        
        loginProtocol.bullets[memberCount] = e;
        memberCount++;
    });
    
    
    connection.send(JSON.stringify(loginProtocol));    

    var enterAnyoneProtocol = {id:PID_ENTER_ANYONE, anyone:newCharacter};
    broadcast(JSON.stringify(enterAnyoneProtocol), connection);
}

function onMovementReq(connection, msg)
{
    var character = globalMgr.characters[connection.userid];
    if (character.hp == 0)
        return;

    character.pathfind.path = [];
    character.pathfind.cpath = 0;
    setMovementGoalWithPathFind(character, msg.goal.x, msg.goal.y);
    
    var movementProtocol = {id:PID_MOVEMENT, time:globalMgr.elapsedTime, cx:character.movement.cx, cy:character.movement.cy, limitTime:character.movement.limitTime, characterID:connection.userid, goal:{x:character.movement.ex, y:character.movement.ey}};
    broadcast(JSON.stringify(movementProtocol), null);
}

function sendUpdatePathMovement(character)
{    
    var movementProtocol = {id:PID_MOVEMENT, time:globalMgr.elapsedTime, cx:character.movement.cx, cy:character.movement.cy, limitTime:character.movement.limitTime, characterID:character.id, goal:{x:character.movement.ex, y:character.movement.ey}};
    broadcast(JSON.stringify(movementProtocol), null);
}

function onLeaveAnyoneReq(connection, msg)
{
    broadcast(JSON.stringify(msg), null);

    delete globalMgr.characters[msg.characterID];
    delete globalMgr.connections[msg.characterID];
}

function onShootBulletReq(connection, msg)
{
    var character = globalMgr.characters[connection.userid];
    if (character.hp == 0)
        return;

    var bullet = createBullet(character);
    
    setMovementGoalAsDirection(bullet, msg.goal.x, msg.goal.y, 300);

    var shootBulletProtocol = {id:PID_SHOOT_BULLET, bullet:bullet};
    
    broadcast(JSON.stringify(shootBulletProtocol), null);
}

function onDeleteBulletReq(connection, msg)
{
    delete globalMgr.bullets[msg.bullet_id];
}

function onReviveCharacterReq(connection, msg)
{
   var character = globalMgr.characters[msg.characterID];
   if (character == null)
       return;

   character.movement.cx = msg.x;
   character.movement.cy = msg.y;
   character.movement.sx = msg.x;
   character.movement.sy = msg.y;
   character.movement.ex = msg.x;
   character.movement.ey = msg.y;
   character.movement.elapsedTime = 0;
   character.movement.limitTime = 0;
   character.movement.starTime = globalMgr.elapsedTime;
   character.hp = msg.hp;
   character.state = CharacterState.NOMAL;

   broadcast(JSON.stringify({id:PID_REVIVE_CHARACTER, character:character}), null);
}

wsServer.on('request', function(request) {
    if (!originIsAllowed(request.origin)) {
      // Make sure we only accept requests from an allowed origin
      request.reject();
      console.log((new Date()) + ' Connection from origin ' + request.origin + ' rejected.');
      return;
    }
 
    var connection = request.accept('echo-protocol', request.origin);    
    var loginProtocol = {id:PID_LOGIN};
    loginProtocol.connection = connection;
    globalMgr.inputQueue.push(loginProtocol);
    
    console.log((new Date()) + ' Connection accepted.');
    connection.on('message', function(message) {
    	
        
        if (message.type === 'utf8') {
            console.log('Server Received Message: ' + message.utf8Data + ' len: ' + message.utf8Data.length);

            var protocol = JSON.parse(message.utf8Data);
            protocol.connection = connection;
            globalMgr.inputQueue.push(protocol);
            
            
        }
        else if (message.type === 'binary') {
            console.log('Server Received Binary Message of ' + message.binaryData.length + ' bytes');
            connection.sendBytes(message.binaryData);            
            
        }
    });

    connection.on('close', function(reasonCode, description) {
        console.log((new Date()) + ' Peer ' + connection.remoteAddress + ' disconnected.');
        var leaveProtocol = {id:PID_LEAVE_ANYONE, characterID:connection.userid};
        globalMgr.inputQueue.push(leaveProtocol);

        
    });
    
});

view raw movementsync.node.js hosted with ❤ by GitHub

테스트 해보기

서버 실행하기

웹소켓 모듈이 필요하므로, 없다면, 다음 명령을 콘솔에서 실행한다.

클라 실행하기

서버 실행 후, 클라코드 링크를 클릭해 웹브라우져에서 실행

이동 중, 두 번째 클라를 실행하여, 첫 번째 클라의 원의 위치가 동기화 되는지 확인