Procedural Dungeon Generation Help!

Godot Version



Hello fellow godoters!

Bit of a long shot. I’m wondering if any one is able to assist me with some code i’ve been working on.

I’ve got a scene with a gridmap and a script which generates a random dungeon level. I adapted this from a random room generator which connected the rooms via hallways but i am trying to convert it to use pre-defined rooms with pre-defined door locations rather than having the script place doors where it wants and connect with hallways.

the issue im having is, the hallways im generating using delauney triangulation, an MST graph and astar pathfinding don’t line up correctly with the doors and if I increase the room amount the hallways are just a big mess and some doors/rooms are not even connected.

I’m hoping someone can understand what is going on here better than me and is kind enough to lend a hand.

I’ve uploaded the project here - GitHub - shaunzorr/DungeonGeneratorTest

I would really appreciate it if someone could help me out :slight_smile:

1 Like

I can’t really dive into the code right now, but here are some things I noticed:

  1. Debugging a tool script in-editor is challenging and can cause crashes. I would recommend setting up a test scene that you can run and debug.
  2. You aren’t clearing door_tiles at the start of generate().
  3. The door_tiles array is indexed by the room index, but on lines 135-136, you’re using the door indices.
  4. Your graph is built using the doorways as points, but I would expect the graph to be built using the room centers as points. This isn’t a problem per se, but it means there are extra edges in your graph which make things a bit more complicated. As it is now, the algorithm tries to connect hallways between doors which belong to the same room.

I think the handling of the door_tiles array is the thing causing the most problems right now.

When I get more time, and if you haven’t figured it out by then, I’ll come back and look into it a bit more.

As an aside, the code feels a bit disorganized and hard to follow. If you want some help refactoring it feel free to ask.

1 Like

Also I’ll add that your room generation, Delaunay triangulation, and MST calculation all seem to be fine (although you really should be using Kruskal’s algorithm for that).

And the hallway connections seem to be correctly determined.

It’s really just the actual hallway gridmap construction that seems problematic.

1 Like

thank you for responding.

Yeah the create_hallways function is fubar, I added the line to clear door_tiles and now it’s not generating hallways at all due to an invalid index on line 136.

The script was originally generating randomly sized rooms and using the centre points for the graphs. I am trying to change it so I can set up predefined_rooms that have doors in certain positions so I can just drop pre-made 3d scenes in where the rooms should be and then when the hallways are generated they line up properly with the doors.

any help you can give would be greatly appreciated im really in over my head here haha and yes the code is a mess any help on that would be greatly appreciated also :slight_smile:


1 Like

For line 136 (and 135) you’ve got the door index, but you need to get the room index for that door. A quick fix would be to divide c and p by 2 when indexing into door_tiles, but that would only work because each room has exactly 2 doors.

I would suggest you start from the top.

I did some refactoring of the code out of necessity while testing your project. Allow me to share some changes I made.

Making the scene testable

You shouldn’t be trying to debug stuff like this via a tool script in-editor. As mentioned earlier, you can easily crash the editor itself, and some errors are suppressed.

The first thing I did was add the default Sun and Environment to the scene (you can do this by clicking on the triple-dot icon in the 3D view’s toolbar).

Next, I found a nice viewpoint above the dungeon, added a Camera3D, and used Ctrl+Alt+M to align the camera to my current viewpoint.

My scene looks like this:

Next, I added an input function to the generator script to regenerate the dungeon when I hit Space:

func _unhandled_key_input(event: InputEvent) -> void:
	if Engine.is_editor_hint():
	if event.pressed:
		match event.physical_keycode:

At this point I was able to run the scene with F5 and debug as normal.
Of course, it still works in-editor with the “Start” button.

Data Structure

The first thing I would do is reevaluate how you’re storing the room and door data. The current data seems a little clunky to use. Here is how I would have structured it:

