Home

이진 공간분할법은 하나의 공간을 최종목적에 도달할 때 까지 재귀적으로 2개씩 분할하는 과정이다, 해당 방법론은 이진 공간분할법을 통해 생성된 완전히 분리된 공간들을 활용하여 절차적 미로를 생성한다. 그 일련의 과정은 변수할당, 공간분할, 방생성 및 통로연결의 과정을 이루어진다.

첫째, 변수할당과정에서는 공간을 나누는데 사용될 난수의 범위를 결정한다. 이때 난수의 범위 폭이 넓을수록 과하게 작거나 큰방이 생성될 수 있으며, 좁을수록 매번 비슷한 형태의 맵이 생성된다. 둘째, 공간분할 과정에서는 맵을 저장할 전체 공간을 하나의 노드로 만들고 트리의 새로운 잎으로써 기록한다[8]. 이때 노드는 해당공간의 좌 하단 좌표와 우 상단 좌표 값을 정보로 갖는다. 그리고 범위가 결정된 난수를 생성하여, 해당 비율에 맞춰 주어진 공간을 수평 혹은 수직으로 분할한다. 이때 분할로 만들어진 두 개의 공간은 별개의 노드로서 기록하며 기록되어 있는 노드의 수만큼 새로 난수를 생성하여 분할한다. 이때 분할 방향은 수직방향과 수평방향을 진행되며 이전의 분할방향과 반대로 분할을 진행한다. 만들어진 공간들은 별개의 노드로서 새로 기록한다. 반복 횟수가 N보다 작다면, 일련의 과정을 반복한다.

셋째, 방생성에서는 최종적으로 기록된 노드들로부터 분할된 공간의 정보를 받아온다. 그리고 공간을 일정한 비율만큼 차지하는 방을 생성해준다. 이때 방의 크기가 목표로 하는 방의 최소크기를 만족하지 못한 경우 비율을 새로 산정하여 방을 다시 생성한다.

마지막 통로 연결하기에서는 최종적으로 나누어진 방으로부터 다시 트리를 거슬러 올라가며 통로를 이어 미로를 완성한다. 그림 1은 위에서 설명한 과정을 거쳐 생성된 맵을 나타낸다. 그림 1 내 노란색 표시선은 시작점에서 최종 탈출구까지의 경로를 나타낸다.

Fig. 1. 
Path generation by BSP

그림 1에서와 같이 BSP를 활용한 절차적 콘텐츠 생성방법은 알고리즘에 의해 맵이나 미로생성이 용이하여 개발자의 수고를 덜 수는 있다. 그러나 공간을 나누는 난수의 비율설정에서 난수 범위를 넓히면 잘못된 결과 값이 나올 수 있기에 분할비율을 크게 바꿀 수 없어 생성된 미로들은 일정한 틀을 크게 벗어나지 못하여 품질이 다소 떨어진다는 단점을 가지며 맵의 난이도나 복잡도 또한 그다지 높지 않다.

트리구조 확장 방식은 알고리즘의 명칭이 따로 있는 것은 아니지만, 간단하게 구현할 수 있는 만큼 절차적 맵 생성의 한 방법으로 많이 사용되어왔다. 해당 방법론은 BSP처럼 방을 만들어낼 공간을 미리 확보해 놓기보다는, 해당 공간에 방을 생성할 수 있는지 조건만을 판별하여 계속해서 방을 확장시킨다. 몇 개가 만들어질지 알 수 없다는 단점을 갖는다. 알고리즘은 임의좌표생성, 방생성의 과정으로 이루어진다.

첫째, 임의 좌표 생성과정에서 미로를 생성할 공간의 중심점에서 일정한 가중치를 줘서 임의의 좌표를 생성한다. 생성한 좌표를 기준으로 상하좌우 중, 임의의 방향 값을 받아 방 생성을 시작한다.

둘째, 방 생성과정에서 방의 최대 크기와 최소 크기를 기반으로 생성할 방의 크기를 산정한다. 이때 할당받은 좌표를 기준으로 방의 크기만큼 공간이 비어있지 않다면 그대로 종료한다. 하지만 만약 공간이 비어있다면 새롭게 방을 생성해주고, 방의 상하좌우에 문을 생성하여 ‘방 생성’을 반복한다. 그림 2는 위의 설명과 같이 생성된 맵을 나타낸다. 그림 2내의 초록색 표시선은 시작점에서 최종 탈출구까지의 경로를 나타낸다. 그림 1과 그림 2를 비교하였을 때 트리구조 확장 방식에 의해 얻어진 그림 2의 결과에서 방의크기가 다양하게 얻어졌음을 알 수 있다.

Fig. 2. 
Path generation by extended tree structure

BSP방식에 의해 얻어진 그림 2의 결과에 비해 맵의 랜덤성이나 복잡도가 증가함을 보이며 변화의 폭이 넓음을 알 수 있다. 그러나 그림 4에서와 같이 방의 모양이 직사각형으로만 되어있는 방만을 반환함으로써 게임 플레이어에게 흥미를 유발시킬 수 없으며 전체적인 맵의 품질이 떨어지며 랜덤성을 충족하기 어렵다[9]. 따라서 방의구조를 변화시키기 위해 템플릿 도입을 제안한다.

