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

게임에서 길을 찾는

알고리즘을 사용할때

사용하는 A* 알고리즘

입니다.

이번 포스팅 에서는

A* 알고리즘에 대해

최대한 알기 쉽게

작성해 보도록

하겠습니다.

(알고리즘 관련 포스팅

이기 때문에  스크롤이

엄청 깁니다.)

먼저 아래의 이미지에서

초록색에서 빨간색으로

이동 한다고 가정합니다.

(파란색은 장애물 입니다.)

먼저 길찾기 알고리즘을

할때 필요한 개념들이

몇가지 있습니다.

열린 목록 (Open List)

길찾기를 진행 하면서

거리를 고려하게 되는

사각형 들의 목록 입니다.

닫힌 목록 (Clised List)

바로 위에 열린 목록에서

목적지 까지 가는데에

가장 짧은 거리를 가진

사각형 들을 목록 입니다.

부모 사각형

사각형들 마다 자신이

어디에 속해 있는지를 가리키는

사각형

나중에 길찾기를 통해

목적지를 찾았을때

최단의 길을 찾기위해

필요합니다.

위의 두가지 개념을

가지고 길찾기 알고리즘

과정을 간단히 설명하자면

시작하는 사각형(녹색) 을

닫힌 목록에 넣고

아래 이미지처럼

닫힌 목록에 있는 사각형의

인접한 사각형들을

모두 열린 목록에

집어 넣습니다.

그리고 각각의 사각형들은

부모 사각형을 시작 사각형

으로 설정 합니다.

그리고 방금 열린목록에

들어간 사각형 들을

하나씩 돌면서

현재 닫힌 목록에 있는

사각형 과의 거리와

목적지까지의 거리

등등을 계산해서

가장 최적의 사각형을

다시 닫힌 목록에 넣습니다.

(닫힌 목록에 들어간 사각형은

열린목록에서 제거해야 합니다.)

그 다음은 최근에

닫힌목록에 들어간

사각형을 기준으로 목적지가

나올때 까지 다시 처음부터

똑같이 계산을 해주는 방식입니다.

여기서 다시 필요한 개념들이

몇가지 더 생기게 됩니다.

방금 위에서 설명했던

현재 닫힌 목록에 있는

사각형 과의 거리와

목적지까지의 거리

등등을 계산할때 필요한

개념들 입니다.

F = G + H

G

현재 닫힌 목록에 있는 사각형

과의 거리

H

목적지까지의 거리

(장애물은 고려하지 않습니다.)

F

G와 H를 더한 값

이 값들을 가지고 길찾기를

할때 판단 합니다.

위에서 나온 개념들을

숙지해서 길찾기 알고리즘을

시작해 보겠습니다.

먼저 시작 사각형(초록) 을

기준으로 인접해 있는

사각형 들의 비용을

아래처럼 계산 합니다.

사각형을 기준으로

왼쪽 아래는 G,

오른쪽 아래는 H,

왼쪽 윗 부분은 F

입니다.

먼저 시작 사각형을 기준으로

위에 있는 사각형을

계산해 보면

G는 시작점으로 부터

한칸이므로 10.

여기서 한칸의 길이를

10으로 둔 이유는

대각선의 길이를 계산할때

간단히 하기 위해

단순화 시켰기 때문입니다.

따라서 직선은 10,

대각선은 14로 계산할 수 있습니다.

그다음 H 는 목적지 까지의

거리가 5칸 이므로 50.

그리고 F는 10 + 50

이므로 60 입니다.

이렇게 주변에 인접해 있는

사각형 들의 값을내고

가장 최적의 F 를 계산해보면

바로 오른쪽에 있는 사각형이

40 으로 가장 가깝다는걸

알 수 있습니다.

따라서 바로 오른쪽에 있는

사각형을 아래 이미지 처럼

닫힌 목록에 넣고 열린 목록에서는

제거해 줍니다. 

그 다음 방금 선택된 사각형을

기준으로 다시 계산을 해줍니다.

장애물을 건너 뛰고

주변 사각형 들의 F를

계산해 보면 위에 있는 사각형과

아래에 있는 사각형의 F 값이

각각 54로 같다는걸 알 수

있는데요..

A* 알고리즘은

휴리스틱^[각주:1] 추정값으로

길을 찾기 때문에..

어느 쪽으로 갈지는

만드는 사람에 따라

다를 수 있을 것 같습니다.

일단은 아래쪽을 선택하는

쪽으로 설명하도록 하겠습니다.

다음 닫힌 목록에 아래쪽에

있는 사각형을 넣어 주고

인접해 있는 사각형 들의

F값들을 계산해 줍니다.

열린 목록에 없는 사각형은

추가해 주고 부모 사각형을

새로 설정해 줍니다.

위와 같은 방식으로

목적지가 나올때 까지

진행해 주면 아래와 같이

계산이 됩니다.

그다음 목적지에서 부터

부모 사각형을 따라서

거슬러 올라가는 길이

가장 빠른 길이 됩니다.

가장 널리 쓰이는

알고리즘 이지만..

맵의 크기가 크거나

길이 상당히 긴 경우에는

그만큼 CPU 나 연산 속도가

느려질 경우도 있겠고..

또 휴리스틱을 이용하기 때문에

특정상황에 따라서는

찾아진 길 보다 더 짧은 길이

존재 할 수도 있을 것 같습니다.

이상 A* 알고리즘에

대한 간단 설명

이었습니다.

1. 시간이나 정보가 불충분하여 합리적인 판단을 할 수 없거나, 굳이 체계적이고 합리적인 판단을 할 필요가 없는 상황에서 신속하게 사용하는 어림짐작의 기술 [본문으로]