[자료구조] 자료구조별 게임의 기능 구현 예시

자료 구조를 공부하며 실제로 게임개발에 어떠한 기능들을 구현할 수 있는지 알아보고자 합니다.

https://choieastsea.github.io/DS00-start/

많은 자료구조가 있지만 이번 게임의 기능 구현 예시에는 7가지 자료구조의 예시를 정리 합니다.

1. 연결 리스트[Linked List]

2. 양방향 연결 리스트[Double Linked List]

3. 스택[Stack]

4. 큐[Queue]

5. 이진 트리[Binary Tree]

6. 힙[Heap]

7. 그래프[Graph]

---

1. 연결 리스트[Linked List]

1.객체 관리

게임에서 수많은 객체를 생성하고 관리해야할때에 효율적인 자료구조 입니다.

예를 들자면 게임 내의 캐릭터, 아이템, 몬스터(적) 등등을 관리할 수 있습니다.

Linked List를 사용한다면 객체를 동적으로 추가하거나 제거할 수 있기때문에 메모리를 상황에 맞게 효율적으로 사용할 수 있습니다.

2. 충돌 감지

충돌은 게임에서 중요한 기능 중 하나입니다.

Linked List를 사용하여 충돌을 감지하고 처리할 수 있습니다.

게임에서 객체들의 위치를 리스트에 저장하고, 객체들의 위치가 겹치는지 확인하여 충돌 처리를 합니다.

3. 애니메이션 관리

애니메이션 프레임들을 리스트에 저장하고 순차적으로 재생함으로써 애니메이션을 관리합니다.

리스트는 프레임들을 효율적으로 추가 및 삭제하는데 유용하기 때문에 애니메이션의 재생 속도를 조절하는 등의 기술을 구현할 수 있습니다.

4. 이벤트 처리

키 입력, 마우스 클릭 등의 이벤트를 보관해야 할 때 리스트를 사용할 수 있습니다.

순차적으로 저장함으로서 이벤트의 발생 순서를 유지하여 효율적으로 처리할 수 있습니다.

5. 경로 탐색

몬스터, NPC와 같은 캐릭터의 경로 탐색에 리스트를 사용할 수 있습니다.

맵의 타일(인덱스)들을 리스트로 구성하고, 경로 탐색 알고리즘(A*, 다익스트라 등등)을 통해 최적의 경로를 찾을 수 있습니다.

---

2. 양방향 연결 리스트[Double Linked List]

Double Linked List는 위의 Linked List의 변형 입니다.

각 노드가 이전 노드와 다음 노드에 대한 참조를 가지고 있는 자료구조입니다.

때문에 위에서 언급된 분야 외에도 추가적으로 더 많은 곳에 사용할 수 있습니다.

1. 양방향 탐색

게임에서 양방향 탐색이 필요한 경우에 사용할 수 있습니다.

예시로 이전 노드로 돌아가면서 역방향으로 이동하거나, 특정 노드의 주변 노드들을 탐색할 때 유용합니다.

2. 역방향 반복

각 노드들은 이전노드와 연결이 되어있기 떄문에 역방향으로 반복(iteration)이 가능합니다.

게임에서 역순으로 객체나 이벤트를 처리해야 할 때 유용합니다.

게임에서 스택(Stack)의 동작을 구현하거나, 최근에 발생한 이벤트를 거꾸로 처리해야 할 때 사용됩니다.

3. 노드 삽입 및 삭제

적 또는 아이템을 동적으로 추가하거나 제거해야 할 때 사용할 수 있습니다.

4. 경로 탐색

Linked List 자료구조와 마찬가지로 경로 탐색 알고리즘에서 사용될 수 있습니다.

다만 양방향으로 노드가 이어져 있기 때문에 역추적을 수행할 수 있습니다.

---

3. 스택[Stack]

스택은 후입선출(LIFO / Last In First Out)구조로 데이터를 저장하고 접근합니다.

