평행 분할, 모스 알고리즘 평행 분할(SQRT Decomposition)은 데이터가 N개이면 √N개만큼 나눠서 관리하는 방법이다. 각 그룹은 대푯값을 가지고 있다. 만약 주어지는 쿼리가 구간의 덧셈이라면 그룹의 합이 대푯값이 된다. 모스 알고리즘은 어떤 구간 [s, e]에 속하는 원소들을 이용하여 어떤 값을 계산하는 쿼리를 처리하는 알고리즘이다. 업데이트가 없어 쿼리의 순서를 변경해도 무방하다. 그래서 쿼리 순서를 재배치하여 효율적으로 수행한다. 배열을 k(√N)개로 이루어진 그룹으로 나눠주고, 쿼리를 실행할 때 두 조건 중 하나를 만족하는 경우 먼저 처리한다. [s1/k] < [s2/k] [s1/k] = [s2/k] and e1 < e2 문제 https://www.acmicpc.net/problem/1..

게임 루프 패턴(Game Loop Pattern) 먼저 요약하자면 게임 루프 패턴이란 게임 진행을 유저 입력, 프로세서 속도와 디커플링 하는 것이다. 더 쉽게 말하자면 입력이 없어도 프로세서가 잘 돌아간다는 말이다. 이 패턴은 특수하여 게임 분야 외에서는 찾아보기는 힘들지만 실제로 많이 쓰이고 있다. (유니티 등 게임 엔진) 예전 프로그래머는 코드를 모두 짜고 나서야 프로그램을 돌릴 수 있었다. 즉, 중간에 확인하는 것은 거의 불가능했다. 이런 프로그램을 배치 모드 프로그램이라고 하는데, 모든 작업이 끝나고 나면 프로그램이 멈춘다. 여기서 나오는 문제점은 디버깅하는 데도 오래 걸려 생산성이 떨어지게 된다는 점이다. 그래서 이를 해결하기 위해 대화형 프로그램이 나왔다. 플레이어의 입력을 기다렸다가 응답하면..

10장 분산 서버 구조 사례 4. 몬스터 NPC 처리의 분산 처리 보통 서버에서 하는 몬스터 처리는 다음과 같다. 일정 시간마다 몬스터의 움직임을 델타 타임만큼 시뮬레이션(위치 이동, 모션 변화)한다. 일정 조건(시간)마다 몬스터의 움직임 결과를 가시자 클라이언트에 보낸다. 가시가 클라이언트란 몬스터 주변에 있는 플레이어들을 말한다. 플레이어가 몬스터와 상호 작용(공격)할 경우, 이에 대한 연산을 처리한 후 몬스터 및 플레이어 상태를 갱신한다. 한편 성능상 고려해야 할 것들도 있다. 보통 몬스터 수가 플레이어 수보다 많다. 길 찾기 알고리즘 등 몬스터 움직임을 위한 연산량이 많이 필요할 수도 있다. 몬스터의 연산 로직에는 게임 기획자의 아이디어가 많이 들어가기 때문에 프로그램 구조가 복잡해질 수 있다. ..

10장 분산 서버 구조 사례 대표적인 몇 가지 기능과 관련해서 분산 서버 설계 유형을 살펴보고 게임 장르별로 분산 서버 설계 유형도 알아볼 것이다. 1. 로그온 처리의 분산 보통 로그온 처리는 다음과 같이 한다. 클라이언트는 서버에 ID와 비밀번호를 암호화해서 보낸다. 로그온 담당 서버(인증 서버)에서 이 메시지를 받고 복호화한다. 서버는 복호화된 메시지에서 ID와 비밀번호를 구하고 DB에 질의를 던진다. DB에서 질의를 수행한 후 응답을 서버에 회신한다. 서버는 이를 받아 로그인 성공 혹은 실패를 판단한다. 로그온 결과를 클라이언트에 보낸다. 로그온 처리를 하는 단일 서버는 인증 서버 한 대와 데이터베이스 1개로 구성되어 있다. 여기서 클라이언트가 늘어날 때마다 과부하가 발생하는 지점은 어디일까? 동시..

9장 분산 서버 구조 5. 데이터 분산 (수평 분산) vs 기능적 분산 (수직 분산) 데이터 분산이란 한 머신이 처리해야 하는 데이터를 같은 역할을 하는 여러 머신이 나누어 처리하는 것이다. 즉, 각 서버는 모두 똑같은 종류의 일을 한다. 기능적 분산은 한 머신이 처리해야 하는 데이터의 처리 단계를 세분화해서 여러 머신이 나누어 처리하는 것이다. 이러한 분산 처리 원리는 게임 서버뿐만 아니라 데이터베이스에서도 비슷하다. 데이터베이스에서 데이터 단위 분산(수평 파티셔닝)이란 테이블 1개를 테이블 안의 키 필드 단위로 분배하는 것을 의미한다. 그리고 기능 단위 분산(수직 파티셔닝)이란 서로 다른 테이블을 서로 다른 서버에 배치하는 것을 의미한다. 게임 서버가 분산 처리되어 있다고 하더라도 데이터베이스를 분산..

9장 분산 서버 구조 서버 클러스터, 수직 확장, 수평 확장, 샤드, 로드 밸런싱, 고가용성 등 이러한 용어들이 사용되는 분야가 바로 분산 서버이다. 게임 서버뿐만 아니라 서버 개발에서 반드시 다루는 주제로 어떻게 설계를 하느냐에 따라 게임 서비스가 안정적으로 작동할 수도 있고 심각한 문제가 발생할 수도 있다. 1. 수직 확장과 수평 확장 게임 서버에 품질을 논할 때 나오는 것 중 하나로, 확장성이란 사용자 수가 늘어나더라도 쉽게 대응할 수 있어야 한다는 의미이다. 최대로 처리할 수 있는 사용자 수가 무제한이어도 가능해야 한다는 것이 목표이다. 사용자 수가 늘어나도 서버 성능을 유지하려면 보통 다음 두 가지 중 하나를 수행한다. 스케일 업 = 수직 학장: 서버의 하드웨어를 더 좋은 것으로 교체하여 처리량..