Yet Another Roguelike Tutorial, Part 3

Part 3: Generating a Dungeon

This is the next part to https://selinadev.github.io/06-rogueliketutorial-02/. In this part we will handle dungeon generation. We will write a procedural dungeon generator that will give us a new dungeon each time. The algorithm we will use is relatively simple, we will place rooms in a way that they don’t overlap, then connect each room to the previous with an L-shaped tunnel. We can think about it like starting with solid stone and carving these structures out of it. So to start off, we go into map_data.gd and modify the _setup_tiles() function:

func _setup_tiles() -> void:
	tiles = []
	for y in height:
		for x in width:
			var tile_position := Vector2i(x, y)
			var tile := Tile.new(tile_position, tile_types.wall)
			tiles.append(tile)

We changed two things here. First, we removed the loop at the end that created the little section of wall in the previous part. Second, we changed the tile type we’re filling the map with in the beginning to tile_types.wall. Now the whole map will start off as a solid chunk of wall.

If you’re following the original tutorial in parallel or are familiar with it, you will notice that that tutorial introduces a class for RectangularRooms at this point. We won’t need it, as we can use Godot’s builtin Rect2i for that job. It works just as the rectangular room does. The only thing I need to explain in that context is the use of Rect2i.grow(-1) that you’ll occasionally see in this part. This is equivalent to the RectangularRoom.inner() from the original tutorial. It gives us the room shrunk by 1. That way the dimensions of the room itself give us the coordinates of the walls surrounding the room. If two rooms directly border each other we won’t get any weird holes, but get a full wall around each room (minus the tunnels that run between or across).

Now for the dungeon generator. It will be called directly by the Map. In Godot there are two approaches for a dedicated helper class like this. We can either have it as a plain Node attached to the Map, or we can have it as a non-node variable held by the Map. In a lot of cases these are a matter of preference. Often having it as an actual node in the scene tree serves only the purpose of showing us the relationship more clearly in the editor. One reason to definitely choose the Node route is if you have exported configuration variables, like we have. We will have all the configuration for our dungeon generator as exported variables of the dungeon generator node, so we easily can access them in the editor.

To start with the dungeon generator create a new Node (a plain node, no 2D or 3D) as child of Map and rename it to DungeonGenerator. Attach a new script to it which will be saved at res://src/Map/dungeon_generator.gd. Let’s go through it chunk by chunk. Here’s the top of the script:

class_name DungeonGenerator
extends Node

@export_category("Map Dimensions")
@export var map_width: int = 80
@export var map_height: int = 45

var _rng := RandomNumberGenerator.new()


func _ready() -> void:
	_rng.randomize()

As mentioned, we export the configuration variables. These variables, map_width and map_height are the same as we have defined in the previous part in the map.gd script. We won’t need them there anymore, so you can remove them from the map script. We want procedural generation, so we also need a random number generator, which we store in _rng, and in the ready function we call randomize() on it, just so we get a different dungeon each time we run the game.

I mentioned that we will carve out the dungeon. As we will do a lot of carving, and we’ll be doing so in loops that give us the coordinates separately, we’ll start with the following function:

func _carve_tile(dungeon: MapData, x: int, y: int) -> void:
		var tile_position = Vector2i(x, y)
		var tile: Tile = dungeon.get_tile(tile_position)
		tile.set_tile_type(dungeon.tile_types.floor)

The first thing you might notice here is the C-style programming I’m doing here. We could have the map we are creating as a variable stored in the dungeon generator node. That would work and nothing explicitly forbids it, and it would mean all the functions could directly access it. However, I felt that the dungeon which will become the map_data held by the map should belong to the Map node, which is why I decided that I want to use this style where I simply pass the object we want to manipulate, dungeon in this case, to every function that has to work on it. You will see more of this with the other functions in this class.

In the function itself we get the position as a Vector2i, then we get the corresponding tile at that position from the dungeon. And lastly, we set that tile to dungeon.tile_types.floor.

Now that we can carve individual tiles we want a way to carve whole rooms into the map:

