A* 알고리즘으로 원형 장애물 사이를 누비는 최적 경로 찾기

Circular Obstacle Pathfinding (2017)

A* 알고리즘은 그리드 맵뿐만 아니라 어떤 그래프에서도 동작합니다. 이 글은 원형 장애물로 가득한 숲을 탐색하는 문제에 A*를 적용하는 방법을 설명합니다. 경로를 직선 구간(서핑 엣지)과 곡선 구간(허깅 엣지)으로 나누고, 이를 그래프로 변환하는 '탄젠트 가시성 그래프' 기법을 소개합니다. 두 원 사이의 내부/외부 비탄젠트를 계산하고, 다른 장애물에 막히는 엣지를 제거하는 과정을 상세히 다룹니다. 또한 장애물이 겹치거나 접촉하는 경우와 Minkowski 확장을 통한 가변 에이전트 반지름 처리 등 고급 주제도 함께 살펴봅니다.