[Algorithm] A* 알고리즘

■ 들어가기 전

BFS의 두 가지 문제 중 가장 먼저 발견한 노드들을 방문한다는 한계점을 보완하기 위해 (1) 가중치 그래프(Weighted Graph)와 (2) 우선순위큐 (Priority Queue)를 사용한 다익스트라(Dijikstra) 알고리즘이 탄생했다.

 

https://yjhdevelopdiary.tistory.com/196

[Algorithm] 다익스트라(Dijikstra) 알고리즘

하지만 다익스트라도 또 다른 BFS의 한계점은 보완하지 못했는데 그것은 '목적지'를 모른다는 것이다.

그렇기 때문에 모든 방향으로 이어지는 노드들을 여전히 모두 탐색하고 있으므로 탐색비용이 그래프의 크기가 커질수록 비례하며 증가할 것이다.

 

이러한 문제를 해결하기위해 다익스트라와 유사하지만 목적지에 대한 추가적인 정보 (휴리스틱 혹은 예상 비용)를 사용하여 탐색 과정 중 최적의 경로에 대한 우선순위를 높일 수 있게 되었다.

 

[근데 왜 Astar인가?]

ChatGPT왈:

"Star"는 알고리즘이 휴리스틱 함수를 사용하여 경로를 평가하고 선택하는 데 있어서 "최고의" 경로를 찾는 데에 중요한 역할을 하는 것을 의미합니다. A* 알고리즘은 휴리스틱을 사용하여 각 노드의 예상 비용을 계산하고 이를 기반으로 최적의 경로를 선택합니다.

 

"A"는 "Admissible"를 나타냅니다. 이는 알고리즘이 항상 최단 경로를 찾는다는 것을 의미합니다. 즉, 알고리즘이 최적의 솔루션을 찾을 수 있다는 보장이 있습니다.

 

따라서 "A*"는 "A star"의 약어로, 최적의 경로를 찾기 위해 휴리스틱을 사용하는 동시에 항상 최단 경로를 찾는 알고리즘임을 나타냅니다.

■ A Star

일반 노드와 달리 아래와 같이 f, g, pos값을 갖는다. 

(1) F = 최종 점수. 작을수록 좋다

(2) G = 시작점에서 해당 좌표까지 이동하는데 드는 비용

(3) H = 목적지에서 해당 좌표까지 이동하는데 드는 비용

 

[알고리즘]

알고리즘의 시작은 이전에 우수법을 이용한 미로 탐험 알고리즘에서 추가로 몇 개만 등록해주면 된다.

https://yjhdevelopdiary.tistory.com/192

[C++] 동적 미로 생성, 우수법 탈출 AI

 

방향이 Up, Left, Down, Right 네 가지가 있었으나 이제 아래와 같이 대각선도 추가 해주는 것이다. 그리고 각 방향에 따라 소요되는 비용은 본인이 적절하게 정하면 된다.

 

곧바로 다익스트라와 동일한 원리를 이용한다. 가중치에 따라 제일 최적했던 best case 노드들을 들고 있는 것.

이를 위해 best 이중 벡터를 이용한 것이고 시작지점까지 추적할 수 있도록 parent 이중 벡터를 선언했다.

 

closed는 실제로 방문한 노드들을 캐싱해주는 용도인데 사실 이게 없어도 아래 계산하는 부분에서 다 걸러지기 때문에 이건 기호에 따라 추가할지 말지 하면 될 것이다.

 

아래 사진의 순서는 이와 같다

(1) 먼저 제일 좋은 후보 노드를 추출한다.

(2) closed (이미 방문한 노드 컨테이너)에 포함되어 있다면 다음으로 넘어가준다

(3) 해당 좌표의 캐싱된 F (총 점수)를 방금 막 추출한 노드의 F값과 비교하여 현재 방문한 노드의 F가 더 낮을 경우 [우수할 경우] 코드를 이어 진행한다.

 

(4) 방문 한 노드 좌표를 기준으로 모든 방향에 대해 for문 내 코드를 수행.

    (4-1) 모든 방향을 기준으로 각각 다음 좌표가 될 포지션을 계산해주고

    (4-2) 해당 포지션이 갈 수 있는 곳이라면 g와 h값을 계산 해준다.

    (4-3) 다른 경로에서 더 빠른 길을 찾았다면 스킵해주고 아니라면 우선순위 큐에 해당 노드의 정보를 담아준다.

    (4-4) 목적지에 도달할 때까지 반복한다.

 

그 이후 추적을 위해 심어놨던 parent 벡터에 내포한 포지션 정보들을 역추적하면서 _path에 캐싱해주면 A*알고리즘 완성이다.

[GIF]

대각선 방향을 추가해줬더니 위와 같이 대각선 이동이 가능해진 것을 볼 수 있다.

 

[참고 및 추천]

https://www.inflearn.com/course/%EA%B2%8C%EC%9E%84-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8-%EC%9E%85%EB%AC%B8-%EC%98%AC%EC%9D%B8%EC%9B%90-rookiss/dashboard

[게임 프로그래머 입문 올인원] C++ & 자료구조/알고리즘 & STL & 게임 수학 & Windows API & 게임 서버 |