## Procedural Dungeon Generation

*May 13, 2017*

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

*Tags:
#gamedev
*