SSISO Community

안드로이드 애니매이션1 (Animation) Porter / Duff Mode - 1 간단한 Custom View 작성 PorterDiff.Mode 사용해 모서리가 둥근 이미지 만들기 [Android, Canvas, Paint] 안드로이드 캔버스 기본 예제 게임 동기화 모델의 고민 흔적들 OpenGL ES Shader to outline 2D images 안드로이드 – OpenGL ES에서 숨겨진 선을 제거한 와이어 프레임 메시를 그리려면 어떻게해야합니까? 클라이언트/서버 통신 원리 자바에서 직렬화를 이용한 소켓 통신 정리

시소당

게임 동기화 모델의 고민 흔적들

출처 : https://yakolla.tistory.com/62

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

기본 정의

게임 오브젝트의 상태를 동기화시킨다.

말이 어려울 수도 쉬울수도 있지만, 살펴보자.

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

예) 캐릭터, 몹, 아이템 등

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

예) 이동이라면, x,y의 값이 변경

공격이라면, hp의 값이 변경

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

대표적인 동기화 모델

첫 번째는 클라이언트끼리 동기화를 맞춘다.

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

상태정보의 틀어짐은 없지만, 해킹에 취약하다.

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

구현이 상대적으로 단순하고 쉽다.

둘 째는, 서버와 동기화를 맞춘다.

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

상태정보의 틀어짐이 있어 예측과 보정을 해야 한다.

서버의 허락을 받고 명령이 수락되므로 해킹에 강하지만,

허락 받아야 하므로 반응속도가 떨어진다.

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

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

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

상태정보의 틀어짐이 있어 예측과 보정을 해야 한다.

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

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

도표에서 사용한 용어 정의

P1과 P2는 서로 다른 Peer이며.

P1와 P2는 각 각 200ms과 400ms ping을 갖는다.

S는 Server이며, Tick 100ms(FPS=10)의 프레임 간격을 갖는다.

고려할 갖 가지 상황

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

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

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

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

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

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

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

즉, P1와 P2 각 각의 S.T1 시점에 행위를 하였지만,

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

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

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

다시 말해, 허용하는 ping 값을 정한다.

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

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

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

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

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

이전 시간으로 돌렸더니 히트가 성공한다면,

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

마찬가지로 P2 역시 갑자기 피격될 수 있다.

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

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

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

즉, P1은 2,0까지 이동하진 않아야 한다.

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

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

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

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

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

게임에 따라 서버시간 보정을 할지 말지는 모르겠다.

하지만 ping에 따라, 다음과 같은 현상이 발생한다.

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

게임에서 정한 오차범위 내에 과거를 보고 있다면 괸찮을 듯

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

서버의 캐릭터 상태 메시지가 늦어, 클라에서 자체적으로 진행한 캐릭터 상태와 오차가 발생한다.

일시적인거라면, 거슬리지 않겠지만,

지속적으로 느려진거라면, 캐릭터 상태 보간 역시 지속적으로 필요하다.

지속적인 보간은 어색하지 않을까.

차라리 늦어진 ping만큼 클라의 서버시간 역시 늦추는게 좋지 않을까.

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

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

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

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

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

ping이 들쑥날쑥,

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

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

동기화를 구현한 예제

간단함을 위해 서버는 Node.js를 이용했고,

클라는 웹브라우져를 이용했다.

통신은 웹소켓을 사용했다.

Node.js 서버코드 보기

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

클라코드 보기

http://jsfiddle.net/yakolla/KTkZL/

테스트 해보기

서버 실행하기

Node.js서버에 해당 코드를 파일로 저장하여 그 파일을 실행

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

npm install websocket

클라 실행하기

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

성공적으로 서버에 연결되었다면, 노란색 원이 출력된다.

마우스로 클릭하면, 원이 이동한다.

스페이스를 누르면, 마우스 방향으로 총알을 쏜다.

총알을 맞아 hp가 0이되면, 5초 후에 부활한다.

ping은 서버에서 보내온 메시지를 딜레이 시킨다.

ping 값이 길 수록 좀 더 오래된 과거 서버 상태를 본다.

간단한 테스트 예)

첫 번째 클라를 실행 후, 멀리 이동시킨다.

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

클라 실행 모습

224 view

4.0 stars

SSISO Community

	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( (xx) + (yy) ) ) {
	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);


	});

	});