[게임 프로그래머 입문 올인원] A* 길찾기 알고리즘 + Maze project (62강)

A. A*

1. A* 알고리즘

a. A*란?

🌟 주어진 시작 지점에서 목표 지점까지의 최적 경로를 찾는 데 사용

 

• 그래프 검색 및 경로 탐색 알고리즘의 일종
• 출구의 개념을 알아 출구로 갈수록 가산점이 있음 
• 그래프 내에서 가장 짧은 경로를 찾는 데 사용되며, 다양한 문제 도메인에서 널리 사용
• 우선순위 큐를 사용하여 구현

 

b. A*의 두가지 개념

1. 비용 기능 (Cost function): 각 노드에 대해 시작 지점부터의 비용을 나타내는 함수. 즉, 입구에서부터의 비용
2. 휴리스틱 (Heuristic): 각 노드에서 목표 지점까지의 추정 비용을 나타내는 함수. 휴리스틱은 종종 "거리" 또는 "비용"을 기반으로 함. 즉, 출구에서부터의 비용

 

c. 알고리즘

이 비용 기능과 휴리스틱을 사용하여 각 노드의 "평가 함수"를 계산

평가 함수가 가장 낮은 노드를 우선적으로 탐색

목표 지점에 도달할 때까지 계속해서 노드를 확장하고, 최적 경로를 찾음

 

d. 한계점

휴리스틱이 항상 실제 최적 경로를 제공하는 것은 아님

그러나 A*는 매우 효율적이라 광범위하게 사용됨

 

 

 

---

B. Maze Project 

1. A* 기반 길찾기

a. CalculatePath_AStar()

1) 기초 틀 생성하기

 

마지막 AStar 구현

 

위에 것 들은 사용 안함

 

알고리즘 설명

 

꼭 g랑 h를 동시에 사용해야하는건 아니고 

우선순위로 생각하는 (시작점에서 계산할건지, 혹은 목적지에서 계산할건지) 것에 따라 하나만 사용할 수 있음

 

우선순위 큐 기본 노드 준비

 

2) 기본정보 작성

 

기본적인 행동 구현하고

 

상하좌우 코스트는 기본 10

 

맵의 크기 getsize

 

가장 좋은 비용 찾기 2차배열

 

어떤 좌표가 방문까지 끝냈는지의 여부

 

부모 추적 용도

 

3) 예약시스템 구현

 

초기값 세팅,  시작점 0, 목적지 (y의 차이 + x의 차이 ) * 10 : 언제든지 변경가능

 

예약시스템이 비었는지 확인 (후보 찾기)

 

위 break; 이어서 진행

 

4) 대각선까지 지원해야 한다면 

 

정보 추가

 

dir 비교를 8로 수정

 

 

 

---

출처 : https://www.inflearn.com/course/%EA%B2%8C%EC%9E%84-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8-%EC%9E%85%EB%AC%B8-%EC%98%AC%EC%9D%B8%EC%9B%90-rookiss#curriculum

[게임 프로그래머 입문 올인원] C++ & 자료구조/알고리즘 & STL & 게임 수학 & Windows API & 게임 서버 -