occam's Razor-빠른 길찾기 기법

빠른 길찾기 기법

이 글 역시 인터넷을 헤매다가 얻은 문서에서 아이디어를 얻은 것입니다. 또한 '메모리를 팔아서 속도를 산다!'라는 좌우명에 걸맞는 글입니다.

(빠른 2D 맵 시선처리와 동일한 맥락이지요.)

그럼 시작...

1. 어드벤처 게임에서도 길찾기가 필요하다.

예를 들어 봅시다. 플레이어가 술집 문을 클릭하면, 주인공이 술집으로 들어갑니다. 술집 맨 끝쪽에 바텐더가 있고, 그 중간에는 테이블들이 이리저리 널려 있습니다. 바텐더를 클릭하면 주인공은 테이블들을 적절히 피해서 바텐더까지 갑니다.

이러한 것은 어떻게 구현할까요?

어드벤쳐 게임은 타일을 쓰지는 않지만, 비슷한 기법을 쓰기 마련입니다. 화려한 화면 안에는 다음과 같은 구조가 숨어 있는 것입니다.

+-------+------------+---------------+---------+
|       |            |               |         |
|       |            |      D        |         +
|       |    B       |               |   G
|       |            +-------+-------+         +
|       +------------+       |       |         |
|   A   |            |       |       +---------+
|       |    X       |   E   |   X   |         |
|       +------------+       |       |         |
|       |    C       |       |       |   H     |
|       |            +-------+-------+         |
|       |            |      F        |         |
+----------------------------------------------+

* X는 갈 수 없는 곳, 그 외는 갈 수 있는 곳들입니다.

이것은 사실 자료구조에서 말하는 그래프 구조입니다. 다음과 같습니다.


       B - D - G
     /   |
   A       E   |
        / |
       C - F - H

그래프로 표현할 수 있으니 길찾기 알고리즘도 존재합니다. 그러나 굳이 기존의 알고리즘을 쓰지 않고도 아주 빠른 방법으로 길찾기를 할 수 있습니다. 다음과 같은 표를 만드는 것입니다. 표는 완성하지 않겠으니 직접 완성시켜 보세요.


                  출발점
       A   B   C   D   E   F   G   H
     +-------------------------------
    A| .   A   A   B   C   C   D   F
     |
목 B| A   .   A   B   B   E   D   F
     |
표 C|         .   E   C       D
     |
점 D|             .
     |
    E|                 .
     |
    F|                     .
     |
    G|                         .
     |
    H|                              .

이 표를 어떻게 만드느냐구요? 일단 G에서 C로 가는 것을 한 번 해 보면 알 수 있을것입니다.
출발점 G에서 목표점 C 를 찾으면 D 가 나옵니다. D는 G에서 C로 가는데 꼭 거쳐야 하는 지역입니다. 그럼 D에서 C 를 찾습니다. 그러면 E 가 나옵니다. 다시 E에서 C를 찾습니다. 그러면 드디어 C가 나옵니다. 즉 경로는 G-D-E-C 입니다.

이 표의 각 칸에 있는 값은, 출발점 칸의 지역에서 목표점 줄의 지역에 도달 하기 위해 가장 먼저 들려야 하는 지역입니다.
하나 더 해 볼까요? H에서 A 로 가려면, H에서 F가, F에서 C가, C 에서 A가 나오므로 H-F-C-A 입니다.

프로그래밍을 좀 더 정교하게 하면, 직사각형 영역 뿐만 아니라 다른 다각형 영역도 만들 수 있을 것입니다. 또한 위 같은 표 자체도 자동화시켜서 제작시 그래프 정보만 넣어주면 만들어내게 할 수도 있겠지요.
경로가 나오면, 간단한 직선 알고리즘이나 벽짚고 돌기 알고리즘으로 지역과 지역간을 이동할 수 있습니다. 물론 한 지역 안에서는 직선으로 움직이면 되구요.

어쨌든 어드벤처에서 캐릭터의 이동 경로는 이런 식으로 할 수 있습니다. 개발시 좀 번거롭긴 하지만 속도 면에서는 아주 효율이 좋을 것입니다.

그리고, 개인적인 의견이긴 하지만 이러한 방식을 웨이포인트(Way Point) 방식이라고 부르겠습니다. A,B 등등 그래프의 정점들을 웨이포인트라고 부르자는거지요.

