A*알고리즘

1. A* 알고리즘을 활용한 간단한 예제

우리는 예제에서 diagonal을 사용할 것입니다. 또한 대각선의 가중치와 가로 세로의 가중치는 동일하게 적용합니다.

그렇다면 A* 알고리즘에서 가장 간단한 예로 시작해보겠습니다.

먼저 10 * 10 크기의 캔버스를 하나 만들었습니다. 우리는 이 캔버스 위에서 탐색을 합니다.

왼쪽 빨간색 사각형은 Start 노드이고 오른쪽 파란색 사각형은 End 노드입니다.

또한 가운데 검정색 사각형 세개는 벽이며, 벽을 통과할 수는 없습니다.

다음의 순서를 참고하세요. 이해가 안간다면 그냥 넘어가도 좋습니다. 밑에서 자세하게 설명하겠습니다.

1. 시작지점 A를 open list에 넣습니다.

2. 아래의 과정을 반복합니다.


        a ) open list에 포함된 노드들 중에서 F값(최종 비용)이 가장 작은 노드를 선택하고 현재 노드로 지정합니다.

        b ) 이 노드를 closed list에 넣습니다.

        c ) 현재 노드로부터 인접한 8개의 노드(상하좌우, 대각선)에 대해서 

            - 만약 인접한 노드가 closed list에 포함되어 있거나 장애물 등에 막혀서 이동할 수 없으면 무시합니다. 그렇지 않으면 아래의 절차를 따릅니다.

            - 만약 인접한 노드가 open list에 포함되어 있지 않다면 이를 open list에 넣습니다. 그리고 현재 노드를 부모 노드로 지정하고 f, g, h 값을 계산합니다.

            - 만약 인접한 노드가 이미 open list에 포함되어 있다면 현재 노드를 이용한 경로가 기존의 경로보다 나은지를 판단합니다.

              (g값을 기준으로 g값이 더 작은 경로가 더 나은 경로) 만약 현재 노드를 이용한 경로가 더 낫다면 현재 노드를 부모로 지정하고 f, g값을 새로 추정합니다.

        d ) 아래의 조건일 때 알고리즘이 종료됩니다.

            - 목표지점 b가 closed list에 포함되거나

            - 목표지점 B를 찾는데 실패하고 open list가 비어 있는 경우 (시작지점부터 목표지점까지의 경로가 존재하지 않음)

3. 경로를 저장합니다. 목표지점에서 시작하여 거꾸로 부모 노드를 따라가 시작지점까지 계속 이동합니다. 이 경로가 최단경로가 됩니다.

1) 시작 노드

자, 그럼 차근차근 따라가보겠습니다. 우리가 가장 먼저 해야할 것은 Start 노드를 Open List에 넣는 것입니다. (순서 1에 해당)

Open list는 앞서 말했듯, 최단 경로로 예상될 수 있는 노드들의 집합입니다. 그림에서 Open List는 초록색으로 표현됩니다.

그 다음으로 해야할 것은 Open List에 담겨있는 노드들을 비교하여 F값, 즉 최종 비용이 가장 작은 노드를 현재 노드로 선택하는 것입니다. (순서 2-a에 해당)

현재 Open List에 담겨있는 노드는 Start 노드 하나 밖에 없습니다. 그렇기 때문에 우리는 Start 노드를 “현재 노드”로 선택할 것입니다.

선택이 끝난 노드는 Closed List에 담겠습니다. (순서 2-b에 해당) 그림에서 Closed List는 핑크색으로 표현됩니다.

2) 인접하는 노드의 비용 계산하기

현재노드는 아직까지 Start 노드입니다. 그럼 인접하는 노드들을 볼까요?

우리는 예제에서 대각선으로 이동하는 것을 허용합니다. 그렇기 때문에 대각선 노드까지 포함해서 살펴보도록 하죠.

현재 노드를 둘러싼 8개의 노드 중 우리가 걸어갈 수 있는 노드를 확인해보겠습니다.