게임 개발에서 상태 관리, 이벤트 처리, 다양한 알고리즘 등에 사용 됩니다.

1. Undo / Redo 기능

게임에서 플레이어의 동작을 취소하거나 다시 실행시키는 Undo / Redo 기능구현이 가능합니다.

플레이어의 동작을 스택에 저장하여 이전 상태로 되돌릴 수 있으며, 다시 실행할 때에는 스택에서 제일 나중(Last)에 저장된 동작을 가져와 적용할 수 있습니다.

2. 이벤트 시스템

스택을 이용하여 이벤트를 관리하고 처리할 수 있습니다.

키입력, 마우스클릭등 실행된 이벤트를 스택에 저장하여 나중에 처리 하거나, 이벤트 핸들링 시에 스택을 사용하여 효과적인 이벤트 전달 관리가 가능합니다.

3. 게임 상태 관리

게임 내에서 여러 상태(메뉴, 게임 플레이, 일시정지 등)를 다룰 때 상태 전환을 스택에 쌓고 꺼내어 처리함으로써 이전 상태로 쉽게 돌아갈 수 있습니다.

예를들자면 게임중 > 일시정지버튼을 누른다 > 설정 버튼을 누른다 > 설정을 바꾼다 순서대로 실행을 저장하였다면 한번에 모든창을 닫고 게임을 다시 실행하기보다 가장 나중에 실행한 창들을 순서대로 닫고 다시 게임 플레이 화면으로 오는 것이 자연스럽고 안전합니다.

4. 콜 스택

게임의 함수 호출 및 반환을 추적하고 관리하는 데 스택을 사용할 수 있습니다.

함수 호출 시 스택에 호출 정보를 저장하고, 함수 실행이 완료되면 스택에서 해당 정보를 제거하여 함수 호출의 순서와 관련된 로직을 처리할 수 있습니다.

이 사용법은 게임 엔진, 스크립트 시스템 등에서 만힝 사용되는 기능입니다.

5. 탐색 알고리즘

스택을 활용한 깊이 우선 탐색(DFS / Depth First Search)알고리즘을 사용하여 탐색할 노드의 순서를 관리할 수 있습니다. 게임에서 맵 탐색, 퍼즐 게임의 해결 방법 탐색과 같은 곳에 사용 할 수 있습니다.

---

4. 큐[Queue]

큐는 선입선출(FIFO / First In First Out)구조로 데이터를 저장하고 접근하는 자료구조 입니다.

순서대로의 처리가 필요한 다양한 상황에서 사용될 수 있습니다. 게임 개발에서 이벤트 처리, 애니메이션 관리, 비동기 작업 처리 등의 기능을 구현할 수 있습니다.

1. 이벤트 대기열

게임에서 이벤트를 순차적으로 처리해야 할 때 큐는 유용하게 사용됩니다.

이벤트 대기열을 구현하여 발생한 이벤트를 순서대로 저장하고 순서대로 처리할 수 있습니다.

키입력, 마우스입력, 클릭 등의 다양한 이벤트를 Queue에 추가하고, 게임 로직에서 순차적으로 처리하는 방식으로 이벤트 시스템을 구현 합니다.

2. 애니메이션 큐

애니메이션 큐를 구현하여 여러 애니메이션을 순서대로 재생할 수 있습니다.

캐릭터의 이동 애니메이션, 공격 애니메이션등을 추가하여 순서대로 재생한다면 자연스러운 애니메이션 효과를 구현할 수 있습니다.

3. 태스크 큐

비동기 작업이나 백그라운 작업을 처리해야 할 때에 Queue를 사용할 수 있습니다.

비동기 작업을 Queue에 추가하여 순차적으로 처리하면 작업 간의 충돌을 방지하고 작업로드를 균형있게 분배할 수 있습니다.

예를 들어 맵 데이터의 로딩, 자원 로딩, Ai계산 등을 비동기 적으로 처리할 때 유용 합니다.

