푸지의 블로그

1. 목적

출발점에서 목적지까지 길 찾기를 하고자 할때 중간 중간 장애물을 피해가며 목적지까지 도달하는 알고리즘이 필요해졌다. 물론 길 찾기를 하는동안 목적지까지 도달 할 수 없는 경우도 판별이 가능할 것이다.

2. 개요

이 알고리즘의 아이디어는 어떠한 노드에 대하여 시작점으로부터 온 거리(g)와 앞으로 목적지까지 가는데 남은 거리(h : heuristic)를 더한 값(f)이 가장 적은 노드를 선택하여 목적지 까지 탐색하는 것이다.

여기서 중요한것은 목적지까지 남은 거리(h)를 적절하게 추정하여 설정하는 것이다.

그리고 두개의 목록으로 노드들을 관리해야 하는데 그것이 열린목록(Open list)과 닫힌목록(Close list)이다.

열린목록은 현재 조사중인 노드에 인접한 리스트로 최단거리로써 선택 가능성이 열려있는 노드들의 집합이다.

닫힌목록은 조사가 끝난 노드들의 집합으로 다시 조사할 필요가 없다.

3. 설계

각 노드는 위에서 언급한 g, h, f의 값과 자신의 노드id, 어디로부터 왔는지 부모노드의 id를 저장한다.

열린목록은 일반적인 list를 이용하는 것이 아닌 가장 최선의 방법일 가능성이 높은 즉, f의 값이 가장 작은 노드를 먼저 검색할 것이기 때문에 priority queue를 사용한다.

닫힌목록은 일반적인 queue로 생성한다.

전체적인 흐름은 시작노드를 열린목록에 넣는것으로 시작한다.

그리고 다음을 반복한다.

1. 열린목록의 노드를 꺼내어 접근할 수 있는 노드를 모두 검사한다.

2-1. 해당 노드가 닫힌목록에 있는 노드라면 무시한다.

2-2. 해당 노드가 열린목록에 있는 노드라면 f값을 비교해 더 작은 노드의 정보로 갱신한다.

2-3. 해당 노드가 열린목록 혹은 닫힌목록에 있지 않는 노드라면 열린목록에 넣는다.

3. 1번에서 꺼낸 노드는 닫힌목록으로 이동한다.

4. 목표 노드가 열린목록에 들어왔다면 중지한다.

나머지는 목표 노드로부터 부모노드를 찾아 시작노드까지 조사해 길을 완성한다.

만약 목표 노드가 들어오기전에 열린 목록이 먼저 비었다면 길이 없다는 뜻이다.

4. 예시

다음 예는 대각 이동 불가, h는 목표까지의 x의 차이와 y의 차이를 더한 값, 열린목록에서 같은 f값이 들어왔다면 먼저 들어온 노드에 우선권등 조건을 부여하였다.

소스코드 : https://github.com/puze/AStarAlgorithm/blob/main/AStarAlgorithm.cs

출처 : aidev.co.kr/game/501

en.wikipedia.org/wiki/A*_search_algorithm