정보 [+]

이동 가능지역 표시 기법과 길찾기

류광, 1999

턴 방식의 전략 시뮬 게임에서, 유닛을 클릭하면 그 유닛이 갈 수 있는 곳이 표시됩니다. 사각형 또는 대충 원형의 지역이 표시되는거지요. 그런데 맵 상에 지나갈 수 없는 장애물이 있는 경우 반듯한 형태가 되지 않습니다. 다음과 같은 형태입니다.

    .   ..
   ... ......
  ...##...##..
 ..........#..
 ......@......
 .....&.&.....
  ..      ...

이러한 효과를 어떻게 내야 할까요? 이번에는 이 문제를 살펴보겠습니다. (이 글의 아이디어는... 오랜만에 제 스스로 생각해 낸 것입니다. 물론 세계 최초로 나온 아이디어는 아니겠지요.)

글의 순서는,

가장 간단한 이동지역 표시에 대해 짚은 후
장애물 처리가 가능한 이동지역 표시기법의 기본 알고리즘과
실제 장애물처리,
그리고 적극적인 장애물인 적 유닛 처리 기법을 알아보고,
마지막으로 이를 길찾기에 응용하는 방법을 알아봅니다.

차례 [+]

그럼, 시작.

가장 간단한 이동지역 표시(장애물을 고려하지 않는 것)

이것은 그냥 거리 공식을 쓰면 됩니다. 이동력(칸)을 d, 유닛의 좌표를 (x,y)라고 한다면, 맵의 각 타일(좌표는 tx,ty)을 조사해서(또는 유닛을 중심으로 상하좌우 d 만큼 떨어진 사각형 내의 타일만 조사해도 됨)

 d > root((tx-x)^2 + (ty-y)^2))

인지만 조사하면 됩니다. 이러면 원형이 됩니다. root 대신 |tx-x| + |ty-y| 를 써도 되나, 이러면 마름모꼴이 나옵니다. 위 식을 만족하면 갈 수 있는 곳, 만족하지 못하면 이동거리보다 먼 곳입니다.

본론 - 장애물 효과를 낼 수 있는 표시 기법

여러가지 알고리즘이 있겠지만, 제가 생각한 것은 홍수 효과입니다. 즉 물이 한곳에서 자신이 갈 수 있는 곳으로 확장되어서 흘러가는 것을 이용한 것이지요.

목표는 다음과 같은 맵을 만들어내는 것입니다. 유닛의 이동력이 5인 경우입니다. 숫자가 없는 곳은 0입니다.

     1 1 1 1 1
   1 2 2 2 2 2 1
 1 2 2 3 3 3 2 2 1
 1 2 3 4 4 4 3 2 1
 1 2 3 4 5 4 3 2 1
 1 2 3 4 4 4 3 2 1
 1 2 2 3 3 3 2 2 1
   1 2 2 2 2 2 1
     1 1 1 1 1

과정을 간단히 써 보겠습니다. 우선 이동맵과 임시맵 두가지가 필요합니다.

맵에서 유닛이 있는 곳에 유닛의 이동력을 넣습니다.(위에서는 5)
인접한 주변 타일에 자신의 값-1을 넣습니다. 여기서, 사각형이 아닌 원형의 효과를 내기 위해 홀수인 경우에는 주변 8곳(상하좌우와 대각선방향까지), 짝수인 경우에는 4곳(상하좌우)만 넣어줍니다. 0이 아닌 숫자가 이미 들어 있으면 넣지 않습니다. (이미 숫자가 있다는 것은, 이미 지나온 곳이라는 의미입니다.) 또한 1 이하이면 할 필요가 없습니다. 중요! 여기서 참조는 이동맵에서, 변경은 임시맵에 해야 병렬처리가 됩니다.
한칸 바깥쪽의 사각형 지역에 대해 2번 과정을 반복합니다.
임시맵을 이동맵에 복사합니다.
2에서 4의 과정을 이동력만큼 반복합니다. (위에서 5번 반복하면 0이 나옵니다. 그러면 끝입니다.)

이렇게 하면 위의 그림과 같은 형태가 나옵니다. 개념적으로 설명하면, 물 5리터가 사방으로 흘러가는 것과 같은 이치입니다. 이동지역의 형태는 정확한 원형은 아니지만 원형 비슷하게 나옵니다. 또, 이렇게 숫자를 넣으면 좋은 점은, 이동력 소비를 간단히 계산할 수 있다는 것입니다. 즉 처음에 유닛을 클릭하면 위와 같은 지역이 표시됩니다. 그래서 3인 곳을 클릭하면 거기까지 이동합니다. 거기서 다시 클릭한 경우 3에서 1을 뺀 2가 나머지 이동력이 되는 것입니다. 2를 가지고 다시 1-4를 반복하면 됩니다. 3번의 경우 맵 전체를 다시 계산해도 되지만, 속도를 위해서 집어넣은 것입니다. 말로 잘 설명이 안되는 것 같은데, 다음과 같은 순서로 타일을 조사하는 것입니다.

               0 3 3 3 0
      4 4 4    3 . . . 3
 5 -> 4 . 4 -> 3 . . . 3 ...
      4 4 4    3 . . . 3
               0 3 3 3 0

