Procedural Dungeon Generation

stuff about computer science and programming
Post Reply
User avatar
dendiz
Site Admin
Posts: 114
Joined: Wed Oct 10, 2018 3:48 am

Procedural Dungeon Generation

Post by dendiz » Wed Oct 10, 2018 9:39 pm

The basics of any rogue-like dungeon crawling game is the dungeon. What makes these types of game infinitely re-playable is their use of procedural generation to produce a new dungeon and artifacts for each game. Some one in the internet came up with the idea of generating dungeons based on "pushing out" random rectangles generated with in a circle. To get more realistic results it's best to use a Gaussian random number generator, as rarely anything natural is uniformly randomly created.

So create some random rectangles with in a circle:

Code: Select all

	for i in range(0, num_cells):
		var xy = get_xy()
		var wh = get_wh()
		var type = "hall"
		if wh.x * wh.y > mean_width * mean_height * 0.9:
			type="room"
		cells.append({"id": i, "xy": xy, "wh": wh, "topleft": xy, "bottomright": xy + wh, "type":type})
the get_xy makes sure that the top left lies in a circle:

Code: Select all

func get_xy():
	var r = 100 * randf()
	var theta = randf() * 2 * PI
	var x = r * cos(theta) + 300
	var y = r * sin(theta) + 300
	return Vector2(x,y)
make sure that the width, height is acceptable:

Code: Select all

func get_wh():
	var w = gaussian(mean_width, width_dev)
	var h = gaussian(mean_height, height_dev)
	if w < 10 or h < 10: return get_wh()
	return Vector2(w,h)
now push the rectangles outwards:

Code: Select all

	while touching:
		touching = false
		for i in range(0, num_cells):
			for j in range(i+1, num_cells):
				var a = cells[i]
				var b = cells[j]
				if touches(a, b):
					touching = true
					var dx = min(a["bottomright"].x - b["topleft"].x + padding, a["topleft"].x - b["bottomright"].x - padding)
					var dy = min(a["bottomright"].y - b["topleft"].y + padding, a["topleft"].y - b["bottomright"].y - padding)
					if abs(dx) < abs(dy): dy = 0
					else: dx = 0
					var dxa = -dx/2
					var dxb = dx + dxa
					var dya = -dy/2
					var dyb = dy+dya
					shift_cell(a,Vector2(dxa, dya))
					shift_cell(b,Vector2(dxb, dyb))

User avatar
dendiz
Site Admin
Posts: 114
Joined: Wed Oct 10, 2018 3:48 am

Re: Procedural Dungeon Generation

Post by dendiz » Wed Oct 10, 2018 9:41 pm

Now some of the rectangles are designated as rooms if there are bigger than an average value in area.
We want to use these as the main nodes for joining the rooms together.

Code: Select all

	cells.sort_custom(AreaSorter, "sort")
	var num_rooms = 0
	for c in cells:
		if c["type"] == "room": num_rooms += 1
	for i in range(0, min(num_rooms, num_corridor)):
		var c = cells.pop_back()
		rooms.append(c)
Now connect the main rooms using Relative Neighborhood Graphs RNG

Code: Select all

	# connect main rooms
	var ab_dist = 0
	var ac_dist = 0
	var bc_dist = 0
	var skip = false
	for i in range(0, rooms.size()):
		for j in range(i+1, rooms.size()):
			skip = false
			ab_dist = pow(center_x(rooms[i]) - center_x(rooms[j]), 2) + pow(center_y(rooms[i]) - center_y(rooms[j]), 2)
			for k in range(0, rooms.size()):
				if i == k or j == k: continue
				ac_dist = pow(center_x(rooms[i]) - center_x(rooms[k]), 2) + pow(center_y(rooms[i]) - center_y(rooms[k]), 2)
				bc_dist = pow(center_x(rooms[j]) - center_x(rooms[k]), 2) + pow(center_y(rooms[j]) - center_y(rooms[k]), 2)
				if ac_dist < ab_dist and bc_dist < ab_dist:
					skip = true
				if skip: break
			
			if not skip:
				if not rooms[i]["id"] in graph:
					graph[rooms[i]["id"]] = []
				graph[rooms[i]["id"]].append(rooms[j]["id"])
2.png
2.png (5.63 KiB) Viewed 110 times

User avatar
dendiz
Site Admin
Posts: 114
Joined: Wed Oct 10, 2018 3:48 am

Re: Procedural Dungeon Generation

Post by dendiz » Wed Oct 10, 2018 9:42 pm

The RNG construction and the overlap checking code is the brute force way of solving these problems. The overlap checking can be done using an interval search tree for a better runtime performance, and the wikipedia article mentions a paper with an algorithm to do it in linearithmic time. But since the number of rooms in a dungeon are relatively small, it's not worth the added code complexity

Post Reply