func _carve_room(dungeon: MapData, room: Rect2i) -> void:
	var inner: Rect2i = room.grow(-1)
	for y in range(inner.position.y, inner.end.y + 1):
		for x in range(inner.position.x, inner.end.x + 1):
			_carve_tile(dungeon, x, y)

Apart from the dungeon we also pass the room we want to carve out. I mentioned above that the coordinates actually describe the walls of the room, so what we want to carve out is the inner area, which we get by shrinking the room by 1 (or growing it by -1). We then loop from the start of the rows to the end of the rows, i.e., from inner.position.y to inner.end.y + 1 (we need to add 1 as the end of range() is exclusive). We do the same with all the columns, thereby visiting all tiles. And then we use the _carve_tile() function described above to carve out each individual tile in the inner area of the room. By now we are ready for a simple version of the generator:

func generate_dungeon() -> MapData:
    var dungeon := MapData.new(map_width, map_height)

    var room_1 := Rect2i(20, 15, 10, 15)
    var room_2 := Rect2i(35, 15, 10, 15)

    _carve_room(dungeon, room_1)
    _carve_room(dungeon, room_2)

    return dungeon

We simply create a new MapData object. For testing we create two rooms, and carve them out. At the end of the function we return out dungeon. This means we can now request new dungeons from the DungeonGenerator, so let’s modify map.gd to do just that:

@onready var dungeon_generator: DungeonGenerator = $DungeonGenerator

func _ready() -> void:
	map_data = dungeon_generator.generate_dungeon()
	_place_tiles()

If you haven’t already, remove the exported map_width and map_height variables. Then, we now export a reference to our dungeon_generator. In the _ready() function we now simply get a new map_data from the dungeon_generator and then call _place_tiles(), making the generated dungeon actually drawable.

And that’s the most basic dungeon generator. You should be able to run the project at this point, and see two areas of floor (our two rooms) surrounded by wall. As we don’t handle the player position very gracefully at the moment, depending on what you have configured as window size for the game window, the player might be inside or outside one of the rooms. If you’re inside, have a little walk around, and you see that as we configured in the last part we can still walk over floor, but not into wall. You can’t get into the other room though, and we need a way to connect rooms anyway, so let’s do that now.

Back in the dungeon_generator.gd we will create three new functions. Here’s the first one:

func _tunnel_horizontal(dungeon: MapData, y: int, x_start: int, x_end: int) -> void:
	var x_min: int = mini(x_start, x_end)
	var x_max: int = maxi(x_start, x_end)
	for x in range(x_min, x_max + 1):
		_carve_tile(dungeon, x, y)

We get the dungeon, the y variable that remains constant (i.e., y will be the same throughout), and the start and end positions of x. The way we will use this we won’t know whether the tunnel will go from the left to the right or from the right to the left. That means x_start might be bigger than x_end in some cases, which could cause issues in the range() function. Therefore we first sort them by calculating x_min and x_max. These are the same coordinates, they just ensure that we always go from the left to the right when tunneling. We can plug them into the range to loop over all the x coordinates of the tunnel and carve them out. Note that we again have to add +1 to the end of the range so we won’t leave out the last tile of that tunnel. Next add another function:

func _tunnel_vertical(dungeon: MapData, x: int, y_start: int, y_end: int) -> void:
	var y_min: int = mini(y_start, y_end)
	var y_max: int = maxi(y_start, y_end)
	for y in range(y_min, y_max + 1):
		_carve_tile(dungeon, x, y)

This function follows the same logic, it just works vertically instead of horizontally. Now that we can tunnel both horizontally and vertically we can tackle creating L-shaped tunnels:

func _tunnel_between(dungeon: MapData, start: Vector2i, end: Vector2i) -> void:
	if _rng.randf() < 0.5:
		_tunnel_horizontal(dungeon, start.y, start.x, end.x)
		_tunnel_vertical(dungeon, end.x, start.y, end.y)
	else:
		_tunnel_vertical(dungeon, start.x, start.y, end.y)
		_tunnel_horizontal(dungeon, end.y, start.x, end.x)

