[CS] 게임 개발에서의 자료 구조 활용

1. 배열

 

특징 : 크기 고정, 연속된 메모리 할당, 동일한 데이터 타입만 사용

 

장점)

빠른 읽기와 쓰기

메모리 효율성 (연속적이라 데이터 캐싱이 효율적)

 

단점)

고정된 크기 : 크기를 변경하려면 새 배열을 만들고 데이터를 복사해야함.

낭비되는 메모리 공간 : 넉넉하게 만들어놓고 데이터는 적게 넣으면 낭비됨

복잡한 삽입과 삭제

메모리 할당 문제 : 큰 배열은 연속된 큰 메모리 공간을 필요로 함 (메모리 할당에 실패할 수 있음)

 

배열 활용하기 좋은 상황

1) 데이터 접근이 빈번하고 예측 가능할 때

2) 데이터 크기나 요소 수가 고정되어 있을 때

3) 요소 삽입과 삭제가 적을 때

4) 순차적 접근이 주를 이룰 때

5) 메모리 사용이 중요한 상황일 때 (특히 모바일 게임)

 

게임에서 어떻게 활용하지?

1) 캐릭터 인벤토리 시스템 : 제한된 수의 아이템 보유, 아이템 접근이 빠름

2) 맵 타일 관리 : 그리드 형태의 맵에서 셀은 배열로 관리 가능, 맵의 특정 위치에 접근하기 효율적

3) 애니메이션 프레임 관리 : 애니메이션은 이미지의 연속이니까, 이미지를 배열로 순서대로 저장함. 프레임 접근이 쉬움

4) 오디오 트랙 관리 : BGM, 효과음 등 배열에 저장해서 관리, 특정 상황에서 오디오를 배열에서 바로 찾아 재생

5) 스킬 및 능력치 시스템 : 지정된 스킬만 있는 경우가 많으므로, 배열로 관리하기 효율적

 

 

2. 연결 리스트

 

특징 :

노드 기반 구조 (데이터 data와 포인터next 가 하나의 node를 구성)

비연속적 메모리 할당

동적 크기 조정

C# 에서는 Generic 으로 LinkedList 바로 불러와서 구현 가능.

 

장점 )

동적인 메모리 관리,

데이터 삽입과 삭제의 편리성

 

단점 )

메모리 오버헤드 : 각 노드가 데이터와 포인터를 저장하므로 배열보다 메모리 많이 사용

순차 탐색 접근 : 배열과 달리 특정 요소에 접근하기 위해서는 리스트를 순차적으로 탐색해야한다.

 

연결 리스트 활용하기 좋은 상황

데이터가 자주 추가되거나 제거되는 상황

데이터 접근하는 게 순차적인 상황

데이터 크기가 불확실할 때

 

게임에서 어떻게 활용하지?

1) 동적 인벤토리 시스템

아이템 수가 정해져 있지 않고, 추가되고 삭제되는 게 빈번할 경우

2) NPC 행동 관리

행동을 순차적으로 수행, 게임 상황에 따라 행동이 추가되거나 삭제될 때

3) 레벨 내 동적 객체 관리

적, 아이템, 장애물 등이 계속 추가되거나 제거되는 경우

4) 멀티 플레이어 게임에서 플레이어 관리

플레이어가 접속하거나 접속 해제하는 경우가 빈번하므로, 플레이어 목록을 관리하기 용이함.

5) 타이머 이벤트 관리

시간 순서에 따라 이벤트를 처리하는 경우

예정된 이벤트가 시간이 되면 해당 이벤트를 실행하거나 제거할 때도 편리함

 

 

3. 스택

 

특징

LIFO : 후입선출 방식.

간단한 연산 (push, pop) / 빠른 연산 속도

push 요소 추가 / pop 요소 출력 / peek 맨 위의 요소 확인

 

장점 )

단순한 구조, 데이터 순서 유지, 고정된 메모리 사용 - 스택 사이즈는 지정한 값만큼 고정된다.

단점 )

유연성 부족 (중간의 요소에 접근하거나 수정하기가 어려움)

(스택의 크기가 고정되어 있을 경우, 메모리 용량이 초과됨)

=> stack overflow 발생

 

스택 활용하기 좋은 상황

1) 역순 처리가 필요할 때 (되돌리기 가능)

