# Dungeon generation with Newton's law of gravity

##### February 3, 2021

You might wonder what Newton's law of gravitation has to do with the generation of dungeons, but if we use this concept we can use it to generate a dungeon of rooms. Instead of using something like a BSP algorithm, my idea was to just throw a bunch of rooms on top of each other, and let them push each other away until there are no longer any collisions. The result looks like this.

The method to push them away from each other, is where Newton's law of gravitation comes in. If two rooms are on top of each other, this gravitational force would be used to push the two rooms apart (instead of attracting).

The result of this method can be seen in the included demo below. This demo is available on GitHub, and can be found here. Press F5 if it doesn't load properly, or check it out on GitHub.

*numberOfRooms*: pretty self explanatory, this is the number of the rooms that are generated.*circleRadius*: the radius of the circle in which the rooms are placed randomly.*minRoomSize*: the minimum width/height of a room.*maxRoomSize:**gravitationalForce:*the gravity factor $G$ in Newton's law.*velocityStepSize:*the step size used for changed the position based on the velocity.*maxVelocity*: the maximum amount of velocity for a room.*nearestNeighbours*: the number of rooms a room is connected to with a line.

## Vectors & Math

I have also added two functions to the `Math`

class. A `clamp(x, a, b)`

method, which ensures that $x$ stays between $a$ and $b$, and an `argmin(list)`

function that will return the index of the lowest value in the list.

## Rectangles

Next we define a class for a rectangle, which will be used to define the position and the dimensions of a room. This allows us to define a rectangle with the four variables $x, y, w, h$.

```
1class Rectangle {
2
3 constructor(x, y, w, h) {
4 this.x = x;
5 this.y = y;
6 this.w = w;
7 this.h = h;
8 }
9
10 intersect(rect) {
11 const x = Math.max(this.x, rect.x);
12 const n1 = Math.min(this.x + this.w, rect.x + rect.w);
13 const y = Math.max(this.y, rect.y);
14 const n2 = Math.min(this.y + this.h, rect.y + rect.h);
15 if(n1 >= x && n2 >= y) {
16 return new Rectangle(x, y, n1 - x, n2 - y);
17 }
18 else {
19 return Rectangle.empty;
20 }
21 }
22
23 static empty = new Rectangle(undefined, undefined, undefined, undefined);
24}
```

The class also contains a fast method for finding the rectangle that intersects two rectangles, which comes from an answer on StackOverflow. This answer comes from the implementation of `Rectangle.Intersect`

from the .NET Framework. (Why reinvent the wheel?)

## Random probability functions

The position of the room is also randomly generated. To have them all on top of each other, this should be a random position in the unit circle. To generate a random point in the unit circle, we will generate two random variables $x_0 \in [0, 1]$, and $x_1 \in [0, 1]$. These variables are used to generated a random polar coordinate $(r, \theta)$ within the unit circle. The length is $r=x_0$, and the angle is $\theta = 2\pi\sqrt{x_1}$. The square root is taken because the area of the circle grows faster as the circle becomes bigger. The Cartesian coordinates are given with $x = r\cdot\cos(\theta)$, and $y = r\cdot\sin(\theta)$. All in all, this gives us the following code to generate the random variables.

```
1class Random {
2 static insideUnitCircle() {
3 const theta = Math.random() * 2 * Math.PI;
4 const r = Math.sqrt(Math.random());
5 return new Vec2(r * Math.cos(theta), r * Math.sin(theta));
6 }
7 static exponential() {
8 var r = Math.random();
9 return 1 - Math.exp(r) * (1 - r);
10 }
11 static uniform() {
12 return Math.random();
13 }
14}
```

## Rooms

Next we will create a class for the rooms. This class will hold the rectangle that defines the position and room size, and also a velocity vector which we are going to use to move the room around. We will also add a method to calculate the point at the center of the room. It would probably be better to move this to the rectangle class, but this will do for now. Finally we will add a method to calculate the squared length of the diagonal of the room. This diagonal is used to determine the mass of the room which is used to the determine the force $F$ in Newton's law of gravity.

