대체 경로 탐색 알고리즘 조사

✅ 현 문제 인식

1. A* 알고리즘 자체 특성

• A*는 최단 경로를 보장하는 휴리스틱 기반 탐색 알고리즘이다.
• 최적해를 찾기 위해

  • g(n) = 시작점 → 현재 노드까지의 실제 비용

  • h(n) = 현재 노드 → 목표까지의 예상 비용

    을 합산한 f(n) = g(n) + h(n) 을 최소로 하는 경로를 탐색한다.

✅ 장점: 최단경로 보장, 비교적 단순 구현

✅ 단점: 맵이 크거나 장애물이 많으면 탐색량이 급격히 늘어난다.

2. 현재 프로젝트 적용상 문제점

(1) 복잡한 실내 환경

• 실내 공간은 벽, 교실, 계단, 출입구 등 복잡한 장애물이 존재한다.

• 특히 복도 구조가 길게 뻗어있고,

  노드들이 매우 규칙적이지 않기 때문에

  A*가 불필요한 경로까지 전부 탐색할 위험이 있다.

(2) 맵 크기 및 확장성 이슈

• 현재 6층 건물 기준으로는 A*만으로 충분하지만,

• 향후 벡스코처럼 초대형 실내장으로 확장할 경우,

  탐색 시간과 메모리 사용량이 문제가 될 수 있다.

(3) 경로 자연스러움(UX) 문제

• A*는 격자 기반으로 이동할 때

  경로가 뚝뚝 끊기는 경우가 많다. (ex. ㄱ자 회전, 직각 코너)

• AR 내비게이션에서는 사용자가 직관적으로 이해하기 쉬운,

  부드럽고 직선적인 경로가 요구된다.

(4) 실시간 반응성