jps

더 빠른 길찾기

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