A* Algorithm -1

게임에서 쓰이는 알고리즘 중에서 가장 흔하게 쓰이는 것이 A* 알고리즘이다.

 

근데 A* ALgorithm이 뭐냐고 물어보면.. 암시롱 모른다고 나오니까 차근차근 알아가보자

 

기본적으로 그래프로 그려진 곳에서 쓰인다.

그래프는 노드와 엣지(선)으로 연결되어 있다.

가중치는 엣지에 부여된 값으로, 이동할때 그만큼의 비용이 든다는 뜻이다. 

 

그래서 가장 적은 비용을 지불해서 시작~목적지 까지 최소한의 비용으로 도달하는게 핵심이다.

 

시작 노드부터 현재 노드까지의 비용을 g(n) 이라고 하고, 현재~ 목표까지의 비용을 h(n) 이라고 할때.

 

f(n) = g(n) + h(n) 이다. 

 

여기서 h(n)은 휴리스틱 함수라고도 하며, 이 함수의 설계에 따라서 알고리즘의 성능이 결정된다. 

그래서 맨해튼 거리 함수, 유클리디안 거리 함수 등등 으로 구현할 수 있다.

 

중요한건, 시작 노드에서 목표 노드까지 가면서 주위에 검색되는 지점들을 모두 Priority-Queue(우선 순위)에 넣고, 그 중에서 Top Priority 을 꺼내고 다시 주위로 검색을 반복한다는 것이다.

 

글로만 설명하니 어려우니, 코드와 그림을 함께 포스트 할 예정이다.

(윈도우 콘솔로 되어있는 그래픽 엔진이 있어서 그걸 사용해서 경로를 만들고, A*를 분석할 예정)

 

추가적으로 A* 가 끝나면 JPS 알고리즘도 한번 파볼 예정이다.