2) 임시 데이터 저장할 때

3) 재귀적 구조를 처리할 때

4) UI 관리할 때 

 

게임에서 어떻게 활용하지?

1) 되돌리기 기능 : 플레이어 다양한 행동을 스택에 저장해서 관리 (되돌리기)

2) 대화 시스템 : NPC 랑 대화하다기 이전 대화로 돌아가기 누를 때. 최근 대화를 꺼내 이전 상태로 복구할 때도 유용

3) 이벤트 처리 (전략게임, 턴제 등) : 행동이나 이벤트가 순차적으로 처리될 경우, 이벤트 시퀀스 관리할 때

4) 재귀적 탐색 (퍼즐게임) : 복잡한 퍼즐 시스템 구현 (중첩성이 있을 때) , 재귀적으로 퍼즐 해결 경로를 찾을 때

5) 메뉴 시스템 : 다양한 메뉴가 중첩적으로 열릴 때, 메뉴의 상태가 스택에 저장되고 이전 메뉴로 돌아갈 수 있다.

 

4. 큐

 

특징)

FIFO 선입선출, 순차적 처리

장점 )

직관적인 구조 , 데이터 처리에 공정함, 자원 관리에 유용함 (CPU 스케쥴링)

단점 )

낮은 유연성, 중간에 위치한 요소에 직접 접근이 어렵다. 순차적 접근만을 허용.

 

큐 활용하기 좋은 상황

순차적인 이벤트나 행동 처리,

공유 자원을 순차적으로 관리할 때

멀티플레이어 동기화가 필요한 상황 (서버의 응답을 큐에 담음)

비동기 작업 관리 (데이터 로딩, 네트워크 통신)

 

게임에서 어떻게 활용하지?

1) 입력 이벤트 처리 : 순차적으로 입력을 처리하기 위함

2) 캐릭터 동작 대기열 : 플레이어의 여러 동작이 빠르게 입력될 때

3) AI 명령 처리 : AI는 큐에 저장된 순서대로 움직인다.

4) 네트워크 메시지 처리 : 온라인 게임에서 다른 플레이어나 서버에서 오는 메시지 관리하기

                                         네트워크 지연이나 패킷 손실로 인한 문제 최소화

5) 리소스 로딩 관리 : 리소스도 중요한 순서대로 불러올 수 있다.

                                   로딩 시간을 최적화하고 리소스의 우선순위를 할당할 수 있다.

 

5. 트리

 

특징)

노드로 구성되어 있음 (루트 노드, 부모-자식 노드)

깊이와 높이 속성을 가지고 있음

 

장점 )

계층적 구조 : 파일 시스템

효율적인 검색 및 정렬 : 이진 탐색 트리

동적인 구조 : 노드 추가, 제거가 쉬움

효율적인 데이터 관리 : 데이터 베이스 시스템에 적합

 

단점 )

구현이 복잡함

비효율적인 메모리 사용 : 각 노드는 참조 포인터를 가지고 있어서 추가적 메모리 소모

불균형 구조의 가능성 : 트리가 한쪽으로 치우쳐지면 성능이 저하 - AVL, 레드블랙 트리 사용

 

이진 탐색 트리 (BST)

왼쪽 노드는 작은 값, 오른쪽 노드는 큰 값.

최대 두 개의 자식 노드

 

트리 활용하기 좋은 상황

데이터를 정렬된 상태로 저장하고, 빠른 검색, 삽입, 삭제가 필요할 때 사용

플레이어 인벤토리 시스템에서 아이템을 정렬하고 아이템 찾는 기능 구현할 때 유용함

 

자료 불균형 가능성이 높아서 자주 쓰이지는 않는다.

실제로는 균형잡힌 트리인 AVL, 레드-블랙 트리를 사용하는 경우가 더 많다.

 

AVL, Red-Black Tree

자동으로 균형을 맞추는 기능이 있다.

AVL : 삽입, 삭제 시 더 많은 회전(균형 맞추기)을 하기 때문에 느린 경향이 있다.

레드-블랙 트리 : 삽입 삭제가 빈번할 때 유리한 성능을 보인다.

 

게임에서 어떻게 활용하지?

데이터 균형을 유지하면서 효율적인 탐색이 필요할 때 사용

게임 서버에서 플레이어 랭킹 정보를 검색 - AVL