4. 이펙트 처리

게임에서 이펙트(파티클, 특수효과 등)는 시간적 순서에 따라 처리되어야 합니다.

때문에 Queue를 사용하여 이펙트를 순차적으로 추가하고 재생할 수 있습니다.

이펙트 큐를 구현하여 이펙트들을 순서대로 처리하면, 미리 계산하여둔 정확한 타이밍에 이펙트를 출력 시킬수 있습니다.

5. 트랜잭션 처리

게임 내에서 아이템 구매, 자원 거래 등의 *트랜잭션을 처리할 때 Queue를 사용하여 트랜잭션의 순서를 유지하고, 일괄 처리할 수 있습니다.

 

*트랜잭션(Transaction) 이란?

데이터베이서와 관련된 개념입니다. 하나 이상의 작업을 하나의 논리적 단위로 묶은 것을 의미합니다.

이러한 작업들은 모두 성공적으로 완료되거나, 전혀 실행되지 않아야 합니다. 트랜잭션은 데이터 베이스 시스템에서 데이터의 일관성과 무결성을 보장하기 위해 사용됩니다.

---

5. 이진 트리[Binary Tree]

이진트리는 계층적인 구조를 가지고 있습니다.

때문에 빠른 탐색과 관리가 가능하여 게임 개발에서 충돌 감지, Ai 결정 트리, 레벨 디자인, 자원 관리, 퀘스트 추적 등 다양한 기능에 이진 트리를 사용 할 수 있습니다.

1. 충돌 감지

게임에서 객체들의 충돌을 감지하고 처리합니다.

이진트리를 활용하면 효율적인 충돌 감지 알고리즘을 구현할 수 있으며, 객체들 간의 충돌을 빠르게 탐지할 수 있습니다.

2. Ai 결정 트리

인공지능(Ai) 결정 트리(Decision Tree)의 구현에 사용될 수 있습니다.

게임에서 NPC의 행동 패턴이나 Ai의 의사 결정 로직을 구현할 때, 이진트리를 사용하여 다양한 조건과 선택지를 나타낼 수 있습니다.

플레이어의 상태나 게임 상황에 따라 이진 트리를 탐색하면서 적절한 행돌을 결정할 수 있습니다.

3. 레벨 디자인

게임의 맵이나 레벨 구조를 표현하는 데에 이진 트리를 활용할 수 있습니다.

예를 들어 레벨의 분기점이나 다양한 선택지를 표현하고 관리하는 데에 이진트리를 사용할 수 있습니다.

스킬트리를 연상하면 될 것 같습니다.

4. 자원 관리

게임 내의 자원 관리에 사용될 수 있습니다.

게임에서 사용되는 텍스처, 사운드 리소스들을 효율적으로 관리할 수 있습니다.

리소스들을 구조화하고, 접근이 빠르기 때문에 필요한 리소스에 신속히 접근할 수 있습니다.

5. 퀘스트 추적

퀘스트 또는 임무 추적에 활용될 수 있습니다.

게임 내의 플레이어 퀘스트나 미션을 구조화 하고 관리하기 위하여 이진트리를 사용할 수 있습니다.

이진 트리를 통해 퀘스트의 계층 구조를 표현하고 진행 상황을 추적할 수 있습니다.

---

6. 힙[Heap]

자료구조 힙은 트리 기반의 구조 입니다.

부모 노드와 자식 노드 간의 부분적으로 정렬된 순서를 유지하며 가장 일반적으로는 이진 힙(Binary Heap)이 사용 됩니다.

1. 우선순위 큐

우선순위 큐(Priority Queue)의 구현에 사용됩니다.

게임에서 이벤트나 작업들을 우선순위(조건)에 따라 처리해야 할 때에 Heap을 사용하여 우선 순위 큐를 구현할 수 있습니다.

