[Algorithm] A* 알고리즘

A* 알고리즘이란?

다익스트라 알고리즘에서 동적 계획법(DP)을 적용시켜 확장한 최단 경로 탐색 알고리즘

- 탐색이 가능한 모든 노드 중 현재 최적이라고 판단되는 노드를 탐색

1.  A* 알고리즘의 개념

- 닫힌 목록 : 탐색이 끝난 노드들의 집합 ( 다시 탐색 X )

- 열린 목록 : 탐색이 가능한 노드들의 집합 ( 닫힌 목록과 인접한 노드 )

g(x) : 시작점을 기준으로 한 비용

h(x) : 도착점까지의 예상 비용 // 휴리스틱 함수

f(x) = g(x) + h(x)

 

- 휴리스틱 함수 h(x)에 따라 성능이 변함  -> h(x) 이 g(x) or 0 인 경우 다익스트라 알고리즘과 동일

 

+ 휴리스틱 함수란?

현재 노드에서 목표 노드까지의 예상 비용을 구하는 함수

 -> ex. 맨해튼 거리 함수, 유클리디안 거리 함수

2.  A* 알고리즘의 동작

우선순위 큐(최소 힙)을 이용하여 열린 노드들을 관리

열린 노드의 비용을 연산할 때에는 인근에 있는 닫힌 노드 중 가장 비용이 낮은 노드에서 이동한 비용으로 연산

0. 시작점 인근의 모든 노드의 비용을 연산하고 우선순위 큐에 넣음 ( 비교 기준 : f(x) -> h(x) )

1. 탐색할 노드를 지정 ( 우선순위 큐에서 Pop )

2. 우선 순위 큐에 탐색한 노드로 인해 추가된 열린 노드의 비용을 연산하고 우선순위 큐에 넣음

3. 도착지를 찾을 때까지 1,2번을 반복함

4. 도착지를 찾았다면, 도착지에서부터 루트노드를 찾아 시작점까지 스택에 담아서 반환 ( 최단 경로 반환 )

- 루트노드는 인근의 닫힌 노드 중 가장 g(x) 비용이 적은 노드로 지정

BFS / 다익스트라 / A*

BFS : 가중치가 없는 그래프에서 최단 경로를 찾는 완전 탐색 알고리즘

Dijkstra : 가중치 그래프에서 시작 노드를 기준으로 모든 노드까지의 최단 거리를 구하는 그리디 알고리즘

Astar : 가중치 그래프에서 시작 노드에서 목표 노드까지의 최단 경로만을 구하는 그리디 알고리즘

+ A* 알고리즘에서 모든 휴리스틱 함수의 값이 0이라면 다익스트라 알고리즘과 동일함

WindowsAPI로 구현한 A* 알고리즘의 이해를 돕기 위한 테스트 프로그램 영상

void FindBestNearBlock(int y, int x)
{
    int maxRangeX = blockArrays[0].size();
    int maxRangeY = blockArrays.size();

    for (int i = 0; i < 8; i++)
    {
        int movePosY = y / BLOCKSIZE + dirY[i];
        int movePosX = x / BLOCKSIZE + dirX[i];

        if (movePosY < 0 || movePosY >= maxRangeY || movePosX < 0 || movePosX >= maxRangeX)
            continue;

        if (blockArrays[movePosY][movePosX].blockState == Block_End)
        {
            SetBlockMoveStack();
            player.SpawnPlayer({ startBlock->pos.x + (BLOCKSIZE / 2), startBlock->pos.y + (BLOCKSIZE / 2) });
            player.SetTargetPos({ startBlock->pos.x + (BLOCKSIZE / 2), startBlock->pos.y + (BLOCKSIZE / 2) });
            gameState = Game_MoveTarget;
        }
        else if (blockArrays[movePosY][movePosX].blockState == Block_None)
        {
            SetNearBlockCost(&blockArrays[movePosY][movePosX]);
            blockArrays[movePosY][movePosX].blockState = Block_Queue;
            blockQueue.Enqueue(&blockArrays[movePosY][movePosX]);
        }
    }
}

void MoveToBestBlock()
{
    if (blockQueue.GetCount() == 0)
        return;

    findBlock = blockQueue.Dequeue(); // 최적의 열린 노드
    findBlock->blockState = Block_Mine;

    FindNearBlock(findBlock->pos.y, findBlock->pos.x);
}