템플릿은 트리구조 확장 방식에의 해 생성된 직사각형구조의 방에 대신 넣어줄 다양한 형태의 구조를 의미한다. 그림 3은 다양한 형태의 템플릿을 포함한 전체 방의구조 즉 맵의 구조를 나타낸다.

Fig. 3. 
Map with different templates

그림 3에서와 같이 본 논문에서 사용할 템플릿은 사각형을 기반으로 변형시킨 구조를 함으로써 새로운 알고리즘을 만들어야 하는 어려움을 극복함과 동시에 과도한 연산을 수행하지 않아도 충분히 랜덤성과 복잡성을 향상시키는 장점을 갖는다. 템플릿을 생성하는 과정은 다음과 같다.

• 1) 먼저 템플릿을 적용시킬 사각형 형태의 방(템플릿 적용방)이 있다고 가정한다.
• 2) 해당 템플릿 적용방의 크기보다 작은 또 하나의 사각형을 무작위로 생성한다.
• 3) 사각형을 템플릿 적용방 내 무작위 위치에 배치한다.
• 4) 사각형 크기만큼 템플릿 적용방의 공간을 삭제한다.
• 5) 삭제된 공간과 맞닿는 템플릿 적용방의 경계에 벽을 생성해 준다.

그림 4는 최종 생성된 템플릿을 타나낸다. 그림 4에서 검정영역은 상기 두 번째 과정에서 생성된 사각형만큼 비워진 공간을 의미하며 초기 템플릿적용방에서 공간이 제거되고 만들어진 템플릿은 ㄱ자 모양을 하게 됨을 알 수 있다. 두 번째 과정에서 만들어지는 사각형의 가로세로 크기에 따라 다양한 ㄱ자 모양이 생성됨을 알 수 있다.

Fig. 4. 
Templates with different size

그림 4와 같이 템플릿이 생성되면 생성된 템플릿이 제대로 된 방인가 즉 유효템플릿인가를 검증하기 위한 검증과정이 다음과 같이 진행된다.

• 1) 먼저 방에서 ‘삭제된 공간’과 ‘벽’을 제외한 모든 좌표를 ‘이동 가능 지점’이라고 가정한다.
• 2) ‘이동 가능 지점’중 한 곳을 무작위로 선정하여, 그 위치를 A라고 한다.
• 3) A에서 다른 모든 ‘이동 가능 지점’으로 이동 가능한지를 검사한다. 검사알고리즘은 대각선 이동이 제한된 A* 알고리즘을 사용한다.
• 4) 3)의 과정에서 만약 이동이 불가능한 경우의 수가 있다면 해당 방은 완전하게 연결되어 있지 않은 것이므로 하나의 방이라 할 수 없으며 따라서 유효템플릿이 아닌 것으로 판별한다.
• 5) 3)의 과정에서 모든 경우의 수를 만족시킨다면, 해당 방은 완전하게 연결되어 있는 방으로 유효템플릿으로 판별한다.

이와 같은 템플릿생성 및 검증과정을 거쳐 기본적으로 만들어질 수 있는 방의 크기에 맞는 다양한 크기의 유효템플릿을 만들어 데이터베이스에 구조체의 배열형태로 저장한다.

템플릿을 적용하기 위해서는 기존의 트리구조 확장 방식에서처럼 맵이 만들어질 공간의 중심에 방을 생성하는 것이 먼저 진행된다. 트리구조 확장 방식의 결과로 사각형 형태의 방이 만들어지면, 그 방의 크기와 같은 템플릿들을 ‘후보 템플릿’으로 두고 그 중 하나를 랜덤 선택하여 맵에 적용시킴으로써 다양한 크기와 형태를 갖는 방을 갖는 맵을 구성할 수 있다. 템플릿의 선택은 맵 다양성을 위해 우선순위 없이 랜덤하게 선택하지만 선택된 템플릿 적용 시 다른 방들과 연결되지 않은 방이 만들어 질 수 있으므로 템플릿을 적용시킨 전체 방 즉 맵의 구조가 이 적절하게 생성되었는가를 평가한다. 적절하다고 판별된 경우 그대로 템플릿을 적용시키며, 만약 적절하지 않다고 판별된 경우 ‘후보 템플릿’에서 적절하지 않다고 판별된 템플릿을 제외하고 다시 랜덤선택 하여 재판별 한다. 모든 후보가 탈락하여 ‘후보 템플릿‘이 비게 될 경우 원래의 사각형 형태의 방을 반환하여 방의 생성을 해당 방의 생성을 마무리하게 된다. 그림 5는 템플릿이 적용된 맵생성 결과를 나타낸다. 그림 1또는 그림 2에 비해 다양한 크기와 형태의 방들로 구성된 맵이 생성되었음을 알 수 있다.

Fig. 5. 
Map with templates