여기서 걸어갈 수 있는 노드라는 것은 캔버스 안에 포함되어 있고 장애물이 아니며 장애물을 지나치는 노드가 아니어야 한다는 것입니다.

그림을 볼까요? 우리는 1번 사각형에서 2번 사각형으로 곧바로 이동할 수 없습니다.

그림의 빨간색 동그라미를 캐릭터라고 가정할 때, 1번 사각형에서 2번 사각형으로 곧바로 대각선 방향으로 이동하게 되면 3번 장애물의 모서리에 부딪히게 되기 때문이죠.

사실 이렇게 걸어갈 수 있는 노드를 정의하는 것은 게임에 따라 다릅니다.

장애물에 부딪혀도 지나갈 수 있는 상황이라면 이러한 경우도 걸어갈 수 있는 노드에 포함되겠죠.

하지만 이 포스팅에서는 걸어갈 수 없는 경우에 포함시키겠습니다.

그리고 왼쪽에 크게 사각형으로 둘러싸인 부분도 이동할 수 없는 노드입니다. 캔버스 바깥이기 때문이죠.

왼쪽 뿐만 아니라 캔버스를 벗어나는 모든 범위는 이동이 허용되지 않습니다.

그럼 계속해서 볼까요?

현재 노드를 기준으로 상하좌우 및 대각선에 인접한 노드들 중 걸어갈 수 있는 노드들을 Open List에 담습니다.

그리고 F(최종비용), G(시작노드 ~ 검사할 노드까지의 비용), H(검사할 노드 ~ 마지막노드까지의 추정비용)을 계산합니다.

마지막으로 현재 노드를 부모노드로 지정합니다.

먼저 아래 주황색으로 표시된 사각형부터 비용을 계산해보겠습니다.

G는 시작노드(분홍색 노드)에서부터 검사할 노드(주황색 노드)까지의 비용을 의미합니다. 시작노드에서부터 대각선으로 1칸 떨어져있으니 G = 1으로 계산됩니다.

H는 검사할 노드(주황색 노드)에서부터 도착 노드(파란색 노드)까지의 비용을 의미합니다. 총 5칸이 떨어져있네요.

비용을 계산할 때 장애물은 일단 무시하고 계산하겠습니다.

H = 5 가됩니다.

따라서 주황색으로 표시된 노드는 G = 1(왼쪽), H = 5(오른쪽), F = G + H = 6(위) 이 되겠네요!

그리고 현재 노드(분홍색)를 주황색 노드의 부모로 지정합니다.

그러면 다시 표시된 노드의 G, H, F를 각각 구해볼까요?

G부터 봅시다. 시작 노드로부터 위로 한 칸 떨어져있네요. 따라서 G는 1이 됩니다.

이번에는 H를 보겠습니다. 마지막 노드로부터 총 4칸 떨어져있네요. 말씀드렸다시피 장애물인지 아닌지는 무시하고 계산합니다.

그럼 주황색으로 표시된 노드의 F(위), G(왼쪽), H(오른쪽)를 표시해볼까요? 정답은 다음과 같습니다.

이후 주황색으로 표시된 노드의 부모를 현재 노드(분홍색)로 지정합니다.

나머지 칸들도 모두 노드 위에 표기해 봅시다. 현재 노드를 부모로 지정하는 것도 잊지 말아야합니다.

정답은 아래에 있습니다.

3) 계속해서 탐색하기

우리는 계속해서 탐색하여 마지막 노드까지 나아가야 합니다. 계속해서 탐색해볼까요?

OpenList에 포함된 노드들 중 F값이 가장 작은 노드 하나를 선택합니다.

시작노드를 기준으로 대각선 위, 오른쪽, 대각선 아래 방향이 F = 4로 최소 비용을 갖고 있네요. 이 중 어떤 것을 먼저 탐색해도 상관없습니다.

우리는 오른쪽 노드를 현재 노드로 선택하여 탐색하겠습니다.

현재 노드로 선택했으니 Closed List에 포함시키겠습니다. 그리고 주위에 인접한 노드 중 걸어갈 수 있는 노드들을 Open List에 포함합니다.