장애물 처리

일단 위와 같은 기법을 다 이해했다고 하면, 장애물 처리는 사실 간단합니다. 장애물을 만나면 (원래의 맵을 참조하면 됩니다) 아예 계산을 안하면 됩니다. 다음 그림에서 . 가 장애물입니다. 5가 유닛입니다.

       1 1 1
     1 2 2 2 1
   1 1 1 2 3 2 1
 1 2 2 . . 4 . 2 1
 1 2 3 4 5 4 3 2 1
 1 . 3 4 4 4 . 1
 1 2 2 3 3 .
   1 2 2 2 2 1
     1 1 1 1

5의 위쪽에 원래는 4가 들어가야 하는데, 장애물 때문에 계산을 아예 안하므로 뻗어나가지를 못합니다. 대신 오른쪽 위에 4가 들어갔기 때문에 돌아갈 수는 있게 되었습니다. 실제 코딩시 이동맵에 장애물에 대한 특별한 값을 배정하는 것은 좋지 않습니다. 0은 이동력이 0 또는 아직 계산하지 않은 부분이므로 제외되며, 또 음수의 값은 아래에서 보듯 적 유닛의 효과이므로 장애물에 대해 특별히 배정할 값이 없습니다. 즉 루프 안에서 실제 타일맵을 참조해야만 합니다. 그럼, 여기서 원하는 곳으로 이동하려면 어떻게 해야 할까요? 다음과 같이 하면 됩니다.

자신으로부터 목표점에 가장 가까운 주변 타일로 한칸 이동합니다. 갈 수 없을 때에는, 자신의 값과 비교해서 가장 작은 값의 타일로 갑니다. 작은 값의 타일이 하나 이상이면 역시 목표점에 가장 가까운 타일로 갑니다.
1)번으로 하면 제자리를 맴돌 수도 있는데, 적절히 처리해야 합니다. 플래그 맵을 설정해서 한 번 간 곳은 다시 가지 않도록 하면 해결할 수 있습니다. 작은 값이 없으면 같은 값, 같은 값도 없으면 큰값으로 가지 않았던 곳을 가면 됩니다. 더이상 갈 곳이 없어지면, 목표점으로 갈 수 없는 경우입니다. (이론적으로 그런 경우는 생기지 않지만, 이후에 설명할 길찾기 알고리즘에서는 꼭 필요합니다.)
1-2를 목표점에 도달할 때까지 반복합니다.

위의 그림에서 목표점이 5 위쪽의 1이라면 다음과 같습니다.

적 유닛 처리(적극적인 방해)

적들은 지나갈 수 없을 뿐만 아니라 자기 주변으로 이동하는 것도 방해합니다. 이런 효과를 어떻게 구현할까요?

적 유닛이 있는 자리에 -1을 넣어주면 됩니다. 그리고, 원래의 알고리즘 중 3번을 조금 수정해서, 음수의 값이 있는 타일을 만나면 기억해 두었다가 그 타일들만 다시 계산을 하되, 이번에는 그냥 주변 타일들에 값을 덮어쓰지 말고 주변 타일들의 값에 -1을 더해줍니다.(음수를 더해주므로, 이동력을 떨어뜨리는 결과가 됩니다.)

음수의 경우에는 영향력이 너무 커지지 않도록 상,하,좌,우 4곳만 더하는 것으로 하는게 좋습니다. 또한, 맵 전체를 매번 계산하면 적의 영향력이 맵 전체에 퍼지므로 이 경우에는 반드시 2번글 알고리즘 3번에서 사용한 것 처럼 유닛으로부터 바깥으로 맵을 조사하는 방식을 써야 합니다.

그리고 더해주는 과정이 있으므로, 같은 루프 안에서 해결할 수가 없습니다. 원래의 과정은 값을 덮어쓰는 것이었으므로, 계산 순서때문에 결과가 이상해질 수 있습니다. 반드시 별도의 과정으로 처리해야 합니다.

적이 한 칸 간격으로 두명 서있다고 합시다

                        -1  -1             -1-1-1-1-1
-1 -1      -1 3-1     -1-1 2-1-1          1-1-2 1-2-1 1
 4 4 4    3 4 4 4 3    3 3 4 3 3        1 2 1 1 2 1 1 2 1
 4 5 4 -> 3 4 5 4 3 -> 3 4 5 4 3 -> ... 1 2 3 4 5 4 3 2 1
 4 4 4    3 4 4 4 3    3 4 4 4 3        1 2 3 4 4 4 3 2 1
            3 3 3        3 3 3          1 2 2 3 3 3 2 2 1
                        (-1 주변에        1 2 2 2 2 2 1
                        -1을 더했음)        1 1 1 1 1
숫자가 없는 곳은 0입니다.

