인공지능) Pathfinding

길 찾기 시나리오 아주 중요합니다.

문제를 통해 공부합시다.

Question. Goal에 도달하기 위한 방법은?

Solutions

○ BFS (Breadth First Search)

: 기본적인 방식

- 그래픽 알고리즘의 넓이 우선 방식

- 짧은 경로라면 문제 없음

- 너무 많은 셀을 검색하기 때문에 비용이 큼

○ A*

: Heuristic search algorithm

--> 근사할 수 있는 알고리즘

--> 시작 노드와 골 노드를 이용하여 짧은 거리를 계산해나간다.

--> h(n) : n으로부터 골 까지의 거리

--> 두 개의 측정법 사용

- Euclidean distance

- Manhatten distance

○ 두 탐색 방법 비교

○ 기타 탐색 방법 

- 직접 시뮬레이션 : 링크

- 지도 사례 : 링크

- 슈퍼 마리오 A* : 링크

- 슈퍼 마리오 A* 소스 : 깃헙