Procedural Dungeon Generation (Detect Room Intersection)

Help Physics
, ,
1

Godot Version

v4.3.stable.official [77dcf97d8]

Question

i wanted to make a dungeon generation where rooms get connected via Entrances which are marked with 3D Nodes.

The Generation itself, the alignment and position work fine.

But i cant detect if 2 or more rooms are intersecting with eachother, every room has a Area3D-Box

Here is the main code:


# Constants
const Room_Scenes = [ 
	{ "Length": 10, "Room": preload("res://Dungeons/Tier1/TrappedCorridor.tscn") },
	{ "Length": 10, "Room": preload("res://Dungeons/Tier1/Four_Loot_Room.tscn") },
	#{ "Length": 10, "Room": preload("res://Dungeons/Tier1/Dinning_Room.tscn") },
	#{ "Length": 18, "Room": preload("res://Dungeons/Tier1/RiddleRoom/Riddle_Room.tscn") },
]

# Variables
var rooms = [] 
const Max_Length = 5

@onready var dungeon_generated : bool = false
func _physics_process(delta):
	if not dungeon_generated:
		dungeon_generated = true
		rooms.append($".")
		generate_neighbor_rooms(rooms[0], 1)

func reload_dungeon():
	var main = rooms.pop_at(0)
	for room in rooms:
		room.queue_free()
	rooms.clear()
	rooms.append(main)
	generate_neighbor_rooms($".", 1)

func _unhandled_input(event):
	if Input.is_action_just_pressed("Debug"):
		reload_dungeon()

# Function to generate the dungeon
func generate_neighbor_rooms(room, length):
	var entrances = get_entrances(room)
	var new_rooms = []
	var triedrooms = []
	var newroom_instance = null
	var alignment_succeeded = false
	
	for i in range(entrances.size()):
		if entrances.size() == 0:
			break
		var random_index = randi() % entrances.size()
		var entrance = entrances[random_index]
		triedrooms.clear()
		alignment_succeeded = false
		
		while(triedrooms.size() < Room_Scenes.size() and !alignment_succeeded):
			var newpick = pick_room(length, triedrooms)
			if(newpick == null):
				print("no Room found")
				break
			
			var newroom = newpick.Room
			var instance = newroom.duplicate()
			newroom_instance = instance.instantiate()
			add_child(newroom_instance)
			
			# Ensure room is fully initialized
			await get_tree().physics_frame
			print("Room created")
			alignment_succeeded = false
			
			var newroom_entrances = get_entrances(newroom_instance)
			for x in range(newroom_entrances.size()):
				if entrances.size() == 0:
					break
				var random_index2 = randi() % newroom_entrances.size()
				var newroom_entrance = newroom_entrances[random_index2]
				newroom_entrances.erase(newroom_entrance)
				
				print("Entrance Nr. ", random_index2)
				var erg = await align_room(entrance, newroom_entrance, newroom_instance)
				if erg:
					alignment_succeeded = true
					# Delay deletion to ensure physics update
					await get_tree().physics_frame
					await get_tree().process_frame
					await get_tree().physics_frame
					newroom_entrance.set_meta("Marked_for_Deletion", true)
					entrances.erase(entrance)
					entrance.set_meta("Marked_for_Deletion", true)
					await get_tree().physics_frame
					await get_tree().process_frame
					await get_tree().physics_frame
					
					rooms.append(newroom_instance)
					new_rooms.append(newroom_instance)
					for roomloop in rooms:
						roomloop.is_intersecting = false  # Reset here
					print("new_Room appended")
					break
				await get_tree().physics_frame
				await get_tree().process_frame
				await get_tree().physics_frame
				for roomloop in rooms:
					roomloop.is_intersecting = false
			if (!alignment_succeeded):   
				newroom_instance.queue_free()
				for roomloop in rooms:
					roomloop.is_intersecting = false
				await get_tree().physics_frame
				await get_tree().process_frame
				await get_tree().physics_frame
				for search in Room_Scenes:
					if search["Room"] == newroom:
						triedrooms.append(search)
						print("tried_Room appended")
	
	for roomloop in rooms:
		roomloop.is_intersecting = false
	
	await get_tree().physics_frame
	await get_tree().process_frame
	await get_tree().physics_frame
	
	if length <= Max_Length:
		for new_room in new_rooms:
			await generate_neighbor_rooms(new_room, length + 1)

func pick_room(length: int, filter: Array):
	return Room_Scenes.filter(func(room): return !filter.has(room.Room) and room.Length >= length).pick_random()

# Function to get a list of entrances from a room
func get_entrances(room):
	var entrances = []
	for child in room.get_children():
		if child is Node3D and child.is_in_group("Entrance") and child.has_meta("Marked_for_Deletion") and child.get_meta("Marked_for_Deletion") == false:
			entrances.append(child)
	return entrances

