출처 :  http://blog.naver.com/PostView.nhn?blogId=hermet&logNo=95405999

대학교 2학년, 홀로 어두운 방 안에서 만두로 끼니를 때우며 프로그래밍을 하던 시절...

당시 나도 울티마나 한번 따라 만들어본다고 했던 게임이 불현듯 떠올라, 소스를 훑어보다가 A* 알고리즘을 다시금 정리하게 됐습니다.

(뭥미... -_- )

A* 는 길찾기 알고리즘이며 적절한 비용을 요구한다는 점에서 유용하게 사용됩니다.

넓이 우선과 깊이 우선 탐색을 조합하고 목적지까지의 거리를 고려하여 최적의 비용을 찾아 가는 휴리스틱(Heuristic)한 기법을 이용하죠.

적절한 설명을 위해서 당시 게임을 참고 하겠습니다.

 자, 왼편이 실제 게임 화면이라고 가정했을 때, 오른편은 맵의 내부 구조를 시각화 한 것이라고 보시면 됩니다. 위 게임의 2D 맵은 격자들로 구성하여 지형 데이터를 관리하죠. (격자는 실제보다 크게 그렸습니다)  여기서 색깔이 칠해진 격자는 블록된 구역이라고 보시면 됩니다. 즉 장애물 등으로 캐릭터가 갈 수 없는 곳이죠. 응? 저 벽은 지나갈 수 없는 것 아닌가? 라고 생각하실 수도 있는데 원근감을 생각하시면 캐릭터는 벽 뒤쪽으로 지나갈 수가 있기 때문에 블록된 곳이 아닙니다.

자, 어쨌든... 여기서 임의의 위치로 캐릭터가 이동한다고 가정하고 A* 알고리즘이 어떤 순서로 길을 탐색하는지 보도록 합시다. (모든건 수작업이라는 사실... ㅜㅜ)

노란색 그리드가 목적지라고 가정했을 때, 캐릭터 위치로부터 이동 가능한 그리드를 탐색합니다. 즉, 넓이 우선 탐색을 하는 거죠. 그리고 이동 가능한 8방향에 대한 그리드 검색을 마친 후, 목적지에 가장 가까운 노드를 선택하게 됩니다. 여기서는 녹색화살표.

여기서 데이터는 다음과 같이 관리를 하게 됩니다. Open Node와 Close Node라고 하는 두 개의 링크드 리스트를 구축하게 되는데, Open Node는 앞으로 탐색을 시도할 여지가 있는 노드들의 후보 리스트로 볼 수 있습니다. 즉 한 노드는 8 방향에 대해서 탐색 여부를 시도해야 하는데, 이것을 아직 수행하지 않은 노드가 OpenNode 목록에 추가되는 것이고,  CloseNode는 현재 검색한 노드들 중 더 이상 탐색을 시도할 여지가 없는 노드 리스트로 볼 수 있습니다.  그리고 OpenNode에 목록이 추가될 땐, 항상 목적지까지의 거리의 비용이 적은 순으로 정렬 상태를 유지하죠.

따라서 현재, OpenNode 리스트는 녹색을 비롯한 노란색 화살표의 노드들이 연결되어 있고  CloseNode 리스트는 출발점 노드 하나가 됩니다.  

다음 탐색을 시도합니다. 이번에는 이동 경로의 후보로 선택된 녹색 화살표를 중심으로 8방향을 탐색하게 됩니다. (즉, A*는 가장 가능성이 있는 노드들을 우선적으로 따라가며 탐색을 하므로 깊이 우선 탐색을 하게 되는 것이죠.)

OpenNode에는 새로 탐색한 노란색 화살표의 노드가 새로 추가되었으며

CloseNode에는 출발점과 옅은 녹색 화살표의 노드로 구성이 됩니다.

참고)

 노란색 화살표 - OpenNode에 새로 추가된 노드

 연한 노란색 화살표 - OpenNode에 기존에 추가된 노드

 녹색 화살표 - CloseNode에 새로 추가될 노드

 연한 녹색 화살표 - CloseNode에 기존에 추가된 노드

하지만  막다른 길이어서 다시 OpenNode의 후보로부터 탐색을 하게 됩니다. 하지만, 갈 수 있는 길은 바로 아래 한 칸 밖에 없겠지요.

자, 결국 다음 탐색 역시 모두 블럭되어 있거나 이미 탐색된 지역이기 때문에 OpenNode 리스트의 후보로 탐색을 다시 시도하게 됩니다. 결국 위와 같이 되는 것이지요.

그리곤 다음 탐색 후보는 OpenNode 중에서 목적지와 가장 가까운 노드가 되므로 결국 출발점에서 바로 오른쪽 위치에 대해 탐색 시도를 하게 됩니다. 물론 그 노드는 이미 여덟 방향에 대해 탐색이 되었기 때문에 결국, 바로 CloseNode로 들어가게 되겠죠. 그리고 그 다음 후보는 바로 시작점의 바로 위 노드가 되며 역시 같은 이유로 CloseNode로 들어가며, 그 다음 후보는 맨 상단의 노드가 될 겁니다. (아래 그림)

물론 맨 상단 노드를 확장했을 땐, 새로 탐색한 노드들은 기존 OpenNode 후보보다 모두 멀기 때문에 다음 후보는 시작점 바로 오른쪽 하단 노드가 되는 것이지요.

결국 이런식으로 확장을 하다 보면, 최종적으로 목적지에 도착하게 될 겁니다.

그리고 이 흰색 화살표의 노드들을 역으로 추적하면 결국 최단거리가 나오는 것이지요. 물론 흰색 노드는 ClosedNode에 포함된 노드들이며 최종적으로 목적지에 도달했을 때의 노드를 역으로 추적하면 되는 겁니다.

어때요.. 참 쉽죠잉?  (아 힘들어.. 이거야 말로 충격과 공포 ㅡㅜ)

자, 이론은 이해하셨을 거라고 믿고... 이제 구현 한번 들어가 보도록 하겠습니다.

참고로 평가치 값은 degree + distance로 구하는데 거리와 degree의 값의 단위는 해당 프로그램에 맞게 적절하게 정하시면 될 것 같습니다. (degree간의 값의 차이가 1이라고 본다면 인접한 노드들 간의 거리도 1로 지정하는게 적절할 것 같습니다.)

그리고,  OPEN_NODE와 CLOSE_NODE 그리고 스택을 위한 전역 데이터를 각각 선언합니다.

다음 함수들은 구현하기에 어렵지도 않고 중요하지도 않으니 간단한 주석 설명으로 대처 하였습니다.

물론 위의 의사코드 부분은 첨부파일에 완성되어 있으니 참고하시기 바랍니다.

자, 이제부터 좀 중요한 부분들을 보도록 하죠. 먼저 길찾기 시작 함수입니다.

자 다음으로, 현재 탐색 노드를 확장하는 함수를 보도록 합시다.

여기까지는 이해가 되셨길 합니다. 사실 위의 예에서 보여준 게임같은 경우, 대각선 이동은 인접한 두 그리드가 이동 가능할 때 허용되도록 컨셉을 잡는게 더 현실적일 겁니다. 따라서 대각선 판단은 인접한 두 노드가 이동 가능할 때 판단하면 될 듯 합니다. 그건 직접 수정 가능하시겠죠? :)

-인접한 두 노드의 블럭 상태로 대각선 이동 안됨-

자, 다음 함수를 보도록 합시다. 이번 함수는 노드를 확장하고 필요한 경우 리스트를 재정렬합니다.

이제 좀 머리가 아파오실 수도 있습니다. 본 내용과 소스만으로 이해가 되지 않는다면 직접 가상의 길을 그린 후에 이 알고리즘을 따라 직접 확장해 보시는걸 추천드립니다. 그러면 확실해지겠죠.

주석 설명이 다소 부진할 수 있을지도 모르겠습니다. 예제의 경우에 나타나지 않았던  예외적인 상황에 대한 처리부분이지요. 이 부분은 CloseNode의 순서가 바뀌면서 그에 따른 연결된 노드들을 재평가합니다.

마지막으로 노드를 OpenNode에 추가합니다.  주석 내용이 번잡하게 들릴 수도 있는데 결국은, 노드 삽입 시 목적지에 가까운 순서를 유지 한다는 점.

제 역량 부족으로 설명이 힘들군요. 이중 연결 리스트 2개와 스택이 서로 얽혀있어서 말로는 다소 이해하기 힘들 수도 있구요.

예제 소스를 활용하여 진행 노드 상황을 직접 표현하여 이해해보는 것이 명확할 듯 합니다. ㅎㅎ (이런 무책임한...)

자, 어쨌든 A*에 대한 설명은 여기서 마치렵니다. 사실 최적화 방안은 여러 존재합니다. 예를 들면 직선 이동 노드들에 대해선 생략을 한다던지, 맵에 대한 WayPoint 정보를 추가로 삽입하여 이를 토대로 길찾기를 수행한다든지.. 적어도 위 게임에서 문에 대한 위치 정보를 참고할 수만 있어도 매우 최적화된 탐색이 수행되겠지요.

또한 3D 공간에 대해서는 다소 데이터 자체가 매우 상이할 겁니다. (추가적인 정보는 Game Programming Gems 1권을 추천합니다.)

부족한 설명은 첨부 소스를 참고하여 보충하시기 바랍니다.

https://github.com/qiao/PathFinding.js

출처 : http://cozycoz.egloos.com/viewer/9748811

여러분이 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. 길 저장하기.

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

소스

a star pathfinder v. 1.92.zip

http://qiao.github.io/PathFinding.js/visual/

길 찾기 알고리즘 중에 유명한 것이 A*(A star)라는 것이 있는데 이것을 간단하게 구현하는 방법을 정리한 것이다. 프로 게임 엔진에선 길 찾기 기능도 제공을 한다. 아마추어용 공짜 게임 엔진에선 제공하지 않는다. 물리적 충돌 현상 시뮬레이션은 공짜 게임 엔진에서도 제공한다. 프로 게임 엔진에서도 인공지능은 제공하지 않는다. 이 부분은 직접 구현 해야 한다. A*에 대한 소개는 다른 글에 있다.(http://blog.daum.net/jty71/15645104)

먼저 기본적으로 공간을 조각으로 나눈다. 보통 삼각형, 육각형, 사각형, 마름모꼴을 이용해서 평면을 잘게 나눈다. 이렇게 공간을 나누고 시간을 나누면 편리한 점이 많다. 공간을 잘게 나누어 바둑판을 만들어 거기에 유닛을 배치한다. 마치 장기와 바둑과 비슷하다. 지도는 M x N 평면 2차원 배열이다. 3차원 이상의 다차원 배열은 사용하지 않는다. 왜냐하면 첨자 계산 시간이 그만큼 소모된다. 고로 M x N 크기는 모두 같지만 다른 이름의 여러 바둑판 배열을 만들어 사용한다. 제일 기본은 지도의 지형을 묘사하기 위한 바둑판 배열이다. 이 배열은 지형 그림의 번호를 저장한다. 그 다음에 나무, 건물, 이동 유닛 등의 배치 정보를 기억하는 배열이다. 그 다음이 전쟁 안개라는 것으로 아직 밝혀지지 않는 지도는 검게 나타나며, 지도는 밝혀 졌지만 유닛이 없어 관찰 할 수 없는 곳은 중간 정도로 어둡게 나타나며, 유닛이 있어 관찰이 가능한 곳은 밝게 정상적으로 나오는 그런 것을 묘사하기 위한 배열이다. 그 다음에 길 찾기에서 사용하는 배열이다. 길 찾기 배열은 Max(최대)/Min(최소)을 찾기 위한 1차원 배열도 함께 사용한다.

유닛을 배치하는 배열을 사용하는 장점은 이렇다. 화면에 표시되는 지역의 유닛만 찾으려고 할 때 이 배열을 사용한다. 유닛이 이동 중에 자신과 충돌할 것 같은 다른 유닛을 찾을 때 이 배열을 사용한다. 즉, 유닛이 수백 개가 지도에서 활동 중이라도 모두 충돌 검사를 할 필요가 없다. 지금 보이는 영역의 유닛만 그리면 되고, 지금 이동 중인 유닛 근처의 유닛만 거리 계산에 이용하면 된다. 유명한 실시간 전략 시뮬레이션을 보면 수백 개의 유닛이 등장한다. 나무, 건물, 이동 유닛들을 모두 합하면 수백 개는 된다. 이런 것을 실시간으로 처리하려면 공간을 나누어 배치해야 유리하다.

타일 하나에 유닛이 4개나 9개가 들어갈 수 있도록 되어 있다. 유닛의 크기가 다양한데 가장 큰 유닛이 타일 하나에 배치 된다. 고로 그보다 작은 유닛들은 여럿이 타일 하나에 배치될 수 있다. 고로 유닛 배치용 바둑판 배열은 3차원 배열이 되어야 한다. 한 타일 안의 유닛의 위치는 비교적 자유롭다. 그 유닛의 중심이 그 타일 안에 있으면 그 타일 소속이 된다. 허나 유닛의 위치가 그 안에서 자유롭기 때문에 매우 자연스럽게 배치 되어 보인다. 하지만 이는 눈속임이고 유닛의 크기와 위치를 수학적으로 계산하면 최대 4개(또는 9개) 이상 들어가지 못하게 되어 있다. 왜냐하면 유닛의 크기를 타일 안에 4개, 9개만 들어가도록 결정했기 때문이다.

길 찾기 알고리즘인 A*는 다른 글에서 설명을 했다. 길 찾기를 하려면 지도 타일과 같은 형태의 2차원 배열과 최적의 길을 선택하기 위해서 Max/Min 값을 찾을 수 있는 1차원 배열이 필요하다. 2차원 배열에선 가상의 유닛이 이미 갔던 길을 표시하고, 그 길의 평가 결과를 기록한다. 즉, 이 타일에 오기 전에 어디에서 왔으며, 이 타일에 도달하기까지 필요한 비용은 얼마이며, 이 타일에서 목표까지 직선 거리는 얼마이며, 그래서 최종 평가 결과(지나 온 길의 비용 + 목표까지 직선 거리)는 얼마인지 기록을 한다. 선택할 타일 후보자들 중에 어떤 것이 가장 짧은 길인지 결정을 해야 한다. 그래서 후보자 타일을 기록하고 최소 비용을 찾아 주는 1차원 배열이 필요하다. 이 1차원 배열에는 항상 다음에 선택할 타일들이 들어 있다. A*에선 장애물을 만나기 전까지는 직진을 한다. 그러다 장애물을 만나면 둥글게 확장하며 길을 찾는다. 돌아갈 틈이 발견 되면 거기서 또 직진을 하여 최소 비용의 길을 결정하게 된다. 이 때 둥글게 확장할 때 가장 밖의 얇은 껍질들이 선택해야 할 후보 타일이 되는데 이것들은 1차원 배열에서 기록하고 관리한다.

복잡한 A*를 구현하기 전에 먼저 길이 있는지 없는지 판단부터 해야 한다. A*는 타일에서 8방향으로 확장하면서 계산을 하기 때문에 시간이 많이 걸리고 장애물을 만나서 둥글게 확장하는 부분에선 시간 소모가 많다. 이것을 좀 더 짧게 끝내려면 약간 다른 지능적인 방법을 추가로 사용해야 한다. 먼저 일단 길이 있는지 없는지 판단해야 한다. 먼저 출발점과 목적지를 직선으로 달려 본다. 직선을 긋는 것과 같다. 이 직선에선 타일 중심을 따라 갈 필요는 없다. 그러면 중간에 장애물을 만날 것이다. 이 장애물의 특성에 따라서 길이 없던가, 길이 양쪽으로 돌아갈 수 있거나, 어느 한 방향으로만 돌아가야 한다. A Type 지형에선 길이 없다. 장애물을 만났을 때 그 장애물의 표면을 따라 가 보면 지도의 경계선에 도달한다. 양방향으로 가도 경계선에 도달했다면 막힌 길이다. 고로 길 찾기를 계산할 필요가 없다. 이런 것을 벽 타기라고 한다. 보통 이런 계산은 지도가 완성될 때 해 두면 좋다. 즉, 장애물에 특성이 표시되어 있는데 그 장애물의 특성을 보니 A형 장애물이라면 더 계산해 볼 것도 없다. B형 장애물도 목표에 도달할 수 없다. B Type 장애물의 표면을 따라 이동해 보니 다시 제자리로 왔다면 이것은 성벽처럼 목표를 감싸고 있는 것이다. 이것도 지도를 제작할 때 미리 계산해서 장애물에 식별표시를 붙이면 된다. B형 장애물이면 답이 없는 것이다. C형 장애물의 경우는 어느 한 쪽에 통로가 있다. 고로 이런 것은 어느 방향으로 꺾으면 된다는 정보를 미리 계산해서 장애물에 부여하면 된다. D Type 장애물의 경우는 양쪽으로 돌아갈 수 있다. 이런 장애물의 표면을 따라 돌면 역시 제자리가 되는데 장애물 특성으로 보면 B와 D는 같은 형태다. 목표물이 어디에 있는지가 차이가 있다. 이 경우 B와 D 경우를 구분해야 하는데 이는 목표물이 위치한 영역의 특성을 보면 된다. 지도를 제작할 때 영역들이 단절 되어 있는지 확인해서 영역 ID를 부여할 수 있다. 만약 시작점과 목표점의 영역 ID가 같다면 이것은 이어져 있다는 뜻이 된다. 영역 ID가 다르면 이 둘은 장벽에 의해 갈라진 것이다. 이렇게 미리 계산을 해 놓고 영역과 장애물에 어떤 정보를 부여하면 무식하게 A*를 항상 계산할 필요가 없다. 목표지점에 가장 가까운 곳을 새로운 목표로 정해야 한다.

A*의 계산법을 이용하지 않는 다른 종류의 길 찾기 방법이다. 먼저 시작 지점에서 목표 지점까지 직선으로 달려 본다. 장애물을 만나면 장애물과 대화하여 어떤 종류인지 돌아갈 코너는 있는지 확인한다. 장애물과 대화가 불가능한 게임이라면 장애물의 표면을 따라 벽 타기를 한다. 충돌 지점에서 시작해서 좌측이나 우측으로 돌아 보면 직선으로 연결할 수 있는 코너 지점이란 것을 발견할 수 있다. 이 코너 지점이 많이 발견되면 돌아가는 길이 복잡하다는 말이 된다. 반면에 목표 지점에서 시작 지점으로 역으로 길을 추적해 보니 이런 코너 지점의 수가 더 적어진다면 일단 그 길을 택한다. 가장 적은 코너 지점을 가진 길을 택한 후에 마지막 코너 지점을 시작 지점이나 목표 지점에 직접 직선으로 연결하면 최적화 된 길을 얻을 수 있다. 이 방법의 원리는 장애물 돌출부 주변에 생기는 코너 지점은 서로 직선으로 연결할 수 있다는 점이다. 즉, 코너 지점을 발견하여 연결하면 그 중간은 직선으로 연결되기 때문에 따로 복잡하게 계산할 필요가 없다는 것이다. 장애물에 충돌하는 지점(입사 지점)과 장애물 충돌에서 벗어나는 지점(출사 지점) 이 둘을 우회하여 연결하는 코너 지점들을 먼저 발견한 후에 양쪽 끝의 코너 지점을 직접 시작 지점과 목표 지점에 연결이 되는지 확인하면 최적의 길을 얻게 된다. 즉, 장애물 발견, 장애물 우회하면서 코너 발견, 마지막 코너를 직접 연결해 보기, 이런 식으로 일을 진행한다. A*보다는 간단하다.

A* 방법은 아니지만 이동 비용이 0 아니면 무한대인 간단한 형태의 지형에선 A* 대신 이용할 수 있는 방법이다. 즉, 갈 수 있거나 갈 수 없는 2가지 경우뿐이다. A*는 이동 비용이 0 ~ 무한대까지 다양한 지형에 적용하는 것이 더 좋다. 먼저 직선 달리기를 해서 입사 지점과 출사 지점을 구한다. 입사 지점과 출사 지점을 벽을 타고 돌아서 연결하면 장애물의 특징이 나온다. 입사 지점과 출사 지점이 만나야 길이 있는 것이다. 만나지 못 하면 길이 없는 것이다. 우회로가 2가지인 경우와 1 가지인 경우가 있을 것이다. 우회로가 2가지인 경우는 2개의 경로 중에 짧은 것을 선택하는 문제가 있다. 일단 입사~출사 벽 타기 경로를 구한다. 이 경로를 구하는 중에 코너 지점을 찾게 된다. 코너 지점을 찾으면 코너 지점 사이의 경로는 직선으로 대체할 수 있기 때문에 길을 묘사하기 쉬워진다. 즉, 어디서 어디까지는 직선으로 가라는 식으로 간단하게 길을 묘사하게 된다. 양 끝의 코너 지점을 직접 출발지와 도착지에 연결해 본다. 장애물이 없다면 직접 연결이 되고, 그 길이 더 짧아지면 그 경로를 선택한다. 그 다음에도 중간 코너와 출발지와 도착지를 직접 연결해 보고 장애물이 없이 직접 연결되며 경로가 더 짧다면 그 경로를 취한다. 코너 지점을 시작점과 목표점에 연결하는 중에 또 다른 종류의 장애물이 나타난다면 그 구간에 대해서 길 찾기를 다시 한다. 우회하려던 장애물과 다른 장애물이 나타났다는 말은 처음에는 없던 장애물이 생겼다는 뜻이다. 이것은 길을 단축하는 과정에서 만난 것이다. 고로 그 구간에서 길 찾기를 하여 연결하면 전체적으로 가장 짧은 길을 구할 수 있다. A*보다는 훨씬 빠를 것이다. 또는 이 방법과 A*의 이동 비용 평가 방법을 함께 사용하는 경우도 있을 수 있으나 결국 총 계산 시간은 같을 것이다. 어차피 모든 길을 미리 다녀 보고 가장 짧은 길을 선택하는 것이기 때문에 총 계산 시간은 같다. 게임 엔진을 이용하는 경우에는 이런 길 찾기를 구현할 필요가 없을 것이다.

또 다른 방법이 있다. 처음에 길이 있는지 확인하는 방법은 위와 같이 우회로를 통해 입사 지점과 출사 지점을 연결할 수 있는지 보는 것이다. 일단 길이 있다면 무조건 목표를 향해 직선 전진을 한다. 장애물을 만나면 우회를 하지만 장애물을 벗어 났다고 판단되면 또 직진을 한다. 즉, 출사 지점으로 가는 것이 아니라 바로 목표로 향한다. 마치 목표물에 중력이 있어 그쪽으로 물이 흐르는 것처럼 그렇게 직진한다. 이런 식으로 길을 찾은 후에 반대로 목표 지점에서 출발 지점으로 같은 방식으로 길을 찾는다. 그러면 양 방향 길이 겹치는 구간이 있고, 서로 갈라지지만 같은 곳으로 도달하는 길이 있다. 겹친 구간은 유일한 통로이기 때문에 그대로 사용하고, 갈라진 구간에선 어느 쪽이 더 짧은지 선택한다. 그렇게 해서 최종적으로 길을 결정한다. 이 길은 가장 짧은 길은 아니지만 비교적 짧은 길이다. 이 길을 A*로 찾으려면 상당히 넓은 지역을 계산해야 하지만 이 방법은 길쭉한 길 몇 개만 계산하면 바로 나온다. 그래서 계산 시간이 짧다. 그런데 문제가 있다. 길을 표시할 때 어디에서 왔는지 정보가 필요한데 그런 정보가 2개 이상일 수 있다. 즉, 여기까지 도달하는 경로가 1개가 아니라 2개 이상이기 때문에 타일에 2개 이상의 정보를 기록할 수 있어야 한다. A*의 경우는 항상 하나의 경로를 통해서 그 지점에 도달하기 때문에 자신이 어디서 왔는지 1개의 정보만 기억하면 된다. 그런데 이 방법에선 2개 이상의 경로를 통해 한 곳에 도달할 수 있기 때문에 왔던 길을 기억하는 것이 좀 복잡하다. A*의 경우는 나무 가지가 퍼지는 듯한 연결 상황을 표시하기 때문에 모든 길은 자신의 부모 길만 기억하면 된다. 두 가지가 합쳐지는 일이 없다. 즉, 2개의 경로가 중간에 다시 합쳐지는 경우가 없다. 그런데 이 방법에선 2개의 경로가 합쳐지기 때문에 약간 골치 아프다. 요점은 입사 지점과 출사 지점을 거치지 않고 바로 코너에 연결하는 경로를 찾으면 되는 것이다. 그러면 A*와 유사한 결과를 만들어낸다.

지금까지 방법을 모두 종합해서 결론적인 방법을 정리하면 이렇다. 무조건 목표를 향해 직진한다. 길이 있는지 없는지 미리 판단할 필요 없다. 장애물이 나타나면 우회를 한다. 벽을 타며 장애물을 회피한다. 장애물을 벗어나는 순간 (회전 각도를 참고하여 원래 회전 각도가 나오면) 또 목표를 향해 직진한다. 그렇게 가다 보면 여러 갈래로 길이 갈라지는데 중간에 다시 모이는 지점이 있게 된다. 중간에 모이는 지점에선 어느 길로 오는 것이 더 짧은지 판단하여 긴 쪽 길을 버린다. 즉, 모든 지점은 자신이 어디서 왔는지 한 방향만 기억할 수 있다. 고로 두 길이 합쳐지는 곳에선 어느 한 길을 버려야 한다. 이런 식으로 목표까지 길을 찾는다. 목표에 도달하지 못 하는 경우는 위에서 본 바와 같이 2가지 경우뿐이다. 둥근 장벽에 둘러 싸여 있거나, 긴 장벽이 갈라 놓은 경우이다. 어느 경우라도 더 이상 길을 추가할 수 없는 경우가 나오는데 그러면 길이 없는 것이다. 일단 목표 근처나 목표에 도달했으면 길을 역으로 거슬러 올라오면서 입사 지점을 생략하는 길 단축 과정을 밟는다. 길 단축 과정에서도 장애물이 새로 나타나는 경우가 있을 것이다. 그러면 같은 방법으로 구간의 새로운 경로를 찾는다. 시작 점까지 도달했다면 다시 시작 점에서 목표 지점으로 길을 따라 내려가면서 다시 입사 지점 제거 작업을 한다. 입사 지점이 모두 제거될 때까지 왔다 갔다 반복을 하면 가장 짧은 길을 찾게 된다. 이 방법은 A*를 대신할 수 있다.

A*와 지금까지 방법을 혼용한 경우이다. A*는 여러 길이 합치는 곳에선 그 지점까지 도달할 수 있는 최단 거리 경로를 취하고 나머지는 연결이 되지 못 하게 한다. 고로 모든 길은 하나의 부모 길만 기억하기 때문에 목표 지점에서 시작 지점으로 역추적을 하면 단일 경로로 연결이 된다. 장애물을 만났을 때는 둥글게 확장하며 탐색을 하는데 여기선 장벽을 따라 이동하면서 그 지점까지 가장 가까운 직선을 찾는 것으로 대신한다. 장벽을 넘을 수 있는 지점이 나오면 이런 직선 탐색은 하지 않는다. 장벽을 만나서 길이 양쪽으로 갈라지면 어느 방향으로 나갈 것인지 결정해야 하는데 여기서 A*의 평가 방식을 사용한다. 이런 방식을 계속 반복하면 A*와 유사한 방식으로 탐색하는 것이 된다. A*에선 그 지점까지 도달 거리와 목표까지의 직선 거리의 합으로 다음 경로를 선택한다. 마찬가지로 여기서도 장벽을 따라갈 때 그 지점까지 가장 짧은 직선과 목표까지 직선을 평가 기준으로 사용할 수 있다. 이 과정에서 중간에 새로운 장애물을 만나면 코너 지점을 추가하여 코너 지점이 최단거리 직선으로 연결 되도록 계속 길을 찾아 가는 방식이다. 최종적으로 얻어진 길은 코너 지점을 직선으로 연결한 형태가 된다. 8방향 타일 탐색 대신 직선 길이를 사용할 뿐이며 A*의 평가 알고리즘을 사용하는 것이다. 직선 이동을 할 때는 수평 수직 타일의 간격 중에 가장 작은 간격을 사용한다. 이렇게 하면 직선 경로 중의 모든 타일에 속한 객체와 충돌을 검사할 수 있다.

갑자기 산지와 평지의 이동 비용을 알고 싶어서 검색을 해 보았다. 산을 넘는 시간을 계산하기 위해서 63빌딩 계단 오르기 기록을 살펴 보았다. 산에는 계단이 없어서 더 힘들 것이나 참고할 수 있을 것 같다. 달리기 기록이나 마라톤 기록과 비교한다. 내려올 때는 올라갈 때보다 쉬우니 평지의 달리기 속도와 같다고 하자. 이렇게 계산을 해 보니 산의 이동 비용은 평지의 이동 비용의 5배이다. 현실 세계에서 보통 평지 행군 속도가 4km/h ~ 6km/h 이기 때문에 산에선 평균 1km/h 정도로 행군한다는 말이 된다. 어디까지나 게임 속의 이동 비용이고 현실 세계에선 많이 다르다. 산의 높이보다는 산의 경사도가 더 결정적이다. 같은 높이를 오를 때 절벽을 기어 오르는 것과 계단을 오르는 것은 차이가 많다.

출처: http://blog.daum.net/jty71/15645104

길 찾기 알고리즘, A* 알고리즘, A Star라고 발음한다. 상당히 오래 전에 만들어진 알고리즘이다. 게임 제작에서 가장 기본적으로 가르치는 방법이라서 외국 글을 읽어 단순히 번역하지 않고 다시 정리해서 올린다. 유사한 방법에 Dijkstra[다익스트라]라는 사람이 만든 방법이 있다고 한다. 발음법이 특이한 것은 네덜란드 사람이라서 그렇다. 약간 독일어를 닮은 언어다. 아마 A*의 원형일 것이다. 컴퓨터 공학과에선 가르치는 것 같다. 우린 모르지만...

 <그림 : 기본 개념>

먼저 알아야 할 것부터 정리하면 이렇다. 컴퓨터는 봉사에 귀머거리다. 그래서 화면 전체를 볼 수 없다. 비유를 하면 봉사 슈퍼 개미가 빛의 속도로 화면을 돌아다니며 더듬어서 길을 찾는 것이다. 일을 간단하게 만들기 위해서 지도를 바둑판 형태로 나눈다. 이것을 격자(Grid)라고 부른다. 그래서 하나의 사각형, 육각형, 삼각형 안에서 다른 것 안으로 이동하거나 또는 바둑판처럼 하나의 교차점에서 다른 교차점으로 이동하는 형태로 생각한다. 사각형, 육각형, 삼각형은 평면을 알뜰하게 나누어 사용할 수 있는 도형이다. 주로 사각형을 많이 쓰지만 뭐를 써도 가능하다. 그렇게 구역을 나누고 각 구역은 뭔가 기억할 수 있는 능력이 있다고 하자! 즉, 각 바둑판 사각형이나 십자 교차점은 컴퓨터에서 말하는 2차원 배열이 된다. 다시 말하면 길을 찾기 위해 지도에 뭔가 표시할 수 있도록 하는 것이다! 여하튼 움직임은 연속적이지 않고 계단식으로 간격을 두고 움직인다! 그리고 그 지점에 뭔가 표시를 한다. 이런 것을 Node[노우드](마디)라고 부른다. 이 말은 원래 나무 형태의 구조에서 가지가 갈라지는 부분을 부르는 말이다. 이런 이름이 붙은 이유는 바둑판에 표시한 길을 보면 마치 나무 가지 형태를 하게 되기 때문이다. 보통 Node가 나오면 List가 따라 나온다. Linked List(연결 목록)이란 것은 배열이다. 그런데 서로 누가 먼저 누가 나중인지 연결된 정보를 가지고 있다. 그래서 순서를 자유롭게 바꾸고, 삽입과 삭제가 쉽다. 지도에 표시하는 대신 이 Linked List를 사용하여 길을 기억하는데 이 연결 상태를 그려보면 나무(Tree) 모양이 된다. 그래서 Node라고 부른다.(^^) 우리의 봉사 슈퍼 개미는 바로 옆의 8개 점만 검사할 수 있다. 그래서 8방향 탐색이다!(^^) 이 8방향에서 또 각자 다음 주변 8방향으로 물결처럼 퍼져나간다. 그런데 이렇게 무조건 8방향으로 퍼져나가면 좀 문제가 있다. 하나만 선택해서 계속 깊게 나가야 한다. 우린 넓이 우선 탐색을 하는 것이 아니라깊이 우선 탐색을 하는 것이다. A 스타는 깊이 우선 탐색 + 넓이 우선 탐색이다. 처음엔 계속 가능성이 높은 것 하나를 선택해서 깊게 나간다. 그러다 막히면 나머지 가능성 중에서 하나를 선택해서 넓게 나간다. 그 가능성 높은 방향을 선택하는 방법이 바로 A 스타 알고리즘이다.

 <그림 : 유사 방법>

<그림 : 진짜 방법>

 a star pathfinder v. 1.92.zip

A*란 8방향을 탐색해야 하며 8방향 중에 어느 하나를 선택하는 방법으로 이미 왔던 거리와 목표까지 예상 거리의 합을 사용해야 하는 것이다. 그렇지 않다면 A*라고 부르기 어렵다. 이 가장 기본적이고 가장 실용적이게 보이는 방법도 문제가 많다.(^^) 아주 긴 장벽을 넘는 것이 어렵게 보인다. 또한 호랑이 입이나 항아리 구조 같은 지형에서도 시간 소모가 많다. 가장 짧은 거리를 선택한다는 것은 말 그대로 Sorting을 한다는 것이고 그러면 시간이 많이 소모된다. 또한 검토할 지점과 이미 검토한 지점을 목록(Linked List)에 잘 저장해서 찾아야 한다. 다만 책에 이름이 자주 거론되니 궁금해서 공부했을 따름이다. 좀 더 간단하고 효과적인 방법이 있다. 이쪽에서 저쪽으로 가는 길을 찾는 것은 복잡하지만 반대로 저쪽에서 이쪽으로 오는 길을 찾는 것은 쉬울 수 있다. 항상 반대로 생각해 봐야 한다. 그래서 양방향 탐색을 한다. 또한 우리가 산 속에서 또는 사막에서 또는 초원에서 또는 바다에서 길을 잃었다고 하자! 그럼 제일 먼저 찾는 것이 뭔가? 산 속에선 계곡의 물줄기다. 따라가면 큰 강이 나온다. 사막이나 초원에선 강을 찾거나 산맥을 찾아야 한다. 바다에선 육지를 찾아야 한다. 모두 경계라는 특징이 있다. 마찬가지로 갈 수 있는 길과 갈 수 없는 장애물 사이의 경계가 바로 따라가야 할 길이다. 장애물이 없다면 무조건 목표 방향을 향해 직진하는 것이 빠르다. 실제 게임에서 Unit들의 움직임을 보면 장애물을 만나기 전까지는 일직선으로 이동한다. 장애물을 만나면 벽을 따라 이동하는 것을 알 수 있다. 물론 이 길을 찾는 방법을 개발해야 하지만 별로 어렵지 않다. 아래 그림을 봐라!

<그림 : 기타 방법>

A*와 유사한 결과를 내지만 더 간단하다. 이 방법은 내가 고민하다가 기억해 낸 것이다. 인터넷에 찾아 보면 우선법/좌선법(우수법/좌수법!? 뭐라고 하든 무슨 상관이냐?)이라는 벽 타기 기법이 유사하다는 것을 느낄 것이다. 미로에서 오른 손이나 왼 손을 벽에 붙이고 계속 가면 출구가 나온다는 그런 이야기다. 이 방법은 계속 벽에 붙어 있기 때문에 벽에서 떨어지는 상황에 대응한 위의 방법과는 다르다. 어느 경험 많은 프로그래머에게서 오래 전에 들은 이야기다. 당시 게임 제작에 대한 막연한 호기심으로 질문을 했었다. 그 사람들 경험으로는 게임 제작은 엄청 골치 아픈 분야라고 한다. 컴퓨터를 생각하도록 만드는 작업은 정말 어렵다. 이런 길 찾기는 아주 쉬운 편에 속한다고 한다. 한 참 후에 세월이 흘러 직접 게임 제작에 관한 글을 쓰다가 궁리 끝에 뭔가 아이디어가 떠올랐는데 알고 보니 옛날에 누군가에게 들은 것이었다.(^^) 진짜 실력이 있는 프로 게임 제작자들은 이미 답을 알고 있었다! 컴퓨터 공학과나 수학과에서 다루는 분야이니까! 컴퓨터는 컴퓨팅(계산)하는 장치이니 수학과와 친하다. 우리 아마추어만 모르고 있었다! 내가 게임 업체의 비밀 알고리즘을 하나 듣게 된 것이었다. 어디 가서 말하지 말라고 했지만 내가 게임 제작자가 될 수도 없는 입장에서 세월은 흘러 이미 늙어 버렸으니 내겐 더 이상 감출 비밀이 아닌 것 같다! 어린 학생들 좋은 꿈 꾸라고 이렇게 글을 올린다. 한국 게임 업체의 비밀은 외국 게임 업체에 비하면 비밀도 아니니까!(^^) 게임 분야는 너무 경쟁이 심하다. 장래 희망이라면 잘 고려해 보길 바란다!

이 글의 참고가 된 A* Path Finder C Code(압축 파일 첨부)를 분석하기 좋게 그림으로 정리한 것이다. 먼저 자료 구조를 이해하면 알고리즘 분석이 쉽다. 모든 프로그램에서 배열과 변수 등의 용도를 이해하면 알고리즘이 쉽게 분석 된다. 그림에선 10 x 10의 타일 방식 지도를 사용한다고 가정한다. 그리고 게임의 인구 수를 100명이라고 본다. 10 x 10의 지도에선 아무리 복잡한 경로가 나와도 10 x 10의 절반보다 약간 많은 길이의 배열이면 담을 수 있다. 10 x 10의 지도 경계에는 갈 수 없는 영역 표시를 하는 것이 편한데, 소스 코드에선 그런 방식을 사용하지 않았다. 지도에서 빨간 셀의 S는 시작 위치고 파란 셀의 T는 목표 지점이다. 빨간 색은 이미 검토한 셀이고, 노란 색은 검토할 셀이다. 노란 색의 검토할 띠 모양의 경계 부분에선 다음 경로를 선택하기 위해서 F값을 계산한다. 가장 작은 F값을 가진 위치를 찾아야 한다. 고로 노란 색의 좌표와 정보를 모아 두는 배열이 필요하다. 최대 탐색 크기는 지도 전체를 복잡하게 탐색하더라도 10 x 10이 되지 못 한다. 여하튼 100개까지 가능할 리는 없지만 100개의 목록에 노란 색의 좌표와 정보를 담아 둔다. 각 인구 수에 맞게 각자의 찾은 길을 기억할 배열을 만들어 연결시킨다. 

2D 배열 : walkability = 갈 수 있는지 없는지 여부

2D 배열 : whichList = 노란 색(검토 대상)에 속하는지, 검토 완료인지 여부

2D 배열 : parentX = 어디서 왔는지에 대한 정보 X방향(부모 좌표)

2D 배열 : parentY = 어디서 왔는지에 대한 정보 Y방향(부모 좌표)

2D 배열 : Gcost = 경로의 비용 누적 값

위의 배열은 지도의 형상과 그대로 대응되는 2차원 배열들이다. 이 지도에 찾은 경로가 기록된다. 찾은 경로는 목표 지점에서 출발 지점으로 거꾸로 역추적하여 힙 영역에 배열로 만든다.

1D 배열 : openList = 목록 관리용 배열 참조 값(포인터로 사용) 저장

1D 배열 : openX = 검토 대상 타일의 X좌표

1D 배열 : openY = 검토 대상 타일의 Y좌표

1D 배열 : Hcost = 검토 대상 타일의 H값(목표까지 직선 거리)

1D 배열 : Fcost = 검토 대상 타일의 F값(최소 값을 항상 선택)

검토 대상 타일(노란 셀)의 정보를 담고 최소 F값을 찾아 처리 후 그 셀의 정보를 목록에서 삭제하고, 새로운 0 ~ 7개의 검토 타일의 정보를 목록에 추가 삽입하는 목적의 배열들이다. 최소 값 찾기와 삽입 삭제가 자주 일어나는 목록이다.

1D 배열 : pathLength = 찾은 길의 길이

1D 배열 : pathLocation = 현재 가고 있는 단계

1D 배열 : *pathBank = 실제 길의 좌표를 담은 배열을 가리키는 포인터

1D 배열 : pathStatus = 경로의 상태

1D 배열 : xPath = 현재 가고 있는 단계의 X좌표(유닛의 좌표)

1D 배열 : yPath = 현재 가고 있는 단계의 X좌표(유닛의 좌표)

각 유닛이 각자의 찾은 길을 기억하고 어디쯤 가고 있는지 확인하기 위한 배열이다. 실제 경로는 지도에서 역추적하여 배열로 힙 영역에 만들고, 목적지에 도달하면 지우는 방식이다. 

노란 색 타일에서 자신의 부모를 결정할 때는 주변 8개 타일에서 빨간 색 타일을 고른 후에 자기 자신에게 오는 G 값을 계산하여 가장 작은 쪽을 부모로 선택한다. 대각으로 왔으면 2의 제곱근인 1.414배의 비용이 든다. 이 때 대각으로 진행이 불가능한 코너 구조가 있으니 이를 판단해야 한다. 대각으로 진행할 때는 그 타일의 주변이 모두 비어 있어야 한다. 노란 색 타일에서 앞으로 나아갈 방향을 결정하기 위해서 주변 8개 타일을 검토할 때는 빨강도 노랑도 아닌 영역일 것이다. 이것들은 새로운 노란 타일로 목록에 추가 되어야 한다. 아마도 0 ~ 7개까지 될 것이다. 최소 F값을 찾고 목록에 삽입, 삭제가 쉬운 형태의 자료 구조를 고안해서 목록을 다룬다. 항상 하나의 셀이 빠져 나가고 새로운 0 ~ 7개의 셀이 추가 된다. 최소 F값인 셀을 찾기 위해서 미리 정렬을 해서 순서를 맞출 것인지, 아니면 매번 비교를 통해 최소 F값인 셀을 선택할 것인지 효율성을 따져 봐야 한다. 정렬에 들어간 시간과 비교에 들어간 시간을 비교해 보아야 한다. 이 C 코드에선 구조체 배열 사용하지 않았다. 가능하면 1차원 배열을 사용하는 것이 속도가 빠르다. 배열의 차수가 높아지면 포인터의 첨자 계산 시간이 추가로 소모된다. 이 소스 코드에선 길이 있는지 없는지는 목표 지점의 정보(평지인지 장벽인지)를 보고 판단하는 방법만 사용한다. 길이 없을 때도 A* 알고리즘을 적용하여 지도의 모든 셀의 검토가 끝나야 길이 없다는 것을 알게 된다. 가장 시간이 많이 소모될 때가 길이 없을 때이다.

알고리즘 중에서 F값의 최소 값을 빨리 찾는 방법이 있다. 최소 값을 찾으면 그것을 뽑아 내기 때문에 배열의 중간에 틈이 생겨 불연속이 될 수가 있다. 중간에 틈이 생기면 배열을 처리하기 까다롭기 때문에 틈이 생기면 뒤의 것을 당겨 와서 연속으로 만들어야 한다. 매번 최소 값을 찾기 위해 비교를 하고, 뽑아 내면 나머지를 당겨 붙여야 하기 때문에 시간이 많이 소모된다. 이런 작업을 최소한으로 하기 위해서 이 C Code에선 2진 트리 형태를 이용하고 있다. 배열에 요소를 삽입할 때마다 약간의 비교 작업과 자리 바꾸기를 해서 항상 최소 값이 앞에 오게 하면서 배열을 연속적으로 붙여 놓는 방법이다. 허나 단순 비교와 삽입/삭제에 따른 데이터 이동 방식도 이미 어느 정도 순서가 잡힌 배열에선 계산 양이 많지 않기 때문에 2진 트리 같은 복잡한 방법을 사용할 필요는 없다. 하지만 2진 트리 알고리즘이 묘하기 때문에 분석해 본다.

그림에선 크기가 10개인 1차원 배열이 있다. 2진 트리 특성상 뿌리의 첨자는 1부터 시작해야 하기 때문에 0번 방이 빈다. 나의 경우는 0번 방에는 배열 내용의 길이를 넣는 방법을 쓴다. 문자열을 다룰 때도 문자열 끝에 Null을 넣는 것보다는 문자열 앞에 길이를 넣는 것이 더 효율적이다. 여하튼 1차원 배열을 2진 트리 형태로 배치하여 그 내용과 첨자를 나열해 보면 어떤 특징이 보인다. 부모와 자식과 형제 사이의 이동이 간단한 계산으로 이루어진다. 이 2진 트리는 항상 정상(뿌리)에 최소 값이 배치되도록 되어 있다. 고로 1번 첨자의 내용을 뽑아 내면 된다. 새로운 데이터를 추가할 때는 1번이나 마지막 번호(그림에선 9번)에 넣는다. 넣은 다음에는 부모 자식 간의 크기 비교를 통해서 가장 작은 값이 정상으로 올라 가도록 자리 바꾸기를 한다. 최악의 경우 자리 바꿈 횟수는 나무의 깊이(층)만큼이다. 자리 바꿈에는 3회의 대입이 필요하다. 3회의 대입은 3개 데이터 이동과 같다. 부모와 자식 간의 비교는 2회이다. 비교는 뺄셈과 같다. 고로 층의 깊이 x 2회의 비교 연산은 기본으로 소모된다. 층의 수는 n이라고 할 때, 2의 n승 – 1 = 데이터의 수량이 된다. 고로 많은 데이터를 처리할 때 시간이 절약 된다.

Cocos2d-x의 메모리 관리

Reference Count

레퍼런스카운터는 c와 c++의 메모리관리의 오래된 방법이다. ios에서는 8년전부터 이 메커니즘을 써왔다.
cocos2d-x에서도 ios ndk 의 NSAutoreleasePool와 거의 같은 CCAutoreleasePool이 존재한다 . 사용방법은 거의 동일하며 만약 너가 ios로 개발한 경험이 없으면 NSAutoreleasePool class Reference를 읽어봐라 

CCAutoreleasePool

CCAutoreleasePool 은 NSAutoreleasePool거의 같지만 2개의 차이점이있?다.

1. CCAutoreleasePool 은NESTED에서 사용할수없다. 오직 게임 인스턴스에서만 사용 가능하다.
2. CCAutoreleasePool 은 멀티쓰레드에서 사용할수 없다. 

CCAutoreleasePool의 로직은 간단하다 만약 너가l object->autorelease()을 실행하면 object는  autorelease pool 에 들어가게 된다. 

autorelease pool은 루프가 끝날시 자동으로 release()이 되게 도와준다. 

예를들어 layer->addChild(sprite), 이 sprite 는 레이어의 차일드이다, 이것은 레이어가 release될때까지 pool에서 유지된다

CCObject::release(), retain() and autorelease()

->release() 가 필요할때
1. "new" 연산자를 사용할때  CCSprite,CCLayer 등(CCObject를 상속받는 자식들)
2. "retain()"을 호출할때

release나 retain이 필요없는 예제:

CCSprite* sprite = CCSprite::spriteWithFile("player.png");

위 예제는 autorelease()풀에 의해서 관리되기때문에  release나 retain이 필요없다.

An Error Sample

bool HelloWorld::init()
{
    bool bRet = false;
    do
    {
        //////////////////////////////////////////////////////////////////////////
        // super init first
        //////////////////////////////////////////////////////////////////////////

        CC_BREAK_IF(! CCLayer::init());

        //////////////////////////////////////////////////////////////////////////
        // add your codes below...
        //////////////////////////////////////////////////////////////////////////

                CCSprite* bomb1 = CCSprite::spriteWithFile("CloseNormal.png");
                CCSprite* bomb2 = CCSprite::spriteWithFile("CloseNormal.png");
                CCSprite* bomb3 = CCSprite::spriteWithFile("CloseNormal.png");
                CCSprite* bomb4 = CCSprite::spriteWithFile("CloseNormal.png");
                CCSprite* bomb5 = CCSprite::spriteWithFile("CloseNormal.png");
                CCSprite* bomb6 = CCSprite::spriteWithFile("CloseNormal.png");

                addChild(bomb1,1);
                addChild(bomb2,1);
                addChild(bomb3,1);
                addChild(bomb4,1);
                addChild(bomb5,1);
                addChild(bomb6,1);

                m_pBombsDisplayed = CCMutableArray<CCSprite*>::arrayWithObjects(bomb1,bomb2,bomb3,bomb4,bomb5,bomb6,NULL);
                //m_pBombsDisplayed is defined in the header as a protected var.
                // <--- We should add m_pBombsDisplayed->retain() here to avoid crashing in HelloWorld::refreshData()

                this-]]>scheduleUpdate();
        bRet = true;
    } while (0);

    return bRet;
}

void HelloWorld::update(ccTime dt)
{
        refreshData();
}

void HelloWorld::refreshData()
{
        CCMutableArray<CCSprite*]]>::CCMutableArrayIterator iter = m_pBombsDisplayed-]]>begin();
        (*iter)-]]>setPosition(ccp(100,100));
}

이 예제의 실수는 m_pBombsDisplayed 는 CCMutalbeArray<CCSprite*>::arrayWithObjects 에 의해 생성되는데, autoRelease()에의해 관리되기때문에

루프가 지나면 사라진다. 
이문제를 해결하기 위해서는  m_pBombsDisplayed = CCMutableArray<CCSprite*]]>::arrayWithObjects(...); 뒤에 m_pBombsDisplayed->retain()를 추가하고, HelloWorld::~HelloWorld() 소멸자에서 m_pBombsDisplayed->release()한다.

---

시작하세요 cocos2d 아이폰 게임 프로그래밍

저자

이재환 지음

출판사

위키북스 | 2011-10-12 출간

카테고리

컴퓨터/IT

책소개

[출판사서평]cocos2d for iPhone을 활용한 게임 개...

---

많은 게임 회사들이 Unity-3d나 cocos2d를 이용해서 게임을 개발합니다. 그중에 2d쪽 게임을 개발할때는 좋은 퍼포먼스와 많은 라이브러리를 제공하는 cocos2d를 많이 씁니다. (Unity-3D로도 2d 게임을 개발 할 수 있지만, cocos2d 보다는 퍼포먼스 면에서 떨어진다고 합니다. 물론 3d쪽으로는 좋은 엔진입니다.)

  저는 mac 이 없는 관계로 windows 개발 환경에서도 안드로이드 게임을 개발 할 수 있는 좋은 방법이 없을까 고민 하던 중 cocos2d-x를 알아 보게 되었고, windows 환경에서도 cocos2d-x라는 멀티플랫폼을 지원하는 게임엔진에 대해서 알게 되었고, 그 매력에 빠져 들게 되었습니다.

cocos2d-x 는 이름에서 알 수 있듯이 cocos2d를 벤치마킹 해서 만든 엔진이며, cocos2d와는 달리 c++을 사용하며, 멀티플랫폼 게임엔진입니다.

지원하는 운영체제는 ios, android, bada, blackberry qnk , win32, linux , win8 metro, mac os X 등 많은 플랫폼을 지원합니다.

하지만 아직까지는 국내에 나와있는 cocos2d-x 전용 서적은 없으므로 cocos2d 서적을 보면서 공부를 해야되는 상황이었습니다.

  가장 먼저 이 책은 책이름에서 알 수 있듯이 초보자를 위한 서적입니다. 가장 기본적인 cocos2d의 기본 구조 및, 스프라이트(이미지)를 그리는 방법, 레이블 다루기, 메뉴 다루기, cocos2d의 강점인 action 사용하기, 타일맵 사용하기 등 cocos2d의 가장 기본적인 기능에 초점을 두고 만든 책 인거 같습니다. 만약 cocos2d에 대해 어느정도 알고 있고, 사용 할 수 있는 프로그래머라면 큰 도움은 되지 않을 것 같지만, 정말 초보자를 위해서 잘 작성된 책인 것 같습니다. 책 뒤에는 기본적인 게임을 만들 수 있는 예제도 수록 되있어, 초보자도 쉽게 익힐 수 있을 겁니다.(cocos2d의 듀토리얼과 거의 같은 수준의 예제 입니다.).

  일단 너무 기본적인 내용에 충실하기 때문에, 제가 이책을 보면서 실제로 게임을 개발 하려고 할때 , 파일들을 어떤식으로 관리하며 cocos2d-x의 경우 클래스를 어떤식으로 나누고 그 클래스에 어떤 변수나 함수를 설정해야 되나 막막했던 기억이 있습니다. 확실히 실무에 바로 써먹기에는 어려운 점이 있는 것 같습니다.

하지만 처음으로 공부를 하는 입장에서는 부담없이 보고 따라하면서 배울 수 있는 책인 것 같습니다.