A* 알고리즘

Hwan's Research & Development | 화니

http://cafe.naver.com/gplab/11

초보자를 위한 AStar 길찾기 알고리즘(사실은 번역 ㅋㅋㅋ)

‘A* Pathfinding for Beginner By Patrick Lester’ <- 원래제목!

원문 http://www.gamedev.net/reference/programming/features/astar

2004. 4. 22

Translated By Generosus.

 

-------------------------------------------------------------------

영어가 딸려 번역하는데 무지 많은 시간이 소요되었으며, 영어식 표현으로 쓰기가 영 어색한 것은 한국식 표현으로 바꾸어 쓰기도 하였습니다. 영어실력이 쫌 되시는분은 좀더 자연스러운 번역으로 다시 올려주셔도 좋을 듯 합니다.

아참! 쓰다보니 반말 존댓말 마구 썩어 놓았는데 너그러이 용서하시길~

Cafe: http://cafe.naver.com/rosuslab.cafe

Email: debugman@hitel.net

-------------------------------------------------------------------

 

이 알고리즘은 이미 스페인어와 프랑스어로 변역되었으며, 또 다른 언어로의 번역도 환영합니다.( 내 것도 링크해 달라고 할까 ~ㅎㅎ )

 

당신이 쉽게 A*알고리즘을 이해할 때, 이 A*알고리즘은 초보자에게는 복잡하게 느껴질수도 있습니다. A*알고리즘을 해석한 논설들이 웹상에 많이 존재합니다. 그러나 그 글들의 대부분은 이미 기본적인 것을 이해한 사람들을 위해 쓰여진 글들이지만. 그와 달리 이 글은 진정 초보자들을 위한 것입니다.

 

이 논설은 A*길찾기 알고리즘의 주제를 완벽히 보여주도록 노력하지는 않습니다. 그보다는 당신이 앞으로 관련된 다른 좀더 구체적인 글들을 읽고 이해하는데 필요한 A*길찾기 알고리즘의 원리와 기본적인 것들을 설명하고 있습니다. 나중에 여러분들이 읽을수 있도록 최고의 몇몇 웹사이트 링크를 마지막 부분에 제공합니다.

 

마지막으로, 이 논설은 어느한쪽으로 특유화된 프로그램이 아닙니다. 나는 이 논설의 마지막 부분에 C++과 Blitz Basic 두가지 버전의 샘플프로그램 패키지의 링크를 넣어 놓았지만 당신은 어떤 컴퓨터 언어로든 A*알고리즘을 적용하는 것이 가능할 것입니다.

샘플프로그램에는 당신이 A*가 동작하는 것을 볼수있도록 실행파일도 포함시켜 놓았습니다.

 

자~ 처음부터 시작해 보자... 우리스스로 헤처나가 보자 ~Let's Go(^^b)

 

 

도입: 범위 찾기(The Search Area)

자~ 가정해 보자 누군가가 A지점에서 B지점으로 가기를 원한다. 그리고 벽이 이 두 지점을 분리시켜놓고 있다. 이것에 대한 그림이 아래에 있다. 녹색은 출발지점A, 빨간 것은 도착지점B, 그리고 파란색으로 채워진 사각형은 양쪽사이에 있는 벽이다.

 

 

먼저 알수 있는 것은 우리의 검색지역이 사각형 격자들(Grid)로 나누어져 있다는 것이다. 우리는 이 단순화된 검색지역 사용한다.

 

우리가 첫 단계로 할 것은 길 찾기이다(당근이쥐!).

(격자들로 지역을 단순화시킨) 이런 특별한 방법은 우리의 검색지역을 단순한 2차원배열로 만들어준다. 각각의 아이템(시작지점,도착지점,벽,길 등등)은 사각형 격자위에 하나의 2차원배열로 묘사된다. 그리고 이것은 ‘갈수 있는곳’, ‘갈수없는곳‘ 이런식으로 상태가 기록된다. 우리가 A에서 B로 갈 수 있는 길은 어떠한 사각형들의 모양으로 나타난다. 사각형의 중앙에서 다음 사각형의 중앙으로의 이동을 목표에 도착할때까지 하면서 길이 찾아진다.

 

이 중심점들을 노드 라고 부른다. 

 

 

다음의 순서들을 실행 하므로써 우리는 길 찾기를 한다.

 

 

1. 지점A로부터 충분히 검토된 사각형을 열린목록(open list)에 추가한다.

열린목록은 쇼핑목록과 비슷하다. 지금은 목록상에 아이템이 하나이지만 나중에 좀더 갖게 될 것이다. 

 

 