# Function to get a random entrance from a room, excluding a specified entrance
func get_random_entrance(room):
	var entrances = get_entrances(room)
	if entrances.size() > 0:
		return entrances[randi() % entrances.size()]
	return null

# Function to align the exits of the previous room with the entrances of the new room
func align_room(previous_exit, new_room_entrance, new_room) -> bool:
	# Get the global forward vectors (-Z is forward)
	var node_forward = -new_room_entrance.global_transform.basis.z
	var destination_forward = -previous_exit.global_transform.basis.z
	var opposite_direction = -destination_forward
	var rotation_axis = node_forward.cross(opposite_direction).normalized()
	var rotation_angle = node_forward.angle_to(opposite_direction)
	new_room.rotate_object_local(rotation_axis, rotation_angle)
	
	var node_global_transform = new_room_entrance.global_transform
	var destination_global_transform = previous_exit.global_transform
	var offset = destination_global_transform.origin - node_global_transform.origin
	new_room.global_transform.origin += offset
	
	# Wait for multiple frames to ensure physics updates
	print("Align started")
	await get_tree().physics_frame
	await get_tree().process_frame
	await get_tree().physics_frame
	print("Align finished")
	
	for room in rooms: 
		if room.is_intersecting:
			return false
	return true

# Helper function to calculate the azimuth (angle in degrees) from a direction vector
func azimuth(direction: Vector3) -> float:
	return rad_to_deg(atan2(direction.x, direction.z))

every Room has a script with that event:

@onready var is_intersecting : bool = false
func _on_bounding_box_area_entered(area):
	if area.is_in_group("Dungeon_Generation"):
		print("FourLootRoom Clipping detected")
		is_intersecting = true

I dont know if the Area3D has trouble detecting the intersection while the dungeon is generatin, i read that the physics engine needs to wait a frame to calculate it correctly, thats why i put a bunch of:

await get_tree().physics_frame
await get_tree().process_frame
await get_tree().physics_frame

there cause i dont know what to do anymore

1 Like
2

Did you ever find a solution to this?
Iā€™m trying to do something similar to yours, but if I add
await get_tree().physics_frame
the game never starts, just perpetualy loading

3

better rely on abstract PackedVector3Array where every vector represents a room position on grid, and check before generate next

#generating map code goes here
if room:Vector3 not in room_array:
	room_array.append(room)
#so if room is exist on given grid pos, it won't be added

then instantiate room scene on tile with offset

@export var room_scene:PackedScene
var level:int=0
var offset:=Vector3(200, 200, 200*level)
for room in room_array:
	var room_node:=room_scene.new()
	room_node.global_position=room*offset
	map.add_child(room_node)

and no extra await will be needed.

4

You can always just check if the overlap by checking their bounds yourself:

5

My code mostly stayed the same but for the intersection im using a StaticBody3D with a Box CollisionShape3D. It works rlly well with PhysicsShapeQueryParameters3D.

Function to align the exits of the previous room with the entrances of the new room

func align_room(previous_exit, new_room_entrance, new_room) -> bool:
# Get the global forward vectors (-Z is forward)
var node_forward = -new_room_entrance.global_transform.basis.z
var destination_forward = -previous_exit.global_transform.basis.z
var opposite_direction = -destination_forward
var rotation_axis = node_forward.cross(opposite_direction).normalized()
var rotation_angle = node_forward.angle_to(opposite_direction)

if rotation_axis.length() > 0:
	new_room.rotate_object_local(rotation_axis, rotation_angle)

var node_global_transform = new_room_entrance.global_transform
var destination_global_transform = previous_exit.global_transform
var offset = destination_global_transform.origin - node_global_transform.origin
new_room.global_transform.origin += offset

# Wait for multiple frames to ensure physics updates
#print("Align started")
await get_tree().physics_frame
#print("Align finished")

return check_intersections(new_room)

Function to check if rooms are intersecting

func check_intersections(new_scene: Node3D) -> bool:
var new_collision_object = new_scene.get_node("RoomShape")
for scene in DungeonManager.Rooms:
	var collision_object = scene.get_node("RoomShape")
	# Only check for collisions if they are on the same layer/mask
	if collision_object is CollisionObject3D and new_collision_object is CollisionObject3D:
		if (new_collision_object.collision_layer & (1 << 31)) != 0:
			var space_state = new_collision_object.get_world_3d().direct_space_state
			var shape1 = collision_object.get_child(0) as CollisionShape3D
			
			# Perform the collision check
			var shape_query_params = PhysicsShapeQueryParameters3D.new()
			shape_query_params.shape = shape1.shape
			shape_query_params.transform = collision_object.global_transform
			shape_query_params.collision_mask = new_collision_object.collision_layer  # Only collide with the layers for room boxes
			var result = space_state.intersect_shape(shape_query_params, 32)
			
			# Debugging information
			#print("Number of intersections: ", result.size())
			
			for collision in result:
				if collision.collider != collision_object and collision.collider == new_collision_object:
					return false
return true