주어진 목표 꼭짓점까지 가는 최단 경로임을 판단할 수 있는 테스트를 통과하는 그래프/트리 탐색 알고리즘
현실 세계를 2D grid로 표현하여 Grid Map 상에서 최단 경로를 탐색, 결정
8 방향에 대한 Cost를 계산해서 출발지점에서 목표지점까지의 최적 경로를 찾는 알고리즘
트리 구조
여러 노드가 한 노드를 가리킬 수 없는 구조
최상위 노드 = 루트 노드
부모 노드 / 자식 노드 관계 -> 최단 경로 선택에 활용, 빠른 경로 탐색 가능
A* 알고리즘 Grid
가로, 세로 n 칸으로 나눔
격자 크기에 따른 경로 생성의 성능 영향
격자 단위가 크면 -> 계산 속도 빠름, 섬세한 경로 생성을 못함
격자 단위 작으면 -> 섬세한 경로 생성, 탐색 격자 개수가 많아 계산량이 많아짐
A* 알고리즘
각 노드마다 부모, 자식 노드의 관계를 맺으며 진행
가장 작은 F 스코어를 가진 것을 선택
F = G + H
F : 현재까지 이동하는데 걸린 비용과 예상 비용을 합친 총 비용
G : 시작점으로부터 현재 사각형까지의 경로를 따라 이동하는데 소요되는 비용
H : 현재 사각형에서 목적지까지의 예상 이동 비용(장애물 등 무시하고 예상 거리 산출 : 맨하탄 방법)
Grid 단위 개념과 Cost에 관한 이해만 동반된다면 어렵지 않게 Application에 적용할 수 있음
- 탐색영역 파악
- 경로 채점
- 계속적 탐색
- 경로 선택
