Procedural Dungeon Generation

Keywords: random number, interval search, brute force, rng construction, dungeon, game, circle, main, code, relative, average. Powered by TextRank.

The basics of any roguelike dungeon crawling game is the dungeon. What makes these types of game infinitely replayable is their use of procedural generation to produce a new dungeon and artifacts for each game. Some one in the internets 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 cirlce:

	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:

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:

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:

	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))

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.

	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)

	# 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"])

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

Procedural Dungeon Generation

Metadata

Similar posts