BSP

BSP(Binary Space Partitioning)알고리즘을 응용해 로그라이크류 게임 방만들기

이진 공간 분할법(Binary Space Partitioning, BSP) 은 재귀적으로 유클리드 공간을 초평면 상의 볼록 집합으로 분할하는 기법이다. 분할 과정으로 BSP 트리라 불리는 트리 구조가 만들어진다. doom은 3차원처럼 보이지만 실제로는 2차원이고 그 2차원을 나타내기 위해 사용됐다. BSP알고리즘을 통한 로그라이크류 방만들기 0: 빈 공간 1 : 방, 3: 가로분할 길, 4: 세로분할 길 로그라이크 게임을 하다보면 일정한 맵을 돌려쓰는 게임도 있긴하지만 매번 새로운 맵을 생성하는 게임들이 존재한다. 매번 새로 맵을 생성할때 BSP알고리즘을 응용하여 새로 맵을 만들수 있다. 위에서 설명한 BSP알고리즘에서 둔각을 찾아 반복하여 나누는 방법이 아니라 2차원상에서 직사각형 모양으로만 방을 나눠..