var room_tiles: Array[PackedVector3Array] # room_tiles[room_id] -> list of covered tiles
var room_doors: Array[PackedInt32Array] # room_doors[room_id] -> door indices
var door_positions: PackedVector3Array # door_positions[door_id] -> door's position
var door_rooms: PackedInt32Array # door_rooms[door_id] -> door's room_id

(You weren’t using room_positions anywhere so I removed it, feel free to keep it of course.)

But either way, the very next thing you should do is write some helper methods:

func add_room(tiles: PackedVector3Array) -> int:
	var room_id := room_tiles.size()
	return room_id

func add_door(room_id: int, door_position: Vector3) -> int:
	assert(room_id >= 0 and room_id < room_tiles.size()) # validate room_id
	var door_id := door_positions.size()
	return door_id

And update the place_predefined_room() function to use them:

	var room : PackedVector3Array = []
	var dt: PackedVector3Array = []
	for r in height:
		for door_id_to in width:
			var pos : Vector3i = start_pos + Vector3i(door_id_to,0,r)
			grid_map.set_cell_item(pos, 0)
	var room_id := add_room(room)
	for door_position in new_room["doors"]:
		var door_pos : Vector3i = start_pos + Vector3i(door_position.x, 0, door_position.z)
		grid_map.set_cell_item(door_pos, 2)
		add_door(room_id, door_pos)
	# Not needed anymore:


Next we need to look at each piece of code accessing these arrays and see if anything needs to be updated.


The first thing I see is in connection_calculations(). You don’t need to use AStar2D.get_available_point_id() to create ids. You already have an id: the door’s index. Let’s refactor that code to just use door indices:

	var door_positions_2d : PackedVector2Array = []
	var del_graph : AStar2D =
	var mst_graph : AStar2D =
	for door_id: int in door_positions.size():
		var p := door_positions[door_id]
		del_graph.add_point(door_id, Vector2(p.x,p.z))
		mst_graph.add_point(door_id, Vector2(p.x,p.z))

(I renamed rvp2 to door_positions_2d as well.)


Now let’s jump down to create_hallways(), since that’s where the real trouble is.

Lines 135-146 are a real mess. There’s a lot of extra work being done to calculate the closest tile inside the room to the door. But… why not just use the door position?

Here’s how I rewrote that section:

	var hallways : Array[PackedVector3Array] = []
	for door_id_from in hallway_graph.get_point_ids():
		for door_id_to in hallway_graph.get_point_connections(door_id_from):
			if door_id_to <= door_id_from:
			var tile_from : Vector3 = door_positions[door_id_from]
			var tile_to : Vector3 = door_positions[door_id_to]
			var hallway : PackedVector3Array = [tile_from,tile_to]

Fixing the same-room problem

Right now, since each door is a node in the graph, sometimes doors belonging to the same room will be connected.

In fact, because of the size of the rooms and the nature of Delaunay triangulation, this will always happen.

It looks like this:


We can fix this very easily by adding the following check to create_hallways():

	var hallways : Array[PackedVector3Array] = []
	for door_id_from in hallway_graph.get_point_ids():
		for door_id_to in hallway_graph.get_point_connections(door_id_from):
			if door_id_to <= door_id_from:
+			# Prevent connecting a room to itself
+			if door_rooms[door_id_from] == door_rooms[door_id_to]:
+				continue
			var tile_from : Vector3 = door_positions[door_id_from]
			var tile_to : Vector3 = door_positions[door_id_to]
			var hallway : PackedVector3Array = [tile_from,tile_to]

Final thoughts

With these fixes you should have a working dungeon generator.

Here is what it looks like in action:

You should be able to get everything else working from this point.

Good luck!

P.S. I made a pull request on your repo with the changes I made, since I’m sure you’ll want to see the full diff.


Thank you so much!!! i really appreciate it. that works perfectly I even added some more predefined_rooms and it performs flawlessly.

You are an absolute god send. I can’t thank you enough!

This topic was automatically closed 30 days after the last reply. New replies are no longer allowed.