We take the dungeon, as well as a start coordinate and an end coordinate. The L could go both ways between those two points. From the start we could either tunnel horizontally first until we are above or below the end point, and then tunnel vertically to the end point. Or we could tunnel vertically first, until we are at the same height at the end point, then tunnel horizontally to it. We want both versions in our tunnel, so we essentially let our random number generator flip a coin by using if _rng.randf() < 0.5. In 50% of cases we will do the first version, in the other 50% the other one. Let’s use this to update the dungeon generation to create a tunnel between the two rooms. Add the following line to the generate_dungeon() function.

func generate_dungeon() -> MapData:
    var dungeon := MapData.new(map_width, map_height)

    var room_1 := Rect2i(20, 15, 10, 15)
    var room_2 := Rect2i(35, 15, 10, 15)

    _carve_room(dungeon, room_1)
    _carve_room(dungeon, room_2)

	_tunnel_between(dungeon, room_1.get_center(), room_2.get_center())

    return dungeon

We now create a tunnel from the center of one room to the center of the other room. This won’t affect the tiles that are already carved out as part of the rooms in any way, but between that you’ll see a little stretch of tunnel between the rooms if you run the project now.

With the basic components of the dungeon generation working, we can now turn our attention to the actual algorithm creating the dungeon. We will need a few more configuration variables first, so expand the section with our @export variables as follows:

@export_category("Map Dimensions")
@export var map_width: int = 80
@export var map_height: int = 45

@export_category("Rooms RNG")
@export var max_rooms: int = 30
@export var room_max_size: int = 10
@export var room_min_size: int = 6

This adds configuration on how the rooms should be created. A quick thing to mention ahead of the function we’re about to write is that we will pass the player as an argument to this function. We want to place the player character at the center of the first room created, and for that we need a reference to it. We’ll have to update the other nodes’ code a bit to accommodate that, but first the algorithm:

func generate_dungeon(player: Entity) -> MapData:
	var dungeon := MapData.new(map_width, map_height)
	
	var rooms: Array[Rect2i] = []
	
	for _try_room in max_rooms:
		var room_width: int = _rng.randi_range(room_min_size, room_max_size)
		var room_height: int = _rng.randi_range(room_min_size, room_max_size)
		
		var x: int = _rng.randi_range(0, dungeon.width - room_width - 1)
		var y: int = _rng.randi_range(0, dungeon.height - room_height - 1)
		
		var new_room := Rect2i(x, y, room_width, room_height)
		
		var has_intersections := false
		for room in rooms:
			# Rect2i.intersects() checks for overlapping points. In order to allow bordering rooms one room is shrunk.
			if room.intersects(new_room.grow(-1)):
				has_intersections = true
				break
		if has_intersections:
			continue
		
		_carve_room(dungeon, new_room)
		
		if rooms.is_empty():
			player.grid_position = new_room.get_center()
		else:
			_tunnel_between(dungeon, rooms.back().get_center(), new_room.get_center())
		
		rooms.append(new_room)
	
	return dungeon

This is quite a hand full, so let’s go through it bit by bit. As before we start with creating a fresh MapData object we call dungeon. We also need to keep track of the rooms we create, so we create an Array of Rect2i called rooms.

Then we have a big loop that places rooms and connects them, after which we return the resulting dungeon. Let’s take a closer look at the logic of the loop, first at a high level. We create a randomly sized (within our constraints) room and place it at a random position inside the map. If it’s overlapping with another room we discard it and try again. We try as often as our maximum number of rooms allows. However, if we can place it we do so. Then, if it’s the first room we created we will place the player character in it. Otherwise we connect it to the previous room with a tunnel.

Now in a bit more detail. First, we start with the loop. We only use the loop to do something a number of times, we don’t care how often we have already done it. That’s why for _try_room in max_rooms: has the _try_room with the underscore. This is how we tell Godot that we don’t actually want to use the index within the loop (it will work without the underscore, but Godot will give you a warning). Now let’s look at the first block of the loop again:

var room_width: int = _rng.randi_range(room_min_size, room_max_size)
var room_height: int = _rng.randi_range(room_min_size, room_max_size)

