글그리 블로그

길찾기 알고리즘 중 하나인 A* 알고리즘에 대해 알아보자. 단순히 2D 타일맵에만 적용할 수 있다고 생각했는데 원리를 알고보니 가중치로 연결된 그래프에 모두 적용할 수 있는 방법이었다. 복잡한 공간도 다각형으로 분할한다면 A* 알고리즘을 적용시켜서 길을 찾을 수 있다. A* 알고리즘은 닫힌 목록과 열린 목록이 있고, 이 두 목록을 갱신하면서 길을 찾아간다. 현재 위치에서 갈 수 있는 위치에 대해 G, F, Parent를계산해서 열린 목록에 넣고, 열린 목록에서 최소 F값을 가지고있는 위치를 닫힌 목록에 넣은 후 반복한다. G : 해당 위치로 이동하기 위해 필요한 비용 F : G + 해당 위치에서 목표지점까지의 예상거리 Parent : 해당 위치로 오기 직전 위치 간단한 2D 길찾기 예제를 통해서 원리를 ..