```
1class Room {
2 constructor(x, y, w, h) {
3 this.rect = new Rectangle(x, y, w, h);
4 this.velocity = new Vec2(0);
5 this.neighbours = [];
6 }
7
8 center() {
9 return new Vec2(this.rect.w / 2 + this.rect.x, this.rect.h / 2 + this.rect.y);
10 }
11
12 lengthSquared() {
13 return new Vec2(this.rect.w, this.rect.h).lengthSquared();
14 }
15}
```

The neighbours list is used to store all the nearest rooms, based on the nearest neighbour algorithm. This is used to draw the lines between the rooms.

## Generating the rooms

Now we can generate all the rooms, which is done with the following function.

```
1generateRooms() {
2 const r = this.circleRadius;
3 const range = this.maxRoomSize - this.minRoomSize;
4 for(let i = 0; i < this.numberOfRooms; i++) {
5 const p = Random.insideUnitCircle().scale(r);
6 const w = Random.exponential() * range + this.minRoomSize;
7 const h = Random.exponential() * range + this.minRoomSize;
8 const room = new Room(p.x - w/2, p.y - h/2, w, h, this.numberOfRooms);
9 this.points.push(p);
10 this.rooms.push(room);
11 }
12}
```

Here we will generate $n$ rooms based on the settings provided by the user. All the rooms will be stored a list rooms. There also is a list for all the points, which is used by the drawing algorithm to draw all the rooms.

## Applying Newton's law of gravity

- For $i=0$ to $n$ (for each room $R_i$):
- For $j=i$ to $n$ (for each room from $R_i$ to room $R_j$):
- If the two rooms
**do not intersect**, skip all below, and go to the next room (increase $j$). - Calculate the "mass" $m_1$ of room $R_i$, which is the squared length of the diagonal.
- Calculate the "mass" $m_2$ of room $R_j$.
- Calculate the squared distance $r^2$ between $R_i$ and $R_j$.
- Calculate the force $F$ with Newton's law of gravity.
- Calculate the vector $\hat{r}_i$ which is the vector from room $R_i$ to $R_j$.
- Calculate the vector $\hat{r}_j$ which is the vector from room $R_j$ to $R_i$.
- Calculate the velocity of room $R_i$ which is $-F\cdot\hat r_i$.
- Calculate the velocity of room $R_j$ which is $-F\cdot \hat r_j$.
- Add the velocity multiplied by the step size ($h\cdot\hat{r}_i$) to the position of room $R_i$.
- Add the velocity multiplied by the step size ($h\cdot\hat{r}_j$) to the position of room $R_j$.
- Set the intersected variable to true.

```
1updateVelocity() {
2 let intersected = false;
3 for(let i = 0; i < this.rooms.length; i++) {
4 for(let j = i; j < this.rooms.length; j++) {
5 if(i == j) {
6 continue;
7 }
8
9 const intersectedRect = this.rooms[i].rect.intersect(this.rooms[j].rect);
10 if(intersectedRect != Rectangle.empty) {
11 // Using an adjusted form of the formula for gravity to calculate
12 // the force, but is instead used to push the objects apart.
13 const room1 = this.rooms[i];
14 const room2 = this.rooms[j];
15 const m1 = room1.rect.w * room1.rect.h;
16 const m2 = room2.rect.w * room2.rect.h;
17 const r = room1.center().subtract(room2.center()).lengthSquared();
18 const G = this.gravitationalForce;
19 const fg1 = G * m1 * m2 / r;
20 const fg2 = G * m1 * m2 / r;
21 const v1 = room1.center().subtract(room2.center()).normalize();
22 const v2 = room2.center().subtract(room1.center()).normalize();
23 const maxV = this.maxVelocity;
24 room1.velocity = Vec2.clamp(v1.scale(fg1), -maxV, maxV);
25 room2.velocity = Vec2.clamp(v2.scale(fg2), -maxV, maxV);
26 const stepSize = this.velocityStepSize;
27 room1.rect.x += stepSize * room1.velocity.x;
28 room1.rect.y += stepSize * room1.velocity.y;
29 room2.rect.x += stepSize * room2.velocity.x;
30 room2.rect.y += stepSize * room2.velocity.y;
31 intersected = true;
32 }
33 else {
34 this.rooms[i].velocity = this.rooms[j].velocity = Vec2.zero;
35 }
36 }
37 }
38
39 if(intersected) {
40 this.stepsToConverge++;
41 }
42 else {
43 this.converged = true;
44 console.log('Converged in ', this.stepsToConverge, ' steps.');
45 }
46}
```

