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.

The demo has the following variables that can be altered to change the result of the algorithm:

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: the maximum width/height of a room.
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.

The rest of this post will explain the various techniques that have been used to in this demo.

Vectors & Math

The first thing I did was to define a vector class for a 2D vector, which simplifies a lot of the mathematical operations. The vector class has the following methods that are used in the demo: addition/subtraction, scaling, dot product, length, length squared (faster if the distance isn't used properly), and normalize. The entire implementation can be found here, because otherwise this post would get very long.

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

To randomly generated the width and the height of the rooms, I wanted a function that usually creates a small room, and sometimes a big room. Luckily there is the exponential function $e^x$, which we can use to create such a function. If we multiply $e^x$ by $(1-x)$, we can shape the function such that $f(0) = 1$, and $f(1) = 0$. If we then subtract this from $1$, we get our function $f(x) = 1 - e^x(1-x)$. The graph below shows this function $f$ (in orange):

If we look at the orange function, we can see that if $y = 0.6$, then $x \approx 0.82$. We will then generate a random uniform variable $\underline{x} \in [0, 1]$, and evaluate $f(\underline{x})$ to generate the width and the height of the room.

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

If we recall that Newton's law of gravity is

$$ F = \dfrac{G\cdot m_1\cdot m_2}{r^2}\cdot\hat{r} $$

where $F$ is the force, $G$ is the gravitational constant, $m_1$ the mass of the first object, $m_2$ the mass of the second object, and $r^2$ is the squared distance between the center of mass between those objects, and $\hat{r}$ is the vector between the objects, which is normalized).

The force $F$ that is calculated will be used as the velocity, so instead of attracting, we want to repel, which means that we should use $-F$. We will then use this velocity and use "Euler integration" to change the position of the room. This basically means is that at each step, we are going to add a little bit of the velocity to the position of the room. How much velocity is added, is based on the step size $h$.

Now to move the rooms, we are going to check if there are any intersections. If there are intersections, then we will run the this algorithm to move the rooms.

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.

If there are no intersections, then the algorithm has finished. If we implement this, we get the following function that performs a single step of the algorithm.

 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]$.