[Algorithm] A* 알고리즘

게임에서 목적지에 대한 길을 찾는 알고리즘을 사용할 때를 위해 A* 알고리즘을 학습해 놓자.

(참고)

잘 설명해주는 유툽강의 (Sebastian Lague) : 아래 이미지들 출처

A* 알고리즘에는 우선

열린목록 (Open List ) // 거리를 고려할 수 있는 갈 수 있는 곳

닫힌목록 (Close List) // 가장 짧은 거리를 가진 곳

부모 // 각 노드들이 속해있는 부모

가 존재하게 된다.

F = G + H

길찾기를 위해 판단할 값 = 닫힌 목록에 있는 사각형과의 거리 + 목적지까지의 거리(장애물 고려X)

목적지에 도착하고서는 목적에서부터 부모 사각형을 따라서 거슬러 올라가는 길이

최단거리가 된다.

초록색들이 열린 목록

빨간색이 닫힌 목록에 추가되어 고려되었던 곳들

파란색이 최종 닫힌목록을 따라 목적지에 도착했을시 최단 거리 이다.

하지만, 맵의 크기가 크거나 길이 상당히 긴 경우에는 느려질 수도 있다.

때문에 구간구간이 존재하는 방법에서 사용할 수 있다.

아래는 쉐도코딩으로 나타내는 A 스타 알고리즘이다.

▼ 동영상 따라서 구현해본 결과물 ( 회색: 지나갈 수 있는 길 , 빨간색 : 장애물이있는 길 , 검정색 : 최단 거리)

NOTE.COM