2. 시작점 근처에 붙어있고 지나갈 수 있는 모든 사각형들을 보아라.

벽, 물 또는 다른 잘못된 지역들은 무시해라. 그리고 그것들(정상적인 사각형) 역시 열린목록에 추가해라.

각각의 그 사각형들에게 지점A를 저장하라 ‘부모사각형’이라고~.

이 ‘부모사각형’은 우리의 길을 거슬러 올러갈 때 아주 중요하다. 좀더 후에 이것에 대해 확실하게 알게 될 것이다.

 

>붙어 있는 정상적인 사각형을 열린 목록에 추가.

>각각의 열린 목록에는 부모 사각형을 저장

 

 

3. 시작사각형 A를 열린목록에서 빼고, 이것을 다시는 볼 필요가 없는 사각형들의 목록인 닫힌목록(closed list)에 추가해라

 

> 시작 사각형 A를 열린 목록에서 제거, 닫힌 목록에 추가.

 

 

이 시점에서, 당신은 다음과 같은 그림을 얻을수 있다. 이 그림에서 중심에 어두운 녹색 사각형은 출발사각형이다.

이것은 밝은파란 외곽선으로 되어있고 이것은 닫힌목록에 추가되었음을 의미한다.

 

그리고 인접한 모든 사각형들은 검사되어진후 열린목록에 들어가 있다.

그리고 그것들은 밝은녹색 외곽으로 되어있다.

각각은 회색의 포인터를 가지고 있고 이것은 부모사각형인 시작점을 가리키고 있다.

 

 

다음으로, 우리는 열린목록에 있는 인접한 사각형중에 하나를 선택하고 앞에서 했던 처리를 아래에 설명된 방법으로 반복한다.

  좀더 많이 할 수도 있고 덜 할 수도 있다. 그런데 어떤 사각형을 선택해야 할까? 그것은 바로 가장 작은 F비용을 가진 것을 선택한다.

(F비용이 무엇 일까요?? ^^ 아래를 보면 알게 된다구요.~)

 

 

길 기록(Path Scoring)

 

길을 찾아내야 할 때 사용할 사각형을 선택하는 방법은 바로 다음 방정식이다.

F = G + H

 

G = 출발점 A로부터 얻어진 새로운 사각형까지의 이동비용이다.

      길을 찾아가면서 생성되게 된다.

 

H = 얻어진 사각형으로부터 최종목적지점 B까지의 예상이동비용이다.

      이것은 매번 조회될때마다 발견된다. 

     우리는 완전한 길을 찾을때까지 정확한 거리를 알수 없다.

     왜냐하면 모든성격의 것들(물,벽,기타등등 갈수없는사각형)이 길위에 있기 때문이다. 당신은 H를 계산하는 한가지 방법을 연습을 통해 알게 될것이다.

     그리고 H를 계산하는 방법은 웹상에 다른 많은 방법이 존재한다.

 

우리의 길은 열린목록과 F비용이 작은 사각형을 선택하는것의 반복을 통해서 얻어진다.

 

위에 설명된 것처럼, G는 출발점으로부터 길을 만들기 위해 얻게 되는 사각형으로 이동하는데 드는 이동비용이다.

 

세로 또는 가로로 이동 ->  각각 10의 비용을 할당

대각선이동 -> 14의비용을 할당

 

우리는 얻어지는 사각형의 일정한 길을 따라 G비용을 계산하기 때문에, 사각형의 G비용을 알아내는 방법은 그 부모로부터 G비용을 가져와서 부모로부터 직각으로 움직였냐 대각선으로 움직였냐에 따라서 10또는 14를 추가해 주는것이다. 이 방법이 좀더 명확하게 되도록 하기위해서 이 예제상에서 좀더 멀리까지 해볼 필요가 있다. 그래서 우리는 시작점으로부터 떨어져 있는 하나 이상의 사각형을 얻는다.

 

H는 길들의 변화 안에서 어림잡아 예측될 수 있다.

