[Sebastian Lague] A* Pathfinding (E01: algorithm explanation)

이 포스팅은 Sebastian Lague의 A* Pathfinding 영상을 기반으로 진행됩니다.

💡 알고리즘

A*는 휴리스틱기반 그래프 탐색 알고리즘이다. 이는 BFS와 다익스트라 알고리즘을 섞은 것과 비슷하다.

👉🏻 노드

노드에는 총 3개의 주요 변수가 있다.

F = G + H
G = [시작 노드-현재 노드] 거리
H = [현재 노드-도착 노드] 거리

이 영상에선 맞닿은 노드끼리의 거리는 10으로 하고, 대각선 거리는 14로 간단히 계산하고 있다.

👉🏻 흐름

// 계산되어야 할 노드의 집합
OPEN
// 이미 계산된 노드의 집합
CLOSED
// OPEN 집합에 시작 노드를 집어넣음
add the start node to OPEN

loop
    // OPEN 집합에서 가장 낮은 f_cost를 가진 노드를 현재 노드로 선정
    current = node in OPEN with the lowest f_cost
    // OPEN 집합에서 현재 노드 제외
    remove current from OPEN
    // CLOSED 집합에 현재 노드 추가
    add current to CLOSED

    // 현재 노드가 도착 노드라면 끝낸다.
    if current is the target node
        return

    // 현재 노드에서 맞닿은 총 8개의 노드를 순환
    foreach neighbour of the current node
        // 이웃 노드가 CLOSED에 속했거나, 갈수 없는 노드인 경우,
        if neighbour is not traversable or neighbour is in CLOSED
            // continue;
            skip to the next neighbour

        // 이웃 노드로 가는 새로운 경로가 더 짧거나, OPEN 집합에 없는 경우(한번도 계산된 적 없다는 것)
        if new path to neighbour is shorter OR neighbour is not in OPEN
            // 이웃 노드의 f_cost를 새로운 f_cost로 대체
            set f_cost of neighbour
            // 이웃 노드의 부모를 현재 노드로. 코드 종료시 시작 노드와 도착 노드의 경로를 파악하기 위함.
            set parent of neighbour to current
            // 이웃이 OPEN 집합에 없다면
            if neighbour is not in OPEN
                // 이웃을 OPEN 집합에 추가한다.
                add neighbour to OPEN

영상에서 나오는 pseudo 코드이다.

노드에 traversable이란 것과 parent라는 것이 추가됐다.

traversable은 해당 노드를 장애물로 두기 위함이다. parent는 [시작 노드-도착 노드] 간의 경로를 파악하기 위함이다.
도착 노드에서 parent를 따라가면 시작 노드가 나오므로 경로를 파악하기에 유용하다.

Techniques 카테고리 내 다른 글 보러가기