관련글
서론
여러 프로젝트를 진행하다 보면, 최단 경로를 찾는 코드를 작성해야할 때가 있습니다. 미로 찾기 같은 경우가 바로 그런 경우이죠. 게임에서도 마찬가지로 AI나 NPC들이 자동으로 목표 지점까지 이동하는 것도 바로 최단 경로 찾기 알고리즘을 이용하여 찾는 것이고, T map / Kakao map 또한 이러한 경로 찾기 알고리즘 기반으로 출시된 서비스들이죠.
이처럼 최단 경로 찾기 알고리즘은 우리 실생활에 자연스래 스며들어 있습니다. 이렇게 우리 생활 가까이에 경로 찾기 알고리즘이 존재하는데, 그 종류에는 어떤 것들이 존재할까요? 많이들 아시는 것이 다익스트라 알고리즘, A star 알고리즘이 있을 것입니다.
이번 시리즈에서는 그 중에서 경로 탐색의 기본적인 원리와 A star 알고리즘은 어떤 원리로 최단 경로를 찾고, C 언어로 어떻게 구현하는지 알아보도록 하겠습니다.
경로를 탐색하는 방법
A star
참고 자료
최단 경로 탐색 – A* 알고리즘 – GIS Developer
A*(A star) 알고리즘 정의 및 개념 (tistory.com)
경로를 탐색하는 방법
다음과 같은 경로들이 존재한다고 가정해 봅시다.
가정:
여러분은 붉은색 지점에서 푸른색 지점으로 이동하려고 합니다. 여러분들은 여러분 자신의 위치와, 푸른색 지점의 위치를 알고 있습니다. 여러분들은 자신의 위치와 붉은색 지점까지의 직선 거리, 푸른색 지점까지의 직선 거리를 계산할 수 있습니다. 또한 여러분들은 붉은색, 푸른색, 노란색 지점으로만 움직일 수 있습니다.
방식:
여러분들은 시작 점인 붉은색 지점에서 3가지 경로를 통해 1, 2, 3 지점에 갈 수 있습니다. 최단 거리를 계산하기 위해 세 지점의 상황을 계산합니다.
우선 어느 길이 가장 빠른 길인지 모르기에 A 경로를 통해 1 지점의 상황을 봅니다.
1 지점을 방문한 여러분들은 현재 걸어 온 거리가 10m, 목적지까지의 직선 거리가 10m라는 것을 계산합니다.
그 다음으로 시작 점에서 다시 시작하여 이번에는 B 경로를 통해 2 지점의 상황을 계산합니다.
2 지점을 방문한 여러분들은 현재 걸어 온 거리가 6m, 목적지까지의 직선 거리가 6m라는 것을 계산합니다.
마지막으로 시작 점에서 다시 시작하여 이번에는 C 경로를 통해 3 지점의 상황을 계산합니다.
3 지점을 방문한 여러분들은 현재 걸어 온 거리가 6m, 목적지까지의 직선 거리가 6m라는 것을 계산합니다.
여기까지 현재 여러분들은 시작점 위치해서 주변 지점의 상황을 계산했습니다.
즉, 여러분이 방문한 지점(탐색 완료한 지점)은 아직까지는 시작점입니다.
| 탐색 완료한 지점 |
| 시작 점 |
지금까지 계산한 바로는 여러분들이 갈 수 있는 지점은 다음과 같습니다.
| 갈 수 있는 지점 | 1 지점 | 2 지점 | 3 지점 |
| 걸어 온 거리 | 10m | 6m | 6m |
| 도착지까지의 직선 거리 | 10m | 6m | 6m |
| 시작점에서 도착지까지 총 예상 거리 |
20m | 12m | 12m |
위의 갈 수 있는 지점표를 보시면 2 지점, 3 지점을 경유한 경로가 최단 경로라고 예측할 수 있습니다. (실제로는 아닐 수 있습니다.)
즉, 여러분은 1 지점보다는 2 지점 또는 3 지점을 경유하겠죠.
일단 2 지점으로 이동해 봅시다.
2 지점에서 여러분들이 확인한 지점은 3 지점과, 녹색 지점 그리고 붉은색 지점입니다.
여기서 붉은색 지점에서 왔기 때문에 붉은 지점은 탐색 범위에서 제외합니다.
우선 초록색 지점의 상황을 계산합니다.
여기서 초록색 지점은 장애물이기 때문에 더이상 여러분들은 진행할 수 없습니다.
다음으로 3번 지점의 상황을 계산합니다.
지금까지 온 거리는 6.1m, 앞으로 남았을 거라 예상되는 거리(=>직선거리)는 6m입니다.
여기까지 현재 여러분들은 시작점 위치해서 주변 지점의 상황을 계산했습니다.
| 탐색 완료한 지점 |
| 시작 점 2 지점 |
지금까지 계산한 바로는 여러분들이 갈 수 있는 지점은 다음과 같습니다.
| 갈 수 있는 지점 | 1 지점 | 2 지점을 경유하여 3 지점으로 | 3 지점 |
| 걸어 온 거리 (G) | 10m | 6.1m | 6m |
| 도착지까지의 직선 거리 (H) | 10m | 6m | 6m |
| 시작점에서 도착지까지 총 예상 거리 (F) |
20m | 12.1m | 12m |
여기서 여러분들은 2 지점을 경유하여 3지점으로 왔을 때 거리가 시작점에서 바로 3 지점으로 왔을 때의 거리보다 크다는 것을 알 수 있습니다.
즉 2 지점을 경유하여 3 지점으로 왔을 때의 G = 6.1 > 3 지점 바로 G = 6이라는 거죠.
따라서 여러분들은 시작 -> 2 -> 3보단 시작 -> 3이 더 효율적이라는 것을 깨달으셨고, 갈 수 있는 지점의 목록을 수정합니다.
| 갈 수 있는 지점 | 1 지점 | 3 지점 | |
| 걸어 온 거리 (G) | 10m | 6m | |
| 도착지까지의 직선 거리 (H) | 10m | 6m | |
| 시작점에서 도착지까지 총 예상 거리 (F) |
20m | 12m |
위의 갈 수 있는 지점표를 보시면 3 지점을 경유한 경로가 최단 경로라고 예측할 수 있습니다. (실제로는 아닐 수 있습니다.) 즉, 여러분은 1 지점보다는 3 지점을 경유하겠죠.
일단 3 지점으로 이동해 봅시다.
3 지점에서 여러분들이 확인한 지점은 2 지점과, 도착지점 그리고 붉은색 지점입니다.
도착지점을 확인했기 때문에 여러분들은 시작점 -> 3 번 지점 -> 도착점이 최단 경로라는 것을 알 수 있습니다.
A star
A star 알고리즘은 위에서 언급한 방식을 구현한 알고리즘입니다.
위의 상황과 같이 갈 수 있는 지점(=openList)을 계속해서 업데이트하고, 이미 탐색이 완료된 지점(=closedList)을 업데이트 합니다.
다음으로 진행할 지점은 갈 수 있는 지점(=openList)에서 총 예상 거리(F)가 가장 작은 지점을 가져와 그 지점으로 이동합니다. 해당 지점에서 주위의 갈 수 있는 지점의 정보를 갈 수 있는 지점(=openList)에 저장합니다. 이때, 기존의 갈 수 있는 지점(=openList)에 해당 위치가 존재하면 걸어 온 거리(G) 값을 비교하여 더 작은 것으로 바꿉니다.
마지막으로 해당 지점은 이제 방문했기 때문에 탐색이 완료된 지점(=closedList)에 등록합니다.
이런 방식으로 진행하다, 도착지를 만나게 되면 최단 경로가 계산된 것입니다.
참고 자료(개념 설명은 여기가 더 잘 되어 있습니다.)
Continue
'알고리즘' 카테고리의 다른 글
| A star 경로 알고리즘 (Part2 관련 헤더파일) (0) | 2021.09.29 |
|---|
