2D 맵에서의 시선 처리(명암 처리)

류광, 1999

이 글에 나온 아이디어와 알고리즘은 기본적으로 Joseph Hall이란 사람이 제시한 것입니다. 원본은 게임제작 관련 뉴스그룹인데, 정확히 기억이 나지 않는군요.

저자는 아이디어와 알고리즘을 공개한다고 밝혔으니, 문제는 없겠지요. (사실 뭐 대단한 것도 아닌 것 같지만...)

참, Moria 라고 하는 네트핵 류의 텍스트 RPG가 이 기법을 썼다고 합니다. Joseph Hall 이 Moria 제작진인지는 잘 모르겠습니다.

네트핵 같은 텍스트 게임을 비롯해서, XCOM이나 듄2, 또 워크래프트 등등 2차원 맵을 사용한 게임들을 보면, 플레이어의 캐릭터나 유닛이 가지 않은 곳은 볼 수 가 없습니다. 캐릭터의 주변만 보이지요. 물론, 장애물의 뒷쪽은 보이지 않습니다.

이런 것을 Line Of Sight라고 합니다. 즉 시선입니다. 전략 시뮬에서는 Fog of War, 즉 전장의 안개라고도 합니다. 우리말로는 명암 처리라고 하는게 의미가 더 뚜렷해질 것 같기도 합니다만...

전략성이 중시된 게임이라면 (비록 RPG라도) 특히 턴방식이라면 이러한 시선처리는 필수적이지요. 그런데 일본 게임들은 별로 안하더군요. (대전략 시리즈는 하나? 모르겠네요.)

말로 설명해서는 뭘 말하는지 모르겠다는 분을 위해 간단히 그림을 그려 보지요.

 @ : 캐릭터 (말하자면 광원의 중심)
 # : 장애물 (벽, 산 등등)
 . : 보이는 맵
 * : 보이지 않는 맵
 ....*****....*
 .....***....**
 .....###...***
 ..........##**
 ...........#*.
 ......@.......
 ...#..........
 **............

여기서 * 부분은 미리 정해진 것이 아니라, @와 #의 위치에 의해 생겨나는 것입니다. 즉 이것을 어떻게 계산해 낼 것인가 하는 것이 시선 처리 알고리즘입니다.

맵 방식 게임 프로그래밍의 경험이 있는 사람이라면, 일단은 브랜슨햄 알고리즘을 사용해서 캐릭터로부터 사방으로 직선을 그어 가면서 장애물에 부딪힐때까지만 밝게 만들면 되겠다 하는 생각이 떠오를 것입니다. 이건 그야말로 캐릭터의 눈빛을 쫓아가는, 아주 원칙적인 알고리즘입니다. 굳이 설명할 필요도 없겠지요.

예상이 가능하겠지만 속도가 문제입니다. 캐릭터의 시선이 캐릭터 사방 10*10 크기의 지역에 미친다고 가정하면, 사각형 각 변의 각 타일마다 캐릭터로부터 직선을 그어 봐야 한다는 결론이 나옵니다. 즉 36개의 직선을 그어야 하는 것이지요. (뭐 요즘은 CPU가 워낙 빨라졌으니... 그래도 속도는 중요하죠.)

게다가 타일 맵은 정수의 세계이므로 직선은 항상 계단 현상이 생깁니다. 좀 어색한 결과가 나오기도 합니다. (물론 여기에서 제시하는 알고리즘 역시 정수의 세계를 대상으로 합니다만, 개발자가 그림자 부분의 패턴을 임의로 조정할 수 있다는 장점이 있습니다. 설명이 뒤에 나옵니다.)

Joseph Hall의 아이디어를 이용하면, 수십-수백배 빠른 결과를 얻을 수 있습니다. 기본적인 개념은, 그림자의 패턴을 미리 메모리에 저장해 둔다는 것입니다.

그럼 그림으로 설명을 해 보지요. 다음과 같은 결과를 얻고 싶다고 합시다.

 . . . . . *
 . . . . * *
 . . . * * *
 . . . 3 * *
 . . . 2 * *
 @ . . 1 * *

여기서 @는 캐릭터, 1,2,3은 장애물입니다. *는 보이지 않는 부분. 이때 장애물을 하나씩 분해하면,

                                                                  *
                . .             . .             . .             * *
              . . .           . . .           . . *           * * *
            . 3 . .         . . . .         . . * *         . 3 * .
          . . 2 . .       . . . . .       . . 2 * *       . . . . .
        @ . . 1 . .     @ . . 1 * *     @ . . . . .     @ . . . . .
                             (1)             (2)             (3)

이런 결과를 낳습니다. 여기서 중요한 것은, 각각의 장애물은 자기 이외의 장애물과는 무관하게, 즉 독립적으로 그림자를 만든다는 것입니다. 장애물이 두개 겹쳐있다고 그림자가 더 진해지거나 그림자의 영역이 확대되지는 않는다는 것이지요.

따라서 테이블에 1, 2, 3의 위치가 만드는 그림자 패턴이 담겨 있다면 세 패턴을 합치기만 하면 된다는 것입니다. 이러면 더하기, 빼기나 조건문은 전혀 필요없이 배열이나 포인터로 메모리를 읽고 쓰기만 하면 됩니다... 속도에서 얻는 이득이 상당한 것이지요.

간단히 계산해보면, 캐릭터 주위의 10*10 영역에 대한 시선 처리의 경우 100개의 패턴을 정의해 두면 됩니다. 물론 캐릭터의 오른쪽-위 평면만 패턴을 마련한 후에 X, Y 좌표를 조작하면 4분의 1로 줄일 수 있습니다. 8분의 1로도 가능합니다. (브랜슨햄으로 원을 그릴때 8분의 1 부분만 그린 후 상하좌우로 펼쳐서 원을 완성하는 것과 같습니다.)

Joseph Hall이 제시한 자료구조는 다음과 같습니다.

 byte
 1        # 이 명암에 포함된 래스터의 갯수
 2        #1 시작
 3        #1 끝
 4        #2 시작
 5        #2 끝
         ...

위 그림의 (1), (2), (3) 를 위 방식으로 표현하면:

 (1)      1 4-5
 (2)      3 4-5 4-5 5-5
 (3)      4 4-4 3-5 4-5 5-5

처럼 됩니다.

이러한 구조의 데이터를 2차원 배열로 작성해 놓고, (속도는 느리더라도 결과는 확실한 패턴 생성기를 하나 만들어서 자동으로 처리해도 좋겠지요.) 실제로 맵을 출력할때 캐릭터 주변 x,y좌표에 장애물이 있느면 패턴테이블(x,y) 의 패턴을 명암 처리 맵에 찍어주면 되는겁니다.

그리고, 최종적으로 다음과 같은 형태의 패턴을 덮어씌우면 원형 처리가 됩니다. (크기는 게임에 따라 조절을 해야겠죠.)

 * * * * . . . . * * * *
 * *                 * *
 *                     *
 *                     *
             .
             .
             .
 *                     *
 *                     *
 * *                 * *
 * * * * . . . . * * * *