2022.09.07 경일 메타버스 23주차 3일 특강 수업내용. 자료구조와 알고리즘 - 힙(Heap), 게임 서버에 대한 이해

힙 (Heap)

• 자료 : https://docs.google.com/document/d/1wUms27Vj8si-jEjfRQJwSvsQ2CJNCv4IU6GOtesY4TE/edit

힙의 구현

• 다른 자료구조와 달리 리스트가 아닌 배열 vector를 이용해 구현하는 이유

  • 자료구조를 만들 때 빈 칸이 많아질 수 있다 → 배열의 메모리 낭비

  • 그에 비해 힙은 완전 이진 트리 → 꽉 찬 노드
    따라서 배열을 사용함에 적합하다

• 힙(Heap)의 구현

  • MaxHeap

2022. 09. 07 힙(Heap) 구현 : 헤더 파일

2022. 09. 07 힙(Heap) 구현 : 소스 파일

2022. 09. 07 힙(Heap) 구현 : 체크 (힙 정렬)

게임 서버에 대한 이해

• 자료 : https://docs.google.com/document/d/1a8TbfG0FoSqat8b58ZkQ_QC8O03oTz2-g8j4kupZwYo/edit#

• 추가로 공부하려면 : https://www.inven.co.kr/webzine/news/?news=42073

멀티플레이어 게임의 역사

1. 로컬 멀티플레이어 게임
   한 컴퓨터에서 2명 이상의 플레이어가 같이 즐기는 방식.
   구현은 싱글플레이어 게임과 다르지 않다.

2. 초기 네트워크 멀티플레이어 게임
   메인프레임으로 구성된 소규모 네트워크.
   직렬 포트를 사용해 서로 통신했다.

3. MUD
   멀티 유저 던전(Multi-User Dungeon; MUD)
   텍스트 기반으로 진행되는 멀티플레이어 게임이다.
   에식스 대학에 재학 중이던 랍 트루쇼가 만든 MUD에서 유래됐다.

4. LAN 게임
   이더넷이 보급되며 근거리 통신망(LAN; Local Area Network)을 이용한 게임이 등장했다.

5. 온라인 게임
   인터넷이 보급되며 비로소 이때부터 우리가 아는 형태의 멀티플레이어 게임이 생겨났다.
   랜 게임과 구현은 비슷했지만 레이턴시(Latency)에 따른 부작용을 최소화하는 기법이 생겨났다.

   • 레이턴시 : 네트워크로 데이터를 전송하며 발생하는 시간 지연

6. MMO 게임
   하나의 게임 세션에 수백, 수천 명의 플레이어가 동시에 참여하는 게임을 말한다.
   가장 고전은 울티마 온라인이라고 할 수 있다.

7. 모바일 네트워크 게임
   초기 모바일 네트워크 게임은 게임의 진행은 클라이언트에서 전부 진행하고, 결과나 스테이지에 대한 데이터는 서버에서 받아오는 구현이 주를 이루었다.
   요즘은 무선망이 많이 발달되어 실시간 네트워크를 지원하는 게임이 많아지고 있다.

게임 서버

역할

• 게임 서버는 게임 루프 중 업데이트 일부를 떼어 내어 실행한다.

1. 클라이언트에서 해킹 당하면 안 되는 처리
   ex. 아이템 획득

2. 플레이어 데이터를 저장

3. 여러 사용자 간의 행동을 중재해 결과를 판정

네트워크 토폴로지(Network Topology)

• 여러 컴퓨터가 네트워크 상 연결되어 있는 양태

• 여기서는 게임 서버에 사용되는 토폴로지만 다룬다.

1. 클라이언트-서버(Client-Server)

   • 하나의 컴퓨터에 여러 컴퓨터가 접속하는 방식

   • CS라고 약칭

   • 가장 대중적인 구조

   • 권한 집중형(Authoritative)으로 서버가 모든 행동에 대한 판정을 내린다.

   • 종류

     1. 데디케이티드 서버(Dedicated Server) :
        게임 서비스를 제공하는 업체가 고성능의 컴퓨터를 이용해 서비스

     2. 리스닝 서버(Listening Server) :
        플레이어가 게임에서 제공하는 프로그램을 이용해 직접 서비스.
        피어 호스팅(Peer Hosting)이라고도 한다.

2. 피어 투 피어(Peer To Peer)

   • 게임에 참여하는 모든 컴퓨터끼리 서로 접속하는 방식

   • P2P라고 약칭

   • CS와 달리 판정 권한이 어디 있는지 불분명하다.

   • 보편적으로 각 피어마다 입력을 서로 공유해 각자가 이들 입력을 스스로 시뮬레이션 한다.

게임 플레이 네트워킹

모든 연산을 서버가 부담

• 클라이언트는 단순히 입력 전달과 화면 출력만 하고, 서버에서 게임 로직 연산, 화면 렌더링, 송출까지 하는 방법

• 가장 고전적인 방법으로, 최근에는 그래픽 품질이 매우 높아 비용이 비싸므로 사용하지 않았다.

• 하지만 기술이 발전하면서 스테디아, 지포스 나우 등 클라우드 게이밍으로 재탄생 하게 되었다.

렌더링을 클라이언트에서 하기

• 서버가 클라이언트에 게임 월드 상태를 보내어 렌더링 하는 것

• 가장 보편적인 방법

• 게임 월드의 업데이트는 서버가 클라이언트로부터 메시지를 받아 진행

• 이상적인 건 게임이 목표한 프레임률만큼 업데이트를 하는 것이겠지만 네트워크란 것이 워낙 변수가 많으므로 그렇게 하기란 쉽지 않다.

• 따라서 업데이트 주기를 늘리게 되는데, 이를 플레이어가 못 느끼게 하기 위해 다음과 같은 다양한 방법을 활용한다.

  • 추측항법(Dead Reckoning)

  • 레이턴시 마스킹(Latency Masking)

  • 플레이어 가시 영역 부분만을 전달

  • 락스텝(Lockstep) 동기화

리플리케이션 (Replication)

• 객체의 상태를 한 호스트에서 다른 호스트로 복제 전달하는 행위

• 일관된 게임 월드 상태를 유지하기 위해 이루어져야 한다.

• 리플리케이션을 위해 먼저 직렬화가 이루어져야 한다.

직렬화 (Serialize)

• 서로 다른 컴퓨터 간에 데이터 전송을 위한 기법으로, 전송할 데이터를 일련의 바이트열로 바꾸는 것

  • 반대는 역직렬화(Deserialize)

• 메모리 주소값을 보내주는 경우나 보낼 데이터의 크기가 큰 경우 그냥 보낼 수 없으므로 이를 적절하게 처리하기 위해서 필요

• JSON 형식이나 구글이 만든 프로토콜 버퍼가 사용된다.

  • 프로토콜 버퍼

• 객체의 메소드를 호출할 때는 RPC(Remote Procedure Call)를 사용한다.

  • RPC란 다른 호스트의 특정 프로시저가 원격 수행되도록 지시하는 것을 말한다.

    • 엄밀하게 RMI(Remote Method Invocation)으로 구분하기도 한다.

게임 서버 제작을 위한 포톤 연습

• 포톤 자료 (RPCs 와 RaiseEvent) : https://doc.photonengine.com/ko-kr/pun/current/gameplay/rpcsandraiseevent
  

참고자료

• 게임 서버 프로그래밍 교과서 - YES24
• 멀티플레이어 게임 프로그래밍 - YES24