What's wrong with my dungeon walk algorithm?

Roodiger

Hey guys! So, I'm working on a project and am looking to build a binding of isaac type of dungeon generation. I've build it out, but keep getting issues with it. I wanted it to loop through and have exactly the amount of rooms that I specify, but when I added a unique room check it just keeps crashing.

Could you point to me what I'm doing wrong?

I know my code is probably garbage, and I'm sure the answer is obvious.

extends Node

# The array that holds the walkers x and y pos
var walker = {"x":0,"y":0}
# The array that holds the rooms positions
var rooms = []
# Holds the player scene instance
var player
# Boolean var that checks if the room is unique
var uniqueRoom
# The amount of rooms to spawn
var roomCount = 15

# When the code loads it will generate the dungeon.
func _ready():
	generate_dungeon()

# Function to check if there is a unique room (THIS ISN'T WORKING')
func check_for_unique_room():
	# Initially sets this to true
	uniqueRoom = true
	# Loops through all of the rooms in the array so far
	for room in rooms:
		# If the room in the array is equal to the room at the end of the array 
		# (This is when this function gets called. It is checking the new room against the other rooms)
		if room.get_position() == rooms.back().get_position():
			# Remove the room because it isn't unique
			rooms.pop_back()
			# Set unique to false
			uniqueRoom = false
			# Break out of the loop
			break

# The function to actually generate the rooms and positions
func generate_dungeon():
	# Keeps it random on load
	randomize()
	# This is where you choose how many rooms the dungeon spawns
	while rooms.size() <= roomCount:
		# If rooms is empty it means it is the first room. So if it isn't empty, do this code
		if rooms.empty() == false:
			# Initially sets the uniqueness of the room to false
			var uniqueRoom = false
			# While the room isn't unique, do the following code
			while uniqueRoom == false:
				# Add the room scene to the array 
				rooms.push_back(load("res://World/DungeonRoom.tscn").instance())
				# Set the name of the room
				rooms.back().set_name("room_" + str(rooms.size()) + "_" + str(walker["x"]) + '_' + str(walker["y"]))
				# Calculate the position of the room
				var room_pos = Vector2((335 * 1.5)*walker["x"], (195 * 1.5)*walker["y"])+Vector2(-335 * 1.5, -195 * 1.5)
				# Set the position
				rooms.back().set_position(room_pos)
				# Adds the child to the current scene
				self.add_child(rooms.back())
				# Checks if the room is unique or not
				check_for_unique_room()
				# Makes the walker step
				walker_step()
			
			# If the room is unique do the following
			if uniqueRoom == true:
				# This sets the label. Just for testing purposes
				rooms.back().get_node("Label").text = str(rooms.size())
				# This shows the room which is originally hidden (Becuase of duplicate room issues I'm having)
				rooms.back().show()
				# Makes the walker step
				walker_step()
		
		# If the rooms array is empty it is the first room. Do this code
		elif rooms.empty() == true:
			# Push the room to the first array position
			rooms.push_front(load("res://World/DungeonRoom.tscn").instance())
			# Set the name of the room
			rooms[0].set_name("room_0," +  str(walker["x"]) + '_' + str(walker["y"]))
			# Set the testing label room
			rooms[0].get_node("Label").text = "0" 
			# Set the position of the room to 0, 0
			rooms[0].set_position(Vector2.ZERO)
			# Add the room to the scene
			self.add_child(rooms[0])
			# Show the room
			rooms[0].show()
			# If there is no player, add one to the room.
			if get_tree().get_root().has_node("Player") == false:
				player = load("res://Player/Player.tscn").instance()
				player.set_position(rooms[0].get_position() + Vector2((320 /2), (180/2)))
				player.show()
				get_parent().call_deferred("add_child", player)
				print("Player = " + str(player.get_position()))
			# Makes the walker step
			walker_step()
		else:
			break;

# The function for the walker
func walker_step():
	# The walker chooses a random number between 0 and 3. It will change the x or y postion
	# depending on the number it chooses
	var choice = (randi() % 4)
	if choice == 0:
		walker["x"]+=1
	if choice == 1:
		walker["x"]-=1
	if choice == 2:
		walker["y"]+=1
	if choice == 3:
		walker["y"]-=1

# Just a function to generate a new dungeon for testing purposes
func _on_Button_pressed():
	get_parent().remove_child(player)
	get_tree().reload_current_scene()
	Global.dungeonMusic = false

TwistedTwigleg

Welcome to the forums @Roodiger!

Are these two different code files? I ask this because you have two different extends Node, but the code is being rendered as a single block. If they are separate, can you please post each one individually and/or edit your above comment so they rendered separately? Additionally, can you mark what each is supposed to do? That would make it easier to see what is going on, which in turn would make it much easier to try and help.

As for the algorithm, one issue might be how you are spawning the rooms. You are creating instances of them, but as far as I can see, you are not adding them to the scene using add_child. This could be causing some of the issues you are seeing. Additionally, in the first file, you have an infinite loop, because unique_room will never not be false, because in the while loop there is nothing to change its value (the loop just adds rooms).

I'm not sure on the second file. The way the walking is being stored is kinda strange, at least from my experience, and so I'm struggling to see what the issue could be.

Roodiger

Sorry, the first part of the code got copied in twice. I edited it to remove that.

Also, the rooms are being added on lines 41 and 61.

I'll take a minute a bit later on and clean up the code and add in some comments to make it easier. I've never made a walker before, so this is just something I through together.

As for the loop, that loop calls check_for_unique_room(), and in that function it sets uniqueRoom to be true. And then if it finds a matching room it sets it to false. So it should return true if there are no matching rooms right?