대규모 멀티플레이어 게임에서 플레이어 상태 정보가 빠르게 업데이트 되어야 할 때 - Red Black Tree

 

 

서버 개발 : B-- 트리, B++ 트리,

대량의 데이터를 관리하는데 적합한 구조

 

클라이언트 개발 : 옥트리, 쿼드트리,

2D 와 3D 공간을 분할하고 렌더링, 물리 시뮬레이션 등 최적화에 사용됨

 

5-1. Heap 

 

특징)

완전 이진 트리 방식.

최대값 혹은 최소값이 루트에 위치

우선순위 큐, 힙 소트의 구현에도 사용됨

 

힙은 게임에서 어떻게 활용하지?

힙은 최댓값 최솟값에 빠르게 접근해야할 때 사용

게임에서 여러 이벤트의 우선순위에 따라 처리해야할 때, AI의 행동 중 가장 중요한 행동을 결정할 때 

 

6. 그래프

 

특징)

노드와 간선, 방향성 (방향or무방향)

트리처럼 구조가 정해져있지 않음

일부 그래프는 사이클이 포함될 수 있음.

 

장점 )

다양한 데이터의 복잡한 관계 표현이 가능.

실세계 복잡한 시스템을 모델링하기 적합.

다양한 알고리즘 적용 가능.

 

단점 )

대규모 그래프는 복잡한다.

상당한 양의 메모리 요구,

알고리즘 최적화가 어려움

 

1) 탐색 그래프 : 게임 세계의 특정 위치나 지역을 노드가 나타내고, 간선은 위치 간 이동 가능한 경로 구현

2) 내비게이션 그래프 : AI가 이동 가능한 경로를 나타냄

3) 상호작용 그래프 : 게임 캐릭터나 객체가 노드, 간선은 이들 간의 관게나 상호작용 표현

 

그래프 알고리즘 유형

1. 경로 탐색 알고리즘 : A*, 다익스트라, BFS, DFS 등등

캐릭터나 AI가 특정 지점까지 갈 수 있는 최적 또는 유효한 경로를 찾기

NPC가 플레이어를 추적하기

 

2. 최소 신장 트리 알고리즘 : 크루스칼, 프림

네트워크 구축 게임이나 퍼즐 게임에서 자원을 연결하거나

최소 비용으로 네트워크 구축할 때.

도시 건설 게임에서 도로나 전력망을 최소 비용으로 구축할 때.

 

 

그래프는 게임에서 어떻게 활용하지?

1. 경로찾기 

2. 캐릭터 행동 제어 : 캐릭터가 피해를 받으면 방어 상태로 전환, 특정 조건에서 궁극기 사용하면 상태 변환

3. NPC와의 관계 모델링 : 친분, 플레이어의 결정에 따라 관계 변화 구현

4. 오픈 월드 지도 설계 : 탐색 그래프를 통해 오픈 월드 지도에서의 캐릭터 탐험 여부를 등록하기 (지도가 밝혀짐)

 

7. Hash

 

C#에서는 Dictionary 로 사용

 

해시 함수 : 키를 해시테이블의 주소로 변환 / key-value 쌍 구조

해시 충돌 : 두 개 이상의 같은 해시 값을 가질 때 충돌 발생. (여러 가지 해결 방법이 존재)

 

장점 )  

빠른 검색 속도, O(1)

데이터의 삽입과 삭제가 빠름

직관적인 키 - 값

데이터 확장성이  뛰어남

 

단점 )

해시 충돌로 인한 성능 저하

해시 테이블은 순서가 없음 (저장 순서가 랜덤)

좋은 해시 함수의 필요성

 

해시 활용하기 좋은 상황

대량 데이터를 빠르게 접근하고 수정해야할 때

리소스 관리

서버와 클라이언트 간에 데이터를 주고받을 때 데이터의 무결성을 보장받아야 할 때

게임 내에서 중요한 정보 (비밀번호, 게임 상태)를 암호화

무작위 수를 생성

 

게임에서 어떻게 활용하지?

1. 아이템 관리 : 대형 아이템 데이터베이스 다룰 때 검색 용이

2. 리소스 관리

3. 멀티 플레이 에서 데이터 동기화

- 서버에서 데이터 보낼 때 해시값 변환, 클라이언트와 해시값 비교