## Putting it all together

Not all the code in the demo is explained in this project, but this should give a broad idea of how it works. The final last step, is to continuously call the `updateVelocity`

function, to perform a step, until there are no more intersections. After each step, the dungeon is also drawn on the canvas, which gives the animations. This is done with the following function.

```
1const generate = () => {
2 const dungeon = new DungeonGenerator(settings);
3 dungeon.generate();
4 const drawer = new DungeonDrawer(canvas);
5
6 const animate = () => {
7 canvas.clear();
8 if (!dungeon.step()) {
9 requestAnimationFrame(animate);
10 }
11 else {
12 dungeon.calculateNearestNeighbours();
13 }
14 drawer.draw(dungeon);
15 }
16
17 animate();
18}
```

## Finding the nearest rooms

To draw the lines between the nearest rooms, a nearest neighbour algorithm is used. This is a quite straightforward algorithm, which I will list below:

- For each room
- Calculate the distance to every other room, and store this distance
- Sort this array of distance from low to high.
- Pick the first $n$ elements, which are the nearest neighbours of the room.
- Draw a line to each of them.

The following code will create a graph with this algorithm. This graph is then drawn to the canvas to display the lines between the rooms.

```
1calculateNearestNeighbours() {
2 for(let i = 0; i < this.rooms.length; i++) {
3
4 let distances = [];
5
6 for(let j = 0; j < this.rooms.length; j++) {
7 if(i == j) {
8 continue;
9 }
10 const d = this.rooms[i].center().subtract(this.rooms[j].center()).lengthSquared();
11 distances.push([i, j, d]);
12 }
13
14 distances.sort((first, second) => {
15 return first[2] - second[2];
16 });
17
18 for(let k = 0; k < this.nearestNeighbours; k++) {
19 const neighbour = this.rooms[distances[k][1]];
20 this.rooms[distances[k][0]].neighbours.push(neighbour);
21 this.graph.addEdge(...distances[k]);
22 }
23 }
24}
```

Using this algorithm it is possible that the dungeon is split into multiple subgraphs. This means that the dungeon is disconnected, and a player might not be able to reach the end. This can be solved, by determining the connected components of a graph. In simpler terms, these are the subgraphs that are in a graph, and if there is only one subgraph, we know that we have a completely connected dungeon. An algorithm to find the connected components of a graph can be found in my C# graph library. If subgraphs are found, you could either try to connect them, or simply discard the entire dungeon and generate a new one.

## After thoughts

This algorithm can create quite a variety of rooms. If the step size is low (or gravitational force is low), then the rooms will be clumped together. If some space between the rooms is desired, we could increase the gravitational force, or the step size.

I also thought about a few methods for the corridors. First we could simply draw a corridor for each line, but if slanted corridors are not desired, you could perhaps only use the lines where the slope is almost vertical of horizontal, and discard the rest. This could however result in disconnected rooms, which is a problem. Because everything is randomly generated, at some point it will generate a disconnected dungeon. This is very bad.

Another method is to use the lines as springs, and let them pull the rooms together after they have been placed. They don't have to behave like actual springs, so we could again use this formula to generate some force to attract only the rooms which are connected. I think the end result will give only horizontal and vertical lines, because that gives the shortest distance for the line between the two rooms, but I have not verified this.

Another thing I've noticed is that if there is a big range between the minimum size of a room, and the maximum size of a room, quite ugly "corridor" like rooms are generated. Maybe you like them, maybe not. A method to get rid of them is to define a maximum range between these variables, and if the range is too big, then increase the smaller width/height with the missing range. Another method is to divide the width by the height to create a ratio, and keep generating new rooms until this ratio is between some threshold such as $[0.5, 1.5]$.