Roodiger

Also, thanks @TwistedTwigleg ! It's awesome to be here. I'm loving Godot so far except for a few quirks I've been running into. I'm sure you'll see me around here quite often :)

TwistedTwigleg

Great! I'll take a look at it tomorrow and see if I can figure out what is going on :+1:

Roodiger

Thanks a lot! I'll go through it tonight and clean it up a bit to make it easier to view for you @TwistedTwigleg

Roodiger

@TwistedTwigleg I updated the main post code and added a bunch of comments. Let me know what you see! Thanks again :)

TwistedTwigleg

Okay, I looked at the code, and I think the issue is in your check for unique room function. From what I can gather, the function is for making sure no two rooms are in the same position, correct? If so, then I would suggest changing the function to the following:

# Returns a boolean if the passed-in room node's position overlaps an already existing room
func check_for_unique_room(new_room):
	# Go through all the rooms
	for room in rooms:
		# Don't process the passed-in room.
		if new_room == room:
			continue
		
		# Get the position of the room using its name by splitting the name up
		var room_data = room.name.split("_", true)
		# the position should be on the third [2] and fourth [3] indexes
		# (first is room, second is the room number)
		var room_position_x = room_data[2]
		var room_position_y = room_data[3]

		# do the same for the passed-in room
		var new_room_data = new_room.name.split("_", true)
		var new_room_position_x = new_room_data[2]
		var new_room_position_y = new_room_data[3]
		
		# compare!
		if (new_room_position_x == room_position_x and new_room_position_y == room_position_y):
			# overlap! Return false!
			return false
	
	# If we didn't find any collisions/overlaps, then return true
	return true

Then, I would recommend making the following modifications to the generate_dungeon function:

# for performance reasons, the room should probably be loaded outside of the function.
var dungeon_room_scene = preload("res://World/DungeonRoom.tscn")

func generate_dungeon():
	randomize()

	while rooms.size() <= roomCount:
		# Not the first room...
		if rooms.empty() == false:
			var new_room = dungeon_room_scene.instance()
			# set the name of the room
			new_room.set_name("room_" + str(rooms.size()) + "_" + str(walker["x"]) + "_" + str(walker["y"]))
			# make sure the room position is unique
			var is_room_unique = check_for_unique_room(new_room)
			# if it is not unique, then just continue
			if is_room_unique == false:
				continue
			else:
				# add the new room to the list, and then the scene
				rooms.push_back(new_room)
				add_child(new_room)
				# calculate the position
				var room_pos = Vector2((335 * 1.5)*walker["x"], (195 * 1.5)*walker["y"])+Vector2(-335 * 1.5, -195 * 1.5)
				# set the position
				new_room.set_position(room_pos)
			# make the walker step!
			walker_step()
		# The first room...
		else:
			var new_room = dungeon_room_scene.instance()
			# set the name of the room
			new_room.set_name("room_" + str(rooms.size()) + "_" + str(walker["x"]) + "_" + str(walker["y"]))
			# add the new room to the list and then the scene
			rooms.push_back(new_room)
			add_child(new_room)
			# set the position
			new_room.set_position(Vector2(0, 0))
			
			# if there is no player, then spawn one!
			if get_tree().get_root().has_node("Player") == false:
				player = load("res://Player/Player.tscn").instance()
				player.set_position(rooms[0].get_position() + Vector2((320 /2), (180/2)))
				player.show()
				get_parent().call_deferred("add_child", player)
				print("Player = " + str(player.get_position()))
			# make the walker step!
			walker_step()

(You may eventually need to add a condition to make sure the code does not loop endlessly, but that's another problem for another day, and shouldn't be an issue in most cases.)

The rest looks fine though, and with those modifications, I believe it should work :smile:

Roodiger

@TwistedTwigleg

Hmm, I gave it a go with that code and the game just won't load. I'll try to fiddle around with it when I'm around later and see if I can get it working. Thanks a bunch for looking at it!

Roodiger

@TwistedTwigleg

I tested it, and something in your code for checking for a unique room is causing the scene to not load up. I commented it all out and it ran.

TwistedTwigleg

@Roodiger - does the console show any errors when you try to load the scene with the code not commented out? Maybe the issue is the indexes. Maybe try subtracting them by one and see if that fixes the issue? So var room_position_x = room_data[2] would become var room_position_x = room_data[1], for example.

Roodiger

I was able to get it to work! I had to change something in the generation code.

func generate_dungeon():
	randomize()
	while rooms.size() <= roomCount:
		# Not the first room...
		if rooms.empty() == false:
			var new_room = dungeon_room_scene.instance()
			# set the name of the room
			new_room.set_name("room_" + str(rooms.size()) + "_" + str(walker["x"]) + "_" + str(walker["y"]))
			# set the label for testing
			new_room.get_node("Label").text = str(rooms.size()) 
			# make sure the room position is unique
			var is_room_unique = check_for_unique_room(new_room)
			# add the new room to the list, and then the scene
			if is_room_unique == true:
				# Push the room to the array
				rooms.push_back(new_room)
				# Add the room to the scene
				add_child(new_room)
				# calculate the position
				var room_pos = Vector2((335 * 1.5)*walker["x"], (195 * 1.5)*walker["y"])+Vector2(-335 * 1.5, -195 * 1.5)
				# set the position
				new_room.set_position(room_pos)
			# make the walker step!
			walker_step()

Now I just need to figure out how to make the doors work, and fix the camera issues haha Thanks for the help!

TwistedTwigleg

Awesome! I'm glad you got it working! :smile: