Unity3D

출처: 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 = 데이터의 수량이 된다. 고로 많은 데이터를 처리할 때 시간이 절약 된다.