3279 words
16 minutes
[Algorithm] BSP 알고리즘(맵 생성)
이 포스트는 Only BSP algorithm 이론 파트입니다.
혹시나 구현을 가져가고 싶으시다면 맨 아래에 있는 링크로 들어가시면 됩니다.
BSP 알고리즘이란?
BSP(Binary Space Partitioning)는 재귀적으로 유클리드 공간을 초평면 상의 볼록 집합으로 분할하는 기법이다. 분할 과정으로 BSP 트리라 불리는 트리 구조가 만들어진다.
근데 이게 왜 게임에 많이 쓰일까요?? 일단 유명해진 계기는 둠(Doom)이 요 BSP 알고리즘을 사용하면서 굉장히 유명해 졌습니당.
자 BSP 알고리즘은 이제 랜더링에서도 사용이 되는데 사실 이번에 볼 것은 랜더링이 아니라 “맵 생성”을 해볼겁니다. (랜더링 관련해서는 다른 포스팅에서…)
랜덤 맵 생성.. 정말 매력적인 친굽니다. 어릴적 나도 게임을 만들거야!! 했는데 레벨 디자인 가다보면 도대체 시중에 나와있는 게임처럼 어떻게 랜덤으로 맵을 만들까? 라는 의문이 진짜 해결이 안되다가 여러가지 알고리즘 BSP, WFC 등등 이런 애들을 배우면서 와 이게 되누 ㅋㅋ
하면서 해봤던 기억이 있는데요. 그때는 사실 구현이 다 야매였습니다. 진짜 어떻게든 구현한다! 그 마인드.. 그래서 나중에 다른 게임에서 사용하려면 많이 수정을 해야됐었습니다.
그래서 그때의 시절에 있는 분들께 소개시켜드리고 싶은 알고리즘인데 게임 공부하다 보면 분명 한번쯤은 들어봤을 겁니당.
그래서 원리부터 쭉 살펴보죠
알고리즘
다시한번 돌아보면서 시작해보죠!(이 포스트에서는 2차원에 대해서만 설명하겠습니다)
BSP는 공간을 이진 트리 구조로 재귀적으로 분할하는 방식입니다. 큰 공간을 두 개의 작은 공간으로 나누고, 각각의 작은 공간을 다시 두 개로 나누는 과정을 반복합니다. 계속해서 하나의 판을 반->반->반으로 계속 자르는 것을 생각하시면 좋아요
좀 더 자세히 설명해보죠!
공간 분할 과정
1. 초기 공간 설정
저는 구현을 전체 맵을 하나의 직사각형 공간으로 잡고서 하였습니다. 뭐 어떻게든 잡아도 되지만 보통 구현이 편한건 당연히 사각형입니다.
2. 재귀적 분할
이것도 구현에 따라 다르긴 하지만 일반적으로 사용하는 방법을 소개해드리겠습니다.(물론 저도 일반적인 방법으로 구현을 하였구요)
a) 분할 방향 결정:
- 공간의 가로/세로 비율을 확인
- 너비가 더 크면 수직 분할 선호
- 높이가 더 크면 수평 분할 선호
- 비슷한 경우 무작위 선택
b) 분할 위치 결정:
- 일반적으로 공간의 40%~60% 지점에서 분할
- 완전히 중앙에서 분할하지 않는 이유는 다양한 크기의 공간을 만들기 위함
- 최소 크기 제한을 두어 너무 작은 공간이 생기지 않도록 함
목적들은 다 직관적으로 이해할만한 것들입니다.
3. 종료 조건
- 공간이 최소 크기에 도달
- 정해진 분할 횟수에 도달
- 가로/세로 비율이 적절한 범위에 들어옴
[이해를 돕기 위한 자료]
방 생성 과정
여기서 말하는 노드란?앞서 분할 과정에서 생긴 부분들을 노드로 생각하고, 그것을 트리 형태로 바라보면 Leaf node임. 그래서 여기서 말하는 노드는 leaf node를 말함.
- 노드의 크기보다 약간 작게 방을 생성(이 노드가 분리된 공간)
- 벽과의 최소 간격 유지
- 방 크기는 정해진 범위 내에서 무작위로 결정
- 보통 노드 중앙에 방을 배치
[이해를 돕기 위한 자료2]
복도 생성 과정
- 이웃한 방들을 우선적으로 연결
- L자 형태의 복도가 일반적
- 모든 방이 최소한 하나의 다른 방과 연결되도록 보장
- 선택적으로 순환 경로(루프) 추가 가능(그래서 여러개 나올 수도 있음)
[이해를 돕기 위한 자료3]
확장
- 불필요한 복도 제거
- 막힌 공간 처리
- 장식 요소 추가
- 게임플레이를 위한 요소 배치
장/단점
장점
- 구현이 비교적 단순하면서도 다양한 결과물 생성 가능(다른 맵 생성 알고리즘에 비해서 굉장히 쉬운편)
- 자연스러운 공간 구획이 가능(이거는 구현에 따라 좀 달라지긴 합니다.)
- 생성된 맵의 구조가 명확하고 탐색하기 쉬움
- 확장성이 좋아 다양한 변형이 가능(1번 부가 설명이죠)
단점
- 메모리 이슈(매번 노드를 분리하면서 많은 양의 데이터를 계속 저장함)
- 맵을 생성하는 과정에서 꽤 많은 시간이 소모됨
구현 영상
일단 구현하는게 쉽지만은 않았습니다. 원래 알고리즘은 전에 여러번 구현해보기도 해서 그런 것에는 문제가 없을 줄 알았는데… 이게 완벽히 파이썬처럼 작성하기도 하고, 다시 뭔가 oop도 따라하려고 하고 막 어찌저찌 스타일도 섞으면서 하게됐는데요.
일단 이번에 느낀 것은 Mojo와 Python은 진짜 전혀 다른 언어라는거죠..
일단 struct로 뭔가를 만들어서 List에 넣고 하려고해도. copyable, moveable을 무조건 넣어줘야 됐다는 것. 그리고 검사가 너무 깐깐합니다. 그래서 나중에 코드 보면서 트러블 슈팅할 때는 괜찮았어요. 오히려 이런 것에서 장점이 나오는 것 같아서 좋긴했는데..
이 코드가 복잡한 코드도 아니고 그냥 한번 작성하고 보여주기 코드였는데 뭔가 쓸데없는 곳에서 계속 걸리니까 그런 장점보다는 오히려 짜증이 나기도 하더라구요.
일단 ide가 없고, 자동 완성도 안됩니다. 현재 jetbrain에서 plugin이 있는데 구버전에다가… 성능이 안 좋아서 잘 못잡아요. 허구언날 빨간줄만 띄웁니다.
그래서 그냥 기능 다 끄고 했구요. 자동 들여쓰기만 키고서 작성했습니다.
그래서 시간이 오래걸린 것 같아요. 또 이번에 많은 것을 알아갑니다. Mojo에 대해서 많은 것을 알아가요… 어후..
또 로직에 문제가 없다고 생각했는데 네… 리스트 값이 변경이 안되고 주소 확인해 보니까 copy가 되더라구요? 그래서 오잉? 하고서 값을 reference로 받거나 아니면 그냥 리스트에 self.nodes[idx] 이거를 직접 사용하거나 이렇게 했어야 했다.
저는 그냥 var node = … 뺀 다음에 연산 다 끝나고 self.nodes[idx] = node로 처리를 했습니다. 이게 그 뻘짓 중에 그냥 고치기 쉬웠던 것들 중 하나구요..
하나하나 쓰기는 좀 그렇고 네.. 힘들었습니다. 그래도 보람이 있었고, 재미있었습니다. 이제 이 언어를 가지고 인공지능을 좀 해보려고 하는데.. 일단 다른 경험으로 IDE를 만들어보려고 합니다. 진짜 힘든 길이겠지만 뭐… 해야죠 저는 이 언어를 쓰고싶은데
네 여기까지 하소연이였구용.. 하튼 재미있었습니다.
구현 코드
제가 구현한 코드 로직의 순서도입니다. 깔끔하게 정리되는 사이트가 없더라구용.. 
또 스네이크로 작성해본 것도 좀 오랜만이네용!
from python import Python, PythonObject
import random
import time
struct Corridor(Copyable, Movable):
var start_x: Int
var start_y: Int
var end_y: Int
var end_x: Int
var is_vertical: Bool
fn __init__(mut self, start_x: Int, start_y: Int, end_x: Int, end_y: Int, is_vertical: Bool):
self.start_x = start_x
self.start_y = start_y
self.end_x = end_x
self.end_y = end_y
self.is_vertical = is_vertical
fn __copyinit__(mut self, other: Self):
self.start_x = other.start_x
self.start_y = other.start_y
self.end_x = other.end_x
self.end_y = other.end_y
self.is_vertical = other.is_vertical
fn __moveinit__(mut self, owned other: Self):
self.start_x = other.start_x
self.start_y = other.start_y
self.end_x = other.end_x
self.end_y = other.end_y
self.is_vertical = other.is_vertical
struct BSPNode(Copyable, Movable):
var x: Int
var y: Int
var width: Int
var height: Int
var min_size: Int
var split_vertical: Bool
var split_pos: Int
var is_split: Bool
var is_leaf: Bool
var has_room: Bool
var room_x: Int
var room_y: Int
var room_width: Int
var room_height: Int
var corridors: List[Corridor]
fn __init__(mut self, x: Int, y: Int, width: Int, height: Int, min_size: Int):
self.x = x
self.y = y
self.width = width
self.height = height
self.min_size = min_size
self.split_vertical = False
self.split_pos = 0
self.is_split = False
self.is_leaf = True
self.has_room = False
self.room_x = 0
self.room_y = 0
self.room_width = 0
self.room_height = 0
self.corridors = List[Corridor]()
fn __copyinit__(mut self, other: Self):
self.x = other.x
self.y = other.y
self.width = other.width
self.height = other.height
self.split_vertical = other.split_vertical
self.split_pos = other.split_pos
self.has_room = other.has_room
self.room_x = other.room_x
self.room_y = other.room_y
self.room_width = other.room_width
self.room_height = other.room_height
self.is_split = other.is_split
self.is_leaf = other.is_leaf
self.min_size = other.min_size
self.corridors = other.corridors
fn __moveinit__(mut self, owned other: Self):
self.x = other.x
self.y = other.y
self.width = other.width
self.height = other.height
self.split_vertical = other.split_vertical
self.split_pos = other.split_pos
self.has_room = other.has_room
self.room_x = other.room_x
self.room_y = other.room_y
self.room_width = other.room_width
self.room_height = other.room_height
self.is_split = other.is_split
self.is_leaf = other.is_leaf
self.min_size = other.min_size
self.corridors = other.corridors
fn can_split(self) -> Bool:
if self.is_split or not self.is_leaf:
return False
if self.width < self.min_size * 2 and self.height < self.min_size * 2:
return False
return True
fn split(mut self) -> Bool:
if not self.can_split():
return False
if self.width * 4 >= self.height * 5:
self.split_vertical = True
elif self.height * 4 >= self.width * 5:
self.split_vertical = False
else:
self.split_vertical = random.random_si64(0, 1)[0] == 1
if self.split_vertical:
self.split_pos = self.x + Int(random.random_si64(
self.width * 4 // 10,
self.width * 6 // 10
)[0])
else:
self.split_pos = self.y + Int(random.random_si64(
self.height * 4 // 10,
self.height * 6 // 10
)[0])
self.is_split = True
self.is_leaf = False
return True
fn create_room(mut self) -> Bool:
if not self.is_leaf or self.has_room:
return False
var padding = max(2, self.min_size // 4)
var min_room_size = self.min_size
var max_width = self.width - (padding * 2)
var max_height = self.height - (padding * 2)
var min_width = min(min_room_size, max_width)
var min_height = min(min_room_size, max_height)
if max_width < min_width or max_height < min_height:
return False
self.room_width = Int(random.random_si64(
max(min_width, max_width // 2),
max_width
)[0])
self.room_height = Int(random.random_si64(
max(min_height, max_height // 2),
max_height
)[0])
var available_x = self.width - self.room_width
var available_y = self.height - self.room_height
self.room_x = self.x + (available_x // 2)
self.room_y = self.y + (available_y // 2)
self.has_room = True
return True
fn get_room_center(self) -> Tuple[Int, Int]:
return (
self.room_x + self.room_width // 2,
self.room_y + self.room_height // 2
)
struct DungeonGenerator:
var nodes: List[BSPNode]
var stage: Int
var current_idx: Int
var min_room_size: Int
var split_count: Int
var max_splits: Int
var corridors: List[Corridor]
fn __init__(mut self, width: Int, height: Int, min_room_size: Int, max_splits: Int):
self.nodes = List[BSPNode]()
self.nodes.append(BSPNode(0, 0, width, height, min_room_size))
self.stage = 0
self.current_idx = 0
self.min_room_size = min_room_size
self.split_count = 0
self.max_splits = max_splits
self.corridors = List[Corridor]()
fn connect_rooms(mut self):
var leaf_nodes = List[BSPNode]()
for idx in range(len(self.nodes)):
var node = self.nodes[idx]
if node.is_leaf and node.has_room:
leaf_nodes.append(self.nodes[idx])
if len(leaf_nodes) < 2:
return
for i in range(len(leaf_nodes)):
for j in range(i + 1, len(leaf_nodes)):
var room1 = leaf_nodes[i]
var room2 = leaf_nodes[j]
var center1 = room1.get_room_center()
var center2 = room2.get_room_center()
if random.random_si64(0, 1)[0] == 0:
var mid_y = center2[1]
self.corridors.append(Corridor(
center1[0], center1[1],
center1[0], mid_y,
True
))
self.corridors.append(Corridor(
center1[0], mid_y,
center2[0], mid_y,
False
))
else:
var mid_x = center2[0]
self.corridors.append(Corridor(
center1[0], center1[1],
mid_x, center1[1],
False
))
self.corridors.append(Corridor(
mid_x, center1[1],
mid_x, center2[1],
True
))
fn step(mut self) -> Bool:
if self.stage == 0:
if self.split_count >= self.max_splits:
self.stage = 1
self.current_idx = 0
return True
if self.current_idx < len(self.nodes):
var node = self.nodes[self.current_idx]
if node.split():
if node.split_vertical:
self.nodes.append(BSPNode(
node.x, node.y,
node.split_pos - node.x, node.height,
self.min_room_size
))
self.nodes.append(BSPNode(
node.split_pos, node.y,
node.width - (node.split_pos - node.x), node.height,
self.min_room_size
))
else:
self.nodes.append(BSPNode(
node.x, node.y,
node.width, node.split_pos - node.y,
self.min_room_size
))
self.nodes.append(BSPNode(
node.x, node.split_pos,
node.width, node.height - (node.split_pos - node.y),
self.min_room_size
))
self.split_count += 1
self.nodes[self.current_idx] = node
self.current_idx += 1
return True
else:
self.current_idx = 0
return True
elif self.stage == 1:
if self.current_idx >= len(self.nodes):
self.stage = 2
self.current_idx = 0
return True
if self.nodes[self.current_idx].create_room():
print("Created room in node", self.current_idx)
self.current_idx += 1
return True
elif self.stage == 2:
if self.current_idx == 0:
self.connect_rooms()
self.current_idx += 1
return True
return False
return False
fn run_display(width: Int = 800, height: Int = 600, min_room_size: Int = 50, split_count: Int = 5) raises:
pygame = Python.import_module("pygame")
pygame.init()
var window = pygame.display.set_mode((width, height))
pygame.display.set_caption("Compy BSP")
var generator = DungeonGenerator(width, height, min_room_size, split_count)
var running = True
while running:
var event = pygame.event.poll()
if event.type == pygame.QUIT:
running = False
elif event.type == pygame.KEYDOWN:
if event.key == pygame.K_ESCAPE or event.key == pygame.K_q:
running = False
elif event.key == pygame.K_SPACE:
if not generator.step():
generator = DungeonGenerator(width, height, min_room_size, split_count)
window.fill((0, 0, 0))
for i in range(len(generator.corridors)):
var corridor = generator.corridors[i]
var start_x = corridor.start_x
var start_y = corridor.start_y
var end_x = corridor.end_x
var end_y = corridor.end_y
pygame.draw.line(
window,
(0, 0, 255),
(start_x, start_y),
(end_x, end_y),
3
)
for i in range(len(generator.nodes)):
var node = generator.nodes[i]
pygame.draw.rect(
window,
(255, 255, 255),
(node.x, node.y, node.width, node.height),
1
)
if node.is_split:
if node.split_vertical:
pygame.draw.line(
window,
(255, 0, 0),
(node.split_pos, node.y),
(node.split_pos, node.y + node.height),
2
)
else:
pygame.draw.line(
window,
(255, 0, 0),
(node.x, node.split_pos),
(node.x + node.width, node.split_pos),
2
)
if node.has_room and node.is_leaf:
pygame.draw.rect(
window,
(0, 255, 0),
(node.room_x, node.room_y, node.room_width, node.room_height),
0
)
var font = pygame.font.Font(None, 36)
var stage_text = String("")
if generator.stage == 0: stage_text = "Phase 1: Splitting (" + str(generator.split_count) + "/" + str(generator.max_splits) + ")"
elif generator.stage == 1: stage_text = "Phase 2: Creating Rooms"
else: stage_text = "Phase 3: Connecting Rooms"
var text = font.render(stage_text, True, (255, 255, 0))
var text_rect = text.get_rect()
text_rect.midtop = (width // 2, 10)
window.blit(text, text_rect)
var help_text = "Space: Next Step | ESC/Q: Quit"
var help_surface = font.render(help_text, True, (128, 128, 128))
var help_rect = help_surface.get_rect()
help_rect.midbottom = (width // 2, height - 10)
window.blit(help_surface, help_rect)
pygame.display.flip()
time.sleep(0.1)
pygame.quit()
fn main() raises:
run_display(800, 600, 50, 8)Unity로 확장해서 해커톤에 활용하기!
Reference
wiki
wiki 2
[Algorithm] BSP 알고리즘(맵 생성)
https://compy07.github.io/Blog/posts/algorithms/bsp/theory/