[유니티] BSP 알고리즘을 이용해서 랜덤한 게임 맵 생성하기 [이론]

BSP 알고리즘 (Binary Space Partitioning)은 한국어로 이진 공간 분할법이라는 뜻이다.

말 그대로 한 공간을 계속해서 2개로 나눠주면서 맵을 만들어 주는건데, 특히나 다회차 진행을 반복하게 되는 로그라이크 류 게임에서 플레이어에게 다양한 경험을 주기 위해서 자주 사용되곤 한다.

예시를 보이자면,

위와 같은 그림의 전체적인 맵이 주어졌다고 가정을 할 때, 이 공간을 둘로 나눠준다.

전반적으로 맵의 크기가 균형있게 되려면, 가로와 세로 중 더 긴 방향을 둘로 나눠주는게 좋은 결과가 나오게 된다.

위의 사각형은 가로가 더 기므로 가로로 나눠주면 되는데, 정확히 반반으로 나누기 보다는 랜덤한 좌표에서 잘라준다면

이런식으로 2개의 공간으로 나눠지는걸 볼 수 있다.

또한, 처음 공간을 root 노드라고 생각한다면,

root 노드의 자식 노드(왼쪽, 오른쪽 두가지 존재)는 1,2번 노드가 되는 것이고, 1,2번 노드의 부모노드는 root 노드가 된다.

다시, 나눠진 공간을 반복해서 나눠준다.

이 때, 왼쪽으로 나눠진 공간은 세로가 더 기므로 이번에는 세로로 나눠주도록 하겠다.

이러한 과정을 계속해서 반복하게 되면,

위 모양과 같이 랜덤한 형태의 여러 방으로 나눠지는 모습을 볼 수 있게 된다.

 

다음과 같이 공간을 나누고, 게임 내에서 각 방을 만들고 싶다면

나누어진 공간에 기반해서, 공간보다 작은 랜덤한 크기의 방을 공간의 임의의 위치로 이동시킨다.

위 공간들은 tree에서 모두 leaf node에 해당되는 공간들이다.

이제 마지막으로 방들을 이을 길을 만들어주면 되는데, 길은 leaf node가 아닌 노드들에서 각 자식 노드들을 잇는 길을 만들어주면 된다.

이 때, 잘라진 방향과 수직으로 길을 만들어주면 된다.

이런 식으로 길을 이어주면 완성이다.

 

다음 포스팅에서는 유니티 내에서 직접 BSP를 통해 랜덤한 맵을 생성해보도록 하겠다.