우리가 사용하는 이 방법을 맨하탄방식(Manhattan method)이라고 부른다.

     -> 당신은 현재사각형에서 목표사각형에 도달하기 까지의 대각선이동을 제외한 가로 또는 세로로 이동한 총숫자를

         계산할수 있다. 그리고 거기에 10을 곱한다.

     -> 여기서 당신은 대각선으로 블록을 가로질러 자를수는 없다.

     -> 중요하게도, H비용을 계산할 때 우리는 어떤 끼여드는 방해물도 무시한다.

          H비용은 단지 남은거리에 대한 어림잡은 추측일 뿐이다. 진짜 거리가 아니다.

          또한 발견적방식이라고 불리는 이유이기도하다. 좀더 알기를 원하는가?

          당신은 발견적방식상의 방정식들과 추가적인 사항들을 여기(http://www.policyalmanac.org/games/heuristics.htm)

          에서 발견할수 있을 것이다.

 

G와 H를 더하므로써 F 가 계산된다.우리의 검색의 첫단계의 결과를 아래 그림에서 볼수있다. F,G,H 비용이 각각의 사각형에 표시되어 있다.

 

F

G  H

 

 

 

 

그럼, 저 사각형들을 살펴보자.

글자와 같이 있는 사각형을 보면, G비용이 10이다. 이것은 시작 사각형으로부터 수평방향으로 위치한 사각형이기 때문이다. 즉, 시작사각형으로부터 위, 아래, 왼쪽, 오른쪽에 있는 모든사각형들은 모두 똑같이 G비용이 10이다. 대각선으로 위치한 사각형들은 14의 G비용을 갖는다.

 

이제 F비용은 단순히 H 와 G 값을 더하면 되는것이다.

 

 

찾기 계속하기(Continuing the Search)

 

계속 찾기를 해 나가기위해서 우리는 단순히 열린목록에 있는 사각형들 중에서 가장 작은 F비용을 가지고 있는 사각형을 선택하고 그 선택된 사각형으로 다음의 과정을 하면 된다.

 

4. 이것을 열림목록에서 빼고 단힌목록에 추가한다. 

    (선택된 사각형)

 

5. 인접한 모든 사각형을 검사해서

    닫힌목록에 있거나 갈수없는것(벽,물,그밖에 장애물)들을 제외하고 나머지중에서

    열린목록에 들어가 있지 않은것들을 열린목록에 추가한다.

 

   > 열린 목록에 추가할 것 ==> 인접한 사각형 - 닫힌목록 - 갈 수 없는 것 -열린목록에 들어가 있는 것  

 

    선택되었던 사각형을 새로운 사각형들의 부모로 만든다.

    (선택되었던 사각형이란 4.에서 단힌목록에 추가된 그 사각형을 말한다. 새로운 사각형이란 5.에서 열린목록에 새롭게 추가된 사각형을 말한다.)

 

 

6. 만약 인접한 사각형중에 이미 열린목록에 있는 사각형이 있다면 이사각형으로 가는길이 더 좋은 길인지 확인해 봐라.

   다시 말하면, 우리가 현재 선택된 사각형보다 G비용이 더 작은지를 검사해 봐라.

   ->만약 아니라면 아무것도 할 필요가 없다.

   ->그러나 새로운 길이 G비용이 더 작다면 선택되었던 사각형의 인접사각형들의 부모를 새로운 사각형으로 바꿔라

      (위쪽 그림에서 보면, 선택된 사각형으로 향하는 포인터들의 방향을 바꾸는 것을 말한다.).

       마지막으로, 그 사각형의 F와 G를 다시 계산해라. 이것이 좀 복잡하게 느껴진다면, 아래 그림을 보아라

.

 

 

 

 

최초에 9개의 사각형중에 우리는 시작사각형을 닫힌목록에 넣은후 열린목록에 8개의 사각형을 가지고 있다.

> 열린목록 : 8개(1,2,3,4,6,7,8,9), 닫힌 목록 1개(5)

 

 이들중에서 F비용이 가장작은 것은 시작사각형에 오른쪽에 있는 사각형 하나이다.

 

이사각형은 다음 그림에서 파란색 안에 강조되어 있다.

 

제일 먼저 할 것은, 이것을 열린목록에서 빼는것이다.. 그리고 닫힌목록에 넣는다.

(이것이 바로 지금 저 사각형이 파란색 외관선으로 강조된 이유이다).

> 열린목록 7개(1,2,3,4,7,8,9), 닫힌목록 2개(5,6)

 

그리고 우리는 인접한 사각형들을 검사한다. (6번을 기준)

2, <-이미 열린목록에 있음

3, <-이미 열린목록에 있음

5  <- 시작 사각형 (닫힌 목록에 있음)

7, <-이미 열린목록에 있음

8 <-이미 열린목록에 있음

 

오른쪽에 있는 사각형은 벽이다. 그래서 이것들은 무시한다. 왼쪽에 있는 것은 시작사각형이고 이것은 닫힌목록에 있다. 그래서 이것역시 무시한다.

다른 4개의 사각형들은 이미 열린목록에 있다.

(만약 이미 열린 목록에 없는것이라면 열린 목록에 추가한다. )

 

 

그래서 우리는 그것들을(2,3,7,8) 이용한 길 중에 현재 이사각형(6)을 이용하는 것 보다 좋은 것이 있는지 G비용을 이용한 검사가 필요한다.

우상단의 사각형을 보자.(3)

이것의 G비용은 14이다. 만약 우리가 선택된 사각형(6)을 거쳐서 그곳으로 이동한다고 하면 G비용은 20과 같을것이다

(현재사각형이 G비용이 10이고 이것에서 수직으로 위쪽으로 한번 이동하였으므로 10을 더한다.).

 G비용 20은 14보다 크다. 그래서 이것은 좋은 길이 아니다. 그림을 보면 좀더 알기쉬울것이다.

단순히 시작사각형에서 대각선으로 1번 움직이는 것이 가로로 한번 세로로 한번 이렇게 움직이는거 보다 더 직접적이다.

 

우리가 열린목록상에 이미 있는 4개의 인접한 사각형(2,3,7,8)에 대한 처리를 할때, 현재의 사각형으로는 더 이상 길을 개선할 수 없다는 것을 알게 된다. 그래서 우리는 아무것도 변경하지 않고 이제는 인접한 사각형들에 주목하자(2,3,7,8).

 이제 우리는 이것을 가지고 처리 할 것이고, 다음 사각형으로 이동할 준비를 할 것이다.

 

그럼 열린목록에 있는 사각형은 7개로 줄었다.

> 열린목록 7개(1,2,3,4,7,8,9), 닫힌목록 2개(5,6)

 

그중에 가장 작은 F비용을 가지고 있는 것을 하나 고르자.

 흥미롭게도 이 경우 두개의 사각형이 54의 F비용을 가지고 있다.

어떤 것을 사용할까? 이건 사실 별로 중요한 문제는 아니다.

속도상의 목적으로는 둘중 열린목록에 더 늦게 추가된 것을 선택하는 것이 속도상 빠르다.

이것은 그냥 단지 하나의 성향인데 당신이 목표에 다가갈 때 검색상에서 더 늦게 발견된 사각형들을 선호하는 검색성향일 뿐이다. (각각 다른 두개의 A* 버전을 만들더라도 길이가 같은 각각 두개의 길을 찾게 될 것이기 때문에 F점수가 둘 다 같더라도 서로 다르게 처리해도 상관없다.)

 

그래서, 우리는 그냥 단지 아래쪽에 있는 것을 선택하자,(9)

 그리고 다음 그림에 보여지는 시작사각형의 오른편을 보자

 

 

이제, 우리는 인접한 사각형들을 검사할 때 바로 오른쪽에 사각형이 벽이라는 것을 발견하게 된다.

그래서 우리는 이것을 무시한다.

그 바로위도 똑같이 벽이기 때문에 이것도 역시 무시한다.

그리고 우리는 벽 바로 아래 사각형도 무시한다. 왜그럴까?

 왜냐하면 당신은 벽의 모서리 부분을 자르지 않고는 그 사각형으로 바로 갈수가 없기 때문이다.(뽀쪽한게 막구있잖아요~).

당신은 일단 밑으로 내려가서 그다음 그사각형을 거쳐서 지나간다.

이 처리에서는 이렇게 코너를 돌아서 이동한다.

(노트: 코너를 자르는 규칙은 옵션이다. 당신의 노드를 어떻게 위치시키느냐에 따라서 사용된다.)

 

이렇게 5개의 사각형(5,6,과 벽 2개, 벽의 아래에 있는 것 1개)이 계산에서 빠진다. 

현재사각형(9) 아래에 있는 2개의 사각형(10,11)은 열린목록에 없는것이다.

그래서 우리는 이것들을 추가한다. 그리고 현재 사각형은 이것들의 부모가 된다. 다른 3개의 사각형중 2개(5,6)는 이미 닫힌목록(시작사각형과 현재사각형위에있는 사각형, 둘다 파란색 외관선안에 있다)상에 있다.

그래서 우리는 이것들을 무시한다.

 

그리고 바로 왼쪽에 있는 마지막 사각형(9)은 현재사각형을 통해서 가는것보다 G비용이 적은지 검사를 해보자.

아니군~, 그래서 이제 다 했고 열린목록에서 다음으로 이동할 사각형을 검사해보자

 

우리는 목표사각형을 열린목록에 추가 할때까지 이 처리를 계속 반복한다. 이것에 대해 정리된 그림을 아래에서 볼수 있다.

 

 

시작사각형으로부터 2개의 사각형만큼 밑에 있는 사각형의 부모사각형이 이전 그림에서 변경되었다는 것을 주목하라. 전에 이것은 G비용이 28이었고 오른쪽위에 사각형을 가리키고 있었다. 지금은 G비용은 20이고 위쪽 사각형을 가리키고 있다.

이 일은 우리가 길찾기를 처리해 나가면서 어디선가에서 일어난 것이다.

어딘가에서 G비용을 검사했고 여기서 더 비용이 적게드는 길을 찾아냈다 그러므로써 부모가 바뀌것이고

G, F비용이 다시 계산되어진것이다.

 

이변화가 일어나는 동안에 예제에서 아주 중요하다고 보이는 것은 없는 것 같다.

 

가능성이 많은 장소들에서 이 검사는 목표지점으로 가는 가장 좋은 길을 찾아가면서 모든 것들을 다르게 만들것이다.(모든것들이란~ 더 빨리 갈 수 있는 곳을 말하는듯~-_- 그러니까 좀더 좋은 길은 G,F 값이 전하고 다른게 바뀐다. 이런 뜻인 것 같다.)

 

그래 그러면 이제 어떻게 최종적인 진짜 길을 찾아내지? 단순히, 단지 빨간 목표지점에서 시작해서 화살표를 따라서 부모사각형으로 한걸음씩 거슬러 올라가면 된다. 이렇게하면 결국 시작사각형까지 되돌아 가게된다. 그리고 그것이 당신의 최종적인 길이다. 이것은 다음의 그림에서 볼수있다. 시작지점 A에서 목표지점 B까지 이동하는 것은 단순히 길을 따라있는 각각의 사각형의 중심(노드)에서 다음사각형의 중심으로 이동하면 된다. 당신이 목표지점에 도달할때까지~ 쉽지~ㅋ

 

  A* 방식의 요약(Summary of the A* Method)  

좋다. 지금시점에서 이제 당신은 설명을 통해서 했던 것 들은 까먹었을 것이다. 차례차례 이 A* 방식을 여기에서 정리해보자.

 

1. 시작사각형을 열린목록에서 넣는다.

2. 다음의 과정들을 반복한다.

a) 열린목록에서 가장 낮은 F 비용을 찾는다. 그리고 우리는 이것을 현재사각형으로 선택한다.

