[Unity] A* 알고리즘 2d 길찾기 설명

2d 로그라이크 게임을 제작 중 최적의 길을 찾는 방법에 대하여 검색하다가 A* 알고리즘을 알게 되었다. 기본적으로 A* 알고리즘에는 시작 지점과 끝 지점을 알고 있다는 전제하에 실행이 된다. 그리고 A* 알고리즘에는 G, H, F, neighborNode, OpenList, ClosedList, FinalList라는 단어들을 기본적으로 알아야 한다.

 

• G = 이동했던 거리를 저장한다.
• H = 현재 노드를 기준으로 장애물을 무시한 가로 세로 최단 거리를 저장한다.
• F = G + H 값을 저장한다.
• neighborNode = 기준 타일에서 갈 수 있는 타일들을 neighborNode이라고 한다.
• OpenList = 검색대상들을 집어넣는 리스트
• ClosedList = 검색을 마친 노드들을 집어놓는 리스트
• FinalList = 시작지점부터 목표지점까지 최단경로가 담긴 리스트

A* 알고리즘 동작 방식

• 기준 노드에서 neighborNode가 있는지 검사한다.
• 해당 neighborNode의 G, H, F 값을 설정하고 가장 적은 F를 가지고 있는 노드를 기준 노드로 초기화한다. (만약 F의 값이 같다면 H값이 작은 값을 기준 노드로 초기화한다.)
• 위의 방법을 기준 노드가 목표 노드가 될 때까지 실행한다.

설명을 도와줄 그림

• S = 시작 노드
• T = 목표 노드
• 회색 = 벽

A* 알고리즘 동작 - 1번째

S(G = 0, H = 40, F = 40)

neighborNode = A

OpenList = A

ClosedList = S

FinalList 

 

A* 알고리즘 동작 - 2번째

A(G = 10, H = 30, F = 40)

neighborNode = B

OpenList = B

ClosedList = S, A

FinalList = A

 

A* 알고리즘 동작 - 3번째

B(G = 20, H = 20, F = 40)

neighborNode = C

OpenList = C

ClosedList = S, A, B

FinalList = A, B

 

A* 알고리즘 동작 - 4번째

C(G = 30, H = 10, F = 40)

neighborNode = T

OpenList = T

ClosedList = S, A, B, C

FinalList = A, B, C

 

이렇게 4번의 과정을 거치면 S에서 T까지 가는 최단 거리 A-B-C를 구할 수 있다.