들어가며
로그라이크 게임의 핵심 요소 중에는 FoV라는 것이 있다. FoV란, 'Field of View' 또는 'Field of Vision'의 약자로써, 아래 이미지 처럼 플레이가 던전과 같은 필드의 특정 위치에서 볼 수 있는 오브젝트와 가려지는 오브젝트를 구분하여 디스플레이하는 기능을 말한다.
FoV를 구현하기 위해 간단하게 사용되는 방법으로는 '라이트 트레이싱(Light tracing)'이 있다. 라이트 트레이싱이란 시작점 - 일반적으로 플레이어 캐릭터 - 에서 바깥 쪽으로 가상의 빛을 쏘아 장애물에 의해 막히는 맵 셀을 탐지하는 방법이다. 라이트 트레이싱은 간단히 구현할 수 있다는 장점이 있는 반면, 아래 이미지 처럼 같은 셀에 대해 여러번 같은 연산을 수행하게 되어 CPU의 낭비가 발생한다는 단점이 있다.
이와 같은 이유로 실제 로그 라이크 게임을 구현할 때는 라이트 캐스팅 보다는 개선된 다른 알고리즘을 사용하는 것이 일반적이다. 이번 포스트에서는 이런 라이트 트레이싱의 비효율성을 보완할 수 있는 쉐도우 캐스팅(Shadow casting) 알고리즘에 대해 살펴 보도록 하겠다.
본 포스트는 roguebasin.com의 FOV using recursive shadowcasting를 기반으로 작성 되었으며 설명을 돕기 위해 Unity를 이용한 예제를 포함했다. 쉐도우 캐스팅을 구현한 소스와 유니티 프로젝트는 아래 링크에서 확인할 수 있다.
- 쉐도우 캐스팅 전체 소스 코드 : https://github.com/ChoiIngon/blog/blob/master/438/Assets/Scripts/Map.cs
- 쉐도우 캐스팅 유니티 프로젝트 : https://github.com/ChoiIngon/blog/tree/master/438
쉐도우 캐스팅(Shadow Casting)
쉐도우 캐스팅은 라이트 캐스팅 처럼 직선을 따라 셀들을 반복하여 검사하는 방법이 아닌 시작점과 장애물 사이의 기울기를 이용하여 그림자에 가리워진 물체가 우리의 눈에 보이지 않는 원리를 이용하여 장애물이 시야에 보이는지 그렇지 않은지 판단하는 알고리즘이다. 이는 약간의(?) 수학적 지식이 필요하므로 라이트 트레이싱 보다는 직관적이진 않지만 동일한 맵 셀을 반복하여 검사하지 않아 라이트 트레이싱 보다 효율적이다.
쉐도우 캐스팅의 기본 탐색 방식은 아래 그림과 같이 맵을 8분면으로 나누어 각 분면에 대해 각각 탐색을 진행한다.
또한 쉐도우 캐스팅은 라이트 트레이싱 처럼 시작접에서 바깥쪽으로 하나의 직선을 따라 탐색하지 않는다. 각 분면에 따라 시작 점에서 행(row) 단위 또는 열(column)단위로 탐색해 나간다.
1분면에서의 탐색을 예롤 들면, 시작점에서 부터 바깥 쪽, 즉 1행에서 부터 9행으로 방향으로 행(row) 단위로 탐색이 진행 되며 각 행들에서는 바깥 쪽에서 안쪽(시작점 쪽)으로 탐색을 진행 한다.
탐색 중 장애물로 막혀 있는 셀을 발견하게 되면 원점에서 부터 해당 셀을 지나는 좌, 우 기울기를 구하여 두 기울기 사이에 위치하는 셀들은 원점에서 보이지 않는 것으로 판단 한다. 이런 방식이 마치 그림자 뒤에 감춰지는 것 같다고 하여 그림자를 이용한 장애물 탐색, 즉, '쉐도우 캐스팅'이라고 한다.
직선의 기울기
쉐도우 캐스팅을 이해하기 위해서는 먼저 직선의 기울기(slope)에 대해 이해해야 한다. 직선이란 두 점을 지나는 선을 의미하며 두 점의 위치에 따라 직선의 기울기가 결정 된다. 기울기는 아래와 같은 간단한 공식에 의해 계산 되어질 수 있다.
기울기 = (x1 - x2) / (y1-y2)
예를 들어 두 점 [3,2]과 [5,8]을 지나는 직선의 기울기는 아래와 같이 구할 수 있다.
기울기 = (3-5) / (2-8) = 2 / 6 = 0.333333
만일 우리가 이 직선을 따라 이동한다면 y 축 값이 1 증가 할 때 마다 x 축 값이 0.33333 증가하는 것을 확인할 수 있다.
직선의 기울기에 대한 보다 상세한 내용은 [여기]를 참고 하자. 참고로, 소개된 링크에서는 x축을 분모로 삼고 있어서 헷깔릴수 있는데, 본문과의 차이는 x축이 기준이 되느냐, y축이 기준이 되느냐 뿐이다. 쉽게 생각해서 그림을 90도 옆으로 기울여서 생각하면 본문과 링크의 내용은 동일하다.
재귀 쉐도우 캐스팅
앞서 소개된 일반적인 쉐도우캐스팅 방식은 'Computing LOS for Large Areas' 라는 포스트에 자세히 소개 되어 있다. 하지만 이 알고리즘은 임시 배열을 사용하여 다소 복잡한 구현을 필요로 한다. 본 포스트에서는 '재귀(recursion)'를 사용하여 코드를 보다 간단하게 구현해 보도록하겠다.
재귀 쉐도우 캐스팅 역시 일반 쉐도우 캐스팅과 마찬가지로 필드를 8개 분면으로 나누어 탐색한다. 각 분면간 맞닿아 겹치는 부분은 공통으로 계산한다. 그림으로 나타내 보면 아래와 같다.
재귀 쉐도우 캐스팅 알고리즘도 각 8분면을 분면의 위치에 따라 행(row) 또는 열(column) 단위로 탐색을 진행한다. 각 분면에서 탐색 시작은 시작점에 가까운 부분 부터 시작하여 아래와 같이 진행 된다.
- 1, 6분면은 원점에서 부터 바깥 쪽으로 행(row)단위로 탐색하며 열(column)은 왼쪽에서 오른쪽으로 진행한다.
- 2, 5분면은 원점에서 부터 바깥 쪽으로 행(row)단위로 탐색하며 열(column)은 오른쪽에서 왼쪽으로 진행한다.
- 3, 8분면은 원점에서 부터 바깥 쪽으로 열(column)단위로 스캔을 진행하며 행(row)은 위에서 아래로 진행한다.
- 4, 7분면은 원점에서 부터 바깥 쪽으로 열(column)단위로 스캔을 진행하며 행(row)은 아래에서 위로 진행한다.
탐색을 진행하는 중 장애물이 탐지 되면 다음 행/열에서 부터 이전 행 또는 열에서 탐지된 장애물의 그림자를 만나기 전까지 탐색을 진행한다.
반면, 장애물이 탐지 되었던 원래 행/열은 계속 탐색을 이어 나간다. 장애물 바로 옆에 다시 장애물이 탐지 된다면 해당 셀은 건너 뛴다. 만일 장애물 옆에 아무런 장애물이 없는 셀이 탐지 된다면 위의 과정이 다시 반복 된다..
이해를 돕기 위해 아래 그림과 함께 쉐도우 캐스팅 알고리즘을 따라가 보도록 하자.
위 그림은 1분면의 스캔을 시뮬레이션하고 있다. 1분면은 원점에서 부터 바깥 쪽으로 행(row)단위 탐색을 진행한다. 각 행에 대한 탐색은 왼쪽에서 부터 오른쪽으로 진행되며 가장 오른쪽에 있는 셀까지 탐색이 완료된 경우엔 다음 행으로 이동하여 동일한 과정을 반복한다.
위에서 주목해야 할 점은 시작점의 부터 가장 왼쪽 셀들에 대해 선을 그어 보면 기울기가 1임을 알 수 있다. 우리는 이것을 '시작 기울기(start slope)'라고 부르기로 하겠다. 같은 방식으로 행에 대한 탐색이 끝나는 가장 오른쪽 셀들에 대해 선을 그어 보면 기울기가 0이다. 이것을 '종료 기울기(end slope)'라고 한다.
쉐도우 캐스팅은 각 행(또는 열) 단위의 탐색을 이 '시작 기울기'와 '종료 기울기'를 기준으로 진행한다. 셀의 기울기가 '시작 기울기'인 셀에서 부터 탐색을 시작하여 '종료 기울기'인 셀에 닿으면 탐색을 종료한다. 이렇게 1 행 부터 11 행 까지는 아무런 별다른 특이 사항 없이 탐색이 진행된다.
하지만 탐색이 12행에 이르게 되면 흥미로운 일이 발생한다. 아래 그림의 빨간색으로 추가된 부분들에 대해 주목하자.
12 행 탐색 중 첫번째 장애물(9열)에 도착하게 되면 새로운 시작 기울기와 종료 기울기를 가지고 다음 행(13행)에서 새로운 탐색이 재귀적으로 시작 된다.
13 행에서 시작 기울기는 이전행(12행)과 같지만 종료 기울기는 기존 종료 기울기 '0' 대신, 장애물과 시작점과의 기울기를 계산해 새로이 지정 된다. 일반적으로 종료 기울기는 시작점에서 장애물의 왼쪽 선이 닿는 점을 이용해 계산 된다. 만일 우리가 맵을 확대한다면 아래와 같은 그림이 그려진다.
종료 기울기는 시작점의 중심에서 부터 위 그림에서 노란점으로 마크 된 점 까지 선을 그어 구할 수 있다. 장애물이 있는 셀의 위치는 시작점으로 부터 x축 9, y축 12만큼 떨어져 있으며, 그것을 기준으로 노란색 점의 좌표를 구하면 x:9.5, y:11.5가 된다. 기울기 공식에 따라 9.5/11.5를 하게 되면 약 0.82 정도의 기울기를 구할 수 있다.
이제 우리는 기울기 1에서 부터 0까지 진행 되는 원래 탐색과 12행에서 장애물 탐지로 인해 13행에서 기울기 1에서 부터 0.82까지 진행되는 두번째 탐색을 가지게 되었다. 12행에서 진행되던 탐색은 13행의 재귀함수 호출 이후에도 계속 탐색을 이어나간다. 13행은 1부터 0.82까지 탐색을 진행한다.
위 그림에서 1번 탐색은 최초 진행 되었던 탐색, 2번 탐색은 장애물 탐지로 인해 새로이 시작된 재귀 탐색을 나타낸다.
자, 다시 12행에서 진행 되고 있는 '1번 탐색'으로 돌아가 보자. 이 탐색은 이제 막 첫번째 블록킹 셀을 지났다. 그리고 다음 셀을 체크하여 이것 역시 블록킹 셀이라는 것을 알아낸다. 이전 셀이 블록킹 셀이었다면 아무것도 하지 않고 장애물이 없는 셀을 찾을 때 까지 계속 다음 셀로 탐색을 이어나간다.
블록킹 셀 다음에 처음으로 논블록킹 셀이 발견 되면 새로운 이제 우리는 '새로운 시작 기울기'를 계산 해야한다. 새로운 시작 기울기는 시작점의 가운데서 부터 논블록킹셀의 오른쪽 직선이 스치는 점을 이용해 계산 된다.
새로 탐색된 논블록킹 셀은 시작점으로 부터 x:7, y:12 만큼 떨어져 있으며, 스치는 포인트의 좌표는 x:7.5, y:12.5. 기울기를 계산하면 새로운 시작 기울기는 0.6이 된다.
논블록킹 셀을 만났을 때는 단순히 새로운 시작 기울기만 갱신하고 새로이 재귀 탐색을 시작하거나 그러지는 않는다. 12행의 탐색이 가장 마지막 셀에 닿으면 탐색은 종료 되고, 다음 행(13행)으로 이동하여 다시 탐색이 시작 된다. 단, 13행에서의 시작 기울기는 앞에서 0.6으로 갱신되었으므로 0.6에서 부터 새로이 탐색을 시작하게 된다.
13 행에서 0.6을 시작 기울기로 새로운 스캔을 시작하면 시작하자 마자 블록킹 셀이랑 마주치게 된다.
이런 일이 발생하면 12행헤서 그랬던 것 처럼 종료 기울기를 구해 다음 행에서 탐색을 계속 진행 해야 하지만 위의 경우에는 시작 기울기가 종료 기울기 보다 더 작기 때문에 새로운 재귀 탐색의 시작과 동시에 종료 되어 버린다.
다음은 원래 규칙 대로 블록킹 셀 이후엔 논-블록킹 셀을 만날때 까지 탐색을 계속한다. 위 케이스에서는 바로 다음 셀이 논 블록킹 셀이다. 이제 우리는 아까 12행에서 블록킹 섹션 이후에 했던것 처럼 새로운 시작 기울기를 구할 수 있다. 이 과정이 완료되고 난 뒤에 우리는 마지막 셀에 닿거나 블록킹 셀을 만날때 까지 왼쪽에서 오른쪽으로 검색을 계속 한다. 우리의 예제에서는 마지막 셀에 닿기 전에 블록킹 셀을 만나게 된다.
이제 12행에서와 마찬가지로 새로운 탐색이 재귀적으로 시작 된다. 이 탐색은 원래 탐색인 0.6과 동일한 시작 기울기를 가지며, 종료 기울기는 블록킹 셀의 왼쪽 모서리를 스치는 선에 의해 결정 된다. 이제 우리는 세 개의 탐색을 진행하게 되었다
13행의 x:4, y:13의 블록킹 셀을 빠져나오면 2 개의 새로운 논블록킹 셀을 지나 새로운 블록킹 셀을 만나게 되어 위와 동일한 과정을 다시 한번 더 반복한다. 그리고 다시 다른 블록킹 셀로 진입하게 된다.
13행의 제일 오른쪽에서 스캔이 종료하게 되었을 때 이전과는 달리 논블록킹 셀 대신 블록킹 셀이 위치하고 있다. 스캔이 블록킹 셀을 마지막으로 종료 되었기 때문에 다음 행에서 새로운 재귀 스캔은 시작하지 않는다.이렇게 1번 스캔은 종료 되고 우리는 이제 2, 3, 4번 재귀 스캔을 진행하고 있게 된다. 이 스캔들은 이전 스캔과 동일한 과정을 거친다.
모든 스캔이 종료 되고 나면 아래와 같은 뷰가 결과로 나온다.
이 프로세스는 다른 8분면에도 동일하게 적용되며 소스코드느 아래 링크에서 확인할 수 있다. (핵심 포인트: 블록킹 섹션 이후에는 시작 기울기를 다시 구한다).
마치며
위 내용들을 요약하면 아래와 같다.
- 쉐도우 캐스팅은 맵을 8분면으로 분할하여 탐색한다
- 각 분면은 열 또는 행 단위로 탐색을 진행하며, 각 행 또는 열 내에서 바깥쪽에서 안쪽으로 탐색한다.
- 탐색 중 블록킹 셀을 만나게 되면 '종료 기울기'를 재설정하고 다음 행 또는 열에서 재귀적으로 탐색을 계속 한다.
- 블록킹 섹션을 지나 논 블록킹 섹션을 만나면 '시작 기울기'를 재설정 한다.
- 행 또는 열 내에서 '종료 기울기' 까지 탐색이 진행 되었을 경우, 마지막 셀이 블록킹 셀인 경우 해당 탐색을 종료한다.
- 블록킹 셀이 아닌 경우 다음 행 또는 열에 대해 탐색을 계속 진행한다.
보다 자세한 내용은 [여기]에 소개된 소스 코드와 함께 본문 내용을 비교해 보며 따라가면 보다 이해가 쉬울 것이다.
이상 쉐도우 캐스팅에 대한 포스트를 마무리 하겠다.
부록. 같이 읽으면 좋은 글
- 랜덤 맵 만들기
- 삼각함수
- 벡터(vector)의 크기(길이)
- GitHub 전체 유니티 프로젝트 : https://github.com/ChoiIngon/blog/tree/master/438
- 원문 : FOV using recursive shadowcasting
