초보자를 위한 A* 알고리즘 (기초개념 설명 및 소스) 인공지능...

 

초보자를 위한 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

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

이분이 번역해 놓은 글을 제가 나름대로 좀더 읽기 쉽게 수정하였습니다.

제가 다시 번역한 것이 아니라, 이 분이 작성하신 글을 보며 공부하다 수정한 것이니오해 없으시길 바랍니다.

제가 이해 한 것을 바탕으로 다시 써봤는데, 좀더 읽기 쉽게 수정되었길 바랍니다.

Cozy COZ . The Brainpower Season2

Blog: http://cozycoz.egloos.com/

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

 

여러분이 A*알고리즘을 쉽게 이해할때, 초보자들에게는 복잡하게 느껴질수도 있습니다

 

 A*알고리즘을 해석한 글이 웹상에 많이 존재하지만 그것과 달리 이글은 진정한 초보자들을 위한 것입니다.

이 글은 A* 길찾기 알고리즘에 대해 완벽히 보여주도록 노력하지는 않습니다.
그보다 앞으로 여러분이 좀 더 구체적인 글을 읽고 이해하는데 필요한 A*길찾기 알고리즘의 원리와 기본적인 것들을 설명하고 있습니다.
 

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

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

 

시작합시다


 


 

도입: 범위 찾기(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


F = 비용

G = 시작 A(녹색지점)로부터 새로운 사각형까지의 이동비용입니다. 길을 찾아갈 수록 G의 값은 커지겠죠.(A로부터 멀어지므로..)

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

( 값은 모든 장애물에 대해서는 고려하지 않고 현재 사각형에서 목적지점까지의 거기를 계산하는데 이때 대각선이동이 아닌 가로세로이동에 대한 비용으로 계산하는 것입니다. 장애물을 고려하지 않았으므로 이 비용이 최종이동비용과 같지 않을 확률이 크겠죠.)

 

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

 

위에 설명된 것처럼, G는 출발점으로부터 하나씩 얻게 되는 사각형으로 이동하는데 드는 이동비용이죠. 이 예제에서 우리는 세로 또는 가로로 이동하는데 각각 10의 비용, 대각선이동에 대해서는 14의 비용을 할당 할 것입니다.

(정사각형이고 가로세로가 10이면 대각선의 길이는 이등변삼각형 길이비 루트2:1:1에 의해 루트2 *10 : 10 : 10이 되므로(루트2는 약1.414)  약 14의 값이 나옵니다)

컴퓨터에서 숫자를 사용하는 것은 그만큼 빠르기 때문인데 단순화 시킨 숫자를 사용하지 않으면 길찾기가 매우 느려진다는 것을 알게 될 것입니다.

 

사각형의 G비용을 알아내는 방법은 그 부모로부터 G비용을 얻어와서 부모로부터 직각으로 움직였냐 대각선으로 움직였냐에 따라서 10또는 14를 추가해 주면 되는 것이죠.

 

H비용은 그 사각형 위치의 변화에 따라 예측될 수 있습니다.

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

 여러분은 현재사각형에서 목표사각형에 도달하기 까지의 대각선이동을 제외한 가로,세로로 이동한 총숫자를 계산할수 있고 거기에 10을 곱합니다. 이것이 바로 맨하탄방식인데 도시의 한쪽에서 다른 한쪽까지의 블록을 계산하는것과 같은 방식이기 때문에 명명 됐습니다. 여기서 여러분은 대각선으로 블록을 가로지를 수는 없겠죠. 위에서 말씀드렸듯이, H비용을 계산할 때 우리는 어떤 방해물도 무시합니다. 이 방식은 발견적방식이라고도 불리는데, 좀더 알기를 원하는 분은 여기(http://www.policyalmanac.org/games/heuristics.htm)에서 참고할 수 있을 것입니다.

 

G H를 더하므로써 F 가 계산됩니다.우리가 진행한 검색의 첫단계 결과를 아래 그림에서 볼수있습니다.
F,G,H
비용이 각각의 사각형에 표시되어 있는데, 시작점 우측에 있는 사각형안에 표시된것처럼, F는 좌상단에, G는 좌하단에, 그리고 H는 우하단에 표시됩니다.

 

 

녹색사각의 우측 사각형을 보면, F = G+H (40 = 10+30) 이죠. 이사각형은 부모사각형이 시작점이 됩니다. (그렇죠? 바로 아랫단계로 물려받았으니까요. 한번씩 사각형들이 퍼질때마다 자식들이 탄생한다고 보시면 되겠죠.)

G는 시작점과 새로운 사각형의 거리라고 했으니 10이죠. (한변은 10)

H는 장애물을 무시하고 가로세로 이동으로 목적지(빨간사각형)까지의 이동비용이므로 가로 3*10

이므로 30이죠. (G값이 14인 사각형들은 대각선 이동을 했기 때문인거 아시죠?)

이제 G, H값을 토대로 F값을 구하는 것이죠.


 

찾기 계속하기(Continuing the Search)

 

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

 

4. 선택된 사각형을 열린목록에서 빼고 닫힌목록에 추가합니다.

(부모가 되어 자식노드를 생성할 준비가 된거죠.)

 

5. 인접한 모든 사각형을 검색해서 닫힌목록에 있거나 갈수없는것(,,그밖에 장애물)들을 제외한 나머지 중에서 열린목록에 없는 사각형을 열린목록에 추가합니다.

 선택되었던 사각형을 열린목록에 추가된 새로운 사각형들의 부모로 만듭니다.

(선택되었던 사각형이란 4번에서 단힌목록에 추가된 그 사각형을 말합니다.

 새로운 사각형이란 5번에서 열린목록에 새롭게 추가된 사각형을 말하구요.)

 

6. 만약 인접한 사각형중에 이미 열린목록에 있는 사각형이 있다면 그 사각형으로 가는길이 더 좋은 길인지 확인하세요. 다시 말하면, 현재 선택된 사각형보다 G비용이 더 작은지를 검사하라는 것입니다. 만약 아니라면 아무것도 할 필요가 없지만 G비용이 더 작다면 선택되었던 사각형의 인접사각형들의 부모를 새로운 사각형으로 바꾸세요

(위쪽 그림에서 보면, 선택된 사각형으로 향하는 포인터들의 방향을 바꾸는 것을 말합니다.)
마지막으로, 그 사각형의 F G를 다시 계산합니다.


이제 이 작업들을 직접 해봅시다.

최초에 9개의 사각형중에 우리는 시작사각형을 닫힌목록에 넣은후 열린목록에 8개의 사각형을 가지고 있었습니다. 이들중 F비용이 가장작은 것은 시작사각형에 오른쪽에 있는 사각형 입니다. 이 사각형은 다음 그림에서 하늘색 외곽선으로 표시되어 있습니다.

 

 

제일 먼저 , 이 사각형을 열린목록에서 빼고 닫힌목록에 넣습니다. 그리고 우리는 인접한 사각형들을 검색하게 되는데, 그 오른쪽에 있는 사각형은 벽이죠. 그래서 무시하고, 왼쪽에 있는 것은 시작점이고 이것은 닫힌목록에 있으므로 이것역시 무시합니다.

 

장애물 4개와 시작점을 제외하니 4개의 사각형이 남는데 이 사각형들은 이미 열린목록에 있습니다. 그래서 우리는 그것들을 이용한 길 중에 현재 이 사각형을 이용하는 것 보다 좋은 것이 있는지 G비용을 검색합니다. 녹색사각형의 우상단의 사각형을 봅시다. 이것의 G비용은 14인데, 만약 우리가 현재 선택된 사각형( 녹색점의 우측사각형)을 거쳐서 그곳으로 이동한다고 하면 G비용은 20일 것입니다(현재사각형이 G비용이 10이고 이것에서 수직으로 위쪽으로 한번 이동하였으므로 10을 더합니다.). G비용 20 14보다 크므로 좋은 길이 아니죠.

가로세로 움직이는 것 보다 대각선으로 한번 움직이는게 비용이 적게 들죠 ( 20 : 14)

 

여러분은 현재 선택된 사각형으로는 더 이상 최소비용의 길을 찾을수 없다는 걸 아실것입니다. 그래서 이제 인접한 사각형들에 주목합시다.

 

현재 열린목록에 있는 사각형은 7개입니다. (위 그림에서 녹색 외곽선인 사각형) 그중에 가장 작은 F비용을 가지고 있는 것을 하나 고르세요. 흥미롭게도 이 경우엔 두개의 사각형이 54 F비용을 가지고 있죠. 어떤 것을 사용할지는 중요한 문제가 아닙니다. 속도상의 목적으로는 둘중 열린목록에 더 늦게 추가된 것을 선택하는 것이 빠르겠죠

(각각 다른 두개의 A* 버전을 만들더라도 길이가 같은 각각 두개의 길을 찾게 될 것이기 때문에 F점수가 둘 다 같더라도 서로 다르게 처리해도 상관없습니다.)

 

그래서, 우리는 그냥 아래쪽에 있는 것을 선택합니다.


 

새로운 사각형이 선택되었으니 다시 인접한 사각형들을 검색 해야겠죠.여기서 우리는 바로 오른쪽에 사각형이 벽이라는 것을 발견하게 됩니다. (무시) 그 바로위도 똑같이 벽이기 때문에 이것도 역시 무시합니다. 그리고 벽 바로 아래 사각형(마지막 장애물의 아래 사각형)도 무시해야 합니다. 왜그럴까요? 사각형 자체가 움직인다고 생각하세요. 현재 선택된 사각형이 오른쪽 아래로 대각선 이동한다면 마지막 장애물의 대각선절반을 잘라야 이동이 가능하겠죠? 그러므로 마지막장애물의 아래사각형도 현재 검색에서 제외시키는 것입니다.

여러분은 일단 밑으로 내려가서 그다음 그사각형을 거쳐서 지나가야 합니다.

(이건 말그대로 어떻게 정의하느냐에 따라 틀린건데, 개발자 마음이겠죠. 여기선 그렇게 적용하도록 합니다)

 

이렇게 5개의 사각형이 검색대상에서 빠집니다. 현재사각형 아래에 있는 2개의 사각형은 열린목록에 없는것이므로 추가시킵니다. 그리고 현재 사각형은 이것들의 부모가 되겠죠?

그리고 바로 왼쪽에 있는 마지막 사각형은 현재사각형을 통해서 가는것보다 G비용이 적은지 검사를 해보면 아니라는 걸 알 수 있습니다.

 

우리는 목표사각형을 열린목록에 추가 할때까지 이 처리를 계속 반복합니다. 계속된 검색의 결과는 아래그림입니다.


 

시작점 밑으로 2번째 사각형의 부모사각형이 이전 그림과 변경되었다는 것을 주목하세요.

전에 이것은 G비용이 28이었고 오른쪽위에 사각형을 가리키고 있었습니다. 지금은 G비용은 20이고 위쪽 사각형을 가리키고 있는데, 이 일은 우리가 길찾기를 처리해 나가면서 어디선가에서 일어난 것입니다. 어딘가에서 G비용을 검사했고 여기서 더 비용이 적게드는 길을 찾아냈습니다. 그러므로써 부모가 바뀌것이고 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. 길 저장하기.

 목표사각형으로부터 각각의 사각형의 부모사각형을 향하여 시작사각형에 도착할때까지 거슬러 올라갑니다.
이것이 여러분이 찾는 길입니다.

AStar-5622.zip <- 소스 다운로드


핑백

덧글

  • 나그네켄신 2010/04/20 23:01 # 삭제 답글

    실제론 fhat ghat bhat 이겠지만 수식편집기가 없는 안습이겠네요.. 설명은 깔끔하네요 =ㅅ=b
  • 코즈 2010/04/27 10:32 #

    방문해주셔서 감사합니다 켄신님~
  • RockOn 2010/10/27 23:54 # 삭제 답글

    진짜 잘읽었어요. 시간 가는지 모르고..ㅡ.;;

    어떻게 진행되는지 알겠는데, H랑, G값을 어떻게 알 수 있는지..ㅜㅜ
  • 코즈 2010/11/01 11:46 #

    방문해주셔서 감사합니다^^
    G, H 값은 탐색할 때 마다 달라지겠지요.
    G는 시작노드에서 현재노드와의 거리, H는 현재노드에서 목적지노드와의 거리고
    G+H를 하게되면 시작노드에서 목적지노드까지의 총 거리가 나오게 됩니다.

    한 노드의 거리를 10으로 환산했을 때, 만약 대각선으로 움직이게 된다면 14의 거리값을 가진다는 것은
    알고 계실 겁니다.

    인공지능이라는 것이, 사람과 달라서, 조건조건 마다 탐색을 하고 분석해서
    모든 가능성에서 원하는 결과를 좁혀나가게 되므로,
    첫 시작노드에서 목적지노드로 어떻게 가야할지 먼저 계산을 해야겠죠.

    처음에 시작노드에서 모든 열린 가능성을 기억하고, 그 중 첫번째 가능성부터 탐색을 시작해야합니다.
  • 코즈 2010/11/01 11:52 #

    탐색 후 다시 계산을 하고,
    현재 노드에서 목적지까지 가려면, 주변 노드의 F값을 봐야하죠. (F=G+H)
    F값이 가장 작은 노드를 찾아찾아 가는 것인데,
    문의하신 부분이 G, H값을 알 수 있는 부분인데,
    임의로 10, 14의 각 노드간의 거리를 지정해두었으므로,
    현재위치에서 목적지위치까지의 거리를 장애물 고려하지 않고 단순계산해보면
    가로 세로 대각선 몇번만에 도착할 수 있는지 알 수 있으므로
    (G =10+10+14, H = 10+14) 각 노드마다 G,H값을 구할 수 있습니다.
    아.. 글 실력이 ㅠ
  • 2011/03/07 18:58 # 삭제 답글

    정말감사합니다 A* 알고리즘 공부하는데 많은 도움이 되었습니다 .. ^^
  • 코즈 2011/04/01 15:45 #

    방문해주셔서 감사드립니다 민님~^^
  • finebe 2011/12/27 21:34 # 삭제 답글

    우왓 감사합니다. A*공부하는데 도움이 많이 되었어요~
    이제 구현만 하면 되겠네요 ㅋㅋ;
  • 코즈 2015/06/24 11:07 #

    감사합니다 :)
  • 레드락 2012/05/10 01:21 # 답글

    감사합니다. 해당 포스트 담아 갑니다.
  • 코즈 2015/06/24 11:06 #

    감사합니다 :)
  • 후라 2012/06/16 18:08 # 삭제 답글

    아이폰으로 게임을 만들다가 에이스타 알고리즘이 꼭 필요해서 한참 찾아다녔는데, 잘읽고 ^^ 잘 만들어서 코드해결해서 기쁘네요. ㅎㅎㅎㅎ 감사합니다. 소스가 깔끔하게 되어 있어서 객체화하는데 정말 좋았습니다.
  • 코즈 2015/06/24 11:06 #

    감사합니다. 도움이 되셨다니 기쁩니다.
  • MCP 2013/10/07 22:40 # 삭제 답글

    a* 정말 깔끔하게 정리하셧네요 잘배우고 갑니다
  • 코즈 2015/06/24 11:06 #

    도움이 되셨다니 기쁩니다.
  • nospaces 2014/04/17 10:45 # 삭제 답글

    너무 설명히 잘되어 있네요~
    소스 다운받아갑니다! 감사해요~
  • 코즈 2015/06/24 11:06 #

    감사합니다 :)
  • 방문자 2014/07/07 20:41 # 삭제 답글

    포스트 잘 보았습니다.
    하지만 벽 바로 밑쪽을 탐색하지 못하는건 이상하네요.
    구현상에서는 크게 문제가 안될 이슈인것 같은데, 굳이 사각형이 이동하지 못한다는?? 미묘한 설명으로 탐색이 안된다고 하는건 문제가 있지 않을까요? 실제로 a*는 대각선 추적이 됨에도 불구하고 장애물 바로 앞에서만 맨하탄스럽게 이동하는게... 원본 포스트에서 있던 문제를 인식하지 못하신것 같습니다. 이포스트는 장애물을 만나면 대각선 이동을 하지 않는 A*라고 따로 설명이 필요해 보이네요. 잘봤습니다
  • 코즈 2015/06/24 11:05 #

    안녕하세요 반갑습니다.
    좋은 말씀감사합니다. 본문에 나오듯 이 부분은 개발자가 어떻게 정의하느냐에 따라 달라질 수 있는 부분입니다.
    이동하는 주체가 작은 점이라, 벽이 있더라도 대각선 이동에 영향을 받지 않는다는 개념이면 대각선이동이 가능하도록 할 것이고,
    본문처럼 사각형 전체가 움직인다고 가정을 했을 때에는 이동 할 수 없는 영역이 되는 것도 맞겠지요.
    말씀하신대로, 장애물을 만났을 때, 그 장애물을 겹치면서 대각선 이동을 하지않는 A* 겠네요.
    감사합니다.
  • 제네로소 2014/10/12 13:37 # 삭제 답글

    첫 번역을 한 사람입니다. Translated By Generosus 의 제네로소 입니다. ^^
    회사에서 A*를 쓸일이 있어서 자료를 다시 찾고 있었는데 낮익은 화면을 봐서 깜짝 놀랐네요.
    카페는 닫은지 오래되었거든요.
    이렇게 자료가 사라지지 않게 보존해 주신 코지님 정말 감사드립니다.
  • 제네로소 2014/10/12 13:39 # 삭제

    앗 보존이 아니고 더 좋은글로 만들어 주셨죠.
    저도 다시 잘 공부하고 갑니다. ^^
  • 코즈 2015/06/24 10:57 #

    ^^
    이렇게 뵙게되서 반갑습니다. ㅎㅎ
    좋은 자료 감사합니다 :)
  • 111 2014/10/23 15:38 # 삭제 답글

    이알고리즘을 바탕으로 최단거리 길찾기 슈도 코드를 짤려하는데
    도움좀주세요
    알려주세요
  • 연구원 2015/02/02 14:35 # 삭제 답글

    자세한 설명 덕분에 많은 도움되었습니다. 감사합니다 ^^
    이해가 잘 되지 않는 부분이 있어서 질문드립니다.
    처음에 시작사각형(초록색)의 왼쪽 사각형의 H값이 왜 50 인가요??
  • 코즈 2015/06/24 11:00 #

    메일 주셨던 분 같네요. 반갑습니다~
  • 평범한프로그래머 2015/02/26 15:26 # 삭제 답글

    자세한 설명 감사합니다 ㅎㅎ 블로그에 링크좀 남길께요 ㅎㅎ
  • 코즈 2015/06/24 10:59 #

    넵 감사합니다.
  • 공부중입니다 2015/02/27 00:03 # 삭제 답글

    감사합니다. 블로그에 담아가도될까요?ㅎㅎ!
  • 코즈 2015/06/24 10:59 #

    얼마든지요. 감사합니다.
  • 와.. 2015/05/23 16:33 # 삭제 답글

    한눈에 이해되는 글이네요. 정말 잘 봤습니다. !!
  • 코즈 2015/06/24 10:58 #

    도움이 되셨다니 기쁩니다~
  • locky 2015/07/31 20:24 # 삭제 답글

    많은 도움이 되었습니다
    그런데 제가 숙제로 새로운 길찾기 알고리즘을 만들어봐야 하는데 도움을 주실 수 있나요??
  • sdf 2015/10/16 12:27 # 삭제 답글

    목표지점이 ㅁ 모양으로 막혀있을때에는 어떻게예외처리를 해야하나요?
  • 박병욱 2015/10/22 23:41 # 삭제 답글

    위에도 언급은되어있지만 잘이해가안되서 질문합니다.
    이미 값을받은 노드중에서 길이 막혀서 여기저기 다시찾는과정에서다시 값이 바뀌는 노드가있는데요 그기준이 정확이 몬지 모르겠어요
  • 코즈 2016/01/25 15:20 #

    안녕하세요
    해당 예문에서 말씀인가요?
    길이 막혀 다시 찾는 과정에서 변하는 노드가 어떤 건지요?
  • 박병욱 2015/10/22 23:42 # 삭제 답글

    위에도 언급은되어있지만 잘이해가안되서 질문합니다.
    이미 값을받은 노드중에서 길이 막혀서 여기저기 다시찾는과정에서다시 값이 바뀌는 노드가있는데요 그기준이 정확이 몬지 모르겠어요
  • 박병욱 2015/10/22 23:42 # 삭제 답글

    위에도 언급은되어있지만 잘이해가안되서 질문합니다.
    이미 값을받은 노드중에서 길이 막혀서 여기저기 다시찾는과정에서다시 값이 바뀌는 노드가있는데요 그기준이 정확이 몬지 모르겠어요
  • admin 2016/01/21 17:35 # 삭제 답글

    질문 있습니다. 초기화면에서 우상 방향으로 이동 헀을때
    G는 피타고라스 정리에 의해서 14 정도의 값이 나왔을 것 이고 H의 경우에 새로운 지점에서 부터 목적지 까지의 직선 거리라고 알고있는데
    그렇다면 (x, y)의 좌표를 가지고 있을때 유클리디안의 거리구하는 공식으로 계산해보면36 정도가 나오는것 아닌가요?
  • 코즈 2016/01/25 15:34 #

    안녕하세요.
    전제가 틀린 것 같습니다.

    좌표를 가지고 유클리디안 거리로 계산시, 약 31.6의 값이나
    올라가보시면 "H = 대각선이동이 아닌 가로세로이동에 대한 비용으로 계산" 으로 정의하고 있어 40의 값을 가집니다.
  • 샘물 2016/02/24 16:22 # 삭제 답글

    좋은자료 감사합니다.
    A*알고리즘 공부하는데 큰 도움이됬습니다.
  • 샘물 2016/02/24 16:22 # 삭제 답글

    좋은자료 감사합니다.
    A*알고리즘 공부하는데 큰 도움이됬습니다.
  • ㅇㅇ 2016/03/18 20:43 # 삭제 답글

    와 정성봐 ㄷㄷ이렇게 좋은 정보 줘서 고맙습니다1
  • ㅇㅇ 2016/03/18 20:43 # 삭제 답글

    와 정성봐 ㄷㄷ이렇게 좋은 정보 줘서 고맙습니다1
  • ㅇㅇ 2016/03/18 20:44 # 삭제 답글

    와 정성봐 ㄷㄷ이렇게 좋은 정보 줘서 고맙습니다1
  • ㅇㅇ 2016/03/18 20:44 # 삭제 답글

    와 정성봐 ㄷㄷ이렇게 좋은 정보 줘서 고맙습니다1
  • ㅇㅇ 2016/03/18 20:44 # 삭제 답글

    와 정성봐 ㄷㄷ이렇게 좋은 정보 줘서 고맙습니다1
  • ㅇㅇ 2016/03/18 20:44 # 삭제 답글

    와 정성봐 ㄷㄷ이렇게 좋은 정보 줘서 고맙습니다1
  • ㅇㅇ 2016/03/18 20:44 # 삭제 답글

    와 정성봐 ㄷㄷ이렇게 좋은 정보 줘서 고맙습니다1
  • 감사합니다 2016/05/29 06:40 # 삭제 답글

    많은 도움 되었습니다. 감사합니다
  • 감사합니다 2016/05/29 06:40 # 삭제 답글

    많은 도움 되었습니다. 감사합니다
  • 감사합니다 2016/05/29 06:40 # 삭제 답글

    많은 도움 되었습니다. 감사합니다
  • 감사합니다 2016/05/29 06:40 # 삭제 답글

    많은 도움 되었습니다. 감사합니다
  • ddd 2016/09/26 12:02 # 삭제 답글

    대박 감사합니다. 그런데 대각선 이동은 무조건 하지않는다 하려면 열린목록에 대각선에있는 사각형은 추가를 안한다면 해결되는건가요???
  • 발토 2016/09/27 13:41 # 삭제 답글

    java를 사용해서 만들고 있는데 만약 되돌아 가야 되는 경우가 생기면 어떻게 처리를 해야되는건가요 열린목록의 gx비용이 더 작으면 부모노드를 옴겨서 추적해서 목표지점 까지는 가는데 만약 만힌길이 있어서 다시 돌아가야 하는 경우가 생기면 무한 루프에 빠져 버리네요 ㅠ
  • ㅁㄴㅇㄻㄴㅇㄹ 2016/12/04 14:11 # 삭제 답글

    그리고 바로 왼쪽에 있는 마지막 사각형은 현재사각형을 통해서 가는것보다 G비용이 적은지 검사를 해보면 아니라는 걸 알 수 있습니다.

    이 부분이 이해가 안되네요
    맨 처음 사각형을 우측으로 이동 후, 열린 목록에서 더 적은 비용으로 갈 수 있는 타일인 대각선 아래에 위치한 타일로 한번에 이동하도록 재조정하지 않았나요?
    그 다음 이 타일에서 탐색하는 중에, 한 칸 아래로 이동하는 경우와 좌측으로 이동하는 경우의 총 비용과 출발점으로부터의 비용을 비교해보면 그림에도 나와있듯이 출발점 아래의 사각형이 더 적습니다. 현 타일을 기준으로 다시 계산하면 출발점으로부터의 비용도 같은 값이 나오게 됩니다.
    어떻게 하든 출발점 아래의 타일이 배제될 일이 없는데 뭐가 "아니라"는 건지 명확한 기준을 알 수가 없어요.
    추후에 댓글 보시면 답변 부탁드립니다. ㅜ
댓글 입력 영역


Post-it



cocos2d-x 게임개발자의 블로그입니다