Recursive dungeon generation on Godot 4.1
In this article, we will consider a method for procedural generation of dungeons using a recursive function. The project itself will be 2D with a top view. The room will occupy the entire window of the game.
My room occupies the entire display and has dimensions of 800×800, display, respectively, too.
Dungeon Generation
What is the general algorithm, first we create a two-dimensional array consisting of 0 (as it is written in the documentation for Godot, it is better to use a dictionary of vectors, so we will do it). Further in the center of this array we put 1-ku (if there is no room 0, if 1, then there is a room) and for all neighboring elements of the array we call a function that will probably put 1-ku (create a room), but maybe not. Further, for all elements in which the function has set 1, we again call this function (recursively).
Generation itself
Create the scene with the main node select Node2D. And add a script.
First, let’s declare a few variables, where without them
#Массив хранящий прелоады комнат
var room_array =[]
#Сам генерируемый лабиринт
var labirint_array ={}
#размер лабиринта 5x5
@export var labirint_size = 5
#Количество комнат
@export var room_count = 5
#Переменная потребуется, для увеличение максимально сгенерированного числа
#Если вдруг мы не смогли расставить все комнаты, при первом цикле
var random_max = 1I don’t see the point in explaining
First, let’s write a function that will create a room at the given array coordinates, if possible:
#функция создания одной комнаты
#Аргументы - координаты ячейки массива labirint_array
func add_one_room(j,i):
#Проверили нужны-ли ещё комнаты
if room_count > 0:
#Генерируем случайное число
var room = randi_range(0,random_max)
#Если сгенерировали не 0
if room >= 1:
#То делаем сложную проверку:
#Проверяем не выходят ли переменные, за границы
#Проверяем нет ли уже комнаты
if ((j >= 0) && (j < labirint_size) && (i >= 0) && (i < labirint_size) && (labirint_array[Vector2(j,i)] != 1)):
#и добавляем комнату в массив
labirint_array[Vector2(j,i)] = 1
#не забыли про счётчик
room_count -= 1
#возвращаем вектор, если создали
return Vector2(j,i)
#Если вылетили и какого-то if, то возвращаем другой ветор
return Vector2(-1,-1)Now we have a function that creates a room at the given coordinates and returns them (as a vector, because we use a dictionary), or returns a vector (-1,-1), just such a vector, because we ourselves will not create a vector with coordinates less than (0,0).
Next, we will write a function that will call the function for creating a room for 4 neighboring coordinates, we will take the coordinates as an argument. After that it will call itself, for the created rooms:
#Рекурсивная функция добавления комнат
#Аргументы - координаты ячейки массива labirint_array
func add_rooms(j,i):
var add:Vector2
#Сначала пробуем сгенерировать комнату слева от уже созданной
add = add_one_room(j-1,i)
if add != Vector2(-1,-1):
add_rooms(add.x,add.y)
#пробуем сгенерировать комнату справа от созданной
add = add_one_room(j+1,i)
if add != Vector2(-1,-1):
add_rooms(add.x,add.y)
#пробуем сгенерировать комнату сверху от созданной
add = add_one_room(j,i-1)
if add != Vector2(-1,-1):
add_rooms(add.x,add.y)
#пробуем сгенерировать комнату снизу от созданной
add = add_one_room(j,i+1)
if add != Vector2(-1,-1):
add_rooms(add.x,add.y)
#Рекурсивно вызываем функции
#Поэтому нужно обращаться конкретно к х или уNow let’s create a function that will generate the initial array (consisting of 0), set the first room and run the recursion:
#Функция создания лабиринта
func generate_labirint():
#Сначала заполняем массив нулями
for i in range(labirint_size):
for j in range(labirint_size):
labirint_array[Vector2(j,i)] = 0
#Если вдруг каким-то образом должно быть больше комнат,
#Чем всего на карте, то меняем это, во избежание бесконечной рекурсии
if labirint_array.size() < room_count:
room_count = labirint_array.size()
#Точкой начала выбираем центр лабиринта
labirint_array[Vector2(round(labirint_size/2),round(labirint_size/2))] = 1
#Не забываем про кол-во комнат
room_count -=1
#Вызываем в цикле, потому-что есть вероятность, что ниодной комнаты не добавится
while room_count > 0:
#Вызываем функцию добавления комнаты
add_rooms(round(labirint_size/2),round(labirint_size/2))
#Функция рекурсивная, поэтому закончится,
#когда отработают все вызванные функции
#Увеличиваем счётчик, чтобы быстрее растыкать комнаты
random_max +=1
#Если мы такие невезучие, что счётчик дошёл до 10,
#То хватит с нас этого рандома
if random_max > 10:
breakThis completes the dungeon generation. Next, we will create our rooms in the game scene and add doors to the rooms.
Some blanks
room scene
First, create some room scenes, roughly as it should be:
4 markers: Door1…Door4 – these are the locations of possible doors, it is also worth setting the door rotation angle in the markers. StaticBody2D and CollisionShape2D are needed so that the future game character does not walk on the walls.
Room script:
extends Node2D
#если кто-то наступил на стену,
#то больше не может идти
func _on_area_2d_body_entered(body):
body.velocity = Vector2(0,0)
The script is very basic, we just need a room and nothing else.
Several such rooms should be made.
Stage Doors
The door should look something like this:
When the player comes into contact with the collisionShape2D, it will move to the next room.
Door Script:
extends StaticBody2D
#куда дверь телепортирует игрока
@export var next_pos:Vector2
#Задаём переменную телепорта
func set_next_pos(vector):
next_pos = vector
#Возвращаем эту переменную
func get_next_pos():
return next_posHere, too, everything is clear. Everything is finally done with a little preparation.
Create a map
First, let’s write a couple of functions to create an array with scene preloads:
#Папка с комнатами, у меня все комнаты Room + ID
const MAP_ROOT = "res://Room/Rooms/Room"
#Небольшой хелпер возвращающий уже полный путь сцены
func get_room_path(index):
return MAP_ROOT + str(index) + ".tscn"
#Заполним массив с прелоадами комнат
func get_room_array():
#Счётчик
var i = 1
while true:
#Если такая сцена есть, то добавляем в массив
if load(get_room_path(i)) != null:
room_array.append(load(get_room_path(i)))
#Иначе заканчиваем while
#У меня все комнаты идут по порядку(Room1,Room2...)
#Можно сделать чуть иначе, но так проще...
else:
break
i+=1Now we have an array with scene preloads. Next, we will write functions for the complete creation of the dungeon.
#Функция создания лабиранта в дерево объектов
func build_labirint():
for i in range(labirint_size):
for j in range(labirint_size):
#Если в массиве 1, то рисум комнату
if labirint_array[Vector2(j,i)] == 1:
draw_room(j,i)
#Функция добавления комнат в дерево объектов
#Аргументы - координаты ячейки массива labirint_array
func draw_room(j,i):
#Взяли случайную комнату из массива с комнатами
var s = room_array[randi_range(0,room_array.size())-1].instantiate()
#Задали местоположение
#Умножаем на размер комнаты
s.position = Vector2(j*800,i*800)
#Добавили в дерево объектов
add_child(s)
#Добавляем все двери
#При перемещении на 200 в моем случае пирсонаж окажется у двери
add_one_door(j-1,i,200,0,s,4)
add_one_door(j+1,i,-200,0,s,2)
add_one_door(j,i-1,0,200,s,1)
add_one_door(j,i+1,0,-200,s,3)
#Функция добавления двери
#Аргументы - координаты ячейки массива labirint_array,
#Смещение по х и по у, мы должны появляться возле двери через которую пришли
#Наша сцена комнаты, к которой добавляем дверь
#Порядковый номер нужного маркера в дереве объектов сцены комнаты
func add_one_door(j,i,add_x,add_y,s,n):
#Делаем сложную проверку:
#Проверяем не выходят ли переменные, за границы
#Проверяем есть ли уже комнаты
#Не путайте с условием из add_one_room - ЭТО ДРУГОЕ
if ((j >= 0) && (j < labirint_size) && (i >= 0) && (i < labirint_size) && (labirint_array[Vector2(j,i)] == 1)):
var d = preload("res://Room/Door/Door.tscn").instantiate()
#Перенимаем трансформ с маркера, который за это ответственен
d.transform = s.get_child(n).transform
#Задали положение для телепорта
#Умножаем на размер комнаты
d.set_next_pos(Vector2(j*800+add_x,i*800+add_y))
s.add_child(d)Let’s talk a little about the add_one_door function, specifically the n argument, what it actually is. This is the ordinal number of the child of the scene tree. How it looks for me:
the child with index 0 is Sprite2D, the next 4 children are just our markers, in which the location and rotation of the door are recorded, Door1 is the child with index 1, indicating the position of the upper door. Door2 is a child at index 2, indicating the position of the right door, and so on. clockwise. All room scenes must have the same Marker index.
In the _ready() function, the functions should be called in the following order:
func _ready():
#Подключаем рандомайзер
randomize()
#Создаём лабиринт
generate_labirint()
#Создаём массив комнат
get_room_array()
#Строим либиринта
build_labirint()Now we have a dungeon generated, but there is no way to look at it. Add Camera2D to the game’s scene tree. In InputMap add clickright – RMB and clickleft – LMB.
add a function _process to an existing script:
#играемся с зумом камеры
func _process(delta):
if Input.is_action_just_pressed("clickright"):
$Camera2D.zoom /= 2
if Input.is_action_just_pressed("clickleft"):
$Camera2D.zoom *= 2
With RMB, the camera moves away, with LMB, it approaches.
and set the initial location of the camera in the center of the map:
$Camera2D.position = Vector2(800 * round(labirint_size/2),800 * round(labirint_size/2))results
For clarity, I made the scenes just in different colors, instead of rooms with some kind of scenery.
Small Dungeons:
Medium Dungeons:
TOO huge dungeons:
As you can see, the larger the dungeon, the more interesting its shape. By the time of work, I would not say that the generation takes a lot of time, that is, empty rooms are generated extremely quickly, but it is better to load some kind of loading screen when entering the dungeon generated in this way. But definitely not the fastest and best way, but as an option for some project, being very limited in time for its implementation, it will do.
Character and movement between rooms
Let’s finally create a simple character that will walk around our dungeon.
Element tree:
The most standard tree, nothing more is needed. Character script:
extends CharacterBody2D
#Скорость
const SPEED = 300.0
#Сигнал выхода из двери
signal out
func _physics_process(delta):
#Получаем направление движения
var input_direction = Input.get_vector("left", "right", "up", "down")
#Нормализуем и умножаем на скорость
velocity = input_direction.normalized() * SPEED
#Пошли
move_and_slide()
for i in get_slide_collision_count():
var collision = get_slide_collision(i)
#Если столкнулись и есть у объекта столкновения
#Метод get_next_pos,вызываем его и посылаем сигнал
if collision.get_collider().has_method("get_next_pos"):
position = collision.get_collider().get_next_pos()
emit_signal("out")nothing out of the ordinary either, just move in 8 directions and handle the collision with the door (the door has this function).
Now add a script to the main scene camera, change the camera behavior a bit so that it follows the character:
extends Camera2D
#Переменная хранящая игрока
var player: Node2D
#Присоединяем сигнал игрока
func connect_player():
player.connect("out",_on_player_out)
#Перемещаем камеру
func _on_player_out():
if player != null:
#Используем обычное округления - это важно
var x = round(player.position.x / 800)
var y = round(player.position.y / 800)
position = Vector2(x*800 ,y*800)when moving to another room, the camera will also move to the center of this room.
change the _ready function of the map scene:
func _ready():
#Подключаем рандомайзер
randomize()
#Создаём лабиринт
generate_labirint()
#Создаём массив комнат
get_room_array()
#Строим либиринта
build_labirint()
#Добавляем игрока в центр, центральной комнаты
var h = preload("res://Character/character.tscn").instantiate()
#Умножаем на размер комнаты
h.position = Vector2(800 * round(labirint_size/2),800 * round(labirint_size/2))
add_child(h)
#Привязали к камере игрока
$Camera2D.player = h
#Заделали коннект
$Camera2D.connect_player()
#определили изначальное положение
#Умножаем на размер комнаты
$Camera2D.position = Vector2(800 * round(labirint_size/2),800 * round(labirint_size/2))Now you can run on this map.
Well, something like this algorithm can be used to generate a dungeon, of course, in order to get more interesting dungeons, the algorithm needs to be finalized for specific needs.
