자료구조란?
데이터 값의 모임, 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것을 의미한다.
예를 들면 책장과 책장안에 책이 있다고 하면 책장과 책은 컴퓨터 세계에서는 메모리와 데이터로 유사하게 비유할 수 있다.
연산에 사용되는 컴퓨터의 메모리 자원은 매우 한정적인데 반해 처리해야 할 데이터는 무수히 많을 수 있다. 따라서 이 메모리 공간을 효율적으로 사용해야 하는데 필요한 것이 자료 구조이다.
그러면 게임개발에는 어떠한 자료구조를 이용해 기능들을 구현할 수 있는지 알아보자.
많은 자료구조가 있지만 그중에서 게임의 기능 구현 자료구조의 예시에 대해 알아보자.
1. 연결 리스트[Linked List]
1.객체 관리
게임에서 수많은 객체를 생성하고 관리해야할때에 효율적인 자료구조로 게임구조로 예를 들면 게임 내의 캐릭터, 아이템, 몬스터(적) 등등을 관리할 수 있다.
이런 Linked List를 사용한다면 객체를 동적으로 추가하거나 제거할 수 있기때문에 메모리를 상황에 맞게 효율적으로 사용할 수 있다.
2. 충돌 감지
충돌은 게임에서 중요한 기능 중 하나로 Linked List를 사용하여 충돌을 감지하고 처리할 수 있다.
게임에서 객체들의 위치를 리스트에 저장하고, 객체들의 위치가 겹치는지 확인하여 충돌 을 처리한다.
3. 이벤트 처리
키 입력, 마우스 클릭 등의 이벤트를 보관해야 할 때 리스트를 사용할 수 있습니다.
순차적으로 저장함으로서 이벤트의 발생 순서를 유지하여 효율적으로 처리할 수 있습니다.
4. 경로 탐색
몬스터나 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. 콜 스택
콜 스택은 게임의 함수 호출 및 반환을 추적하고 관리하는 데 스택을 사용할 수 있다.
예를 들면, 함수 호출 시 스택에 호출 정보를 저장하고, 함수 실행이 완료되면 스택에서 해당 정보를 제거하여 함수 호출의 순서와 관련된 로직을 처리할 수 있다.
이 사용법은 게임 엔진, 스크립트 시스템 등에서 만힝 사용되는 기능이다.
4. 큐[Queue]
큐는 선입선출(FIFO / First In First Out)구조로 데이터를 저장하고 접근하는 자료구조이다.
순서대로의 처리가 필요한 다양한 상황에서 사용될 수 있으며, 게임 개발에서 이벤트 처리, 애니메이션 관리, 비동기 작업 처리 등의 기능을 구현할 수 있다.
1. 이벤트 대기열
게임에서 이벤트를 순차적으로 처리해야 할 때 큐는 유용하게 사용된다.
이벤트 대기열을 구현하면 발생한 이벤트를 순서대로 저장하고 순서대로 처리할 수 있다.
또한 키입력, 마우스입력, 클릭 등의 다양한 이벤트를 Queue에 추가하고, 게임 로직에서 순차적으로 처리하는 방식으로 이벤트 시스템을 구현할 수 있다.
2. 트랜잭션 처리
게임 내에서 아이템 구매, 자원 거래 등의 *트랜잭션을 처리할 때 Queue를 사용하여 트랜잭션의 순서를 유지하고, 일괄 처리할 수 있다.
*트랜잭션(Transaction) 이란?
데이터베이서와 관련된 개념으로 하나 이상의 작업을 하나의 논리적 단위로 묶은 것을 의미한다.
이러한 작업들은 모두 성공적으로 완료되거나, 전혀 실행되지 않아야 하며 트랜잭션은 데이터 베이스 시스템에서 데이터의 일관성과 무결성을 보장하기 위해 사용된다.