b) 이것을 닫힌목록으로 바꾼다.

c) 현재 사각형에 인접한 8 개의 사각형에 대해?

● 만약 인접한사각형이 갈수없는 것 이거나 그것이 닫힌목록상에 있다면 이것은 무시한다. 그렇지 않은것은 다음을 계속한다.

● 만약이것이 열린목록에 있지 않다면, 이것을 열린목록에 추가한다. 이사각형의 부모를 현재 사각형으로 만든다. 사각형의 F,G,H 비용을 기록한다.

● 만약 이것이 이미 열린목록에 있다면, 사각형 G비용을 이용하여 이사각형이 더 나은가 알아본다. 그것의 G비용이 더 작으면 그것이 더 나은 길이라는 것을 의미한다. 만약 그렇다면, 부모 사각형을 그 (G비용이 더 작은)사각형으로 바꾸어라, 그리고 그 사각형의 G,F비용을 다시 계산해라. 만약 당신이 당신의 열린목록을 F비용으로 정렬하고 있다면 바뀐것에 따라서 열린목록을 다시 정렬해야한다.

d) 그만할 때

● 길을 찾다는 중 목표사각형을 열린목록에 추가하였을때,

● 열린목록이 비어있게 될 경우 이때는 목표사각형을 찾는데 실패한것인데 이 경우 길이 없는경우다.

 

3. 길 저장하기~. 목표사각형으로부터 각각의 사각의 부모쪽을 향하여 시작사각형에 도착할때까지 거슬러 올라간다. 이것이 당신의 길이다.~

 

 

♡♡♡♡♡♡♡♡♡♡♡♡♡♡♡♡♡♡♡♡♡♡♡♡♡♡

일단, 여기까지 A*알고리즘에 대한 전체적인 설명은 끝났습니다.

허접한 번역 끝까지 읽어 주셔서 감사합니다.

 

맨위에 링크를 따라 원문을 보시면 이뒤로 몇가지 팁들이 더 있는데 여기서는 번역하지 않았습니다.

귀차니즘의 영향으로~~ㅋ.

관심있는분은 직접가셔서 보시길 바랍니다.

 

번역이 개판이라 잘 이해가 안가시는분은 같이 올린 AStar.zip을 받아서 샘플과 소스를 보시면 좀더 이해가 잘가실겁니다.