📄 A* Algorithm
✏️ Pseudo code
1. P = 시작점
2. P에 f, g, h 할당
f = g + h g = 출발점부터 현재 노드 위치까지 거리 h = 현재 노드 위치부터 목표점까지 heuristic한 거리 (≈ 직관적으로 짧아보이는 거리)3. (Open) 리스트에 P 넣기
4. B = Open 리스트에서 가장 낮은 f 값을 가진 노드
a. B가 목표점이면, 경로 완성 b. Open 리스트가 비었으면, 목표점까지 경로가 존재하지 않음5. C = B에 연결된 노드
a. C에 f, g, h 값 할당 b. (Open/Close) 리스트에서 C가 있는지 체크 1. 있으면, 더 낮은 f 값으로 경로 업데이트 2. 없으면, C를 Open 리스트에 넣기 c. 5번으로 돌아가서 B에 연결된 모든 노드를 대상으로 진행6. 4번으로 돌아감
자료 출처
노력하는 게임 개발자