path: root/scripts/bsp_level_generator.gd

extends Node3D

@export_category("Level Generator")
@export var width: int = 40
@export var height: int = 40
@export var min_dim: int = 5

@export_category("Geometry Generator")
## Geometry generation config
@export var wall_thickness: float = 1

var wall_inst = preload("res://models/wall.blend")
var locker_inst = preload("res://prefabs/locker.tscn")
var level_geo: Node3D

enum Direction {LEFT, RIGHT}

signal grid_generated(grid: Array[Tile], p_grid_width: int, p_grid_height: int)

var min_room_size: int = min_dim * min_dim

var grid_width = width + 1
var grid_height = height + 1

var rooms: Array[Rect2i] = []

class BSPNode:
	var axis: int
	var min_dims: Vector2i
	var max_dims: Vector2i
	var left: BSPNode
	var right: BSPNode
	
	func _init(p_axis: int, p_min_dims: Vector2i, p_max_dims: Vector2i, p_left: BSPNode, p_right: BSPNode):
		axis = p_axis
		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
	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:
		return BSPNode.new(new_axis, 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)
	
	return BSPNode.new(axis, min_space, max_space, left, right)
	
func is_leaf(node: BSPNode) -> bool:
	return node.left == null and node.right == null
	
func check_door(grid: Array[Tile.Tile], axis: int, door_pos: Vector2i) -> bool:
	var room_left = door_pos
	room_left[axis] -= 1
	
	var room_right = door_pos
	room_right[axis] += 1
	
	if door_pos.x >= grid_width or door_pos.y >= grid_height:
		return false
	if room_left.x >= grid_width or room_left.y >= grid_height:
		return false
	if room_right.x >= grid_width or room_right.y >= grid_height:
		return false
	
	# Check if there are two spaces to connect
	# And ensure no door already exists in the space
	return grid[room_left.y * grid_width + room_left.x] == Tile.Tile.FLOOR \
	and grid[room_right.y * grid_width + room_right.x] == Tile.Tile.FLOOR \
	and grid[door_pos.y * grid_width + door_pos.x] == Tile.Tile.WALL

func generate_grid(map: BSPNode, grid: Array[Tile.Tile]) -> void:
	if is_leaf(map):
		for y in range(map.min_dims.y, map.max_dims.y - 1):
			for x in range(map.min_dims.x, map.max_dims.x - 1):
				grid[(y+1) * grid_width + (x+1)] = Tile.Tile.FLOOR
		
		# TODO double check room dimensions are correct here
		var room = Rect2i(map.min_dims + Vector2i.ONE, map.max_dims - map.min_dims)
		rooms.append(room)
	else:
		generate_grid(map.left, grid)
		generate_grid(map.right, grid)
		
		# Look for space on dividing wall to place door
		var other_axis = (map.axis + 1) % 2
		var split_axis = map.left.max_dims[map.axis]
		var have_door = false
		var tries = 0
		
		while not have_door:
			var test_door = randi_range(map.min_dims[other_axis], map.max_dims[other_axis] - 1)
			var door_pos = Vector2i.ZERO
			door_pos[map.axis] = split_axis
			door_pos[other_axis] = test_door + 1
			var door_pos2 = door_pos
			door_pos2[other_axis] += 1
			
			if check_door(grid, map.axis, door_pos) and check_door(grid, map.axis, door_pos2):
				have_door = true
				
				# Place grid for mesh
				grid[door_pos.y * grid_width + door_pos.x] = Tile.Tile.DOOR
				grid[door_pos2.y * grid_width + door_pos2.x] = Tile.Tile.DOOR
				#door_pos[map.axis] -= 1
				#grid[door_pos.y * grid_width + door_pos.x] = Tile.Tile.FLOOR

			tries += 1
			if tries > 1000:
				print("Took too many attempts to generate a door")
				get_tree().quit()
				return
				
func get_tile(grid: Array[Tile.Tile], pos: Vector2i) -> Tile.Tile:
	return grid[pos.y * grid_width + pos.x]
	
