[실용적인 자료구조] 게임 Way Point 저장을 위한 자료구조

게임에서 Way Point(웨이포인트)를 저장하기 위해 적합한 자료구조는 위치 정보, 연결 정보 그리고 추가적인 메타 데이터를 효율적으로 다룰 수 있어야 합니다. 웨이포인트는 게임 내에서 특정 지점(좌표)이나 목적지로 이동할 때 중요한 요소로, 경로 찾기나 캐릭터 이동 등에 사용됩니다. 이에 따라 웨이포인트 데이터를 저장하고 관리하기 위한 몇 가지 자료구조를 추천합니다.

1. 리스트(List) 또는 배열(Array)

추천 상황: 간단한 직선 경로, 순차적 이동이 필요한 경우

리스트나 배열은 가장 간단한 자료구조로, 웨이포인트를 순서대로 저장할 수 있습니다. 웨이포인트를 순차적으로 탐색하거나 고정된 경로에 따라 이동해야 하는 경우 적합합니다. 각 웨이포인트는 좌표 정보(예: (x, y, z))와 추가적인 정보(예: 이름, 체크포인트 여부 등)를 포함할 수 있습니다.

예시:

waypoints = [
    { "name": "Start", "position": (0, 0, 0), "isCheckpoint": False },
    { "name": "Midpoint", "position": (10, 5, 3), "isCheckpoint": False },
    { "name": "End", "position": (20, 10, 6), "isCheckpoint": True }
]

장점:

• 구현이 간단하고, 작은 규모의 웨이포인트 관리에 적합
• 순차적인 이동이나 간단한 경로 설정에 효과적

단점:

• 비순차적 경로 탐색이나 복잡한 네트워크 경로 관리에는 부적합
• 웨이포인트를 추가하거나 삭제할 때 비효율적

2. 그래프(Graph)

추천 상황: 복잡한 경로 탐색, 비순차적 이동이 필요한 경우

웨이포인트 간의 경로가 복잡하게 얽혀 있는 경우, 그래프 자료구조가 적합합니다. 그래프는 각 웨이포인트를 노드(Node)로, 웨이포인트 간의 연결을 엣지(Edge)로 표현합니다. 노드에는 위치 정보와 추가적인 데이터를 저장하고, 엣지에는 경로의 거리나 이동 조건 등의 정보를 저장할 수 있습니다.

예시:

waypoints = {
    "A": { "position": (0, 0, 0), "neighbors": {"B": 5, "C": 10} },
    "B": { "position": (10, 5, 3), "neighbors": {"A": 5, "C": 3} },
    "C": { "position": (20, 10, 6), "neighbors": {"A": 10, "B": 3} }
}

장점:

• 비순차적 이동이 가능하며, 경로 탐색 알고리즘(예: 다익스트라 알고리즘, A* 알고리즘)을 쉽게 적용할 수 있음
• 웨이포인트 간의 다중 경로 설정이 가능
• 확장성 좋음, 많은 웨이포인트와 복잡한 경로 설정이 가능

단점:

• 간단한 경로의 경우에는 불필요하게 복잡할 수 있음
• 관리가 복잡해질 수 있으며, 노드 간 연결 정보를 정확히 유지해야 함

3. 큐(Queue)

추천 상황: 실시간 경로 재계산, FIFO 방식으로 경로를 관리해야 할 때

웨이포인트를 실시간으로 처리하거나, 우선 순위에 따라 경로를 선택해야 할 경우 큐(Queue)를 사용할 수 있습니다. 큐는 선입선출(FIFO, First In First Out) 방식으로 웨이포인트를 처리하므로, 캐릭터가 순차적으로 경로를 따라가야 할 때 유용합니다.

예시:

from collections import deque

waypoint_queue = deque([
    { "name": "Start", "position": (0, 0, 0) },
    { "name": "Checkpoint", "position": (15, 10, 5) },
    { "name": "End", "position": (25, 20, 10) }
])

장점:

• 실시간으로 웨이포인트를 관리하고 처리하기 용이
• 간단한 구조로서 경로 처리 속도가 빠름

단점:

• 순차적인 경로 처리에 적합하지만, 복잡한 경로 계산에는 부적합
• 경로 재계산이나 비순차적 이동을 지원하지 않음

4. 우선순위 큐(Priority Queue)

추천 상황: 특정 웨이포인트에 우선 순위를 부여하거나, 특정 조건에 따라 이동해야 할 때

우선순위 큐는 각 웨이포인트에 우선순위를 부여해 가장 중요한 웨이포인트를 먼저 처리하도록 설계된 자료구조입니다. 웨이포인트 간의 거리를 계산할 때, 또는 특정 지점을 우선적으로 처리해야 할 때 유용합니다. 예를 들어, 목적지와의 거리나 위험 수준에 따라 우선순위를 다르게 설정할 수 있습니다.

예시:

import heapq

waypoints = []
heapq.heappush(waypoints, (1, { "name": "End", "position": (25, 20, 10) }))
heapq.heappush(waypoints, (3, { "name": "Start", "position": (0, 0, 0) }))
heapq.heappush(waypoints, (2, { "name": "Checkpoint", "position": (15, 10, 5) }))

장점:

• 각 웨이포인트에 우선순위를 적용할 수 있어, 중요한 지점이나 목표 지점을 먼저 처리 가능
• 경로 탐색에서 최단 경로 알고리즘(예: A*) 구현에 효과적

단점:

• 우선순위 설정이 필요하며, 단순 경로 관리에는 불필요할 수 있음

5. 딕셔너리(Dictionary)

추천 상황: 웨이포인트에 고유한 이름을 부여하고, 해당 이름으로 쉽게 검색할 수 있는 경우

웨이포인트를 키-값 쌍으로 저장해 고유한 이름을 사용하여 접근하고 관리해야 하는 경우에는 딕셔너리가 적합합니다. 각 웨이포인트는 고유한 키로 저장되고, 해당 키로 빠르게 검색할 수 있습니다.

예시:

waypoints = {
    "start": { "position": (0, 0, 0), "isCheckpoint": False },
    "midpoint": { "position": (10, 5, 3), "isCheckpoint": True },
    "end": { "position": (20, 10, 6), "isCheckpoint": True }
}

장점:

• 빠른 검색 속도 (키를 이용한 O(1) 접근)
• 각 웨이포인트에 대한 고유한 식별이 가능

단점:

• 웨이포인트의 순서가 중요할 경우 부적합
• 복잡한 경로 관리에는 사용이 제한적

---

결론

• 리스트나 배열은 순차적인 경로 저장에 적합하며, 간단한 웨이포인트 관리에 좋습니다.
• 그래프는 비순차적이고 복잡한 경로 탐색에 효과적이며, 다양한 경로 선택이 필요한 경우 유용합니다.
• 큐는 순차적인 경로 처리를 원활히 하며, 실시간 이동 경로 관리에 좋습니다.
• 우선순위 큐는 특정 웨이포인트에 중요도를 부여하여 우선적인 처리와 최단 경로 탐색에 적합합니다.
• 딕셔너리는 고유한 이름을 부여하고 빠르게 접근할 수 있는 자료구조로, 검색이 중요한 경우에 적합합니다.

게임의 웨이포인트 시스템의 복잡성에 따라 적합한 자료구조를 선택하면 됩니다. 복잡한 경로 탐색이 필요한 경우 그래프를, 순차적인 경로 관리가 필요하다면 리스트나 큐를 사용하면 좋습니다.