1 files changed, 78 insertions, 0 deletions
diff --git a/scripts/bsp_level_generator.gd b/scripts/bsp_level_generator.gd
new file mode 100644
index 0000000..af34e0b
--- /dev/null
+++ b/scripts/bsp_level_generator.gd
@@ -0,0 +1,78 @@
+extends Node2D
+
+@export var width: int = 40
+@export var height: int = 40
+@export var min_dim: int = 5
+
+var min_room_size: int = min_dim * min_dim
+
+var rects: Array[Vector4i] = []
+
+class BSPNode:
+	var min_dims: Vector2i
+	var max_dims: Vector2i
+	var left: BSPNode
+	var right: BSPNode
+	
+	func _init(p_min_dims: Vector2i, p_max_dims: Vector2i, p_left: BSPNode, p_right: BSPNode):
+		min_dims = p_min_dims
+		max_dims = p_max_dims
+		left = p_left
+		right = p_right
+
+func generate_level(axis: int, min_space: Vector2i, max_space: Vector2i, depth: int = 0) -> BSPNode:
+	var dims = max_space - min_space
+	if dims[axis] / 2 < min_dim:
+		#rects.append(Vector4i(min_space.x, min_space.y, max_space.x, max_space.y))
+		return null
+	
+	var new_axis = (axis + 1) % 2
+	# 10% we stop here and just create a big room
+	if (depth > 2 and randi_range(0, 9) == 0) \
+	or dims.x * dims.y <= min_dim * min_dim \
+	or dims[new_axis] / 2 < min_dim:
+		rects.append(Vector4i(min_space.x, min_space.y, max_space.x, max_space.y))
+		return BSPNode.new(min_space, max_space, null, null)
+		
+	# Calculate min and max ranges so that a split 
+	# doesn't create a room that violates min dimensions
+	var min_value = min_space[axis] + min_dim
+	var max_value = max_space[axis] - min_dim
+	var split = randi_range(min_value, max_value)
+	print("Spliting axis ", axis, " at ", split)
+	
+	var left_min_space = min_space
+	var left_max_space = max_space
+	left_max_space[axis] = split
+	var left = generate_level(new_axis, left_min_space, left_max_space, depth + 1)
+	
+	var right_min_space = min_space
+	right_min_space[axis] = split
+	var right_max_space = max_space
+	var right = generate_level(new_axis, right_min_space, right_max_space, depth + 1)
+	
+	assert((left == null and right == null) or (left != null and right != null))
+	
+	if left == null and right == null:
+		rects.append(Vector4i(min_space.x, min_space.y, max_space.x, max_space.y))
+	
+	return BSPNode.new(min_space, max_space, left, right)
+
+func _ready() -> void:
+	var starting_axis = randi_range(0, 1)
+	var min_space = Vector2i(0, 0)
+	var max_space = Vector2i(width, height)
+	var map = generate_level(starting_axis, min_space, max_space)
+	
+func _draw():
+	var mult = 1
+	for rect in rects:
+		var pos1 = 5*Vector2i(rect.x, rect.y)
+		var pos2 = 5*Vector2i(rect.z, rect.w)
+		var dims = pos2 - pos1
+		draw_rect(Rect2(pos1, dims), mult*Color(0.01, 0.01, 0.01))
+		draw_line(pos1, Vector2i(pos1.x, pos2.y), Color(0, 1, 0))
+		draw_line(Vector2i(pos1.x, pos2.y), pos2, Color(0, 1, 0))
+		draw_line(pos2, Vector2i(pos2.x, pos1.y), Color(0, 1, 0))
+		draw_line(Vector2i(pos2.x, pos1.y), pos1, Color(0, 1, 0))
+		mult += 2