func place_lockers(grid: Array[Tile.Tile]) -> void:
	for room in rooms:
		var num_lockers = randi_range(0, 2)
		print("Generating ", num_lockers, "Lockers")
		for i in range(num_lockers):
			var found = false
			while not found:
				var pos = Vector2i(randi_range(room.position.x, room.end.x - 1), randi_range(room.position.y, room.end.y - 1))
				if grid[pos.y * grid_width + pos.x] == Tile.Tile.FLOOR \
				and (get_tile(grid, pos + Vector2i(1, 0)) == Tile.Tile.WALL \
				or get_tile(grid, pos + Vector2i(-1, 0)) == Tile.Tile.WALL \
				or get_tile(grid, pos + Vector2i(0, 1)) == Tile.Tile.WALL \
				or get_tile(grid, pos + Vector2i(0, -1)) == Tile.Tile.WALL) \
				and get_tile(grid, pos + Vector2i(1, 0)) != Tile.Tile.DOOR \
				and get_tile(grid, pos + Vector2i(-1, 0)) != Tile.Tile.DOOR \
				and get_tile(grid, pos + Vector2i(0, 1)) != Tile.Tile.DOOR \
				and get_tile(grid, pos + Vector2i(0, -1)) != Tile.Tile.DOOR:
					grid[pos.y * grid_width + pos.x] = Tile.Tile.LOCKER
					found = true
					
func place_player(grid: Array[Tile.Tile]) -> Rect2i:
	var player_room: Rect2i = rooms.pick_random()
	var player_pos = Vector2i(player_room.position.x + player_room.size.x / 2, player_room.position.y + player_room.size.y / 2)
	
	grid[player_pos.y * grid_width + player_pos.x] = Tile.Tile.PLAYER
	return player_room

func place_enemies(grid: Array[Tile.Tile], player_room: Rect2i) -> void:
	var num_enemies = randi_range(4, 10)

	for i in range(num_enemies):
		var found_pos = false
		while not found_pos:
			var room: Rect2i = rooms.pick_random()
			if room == player_room:
				continue
				
			var pos = Vector2i(randi_range(room.position.x, room.end.x - 1), randi_range(room.position.y, room.end.y - 1))
			if grid[pos.y * grid_width + pos.x] == Tile.Tile.FLOOR:
				grid[pos.y * grid_width + pos.x] = Tile.Tile.ENEMY
				found_pos = true

func place_exit(grid: Array[Tile.Tile], player_room: Rect2i) -> void:
	var found_pos = false
	
	while not found_pos:
		var room: Rect2i = rooms.pick_random()
		if room == player_room:
			continue
		
		var pos = Vector2i(randi_range(room.position.x, room.end.x - 1), randi_range(room.position.y, room.end.y - 1))
		var left = pos + Vector2i.LEFT
		var right = pos + Vector2i.RIGHT
		var up = pos + Vector2i.UP
		var down = pos + Vector2i.DOWN
		if grid[pos.y * grid_width + pos.x] == Tile.Tile.FLOOR \
		and grid[left.y * grid_width + left.x] == Tile.Tile.FLOOR \
		and grid[right.y * grid_width + right.x] == Tile.Tile.FLOOR \
		and grid[up.y * grid_width + up.x] == Tile.Tile.FLOOR \
		and grid[down.y * grid_width + down.x] == Tile.Tile.FLOOR:
			grid[pos.y * grid_width + pos.x] = Tile.Tile.PORTAL
			found_pos = true

func populate_grid(grid: Array[Tile.Tile]) -> void:
	place_lockers(grid)
	var player_room = place_player(grid)
	place_exit(grid, player_room)
	place_enemies(grid, player_room)

