A* 알고리즘

 

A* 알고리즘에 대해 정리해보았습니다.

구글링 및 ChatGPT의 도움을 받아 작성했습니다.

 

 

A* 알고리즘

목적지까지 가장 짧을 것 같은 길을 먼저 탐색하는 길찾기 알고리즘이다.

 

A*는 모든 노드에 대해 이 값을 계산한다.

f(n) = g(n) + h(n)

 

g(n)	시작점 → 현재 노드까지 실제로 이동한 비용
h(n)	현재 노드 → 목표 지점까지의 추정 비용
f(n)	이 노드를 선택할 “우선순위 점수”

👉 f 값이 가장 작은 노드를 먼저 탐색

 

 

실제 동작 흐름

1. 시작 노드를 Open List에 넣는다
2. Open List에서 f 값이 가장 작은 노드를 선택
3. 그 노드를 Closed List로 이동 (탐색 완료, 방문한 길)
4. 인접 노드들에 대해:
   • g, h, f 계산
   • 더 좋은 경로면 값 갱신
5. 목표 지점에 도달하면 종료

 

h(n) = 휴리스틱 함수

환경	휴리스틱
격자 맵 (4방향)	Manhattan Distance (가로 + 세로 이동 거리)
격자 맵 (8방향)	Diagonal Distance (대각선 + 가로 + 세로 이동 거리)
자유 공간	Euclidean Distance (두 점 사이의 실제 직선 거리)

 

 

A* 알고리즘 예시 코드 (격자 맵, 4방향)

struct Node
{
    int x, y;

    int g; // 시작점 → 현재 노드 비용
    int h; // 현재 노드 → 목표 지점 추정 비용
    int f; // g + h

    Node* parent;

    Node(int _x, int _y)
        : x(_x), y(_y), g(0), h(0), f(0), parent(nullptr) {}
};

int Heuristic(const Node& a, const Node& b)
{
    return abs(a.x - b.x) + abs(a.y - b.y);
}

struct CompareNode
{
    bool operator()(Node* a, Node* b)
    {
        return a->f > b->f; // f 값이 작은 노드가 우선
    }
};

bool AStar(Node* start, Node* goal,
           std::vector<std::vector<int>>& grid,
           std::vector<Node*>& outPath)
{
    std::priority_queue<Node*, std::vector<Node*>, CompareNode> openList;
    std::vector<Node*> closedList;

    openList.push(start);

    while (!openList.empty())
    {
        Node* current = openList.top();
        openList.pop();

        // 목표 도착
        if (current->x == goal->x && current->y == goal->y)
        {
            // 경로 재구성
            Node* node = current;
            while (node)
            {
                outPath.push_back(node);
                node = node->parent;
            }
            std::reverse(outPath.begin(), outPath.end());
            return true;
        }

        closedList.push_back(current);

        // 4방향 이동
        const int dx[4] = { 1, -1, 0, 0 };
        const int dy[4] = { 0, 0, 1, -1 };

        for (int i = 0; i < 4; ++i)
        {
            int nx = current->x + dx[i];
            int ny = current->y + dy[i];

            // 맵 범위 체크
            if (nx < 0 || ny < 0 ||
                nx >= grid.size() || ny >= grid[0].size())
                continue;

            // 장애물 체크 (1 = 벽)
            if (grid[nx][ny] == 1)
                continue;

            // Closed List 체크
            bool inClosed = false;
            for (auto node : closedList)
            {
                if (node->x == nx && node->y == ny)
                {
                    inClosed = true;
                    break;
                }
            }
            if (inClosed)
                continue;
                
            Node* neighbor = new Node(nx, ny);
            
            neighbor->g = current->g + 1;
            neighbor->h = Heuristic(*neighbor, *goal);
            neighbor->f = neighbor->g + neighbor->h;
            neighbor->parent = current;

            openList.push(neighbor);
        }
    }

    return false;
}