A*알고리즘은 출발 노드에서부터 목표 노드까지 가는 최단 경로를 찾아내는 그래프 탐색 알고리즘 중 하나이다.
휴리스틱 방법을 이용하여 최단 경로를 도출해낸다.
-개별 노드에 대한 평가함수(각 노드의 가중치를 평가)
f(n)=g(n)+h(n)
f(x) : 차후 경로 도출을 위한 함수
g(x) : 출발 노드로부터 현재 노드 n까지의 경로 가중치
h(n) : 현재 노드 n으로부터 목표 노드까지의 추정 경로 가중치
-알고리즘의 과정
출발노드를 OPEN List에 삽입->OPEN List에서 pop()하여 f(n)으로비용평가->CLOSED List 삽입 (이 과정을 종료노드까지 반복)
-A*알고리즘 슈도코드
pq.enqueue(start.node, g(start_node)+h(start_node))// 우선순위 큐에 시작 노드를 삽입
while pq is not empty// 우선순위 큐가 비지않으면 반복
node=pq.dequeue// 우선순위 큐에서 pop
if node==goal_node// 만약 노드가 목표노드이면
break// 반복문을 종료
for next_node in (next_node_begin...next_node_end)// 다음 노드가 있는 동안 반복
pq.enquenue(next_node,g(node)+cost+h(next_node)// 우선순위 큐에 다음 노드를 삽입
return goal_node_dist// 시작 노드에서 목표 노드까지 거리 출력
이 알고리즘을 이용하여 C언어 콘솔에서 벽(■)을 피해 플레이어(○)를 쫓아오는 적(##)을 만든 간단한 예시영상이다.