빠른 삽입과 삭제 연산등을 제공하므로, 우선순위에 따라 정렬(Sort)된 작업들을 효율적으로 처리할 수 있습니다.

2. 최대 & 최소 값 구하기

Heap은 최대 힙(Max Heap) 또는 최소 힙(Min Heap)의 형태로 사용될 수 있습니다.

게임에서 최대값 또는 최소값을 빠르게 검색하는 상황에서 유용합니다. 예시로 게임에서 스코어보드의 상위 랭킹을 추적하거나, Ai의 우선순위 결정에 사용할 수 있습니다.

3. 이벤트 시간 관리

게임에서 인벤트의 발생 시간을 관리해야 할 때에 Heap을 사용할 수 있습니다.

다양한 이벤트들을 Heap에 저장하고, 다음에 처리해야 할 가장 빠른 이벤트를 빠르게 찾아 처리 합니다.

이벤트가 시간에 따라 발생하고 처리되어야 하는 경우에 Heap을 사용하여 이벤트 시간 관리를 효율적으로 구현할 수 있습니다.

4. 탐색 알고리즘

최단 경로 탐색 알고리즘인 다익스트라(Dijkstra) 알고리즘에서 Heap을 사용하여 노드들의 최소 거리를 효율적으로 업데이트하고 추출할 수 있습니다. 게임에서 맵 탐색, 길 찾기 알고리즘 등 다양한 상황에서 사용할 수 있습니다.

---

7. 그래프[Graph]

그래프는 노드(Node)와 그들을 연결하는 간선(Edge)으로 구성됩니다.

다양한 상호 관계를 나타낼 수 있는 유연한 자료구조 입니다.

1. 맵 및 레벨 디자인

게임에서 맵이나 레벨을 표현할때 사용할 수 있습니다.

각 노드는 맵의 위치를 나타내고, 간선은 위치들 간의 이동 경로를 나타날 수 있습니다.

그래프를 사용하여 맵의 연결성을 표현하고, 플레이어의 이동 경로를 계산하거나 퍼즐 요소를 관리하는 등의 기능을 구현할 수 있습니다.

2. 경로 탐색

게임에서 캐릭터나 NPC의 이동 경로를 찾아야 할 때 그래프를 사용하여 최단 경로를 탐색할 수 있습니다.

위에서도 언급했던 다익스트라(Dijkstra) 또는 A*(A Star) 알고리즘을 사용하여 그래프에서 최적의 경로를 계산할 수 있습니다.

3. 적 Ai

적 Ai(인공지능)의 동작 구현에 사용될 수 있습니다.

적의 이동 패턴이나 상호 작용을 그래프로 표현하고, 그래프 탐색 알고리즘을 활용하여 적의 행동을 결정할 수 있습니다.

그래프를 사용하여 적의 행동 상태 전이를 모델링하고, 게임 내에서 적과의 상호작용을 다양하게 제어할 수 있습니다.

4. 이벤트 관리

게임 내 이벤트 시스템 구현에 사용될 수 있습니다.

이벤트들을 노드(Node)로 표현하고 이벤트간의 연결 관계를 간선(Edge)로 표현하여 이벤트의 흐름을 제어할 수 있습니다.

이벤트의 실행 순서를 관리하거나, 조건과 상호작용을 통해 게임 내 이벤트를 제어할 수 있습니다.

5. 아이템 관리

아이템이나 리소스의 관계를 표현하고 관리하는데 사용될 수 있습니다.

게임 내의 아이템들을 그래프로 표현하고, 아이템 간의 연결 관계를 나타내어 아이템의 획득, 조합, 사용 등을 관리할 수 있습니다.

---

다양한 자료구조들은 설계자의 의도에 따라 더욱 많은 기능구현에 사용될 수 있습니다.

본문의 예시는 간단히 5개 이하로만 정리하였으나 기능구현에 꼭 정해진 방법만 있는 것은 아니기 때문에 다양하게 생각해 봐야할 듯 합니다.