개요
A* 알고리즘을 2D Tile Map 환경에서 시뮬레이션해본다.
여기서는 기존에 1:1 관계가 아닌 N:M 관계의 길 찾기를 해본다.
사진 및 프로젝트 설명
자유롭게 맵을 제작 후 A* 알고리즘을 시뮬레이션한다.
Global.h 헤더 파일에 쥐의 이동속도와 휴리스틱 값을 바꿀 수 있는 세팅값이 있다.
먼저 다음과 같이 오른쪽에 있는 치즈, 쥐, 벽을 자유롭게 마우스로 왼쪽의 맵에 배치할 수 있다.
다수의 쥐와 다수의 치즈를 맵에 자유롭게 배치 후 쥐가 최단경로에 있는 치즈를 찾아가는 것을 확인할 수 있다.
길 찾기 메커니즘
기본적으로 길 찾기는 Astar.h/cpp 파일에 있는 StartFindPath() 함수에서 시작한다. 모든 쥐는 각자의 AStar 인스텐스를 가지고 있으며 이 인스텐스로 길 찾기를 시작한다.
StartFindPath() 함수에는 3가지 인자가 들어간다. 현재 자신의 위치 값(쥐), 목표값(치즈) 그리고 지형 데이터(내비게이션)를 받는다.
이다음에는 총 3가지 경우에 따른 길 찾기( 1:M, N:1, N:M) 관계에서의 작동을 확인하고 해당 경우에서 어떻게 작동하는지 확인한다.
1:M(쥐:치즈)
먼저 쥐가 한 마리 있고 다수의 치즈가 있는 경우이다. 다수의 목표들 중에서 최적의 경로를 찾아야 하기 때문에 월드 상에 있는 모든 치즈에 대해 길 찾기를 시도하고 우선순위 큐를 사용해 가장 길이가(Size)가 짧은 경로를 뽑아 그 방향으로 이동을 한다.
N:1(쥐:치즈)
이 경우는 여러 마리의 쥐가 하나의 치즈에 길 찾기를 시도하는 경우이다. 이 경우는 앞과 다르게 매 Frame 마다 길 찾기를 시도한다. 그 이유는 쥐는 정적 오브젝트가 아니고 동적 오브젝트 이기 때문에 매번 맵이 바뀌기 때문이다. 매번 길 찾기를 하는 것은 오버헤드가 크기 때문에 여러 가지 다양한 기법을 사용해서 오버헤드를 줄일 수 있다고 생각한다.
N:M(쥐:치즈)
마지막 경우는 여러 마리의 쥐와 다수의 치즈가 있는 경우이다. 이경우는 위 두 개의 경우를 합쳐서 진행한다.
모든 월드상에 있는 치즈들에 대해 길 찾기를 시도하고 가장 짧은 경로를 가진 치즈에 대해 이동을 시작하며 매 프레임마다 동적으로 바뀌는 월드에 맞춰서 길 찾기를 시도하는 가장 큰 타임 컴플렉스(시간 복잡도)를 가지는 경우이다.
후기
A* 알고리즘의 프로젝트에 마지막 부분까지 왔다. A*을 구현한 영상이나 혹은 다른 블로그의 글을 조금 봤는데 N:M의 경우를 탐색하는 것을 찾지 못해서 생각나는 방식으로 구현을 진행했다. 아마 효율적인 방법은 길 찾기를 시도하기 전에 먼저 직선의 경로를 확인해서 길 찾기 횟수를 줄이거나 탐색의 깊이(Depth Of Search)의 값을 적절하게 만들어서 너무 깊게 들어가지 않도록 하는 방법도 있다고 본다.
3D 길 찾기는 지형 데이터(내비게이션 메시)를 이용하면 좀 더 수월하게 찾을 수 있다고 하는데 아마 구현까지는 안 할 거 같다.
유의사항
* x86 환경에서 작동하며 화면 크기를 기존 크기에서 변경하면 마우스 클릭 오류가 있으니 가급적 기본 크기 화면으로 테스트 바랍니다.
* 해당 프로젝트는 예외 처리를 최소한으로 했기 때문에 버그가 있을 수 있습니다.
* 만약 이 블로그 글을 보고 잘못된 점이나 참고 가능한 것 등 공부가 가능한 게 있다면 댓글이나
메일(SnowFleur0128@gmail.com)로 보내주시면 감사하겠습니다.
출처 및 소스코드 링크
git:https://github.com/SnowFleur/2020-AStar-algorithm-Simulation
관련 글
[자료구조 알고리즘/탐색 알고리즘(Search)] - [알고리즘] A* 알고리즘
[자료구조 알고리즘/탐색 알고리즘(Search)] - [알고리즘] A* 치즈 찾기-맵 툴
[자료구조 알고리즘/탐색 알고리즘(Search)] - [알고리즘] A* 치즈 찾기-PathFinding
'자료구조 알고리즘 > 탐색 알고리즘(Search)' 카테고리의 다른 글
| [알고리즘] A* 치즈 찾기-PathFinding (0) | 2020.09.05 |
|---|---|
| [알고리즘] A* 치즈 찾기-맵 툴 (0) | 2020.08.29 |
| [알고리즘] A* 알고리즘 (0) | 2020.08.24 |
| [알고리즘] 백 트래킹(Backtracking) (0) | 2020.03.31 |
| [알고리즘] 다익스트라 알고리즘(Dijkstra algorithm) (0) | 2020.02.25 |