2. 삼국지 류의 전략 시뮬에 응용

일단 아이디어를 이해하면, 여러 곳에 써먹을 수 있을 것입니다. 삼국지의 메인 화면은 큰 지도로, 지도 자체가 그래프입니다. 즉 중국의 각 성들이 이동로로 연결되어 있지요.


인천 - 서울 - 춘천
           |
           대전
          /
         충주 - 청주
           |      |
         광주     대구

                      부산

(삼국지 나라들이 기억이 안나네요. 그리고 대전이 청주 위에 있는거 맞죠?)

장수들의 이동에 바로 써 먹을 수 있습니다. 게임 진행에 따라 이동로가 열리거나 끊기거나 할 수도 있는데, 이럴때에는 그래프 구조를 적절히 변경시켜 주면 됩니다.

그리고, 표 역시 기본 이동표 이외에 경로가 막혔을때 사용할 2차 이동표도 만들어 두면 좀 더 유연한 게임이 되겠지요.

3. 실시간 전략 시뮬에 응용

많은 개발자들이 한 번 손을 대 보고 싶은 게임이 실시간 전략일텐데요. 빠른 길찾기 알고리즘이 아주 절실한 게임 쟝르이지요. 가장 효율적인 길찾기 알고리즘은 아마 A* 알고리즘일텐데, 이 조차도 실시간에서는 잘 안씁니다. 턴방식에서나 쓰지요. 가장 효율적이라고 해도 속도가 문제이기 때문에 상업용 실시간 전략에서도 속도를 높이고 정확성은 낮춘 알고리즘을 쓰더군요.

위에서 말한 웨이포인트 방식을 실시간 전략에도 쓸 수 있습니다. 다만, 우선 단점들부터 말을 해야겠습니다.

첫번째 단점은, 개발시 미션마다 웨이포인트 설정을 하고 표를 만들어야 하기 때문에 번거롭다는 것입니다.

두번째 단점은, 사용자 미션 제작기를 만들기가 힘들다는 것입니다. 물론 사용자가 직접 웨이포인트를 입력하게 하고 표는 자동화 툴을 만들면 되겠지만, 사용자에게 웨이포인트를 지정하게 하는건 왠지 좀...

세번째 단점은, 웨이포인트를 사용하면 이동 경로가 단순해진다는 것입니다. 그럼에도 불구하고 웨이포인트를 쓰는 이유는 물론 속도입니다. 표 참조와 직선 알고리즘만 있으면 빠른 속도로 길을 찾아가니까요.

그럼 어떻게 응용하느냐! 대충 감을 잡은 분도 있겠죠.

맵을 만들고, 직선만으로도 갈 수 있는 지역들을 구분합니다. 그리고 적절히 웨이포인트들을 지정해 줍니다. 웨이포인트들끼리는 직선으로 갈 수 있어야 합니다. 그리고 웨이포인트들을 그래프 구조로 생각하고 위와같은 출발점-목표점 표를 만듭니다.

실제로 유닛이 길을 찾는 과정은 이렇습니다. 우선 목표지점까지 직선으로 갈 수 있는지 검사해서 갈 수 있으면 그냥 갑니다. 갈 수 없으면, 유닛과 가장 가까운 웨이포인트를 찾아서 출발점 웨이포인트로 하고 목표지점과 가장 가까운 웨이포인트를 찾아 목표점 웨이포인트로 합니다.

두 웨이포인트간을 잇는 웨이포인트들의 경로를 결정하고, 출발점 웨이포인트까지 직선으로 이동한 후 웨이포인트들간을 직선으로 거쳐가서 목표점 웨이포인트에서부터 원래의 목표지점까지 직선으로 이동하면 되는겁니다.

속도 이득은 대단할 것입니다. 쓸만한 길찾기 알고리즘은 트리 구조를 써야 하는데 루프를 엄청나게 돌리게 되거든요. 스택과 재순환 구조도 거의 필수적이지요.

거기에 비하면 웨이포인트 방식에서 시간을 소요할 만한 요소는 가까운 웨이포인트 찾기(웨이포인트가 N개라면 N번만 루프를 돌면 됨), 경로 찾기(역시 N에 1차함수적으로 비례) 정도이지요.

위에서 말한 단점 말고도 다른 단점들이 있다면 얘기를 해 주세요. 또 이 기법을 개선시킬 수 있는 방안도 환영입니다.