길 찾기 알고리즘, A* 알고리즘, A Star라고 발음한다. 상당히 오래 전에 만들어진 알고리즘이다. 게임 제작에서 가장 기본적으로 가르치는 방법이라서 외국 글을 읽어 단순히 번역하지 않고 다시 정리해서 올린다. 유사한 방법에 Dijkstra[다익스트라]라는 사람이 만든 방법이 있다고 한다. 발음법이 특이한 것은 네덜란드 사람이라서 그렇다. 약간 독일어를 닮은 언어다. 아마 A*의 원형일 것이다. 컴퓨터 공학과에선 가르치는 것 같다. 우린 모르지만...
<그림 : 기본 개념>
먼저 알아야 할 것부터 정리하면 이렇다. 컴퓨터는 봉사에 귀머거리다. 그래서 화면 전체를 볼 수 없다. 비유를 하면 봉사 슈퍼 개미가 빛의 속도로 화면을 돌아다니며 더듬어서 길을 찾는 것이다. 일을 간단하게 만들기 위해서 지도를 바둑판 형태로 나눈다. 이것을 격자(Grid)라고 부른다. 그래서 하나의 사각형, 육각형, 삼각형 안에서 다른 것 안으로 이동하거나 또는 바둑판처럼 하나의 교차점에서 다른 교차점으로 이동하는 형태로 생각한다. 사각형, 육각형, 삼각형은 평면을 알뜰하게 나누어 사용할 수 있는 도형이다. 주로 사각형을 많이 쓰지만 뭐를 써도 가능하다. 그렇게 구역을 나누고 각 구역은 뭔가 기억할 수 있는 능력이 있다고 하자! 즉, 각 바둑판 사각형이나 십자 교차점은 컴퓨터에서 말하는 2차원 배열이 된다. 다시 말하면 길을 찾기 위해 지도에 뭔가 표시할 수 있도록 하는 것이다! 여하튼 움직임은 연속적이지 않고 계단식으로 간격을 두고 움직인다! 그리고 그 지점에 뭔가 표시를 한다. 이런 것을 Node[노우드](마디)라고 부른다. 이 말은 원래 나무 형태의 구조에서 가지가 갈라지는 부분을 부르는 말이다. 이런 이름이 붙은 이유는 바둑판에 표시한 길을 보면 마치 나무 가지 형태를 하게 되기 때문이다. 보통 Node가 나오면 List가 따라 나온다. Linked List(연결 목록)이란 것은 배열이다. 그런데 서로 누가 먼저 누가 나중인지 연결된 정보를 가지고 있다. 그래서 순서를 자유롭게 바꾸고, 삽입과 삭제가 쉽다. 지도에 표시하는 대신 이 Linked List를 사용하여 길을 기억하는데 이 연결 상태를 그려보면 나무(Tree) 모양이 된다. 그래서 Node라고 부른다.(^^) 우리의 봉사 슈퍼 개미는 바로 옆의 8개 점만 검사할 수 있다. 그래서 8방향 탐색이다!(^^) 이 8방향에서 또 각자 다음 주변 8방향으로 물결처럼 퍼져나간다. 그런데 이렇게 무조건 8방향으로 퍼져나가면 좀 문제가 있다. 하나만 선택해서 계속 깊게 나가야 한다. 우린 넓이 우선 탐색을 하는 것이 아니라 깊이 우선 탐색을 하는 것이다. A 스타는 깊이 우선 탐색 + 넓이 우선 탐색이다. 처음엔 계속 가능성이 높은 것 하나를 선택해서 깊게 나간다. 그러다 막히면 나머지 가능성 중에서 하나를 선택해서 넓게 나간다. 그 가능성 높은 방향을 선택하는 방법이 바로 A 스타 알고리즘이다.
<그림 : 유사 방법>
A*란 8방향을 탐색해야 하며 8방향 중에 어느 하나를 선택하는 방법으로 이미 왔던 거리와 목표까지 예상 거리의 합을 사용해야 하는 것이다. 그렇지 않다면 A*라고 부르기 어렵다. 이 가장 기본적이고 가장 실용적이게 보이는 방법도 문제가 많다.(^^) 아주 긴 장벽을 넘는 것이 어렵게 보인다. 또한 호랑이 입이나 항아리 구조 같은 지형에서도 시간 소모가 많다. 가장 짧은 거리를 선택한다는 것은 말 그대로 Sorting을 한다는 것이고 그러면 시간이 많이 소모된다. 또한 검토할 지점과 이미 검토한 지점을 목록(Linked List)에 잘 저장해서 찾아야 한다. 다만 책에 이름이 자주 거론되니 궁금해서 공부했을 따름이다. 좀 더 간단하고 효과적인 방법이 있다. 이쪽에서 저쪽으로 가는 길을 찾는 것은 복잡하지만 반대로 저쪽에서 이쪽으로 오는 길을 찾는 것은 쉬울 수 있다. 항상 반대로 생각해 봐야 한다. 그래서 양방향 탐색을 한다. 또한 우리가 산 속에서 또는 사막에서 또는 초원에서 또는 바다에서 길을 잃었다고 하자! 그럼 제일 먼저 찾는 것이 뭔가? 산 속에선 계곡의 물줄기다. 따라가면 큰 강이 나온다. 사막이나 초원에선 강을 찾거나 산맥을 찾아야 한다. 바다에선 육지를 찾아야 한다. 모두 경계라는 특징이 있다. 마찬가지로 갈 수 있는 길과 갈 수 없는 장애물 사이의 경계가 바로 따라가야 할 길이다. 장애물이 없다면 무조건 목표 방향을 향해 직진하는 것이 빠르다. 실제 게임에서 Unit들의 움직임을 보면 장애물을 만나기 전까지는 일직선으로 이동한다. 장애물을 만나면 벽을 따라 이동하는 것을 알 수 있다. 물론 이 길을 찾는 방법을 개발해야 하지만 별로 어렵지 않다. 아래 그림을 봐라!
<그림 : 기타 방법>
A*와 유사한 결과를 내지만 더 간단하다. 이 방법은 내가 고민하다가 기억해 낸 것이다. 인터넷에 찾아 보면 우선법/좌선법(우수법/좌수법!? 뭐라고 하든 무슨 상관이냐?)이라는 벽 타기 기법이 유사하다는 것을 느낄 것이다. 미로에서 오른 손이나 왼 손을 벽에 붙이고 계속 가면 출구가 나온다는 그런 이야기다. 이 방법은 계속 벽에 붙어 있기 때문에 벽에서 떨어지는 상황에 대응한 위의 방법과는 다르다. 어느 경험 많은 프로그래머에게서 오래 전에 들은 이야기다. 당시 게임 제작에 대한 막연한 호기심으로 질문을 했었다. 그 사람들 경험으로는 게임 제작은 엄청 골치 아픈 분야라고 한다. 컴퓨터를 생각하도록 만드는 작업은 정말 어렵다. 이런 길 찾기는 아주 쉬운 편에 속한다고 한다. 한 참 후에 세월이 흘러 직접 게임 제작에 관한 글을 쓰다가 궁리 끝에 뭔가 아이디어가 떠올랐는데 알고 보니 옛날에 누군가에게 들은 것이었다.(^^) 진짜 실력이 있는 프로 게임 제작자들은 이미 답을 알고 있었다! 컴퓨터 공학과나 수학과에서 다루는 분야이니까! 컴퓨터는 컴퓨팅(계산)하는 장치이니 수학과와 친하다. 우리 아마추어만 모르고 있었다! 내가 게임 업체의 비밀 알고리즘을 하나 듣게 된 것이었다. 어디 가서 말하지 말라고 했지만 내가 게임 제작자가 될 수도 없는 입장에서 세월은 흘러 이미 늙어 버렸으니 내겐 더 이상 감출 비밀이 아닌 것 같다! 어린 학생들 좋은 꿈 꾸라고 이렇게 글을 올린다. 한국 게임 업체의 비밀은 외국 게임 업체에 비하면 비밀도 아니니까!(^^) 게임 분야는 너무 경쟁이 심하다. 장래 희망이라면 잘 고려해 보길 바란다!
[출처] http://blog.daum.net/jty71/15645104