func generate_plane(array: Array, pos: Vector3, dim: Array[Vector3], normal: Vector3) -> void:
	var index = len(array[Mesh.ARRAY_VERTEX])
	array[Mesh.ARRAY_VERTEX].append(wall_thickness*pos)
	array[Mesh.ARRAY_VERTEX].append(wall_thickness*(pos+dim[0]))
	array[Mesh.ARRAY_VERTEX].append(wall_thickness*(pos+dim[0]+dim[1]))
	array[Mesh.ARRAY_VERTEX].append(wall_thickness*(pos+dim[1]))
	
	array[Mesh.ARRAY_NORMAL].append(normal)
	array[Mesh.ARRAY_NORMAL].append(normal)
	array[Mesh.ARRAY_NORMAL].append(normal)
	array[Mesh.ARRAY_NORMAL].append(normal)
	
	array[Mesh.ARRAY_INDEX].append(index + 0)
	array[Mesh.ARRAY_INDEX].append(index + 1)
	array[Mesh.ARRAY_INDEX].append(index + 2)
	array[Mesh.ARRAY_INDEX].append(index + 0)
	array[Mesh.ARRAY_INDEX].append(index + 2)
	array[Mesh.ARRAY_INDEX].append(index + 3)
				
func generate_geo(grid: Array[Tile.Tile], array: Array) -> void:
	for y in range(grid_height):
		for x in range(grid_width):
			var tile = grid[y * grid_width + x]
			
			if tile == Tile.Tile.WALL:
				generate_plane(array, Vector3(x, 2, y), [Vector3(0, 0, 1), Vector3(0, -2, 0)], Vector3.LEFT)
				generate_plane(array, Vector3(x, 2, y+1), [Vector3(1, 0, 0), Vector3(0, -2, 0)], Vector3.BACK)
				generate_plane(array, Vector3(x+1, 2, y+1), [Vector3(0, 0, -1), Vector3(0, -2, 0)], Vector3.RIGHT)
				generate_plane(array, Vector3(x+1, 2, y), [Vector3(-1, 0, 0), Vector3(0, -2, 0)], Vector3.FORWARD)
				var wall: Node3D = level_geo.get_node("./Wall").duplicate()
				wall.position = Vector3(x, 0, y)
				add_child(wall)
			else:
				generate_plane(array, Vector3(x, 0, y), [Vector3(1, 0, 0), Vector3(0, 0, 1)], Vector3.UP)
				var floor_tile: Node3D = level_geo.get_node("./Floor").duplicate()
				floor_tile.position = Vector3(x, 0, y)
				add_child(floor_tile)
				
				var ciel_tile: Node3D = level_geo.get_node("./Floor").duplicate()
				ciel_tile.rotate_z(deg_to_rad(180))
				ciel_tile.position = Vector3(x+1, 2, y)
				add_child(ciel_tile)
				
			if tile == Tile.Tile.LOCKER:
				var locker: Node3D = locker_inst.instantiate()
				locker.position = Vector3(x, 0, y)
				add_child(locker)

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)
	var grid: Array[Tile.Tile] = []
	grid.resize(grid_width * grid_height)
	grid.fill(Tile.Tile.WALL)
	
	var surface_array = []
	surface_array.resize(Mesh.ARRAY_MAX)
	
	surface_array[Mesh.ARRAY_VERTEX] = PackedVector3Array()
	surface_array[Mesh.ARRAY_INDEX] = PackedInt32Array()
	surface_array[Mesh.ARRAY_NORMAL] = PackedVector3Array()
	
	generate_grid(map, grid)
	populate_grid(grid)
	grid_generated.emit(grid, grid_width, grid_height)
	level_geo = wall_inst.instantiate() 
	generate_geo(grid, surface_array)
	
	var mesh = ArrayMesh.new()
	mesh.add_surface_from_arrays(Mesh.PRIMITIVE_TRIANGLES, surface_array)
	var tri_mesh = mesh.create_trimesh_shape()
	$NavigationRegion3D/StaticBody3D/CollisionShape3D.shape = tri_mesh
	#$NavigationRegion3D.navigation_mesh = NavigationMesh.new()
	#$NavigationRegion3D.navigation_mesh.radius
	$NavigationRegion3D.bake_navigation_mesh(false)