## Procedural Dungeon Generation

stuff about computer science and programming
dendiz
Posts: 114
Joined: Wed Oct 10, 2018 3:48 am

### Procedural Dungeon Generation

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

dendiz
Posts: 114
Joined: Wed Oct 10, 2018 3:48 am

### Re: Procedural Dungeon Generation

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 (5.63 KiB) Viewed 110 times

dendiz