연구한 이야기

더 빠른 길찾기

고전적인 길찾기 방법, ASTAR 그래프 형태의 구조에서 목적지로의 경로를 찾는 방법에는 다익스트라, 벨만-포드 알고리즘 등이 존재합니다. 하지만 이러한 그래프 구조는 실제 MMORPG 게임서버 맵에서 적용하기 쉽지 않기에, 타일 구조로 맵을 변환시켜 길찾기를 시도하고는 합니다. 타일 구조에서의 길찾기 방식 중 가장 대표적이고, 유명하며 간단한 방식이 A-Star 길찾기입니다. 출발지로부터 연결된 모든 인접 노드를 통해 목적지로 탐색해나가며, 탐색하는 노드마다 가중치를 부여해 목적지로 가는 최단 경로를 찾아내는 방식입니다. ASTAR 구현 ASTAR 구현을 위해서는, 각 타일에 대한 ‘탐색한 정보’를 담을 노드 구조체와, 탐색했던 노드와 탐색할 노드를 담을 컨테이너 자료형 두 개가 필요합니다. struc..

레드블랙트리 구현 및 분석

개요 기본 이진트리와 레드블랙트리를 구현해보고, 시각화하여 확인할 수 있도록 합니다. 다른 컨테이너들과 성능을 비교해보고 게임 서버에서의 사용처를 분석합니다. 레드블랙트리 구현 이진탐색트리의 한계 이진탐색트리는 구현이 간편하지만, 다음 극명한 한계점들을 가지고 있습니다. 노드가 한쪽으로 쏠려서 관리될 수 있기에, 성능은 최악의 경우에 O(N)의 시간을 소모합니다. 이러한 경우 선형 탐색과 다를 바가 없기에, 기본 이진탐색트리를 사용하는 경우는 드뭅니다. 균형잡기 (밸런싱)과 회전 이러한 이진탐색트리의 한계를 극복하기 위해, 자체적으로 노드들의 높이를 맞출 수 있는 자가균형트리에서는 회전을 통해 노드간 밸런스를 맞춥니다. 코드와 주석이 문서 뒤에 위치합니다 레드블랙트리의 특징 레드블랙트리는 다음 네 가지의..