[Unity] A* 알고리즘 (길 찾기)

2D게임 개발 중에 공식적인 2D용 NavMesh는 없다고 들었다.

알고리즘으로 해결해보자

 

A* 알고리즘

= 목적지 까지의 최단 경로 찾는 탐색 알고리즘

 

각 노드에는 G cost, H cost, F cost값이 있다

 

G cost = 시작 노드에서 현재 노드까지의 거리

H cost = 목표 노드에서 현재 노드 까지의 거리 (추정한 값)

F cost = G cost + H cost

 

이동에 경우

오,왼,위,아래는 10이 더해지고

대각선으로 이동 시 14가 더해진다

 

 

시작 노드에서 목표 노드까지 도착할 때 까지

인접노드의 cost값들을 계산하고 그 노드들 중에서

F cost가 가장 낮은것을 선택한다.

선택한 노드를 위와 같은 방식으로 계속 탐색해 나간다.

 

 

 

수도코드

open //계산할 노드 넣는 리스트

closed //계산된 노드 넣는 리스트

add the start node to open;

 

loop

{

    current=node in open with the lowest f_cost

    remove current from open

    add current to closed

 

    if current is the target node then return //목표 노드에 도착했다면 루프 끝낸다

 

    foreach neighbour of the current node //현재 노드의 인접 노드들을 검사

    {   if neighbour is not traversable or neighbour is in closed

            skip to the next neighbour

        if new path to neighbour is shorter or neighbour is not in open

            set f_cost of neighbour

            set parent of neighbour to current

            if neighbour is not in open

                add neighbour to open

    }

}

 

 

참고한 영상

https://youtube.com/playlist?list=PLFt_AvWsXl0cq5Umv3pMC9SPnKjfp9eGW

A* Pathfinding Tutorial (Unity)