여기서 의문이 두가지 생기네요.

1) 이미 Closed List에 포함된 노드가 있다.

2) 이미 Open List에 포함된 노드가 있다.

먼저 Closed List에 포함된 노드가 있다면 그 노드는 무시하고 계속해서 다른 인접한 노드를 탐색합니다.

그리고 Open List에 포함된 노드가 있다면 G (시작 노드 ~ 검색할 노드까지의 비용) 값이 기존 G값보다 작다면 부모를 현재 노드로 다시 설정하고 새로 G값과 F값을 갱신해줍니다.

이 때 H값을 갱신하지 않는 이유는 간단합니다. 검색할 노드부터 마지막 노드까지의 추정비용은 동일하기 때문이죠.

그럼 걸어갈 수 있는 노드는 다음 그림에 표시된 노드들이 됩니다.

다음으로 해야할 일은 뭘까요?

Open List에 포함된 노드들 중 가장 작은 F값을 가진 노드를 현재 노드로 선택하는 것이겠죠.

F값이 4인 노드들이 가장 작은 값이네요. 이들 중 아무 노드나 선택합니다. 저는 아래에 있는 노드를 선택했습니다.

선택한 노드는 Closed List에 포함시키고 또 주변에 걸어갈 수 있는 노드를 Open List에 포함시키고 F, G, H값을 계산합니다.

현재 노드의 대각선 아래에 있는 노드가 Open List에 포함되지 않은 이유는 앞서 설명했죠.

현재 노드와 대각선 아래에 있는 노드를 대각선 경로를 따라 이동하려면 장애물에 부딪히기 때문입니다.

이후 현재 노드를 탐색하고 있는 인접 노드의 부모 노드로 설정합니다.

계속해서 탐색해보겠습니다. 남은 Open List중 가장 작은 F값을 가진 노드는 주황색으로 표시된 노드네요.

그럼 이 노드를 현재 노드로 선택하고 걸어갈 수 있는 노드를 OpenList에 포함시키고.. 또 F, G, H값을 기록합니다.

마찬가지로 현재 노드를 걸어갈 수 있는 노드들의 부모 노드로 설정합니다.

이 과정을 계속 반복해서 현재 노드가 마지막 노드가 될 때까지 반복합니다. 혹은 Open List에 아무것도 없다면 종료합니다.

만약 Open List에 아무것도 없어서 종료했다면 경로를 탐색하지 못한 것이 되겠죠.

다시 한 번 복습해보겠습니다.

1) Open List 중 가장 작은 F값을 가진 것을 현재 노드로 선택한다.

2) 현재 노드를 Closed List에 포함한다.

3) 현재 노드를 기준으로 인접한 8개의 노드를 탐색합니다.


 a) 이미 인접한 노드가 Closed List에 포함되어 있거나 걸어갈 수 없는 노드들은(장애물이거나 장애물을 거쳐가거나 캔버스 범위를 벗어나는 노드) 무시하고 다음 인접한 노드를 탐색합니다.

 b) 만약 인접한 노드가 Open List에 포함되어 있지 않으면 Open List에 포함하면 현재 노드를 인접한 노드의 부모 노드로 설정합니다. 또한 F, G, H 의 비용을 계산합니다.

 c) 만약 인접한 노드가 Open List에 포함되어 있으면 이전에 계산한 G값과 현재 노드를 기준으로 한 G값을 비교합니다. 

    만약 현재 노드를 기준으로 한 G값이 더 작다면 F, G값을 갱신하고 현재 노드를 부모 노드로 설정합니다.


4) 만약 OpenList에 아무것도 담겨있지 않거나, 현재 노드가 목적지 노드일 경우 탐색을 종료합니다.

마지막으로 해야할 일은 현재 노드가 목적지 노드일 경우 현재노드의 부모를 쭉 따라가는 것입니다.

이렇게 현재 노드의 부모 노드를 쭉 따라가면 최단일 것이라고 예상되는 경로가 됩니다.

이러한 경로는 다음 이미지에서 노란색으로 표시되어 있습니다.