var x: int = _rng.randi_range(0, dungeon.width - room_width - 1)
var y: int = _rng.randi_range(0, dungeon.height - room_height - 1)

var new_room := Rect2i(x, y, room_width, room_height)

This chooses random room_width and random room_height. Once we have that we can create an x and a y that result in a room that lies fully within the map. That constraint is the reason we have that dungeon.width - room_width - 1 in there (or the same with the height). It’s because we can’t start a room that’s 5 tiles wide 3 tiles away from the right border. The last line then creates a Rect2i corresponding to these variables. So far this is basically just the blueprint for a new room.

var has_intersections := false
for room in rooms:
	# Rect2i.intersects() checks for overlapping points. In order to allow bordering rooms one room is shrunk.
	if room.intersects(new_room):
		has_intersections = true
		break
if has_intersections:
	continue

This part checks if the new_room would intersect with any other rooms. For checks like these we first set a boolean variable, and initialize it with the value we expect if everything goes right. We don’t want any intersections so has_intersections is false. Then we loop through all the existing rooms. For each of those rooms, we check if that room intersects the new_room. If it does we set has_intersection to true, and exit the loop preemptively. We now know that there is at least one intersection, we do not need to check any other rooms. After the loop we check the has_intersections variable. If it’s true we know the loop found an intersection, and in that case we discard the blueprint and move on to try another one. If has_intersection is false, we have looped through all the other rooms without finding any intersections and can happily move on to make this blueprint into a real room (as real as it can be in a video game anyway):

_carve_room(dungeon, new_room)

if rooms.is_empty():
	player.grid_position = new_room.get_center()
else:
	_tunnel_between(dungeon, rooms.back().get_center(), new_room.get_center())

rooms.append(new_room)

So first, we carve the new_room into the dungeon. Then we check if our array of other rooms is still empty. If it is we take the player and change it’s grid position to the center of this new_room. Otherwise we’re not at the first room anymore (and already have placed the player) so we simply dig a tunnel from the center of the new_room to the center of the previous room (i.e., the one at rooms.back()). Lastly, enter the new_room into our array of rooms.

And with that, the dungeon is complete. What’s left is a tiny bit of housekeeping, as we now require the player to be passed into that function. so in map.gd change the _ready() function to the following:

func generate(player: Entity) -> void:
	map_data = dungeon_generator.generate_dungeon(player)
	_place_tiles()

We can’t create the dungeon right away as soon as the Map node exists, we have to wait for the player to exists, so we are no longer generating the dungeon in _ready(), but instead wait for the Game node to call generate() on the Map. Let’s implement that now in game.gd. Change the _ready() function there as follows:

func _ready() -> void:
	player = Entity.new(Vector2i.ZERO, player_definition)
	entities.add_child(player)
	map.generate(player)

You’ll notice we now got rid of our dummy npc. Now as first step we create the player, and simply place it at the coordinate origin. Then we add it to the Entities node, and then pass it to map.generate(). Now everything is taken care of. You can now run the project and should see a bunch of rooms connected by corridors.

We now did everything the original tutorial did for this part. However, when playing you probably can go outside the game window. The python tutorial creates the window at a specific size, and fits the map to perfectly fit that window. We could do something similar. However, I feel it’s easier to just have a camera to follow the player. That’s slightly challenging when you handle all the rendering yourself, but in Godot it’s trivial, as we just need to attach a Camera2D node to our player.

In order to be able to set the camera’s properties in the editor we will make a new Camera2D node as a child of Game. The only option we will edit for now is Zoom, which we will set to (2, 2). That will double the size of all our assets, and we can see a bit better what’s going on. Now, to attach it to the player we once again modify the _ready() function in game.gd:

func _ready() -> void:
	player = Entity.new(Vector2i.ZERO, player_definition)
	var camera: Camera2D = $Camera2D
	remove_child(camera)
	player.add_child(camera)
	entities.add_child(player)
	map.generate(player)

And just like that we have a camera following the player. Now you can explore procedurally generated dungeons. Once you get tired of one simple restart the game and you have a new one. However, we can see most of the dungeon already, so it’s not much exploring. We will remedy that in the next part, when we will take a look at field of view.