Dungeon generation with Newton's law of gravity
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: 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.
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$.
class Rectangle {
constructor(x, y, w, h) {
this.x = x;
this.y = y;
this.w = w;
this.h = h;
}
intersect(rect) {
const x = Math.max(this.x, rect.x);
const n1 = Math.min(this.x + this.w, rect.x + rect.w);
const y = Math.max(this.y, rect.y);
const n2 = Math.min(this.y + this.h, rect.y + rect.h);
if(n1 >= x && n2 >= y) {
return new Rectangle(x, y, n1 - x, n2 - y);
}
else {
return Rectangle.empty;
}
}
static empty = new Rectangle(undefined, undefined, undefined, undefined);
}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.
class Random {
static insideUnitCircle() {
const theta = Math.random() * 2 * Math.PI;
const r = Math.sqrt(Math.random());
return new Vec2(r * Math.cos(theta), r * Math.sin(theta));
}
static exponential() {
var r = Math.random();
return 1 - Math.exp(r) * (1 - r);
}
static uniform() {
return Math.random();
}
}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.
class Room {
constructor(x, y, w, h) {
this.rect = new Rectangle(x, y, w, h);
this.velocity = new Vec2(0);
this.neighbours = [];
}
center() {
return new Vec2(this.rect.w / 2 + this.rect.x, this.rect.h / 2 + this.rect.y);
}
lengthSquared() {
return new Vec2(this.rect.w, this.rect.h).lengthSquared();
}
}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.
generateRooms() {
const r = this.circleRadius;
const range = this.maxRoomSize - this.minRoomSize;
for(let i = 0; i < this.numberOfRooms; i++) {
const p = Random.insideUnitCircle().scale(r);
const w = Random.exponential() * range + this.minRoomSize;
const h = Random.exponential() * range + this.minRoomSize;
const room = new Room(p.x - w/2, p.y - h/2, w, h, this.numberOfRooms);
this.points.push(p);
this.rooms.push(room);
}
}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.
updateVelocity() {
let intersected = false;
for(let i = 0; i < this.rooms.length; i++) {
for(let j = i; j < this.rooms.length; j++) {
if(i == j) {
continue;
}
const intersectedRect = this.rooms[i].rect.intersect(this.rooms[j].rect);
if(intersectedRect != Rectangle.empty) {
// Using an adjusted form of the formula for gravity to calculate
// the force, but is instead used to push the objects apart.
const room1 = this.rooms[i];
const room2 = this.rooms[j];
const m1 = room1.rect.w * room1.rect.h;
const m2 = room2.rect.w * room2.rect.h;
const r = room1.center().subtract(room2.center()).lengthSquared();
const G = this.gravitationalForce;
const fg1 = G * m1 * m2 / r;
const fg2 = G * m1 * m2 / r;
const v1 = room1.center().subtract(room2.center()).normalize();
const v2 = room2.center().subtract(room1.center()).normalize();
const maxV = this.maxVelocity;
room1.velocity = Vec2.clamp(v1.scale(fg1), -maxV, maxV);
room2.velocity = Vec2.clamp(v2.scale(fg2), -maxV, maxV);
const stepSize = this.velocityStepSize;
room1.rect.x += stepSize * room1.velocity.x;
room1.rect.y += stepSize * room1.velocity.y;
room2.rect.x += stepSize * room2.velocity.x;
room2.rect.y += stepSize * room2.velocity.y;
intersected = true;
}
else {
this.rooms[i].velocity = this.rooms[j].velocity = Vec2.zero;
}
}
}
if(intersected) {
this.stepsToConverge++;
}
else {
this.converged = true;
console.log('Converged in ', this.stepsToConverge, ' steps.');
}
}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.
const generate = () => {
const dungeon = new DungeonGenerator(settings);
dungeon.generate();
const drawer = new DungeonDrawer(canvas);
const animate = () => {
canvas.clear();
if (!dungeon.step()) {
requestAnimationFrame(animate);
}
else {
dungeon.calculateNearestNeighbours();
}
drawer.draw(dungeon);
}
animate();
}Finding the nearest rooms
- 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.
calculateNearestNeighbours() {
for(let i = 0; i < this.rooms.length; i++) {
let distances = [];
for(let j = 0; j < this.rooms.length; j++) {
if(i == j) {
continue;
}
const d = this.rooms[i].center().subtract(this.rooms[j].center()).lengthSquared();
distances.push([i, j, d]);
}
distances.sort((first, second) => {
return first[2] - second[2];
});
for(let k = 0; k < this.nearestNeighbours; k++) {
const neighbour = this.rooms[distances[k][1]];
this.rooms[distances[k][0]].neighbours.push(neighbour);
this.graph.addEdge(...distances[k]);
}
}
}