It’s now time to implement the physics simulation of our dungeon. We’re also going to draw on tile-map in real-time to visualize the dungeon building up.
We start by defining the _ready() function which randomizes the RandomNumberGenerator. That way, we get a different result each time we run the project. Then, it delegates the work to the _generate() function.
func _ready() -> void: _rng.randomize() _generate()
Let’s take a look at the _generate() function next.
# Places the rooms and starts the physics simulation. Once the simulation is done # ("rooms_placed" gets emitted), it continues by assigning tiles in the Level node. func _generate() -> void: # Generate `max_rooms` rooms and set them up for _i in range(max_rooms): var room := Room.instance() room.connect("sleeping_state_changed", self, "_on_Room_sleeping_state_changed") room.setup(_rng, level) rooms.add_child(room) _mean_room_size += room.size _mean_room_size /= rooms.get_child_count() # Wait for all rooms to be positioned in the game world. yield(self, "rooms_placed") rooms.queue_free() # Draws the tiles on the `level` tilemap. level.clear() for point in _data: level.set_cellv(point, 0)
As we mentioned before, we need to coordinate execution because the physics simulation will take time to stabilize. In the first part of the function, we instantiate the rooms and add them under the Room node to group them. We connect the sleeping_state_changed signal of each room to the _on_Room_sleeping_state_changed() function and set it up.
As we loop over range(max_rooms), we can accumulate the sum of all room sizes and calculate the mean size: _mean_room_size /= rooms.get_child_count().
If we were to freeze the game at this stage, we’d get the following picture.
All rooms are stacked in the center, and positioned randomly inside a circle. The Room class takes care of this positioning.
We wait for the rooms_placed signal to be emitted which means that our _data dictionary is available for processing. We then remove the Rooms node since we don’t need it anymore. The last lines draw tiles in the tilemap.
The _on_Room_sleeping_state_changed() function does most of the work. It’s called each time a room stabilizes and its mode changes to RigidBody2D.MODE_STATIC. Before covering it, let’s go over the functions on which it depends.
func _is_main_room(room: Room) -> bool: return room.size.x > _mean_room_size.x and room.size.y > _mean_room_size.y
The _is_main_room() function returns true if the room has a greater width and height than _mean_room_size.
The next function uses the room as an iterator. It loops over a room’s tile positions using a for loop and stores each offset in the _data dictionary.
# Adds room tile positions to `_data`. func _add_room(room: Room) -> void: for offset in room: _data[offset] = null
We’re left with _add_corridors() and _add_corridor().
# Adds both secondary room and corridor tile positions to `_data`. Secondary rooms are the ones # intersecting the corridors. func _add_corridors(): # Stores existing connections in its keys. var connected := {} # Checks if points are connected by a corridor. If not, adds a corridor. for point1_id in _path.get_points(): for point2_id in _path.get_point_connections(point1_id): var point1 := _path.get_point_position(point1_id) var point2 := _path.get_point_position(point2_id) if Vector2(point1_id, point2_id) in connected: continue point1 = level.world_to_map(point1) point2 = level.world_to_map(point2) _add_corridor(point1.x, point2.x, point1.y, Vector2.AXIS_X) _add_corridor(point1.y, point2.y, point2.x, Vector2.AXIS_Y) # Stores the connection between point 1 and 2. connected[Vector2(point1_id, point2_id)] = null connected[Vector2(point2_id, point1_id)] = null
Before the loop we define the connected dictionary. We use it to store the pairs of points connected by a corridor. Since the graph we use is bidirectional, we might end up going from point1 to point2 and from point2 to point1. To prevent this we define the connected dictionary.
For each point in the AStar2D graph, we get its connections with AStar2D.get_point_connections(), therefore we need the nested loop. Inside the loop, we get the positions of each pair of points and check to see if they’re connected by a corridor. If that’s the case, we then skip the rest of the code with continue. Otherwise, we run the rest of the loop which:
point1 and point2.We have one last function to look at before moving to _on_Room_sleeping_state_changed():
# Adds a specific corridor (defined by the input parameters) to `_data`. It also adds all # secondary rooms intersecting the corridor path. func _add_corridor(start: int, end: int, constant: int, axis: int) -> void: var t := min(start, end) while t <= max(start, end): var point := Vector2.ZERO match axis: Vector2.AXIS_X: point = Vector2(t, constant) Vector2.AXIS_Y: point = Vector2(constant, t) t += 1 for room in rooms.get_children(): if _is_main_room(room): continue var top_left: Vector2 = level.world_to_map(room.position - room.size / 2) var bottom_right: Vector2 = level.world_to_map(room.position + room.size / 2) if ( top_left.x <= point.x and point.x < bottom_right.x and top_left.y <= point.y and point.y < bottom_right.y ): _add_room(room) t = bottom_right[axis] _data[point] = null
This is similar to the function we saw in the first chapter, where we used Vector2.AXIS_X and Vector2.AXIS_Y to invert the parametrization of the line we need to traverse. Please refer to that chapter for details.
The rest of the code adds secondary rooms that intersect with the corridor while constructing it. The loop goes like this:
_is_main_room() returns false.top_left and bottom_right corners of the room.point, the current corridor position, falls within the rectangle of the room then call _add_room() and move t at the end of the room.Before we exit the outer while loop, we add point to the _data dictionary to save the corridor current position.
Now we’re ready to tackle _on_Room_sleeping_state_changed().
# Calld every time stabilizes (mode changes to RigidBody2D.MODE_STATIC). # # Once all rooms have stabilized it calcualtes a playable dungeon `_path` using the MST # algorithm. Based on the calculated `_path`, it populates `_data` with room and corridor tile # positions. # # It emits the "rooms_placed" signal when it finishes so we can begin the tileset placement. func _on_Room_sleeping_state_changed() -> void: _sleeping_rooms += 1 if _sleeping_rooms < max_rooms: return var main_rooms := [] var main_rooms_positions := [] for room in rooms.get_children(): if _is_main_room(room): main_rooms.push_back(room) main_rooms_positions.push_back(room.position) _path = Utils.mst(main_rooms_positions) for point1_id in _path.get_points(): for point2_id in _path.get_points(): if ( point1_id != point2_id and not _path.are_points_connected(point1_id, point2_id) and _rng.randf() < reconnection_factor ): _path.connect_points(point1_id, point2_id) for room in main_rooms: _add_room(room) _add_corridors() set_process(false) emit_signal("rooms_placed")
Each time a room changes mode to RigidBody2D.MODE_STATIC, we increase _sleeping_rooms by 1. If _sleeping_rooms < max_rooms is true, it means that there are still rooms that need to reach a stable position before moving on. So we return from the function without doing anything else if that happens. If the opposite is true and _sleeping_rooms >= max_rooms then the rest of the function gets executed.
We start by creating two empty arrays: main_rooms and main_rooms_positions. We loop over all the available rooms and if _is_main_room() returns true, then we store that room and its position in these arrays. We then calculate the minimum spanning tree (MST) graph using Utils.mst().
Before constructing the dungeon based on the MST graph, we restore a small fraction of extra graph connections. We do this to create cyclic connections so the player doesn’t have to always backtrack. The implementation goes over all the pairs of points in _path and if we:
point1_id != point2_id).not _path.are_points_connected(point1_id, point2_id)).reconnection_factor.Then we connect these points by an edge. Once we’re done with all of this we add only the main rooms that we previously saved and finally add the corridors. As you saw, when adding the corridors we also add extra secondary rooms along the way. So our dungeon will feature clusters of rooms along these corridors.
At the very end of the function we turn off processing and emit the rooms_placed signal so that _generate() continues with the rest of the code that visually constructs the dungeon from _data. You might be wondering why we turn of processing here as we haven’t implemented _process() yet. Read on to find out.
At this stage we don’t have any visual feedback during dungeon construction, unless we turn on Debug > Visible Collision Shapes. We can fix this by implementing _process() so that we assign tiles based on rooms data:
# This is for visual feedback. We just re-render the rooms every frame. func _process(delta: float) -> void: level.clear() for room in rooms.get_children(): for offset in room: level.set_cellv(offset, 0)
Every frame we start by clearing the level. Next, for each room we iterate over it using our custom iterator once again and setting the appropriate TileMap position.
And with this we finished this tutorial. We hope you had a great time following along and we wish you the best of luck in implementing your own variations!
Below you can find the MSTDungeon generator full script.
# Generates a dungeon using RigidBody2D physics and Minimum Spanning Trees (MST). # # The algorithm works like so: # # 1. Spawns and spreads collision shapes around the game world using the physics engine. # 2. Waits for the rooms to be in a more or less resting state. # 3. Selects some main rooms for the level based on the average room size. # 4. Creates a Minimum Spanning Tree graph that connects the rooms. # 5. Adds back some connections after calculating the MST so the player doesn't need to backtrack. extends Node2D # Emitted when all the rooms stabilized. signal rooms_placed const Room := preload("Room.tscn") # Maximum number of generated rooms. export var max_rooms := 60 # Controls the number of paths we add to the dungeon after generating it, # limiting player backtracking. export var reconnection_factor := 0.025 var _rng := RandomNumberGenerator.new() var _data := {} var _path: AStar2D = null var _sleeping_rooms := 0 var _mean_room_size := Vector2.ZERO onready var rooms: Node2D = $Rooms onready var level: TileMap = $Level func _ready() -> void: _rng.randomize() _generate() # Calld every time stabilizes (mode changes to RigidBody2D.MODE_STATIC). # # Once all rooms have stabilized it calcualtes a playable dungeon `_path` using the MST # algorithm. Based on the calculated `_path`, it populates `_data` with room and corridor tile # positions. # # It emits the "rooms_placed" signal when it finishes so we can begin the tileset placement. func _on_Room_sleeping_state_changed() -> void: _sleeping_rooms += 1 if _sleeping_rooms < max_rooms: return var main_rooms := [] var main_rooms_positions := [] for room in rooms.get_children(): if _is_main_room(room): main_rooms.push_back(room) main_rooms_positions.push_back(room.position) _path = Utils.mst(main_rooms_positions) for point1_id in _path.get_points(): for point2_id in _path.get_points(): if ( point1_id != point2_id and not _path.are_points_connected(point1_id, point2_id) and _rng.randf() < reconnection_factor ): _path.connect_points(point1_id, point2_id) for room in main_rooms: _add_room(room) _add_corridors() set_process(false) emit_signal("rooms_placed") # This is for visual feedback. We just re-render the rooms every frame. func _process(delta: float) -> void: level.clear() for room in rooms.get_children(): for offset in room: level.set_cellv(offset, 0) # Places the rooms and starts the physics simulation. Once the simulation is done # ("rooms_placed" gets emitted), it continues by assigning tiles in the Level node. func _generate() -> void: for _i in range(max_rooms): var room := Room.instance() room.connect("sleeping_state_changed", self, "_on_Room_sleeping_state_changed") room.setup(_rng, level) rooms.add_child(room) _mean_room_size += room.size _mean_room_size /= rooms.get_child_count() yield(self, "rooms_placed") rooms.queue_free() level.clear() for point in _data: level.set_cellv(point, 0) # Adds room tile positions to `_data`. func _add_room(room: Room) -> void: for offset in room: _data[offset] = null # Adds both secondary room and corridor tile positions to `_data`. Secondary rooms are the ones # intersecting the corridors. func _add_corridors(): var connected := {} for point1_id in _path.get_points(): for point2_id in _path.get_point_connections(point1_id): var point1 := _path.get_point_position(point1_id) var point2 := _path.get_point_position(point2_id) if Vector2(point1_id, point2_id) in connected: continue point1 = level.world_to_map(point1) point2 = level.world_to_map(point2) _add_corridor(point1.x, point2.x, point1.y, Vector2.AXIS_X) _add_corridor(point1.y, point2.y, point2.x, Vector2.AXIS_Y) connected[Vector2(point1_id, point2_id)] = null connected[Vector2(point2_id, point1_id)] = null # Adds a specific corridor (defined by the input parameters) to `_data`. It also adds all # secondary rooms intersecting the corridor path. func _add_corridor(start: int, end: int, constant: int, axis: int) -> void: var t := min(start, end) while t <= max(start, end): var point := Vector2.ZERO match axis: Vector2.AXIS_X: point = Vector2(t, constant) Vector2.AXIS_Y: point = Vector2(constant, t) t += 1 for room in rooms.get_children(): if _is_main_room(room): continue var top_left: Vector2 = level.world_to_map(room.position - room.size / 2) var bottom_right: Vector2 = level.world_to_map(room.position + room.size / 2) if ( top_left.x <= point.x and point.x < bottom_right.x and top_left.y <= point.y and point.y < bottom_right.y ): _add_room(room) t = bottom_right[axis] _data[point] = null func _is_main_room(room: Room) -> bool: return room.size.x > _mean_room_size.x and room.size.y > _mean_room_size.y