길찾기 알고리즘에 대해 알고 있는 것이 있나요?
- 주어진 월드 상에서 갈 수 있는 정점과 갈 수 없는 정점을 구분해, 특정 목표 지점까지 갈 수 있는 경로를 찾는 방법
로컬 방식과 글로벌 방식
- 로컬 방식은 자신의 주변에서 인식할 수 있는 정보만을 활용하여 길찾기를 실행
(현재 정면에 장애물이 있는지 없는지 판단) - 글로벌 방식은 전체 영역을 파악해 길찾기를 실행
Crash and Turn
- 로컬 방식의 길찾기
- 전진하다가 전진할 수 없는 곳을 만났을 때 왼쪽 또는 오른쪽으로 회전하여 전진
- 다시 벽이 없어지면 기존 진행 방향으로 전진
- 장애물이 convex 경우에만 무조건 길을 찾을 수 있음
Dijkstra Algorithm
- 최단거리는 각각의 노드에서의 최단거리로 이루어져 있다는 발상으로 전개
- 출발 노드를 기준으로 연결된 노드들을 점검하며 가장 비용이 적은 방식을 탐색
- 이를 반복하며 전체 비용을 갱신하여 최단거리를 계산
- 시각화 했을 때 시작 지점에서 방사형으로 퍼져나가며 길찾기를 수행하는 것으로 표시
A* Algorithm
- 휴리스틱 방식을 사용한 길찾기
- 추정치를 통해 가장 그럴듯한 방향으로 탐색을 실시하고 길찾기에 실패할 경우 다시 반복
- 휴리스틱 함수를 통해 출력되는 값이 가장 작은 노드를 최단거리일 것으로 추정하고 노드를 탐색하므로 해당 함수의 정확도가 성능에 큰 영향을 미침
- 노드들을 휴리스틱 함수의 결과 값에 따라 우선순위 큐에 담고 큐에 저장된 우선 순위에따라 길찾기를 실행