보시다시피 적(-2) 사이로는 통과할 수 없게 됩니다. 대신 한 칸 이상 멀리 돌아갈 수는 있습니다. 이동력이 크거나 적이 가까이 있으면 조금은 뚫고 나갈 수 있습니다. 뚫고 나가는 정도를 조절하려면, -1만 더해주지 않고 (자신의 음수값 -1)을 더해주거나, 주변 4곳 대신 8곳의 타일에 더해주면 됩니다. 이러면 적의 영향력이 좀 더 강해집니다.

길찾기 알고리즘에 응용

위의 알고리즘을 길찾기 알고리즘에 응용할 수 있습니다. 다만, 효율이 그렇게 좋지는 않습니다. 최단 거리를 찾지도 못하며, 갈 수 없는 밀폐된 곳을 가려고 하면 무한 루프에 빠질 수도 있습니다.(자신이 갔던 곳을 기억하기 위한 플래그맵을 사용하면 해결할 수 있습니다만 맵을 온통 헤매다가 못간다는 결론을 내릴 가능성이 많습니다.)

과정은 다음과 같습니다.

우선 출발점에 이동력을 충분히 큰 값으로 넣습니다. 충분히 큰 값을 넣는 이유는, 이번 과제는 길을 찾는 것이므로 충분히 멀리 갈 수 있게 하기 위함입니다. 물론 음수가 나와도 상관없도록 할 수도 있습니다. (아래의 설명을 계속 보면 무슨 의미인지 알 수 있을 것입니다.)
이번처럼 주변타일을 조사해서 값을 넣습니다. 장애물인 경우에는 아예 계산을 하지 않습니다. 단, 이번에는 위에서처럼 유닛으로부터 바깥으로 뻗어나가는 식이 아니라, 0,0에서 (X 최대,Y 최대) 까지 무조건 순차적으로 검사해야 합니다.(이에 대한 개선 사항은 뒤에 설명) 그렇게 해야 멀리 돌아가는 길도 찾아낼 수 있습니다. 물론 참조는 이동맵에서, 변경은 임시맵에서 해야 병렬처리가 됩니다.
임시맵을 이동맵에 복사합니다.
2, 3번 과정을 반복합니다. 그러다가 목표점에 어떤 숫자가 배정되면(즉 0이 아닌) 끝냅니다.

이러면 일단 길찾기에 필요한 이동맵이 완성됩니다. 예를 들어보지요. 50이 출발점, . 는 장애물입니다. 그리고 !가 목표입니다. (중요하지 않은 부분은 생략했습니다.)

         .  .  .  .
         .  43 42 !
46 46 46 .  44 .
46 46 46 45 44 .
46 47 .  .  .  .
46 48 .  49 48
47 48 49 50 49
47 48 48 49 48

위 알고리즘을 반복하면, 결국 41에서 !를 만납니다. 그럼 이 맵을 이용해서 길을 찾아가 봅시다. (출발점을 50으로 했는데, 맵이 크고 길이 복잡하다면 50으로도 모자랄 수 있겠지요. 여기서는 값의 대,소가 중요하므로 음수를 허용하는 것으로 해도 될 것입니다.)

3번 장애물처리에서 말한 길찾기 알고리즘을 사용하면 됩니다. 그것을 위의 예에 적용시키면, 역시 최단거리는 못가고 좀 헤매는 것을 알 수 있습니다. 50에서 출발해서 오른쪽 위 48로 간 후 한바퀴 돌아서 50 옆의 49로 가게됩니다. 거기서부터는 목표점까지 바로 가는 모습입니다. (루프의 x,y 순서에 따라 조금 다르게 나올 수도 있습니다.)

      .  .  .  .
      .  43-42-!
      .  44 .
   46-45-44 .
47/.  .  .  .
48 . /49-48
48-49 50/

이것을 길찾기에 써먹기에는 좀 무리인 것 같지만, 다른 대안이 없을때 써먹을 수는 있을 것입니다.

100x100의 맵이라면 기본적으로 한 번의 계산시 10000개의 타일에 대해 주변 8개 또는 4개를 처리해야 하므로 평균 6으로 치면 이용하면 60000번의 연산이 필요합니다. 이것을 목표점에 도달할때까지 반복해야 하므로 속도는 A* 같은 알고리즘보다 느릴 것입니다. 그래도 재귀 호출이나 스택 같은 것은 쓰지 않으므로, 컴파일러의 성능에 따라서는 더 좋을 수도 있습니다.

물론 계산을 좀 줄일 수는 있습니다. 계산이 필요한 지역만 계산하는 것입니다. 타일을 계산한 맵 좌표의 최대값, 최소값을 기억해서(즉 왼쪽 위와 오른쪽 아래) 그 부분만 계산하고, 매번 계산할때마다 최대, 최소를 갱신해주면 됩니다. 처음에 는 출발점만 계산하고, 확장되어 나감에 따라 최대, 최소를 갱신하는 것입니다.

에필로그

이상이 이동가능지역 표시와 길찾기에 대한 아이디어입니다. 이후에 실제 구현에서 나타난 문제점등이 있으면 다시 글을 올리겠습니다.