I made a primitive dungeon generator (on pure JavaScript) that creates nearby rooms. Link to a working piece of code is in the bottom of post.
Now I am stuck: I need to make a good system of doors and passages between rooms, but I find it difficult to come up with a suitable algorithm. Technically, there is no problem: it's easy to make holes in the walls and even make sure that all parts of the dungeon are connected to each other.
The problem is to find a suitable idea for connecting rooms. Screw all possible connections and close excess? Choose a large room and pull a few corridors out of it, and then connect the remaining rooms to the common system? Start from a corner and move chaotically until all rooms are connected?
I will be very grateful for any idea or advice.
Update. Question is solved. With the help of raul.vila it was possible to bring the algorithm to the working state. Now the generator does the minimum number of doors necessary to get to each room, and then creates several additional doors to improve the connectivity of the dungeon.
Old code: https://jsfiddle.net/Gerasim/f2a8ujpy/3/
Final code: https://jsfiddle.net/Gerasim/f2a8ujpy/29/
var canvas = document.getElementById("canvas");
var ctx = canvas.getContext("2d");
const DWIDTH = 32; // Dungeon width
const DHEIGHT = 32; // Dungeon height
const ROOMINTERVAL = 8; // Room density (3+)
const MINROOM = 3; // Min room size. Must be ROOMINTERVAL - 2 or bigger
const EXTRADOORS = 5; // Additional doors for better connectivity
arrayInstruments();
genDungeon();
showDungeon();
// Displays primitive map of the dungeon
function showDungeon() {
for (var x = 0; x < DWIDTH; x++) {
for (var y = 0; y < DHEIGHT; y++) {
switch (dungeon[x][y]) {
case 0:
ctx.beginPath();
ctx.fillStyle = "lightgrey";
ctx.rect(x * 20, y * 20, 18, 18);
ctx.fill();
break;
case 1:
ctx.beginPath();
ctx.fillStyle = "black";
ctx.rect(x * 20, y * 20, 18, 18);
ctx.fill();
break;
case 2:
ctx.beginPath();
ctx.fillStyle = "black";
ctx.rect(x * 20 + 1, y * 20 + 1, 16, 16);
ctx.rect(x * 20 + 12, y * 20 + 6, 2, 4);
ctx.stroke();
break;
}
}
}
}
// Generates dungeon of rooms and doors
function genDungeon() {
// Fill full dungeon with walls
dungeon = new Array();
dungeon.dup(1, 0, 0, DWIDTH, DHEIGHT);
// Create random seeds of growth in size MINROOM x MINROOM
var seeds = new Array();
while (true) {
var free = dungeon.biggestFree(0, 0, 0, DWIDTH, DHEIGHT);
if (free.biggest < ROOMINTERVAL) {
break;
} else {
roomX = free.x + 1 + rnd(free.biggest - 1 - MINROOM);
roomY = free.y + 1 + rnd(free.biggest - 1 - MINROOM);
dungeon.dup(0, roomX, roomY, MINROOM, MINROOM);
seeds.push({
x: roomX,
y: roomY,
width: MINROOM,
height: MINROOM,
delete: "no"
});
}
}
var rooms = [];
// Now we have seeds of growth in array rooms.
// Lets try to expand seeds by moving their walls
while (seeds.length > 0) {
for (var i = 0; i < seeds.length; i++) {
// Determine the directions in which the room can grow
var dirs = [];
if (seeds[i].x >= 2 && dungeon.freeRect(0, seeds[i].x - 2, seeds[i].y - 1, 1, seeds[i].height + 2)) {
dirs.push('left');
}
if (seeds[i].x + seeds[i].width < DWIDTH - 1 && dungeon.freeRect(0, seeds[i].x + seeds[i].width + 1, seeds[i].y - 1, 1, seeds[i].height + 2)) {
dirs.push('right');
}
if (seeds[i].y >= 2 && dungeon.freeRect(0, seeds[i].x - 1, seeds[i].y - 2, seeds[i].width + 2, 1)) {
dirs.push('up');
}
if (seeds[i].y + seeds[i].height < DHEIGHT - 1 && dungeon.freeRect(0, seeds[i].x - 1, seeds[i].y + seeds[i].height + 1, seeds[i].width + 2, 1)) {
dirs.push('down');
}
// Now expand room in random direction
if (dirs.length > 0) {
dirs.shuffle();
if (dirs[0] == 'left') {
dungeon.dup(0, seeds[i].x - 1, seeds[i].y, 1, seeds[i].height);
seeds[i].x--;
seeds[i].width++;
}
if (dirs[0] == 'right') {
dungeon.dup(0, seeds[i].x + seeds[i].width, seeds[i].y, 1, seeds[i].height);
seeds[i].width++;
}
if (dirs[0] == 'up') {
dungeon.dup(0, seeds[i].x, seeds[i].y - 1, seeds[i].width, 1);
seeds[i].y--;
seeds[i].height++;
}
if (dirs[0] == 'down') {
dungeon.dup(0, seeds[i].x, seeds[i].y + seeds[i].height, seeds[i].width, 1);
seeds[i].height++;
}
} else {
seeds[i].delete = "yes";
rooms.push(seeds[i]);
}
seeds = seeds.filter(o => o.delete == "no");
}
}
// Make required doors
var startRoom = rooms[0];
startRoom.parentRoom = startRoom;
connectToOtherRooms(rooms, startRoom);
// Make extra doors
var i = EXTRADOORS;
var limiter = 1000; // protection from an infinite loop
while (i > 0 && limiter > 0) {
if (connectToRandom(rooms)) {
i--;
}
limiter--;
}
}
// Makes tree of rooms
function connectToOtherRooms(rooms, currentRoom) {
var adyacentRoom = connectToAdyacent(rooms, currentRoom);
if (adyacentRoom) {
connectToOtherRooms(rooms, adyacentRoom);
} else {
if (currentRoom.parentRoom == currentRoom) {
return;
} else {
connectToOtherRooms(rooms, currentRoom.parentRoom);
}
}
}
// Makes door to the adyacent room
function connectToAdyacent(rooms, room) {
var nonVisitedRooms = rooms.filter(o => o != room && !o.parentRoom);
for (var i = 0; i < nonVisitedRooms.length; i++) {
var nonVisitedRoom = nonVisitedRooms[i];
if (makeDoor(room, nonVisitedRoom)) {
nonVisitedRoom.parentRoom = room;
return nonVisitedRoom;
}
}
}
// Makes door to the random room nearby
function connectToRandom(allRooms) {
var room = rnd(allRooms.length);
for (var i = 0; i < allRooms.length; i++) {
if (makeDoor(allRooms[room], allRooms[i])) {
return true;
}
}
return false;
}
// Makes door between two rooms
function makeDoor(room1, room2) {
var walls = commonWalls(room1, room2);
if (walls && !foundDoor(walls)) {
walls.shuffle();
dungeon[walls[0].x][walls[0].y] = 2;
return true;
} else {
return false;
}
}
// Checks if there is a door in walls already to avoid double doors
function foundDoor(walls) {
for (var i = 0; i < walls.length; i++) {
if (dungeon[walls[i].x][walls[i].y] > 1) {
return true;
}
}
return false;
}
// Returns array of cells between two rooms (if any)
function commonWalls(room1, room2) {
var walls = new Array();
var per1 = perimeter(room1);
var per2 = perimeter(room2);
for (var i = 0; i < per1.length; i++) {
var common = per2.filter(o => o.x == per1[i].x && o.y == per1[i].y);
if (common.length > 0) {
walls.push(common[0]);
}
}
if (walls.length > 0) {
return walls;
} else {
return false;
}
}
// Returns array of cells on the external perimeter of room
// Corner cells are excluded, since the door is not made there
function perimeter(room) {
var per = new Array();
for (x = room.x; x < room.x + room.width; x++) {
per.push({
x: x,
y: room.y - 1
});
per.push({
x: x,
y: room.y + room.height
});
}
for (y = room.y; y < room.y + room.height; y++) {
per.push({
x: room.x - 1,
y: y
});
per.push({
x: room.x + room.width,
y: y
});
}
return per;
}
// rnd(4): returns 0, 1, 2 or 3
function rnd(ceil) {
return Math.floor(Math.random() * ceil);
}
// Several instruments that I need to work with arrays
function arrayInstruments() {
// Shuffles array in random order
Array.prototype.shuffle = function() {
var j, temp;
for (var i = 0; i < this.length; i++) {
j = rnd(this.length);
temp = this[i];
this[i] = this[j];
this[j] = temp;
}
return (this);
}
// Fills rectangle in 2D-array with filler
Array.prototype.dup = function(filler, startX, startY, lengthX, lengthY) {
for (var x = startX; x < startX + lengthX; x++) {
if (!Array.isArray(this[x])) {
this[x] = new Array();
}
for (var y = startY; y < startY + lengthY; y++) {
this[x][y] = filler;
}
}
}
// Checks whether the specified area of the two-dimensional array is free of filler
// If it is free, it returns true
Array.prototype.freeRect = function(filler, startX, startY, lengthX, lengthY) {
for (var x = startX; x < startX + lengthX; x++) {
for (var y = startY; y < startY + lengthY; y++) {
if (this[x][y] == filler) {
return false;
}
}
}
return true;
}
// Returns the coordinates of the largest empty square.
// If there are several equally large empty squares, returns the coordinates of the random
Array.prototype.biggestFree = function(filler, startX, startY, lengthX, lengthY) {
var found = new Array();
for (biggest = Math.min(lengthX, lengthY); biggest > 0; biggest--) {
for (var x = startX; x <= startX + lengthX - biggest; x++) {
for (var y = startY; y <= startY + lengthY - biggest; y++) {
if (this.freeRect(filler, x, y, biggest, biggest)) {
found.push({
x: x,
y: y
});
}
}
}
if (found.length > 0) {
found.shuffle();
return {
biggest: biggest,
x: found[0].x,
y: found[0].y
};
}
}
}
}
I'll try to describe an algorithm. The idea is to create a tree starting from a random room and visiting all rooms going from the current room to a non-visited adyacent one.
This should work:
currentRoom variable pointing to a random initial roomcurrentRoom.parentRoom = currentRoom, a trick to identify the initial roomcurrentRoom:
adyNonVisRooms), you can check if a room has a parentRoom property defined to see if it has been visitedadyNonVisRooms.length > 0:
nextRoom = adyNonVisRooms[0] (you can get a random room for a non-deterministic result)currentRoom with nextRoom adding a doornextRoom.parentRoom = currentRoomcurrentRoom = nextRoomadyNonVisRooms.length == 0:
currentRoom == currentRoom.parentRoom:
adyNonVisRooms)adyNonVisRooms.length > 0: goto 321adyNonVisRooms.length == 0: EXITcurrentRoom != currentRoom.parentRoom:
currentRoom = currentRoom.parentRoomI have a working version, you will need to work a bit to get random room positions (functions connectIfOnTop and connectIfOnRight): Jsfiddle
var canvas = document.getElementById("canvas");
var ctx = canvas.getContext("2d");
const DWIDTH = 32; // Dungeon width
const DHEIGHT = 32; // Dungeon height
const ROOMINTERVAL = 8; // Room density (3+)
const MINROOM = 2; // Min room size. Must be ROOMINTERVAL - 2 or bigger
arrayInstruments();
genDungeon();
showDungeon();
function showDungeon() {
for (var x = 0; x < DWIDTH; x++) {
for (var y = 0; y < DHEIGHT; y++) {
ctx.beginPath();
ctx.rect(x * 20, y * 20, 18, 18);
if (dungeon[x][y] == 1) {
ctx.fillStyle = "black";
} else {
ctx.fillStyle = "lightgrey";
}
ctx.fill();
}
}
}
function genDungeon() {
// Fill dungeon with walls
dungeon = new Array();
dungeon.dup(1, 0, 0, DWIDTH, DHEIGHT);
// Create random seeds of growth in size MINROOM x MINROOM
var rooms = new Array();
while (true) {
var free = dungeon.biggestFree(0, 0, 0, DWIDTH, DHEIGHT);
if (free.biggest < ROOMINTERVAL) {
break;
} else {
roomX = free.x + 1 + rnd(free.biggest - 1 - MINROOM);
roomY = free.y + 1 + rnd(free.biggest - 1 - MINROOM);
dungeon.dup(0, roomX, roomY, MINROOM, MINROOM);
rooms.push({
x: roomX,
y: roomY,
width: MINROOM,
height: MINROOM,
delete: "no"
});
}
}
var finalRooms = [];
// Now we have seeds of growth in array rooms.
// Lets try to expand seeds by moving their walls
while (rooms.length > 0) {
for (i = 0; i < rooms.length; i++) {
// Determine the directions in which the room can grow
var dirs = [];
if (rooms[i].x >= 2 && dungeon.freeRect(0, rooms[i].x - 2, rooms[i].y - 1, 1, rooms[i].height + 2)) {
dirs.push('left');
}
if (rooms[i].x + rooms[i].width < DWIDTH - 1 && dungeon.freeRect(0, rooms[i].x + rooms[i].width + 1, rooms[i].y - 1, 1, rooms[i].height + 2)) {
dirs.push('right');
}
if (rooms[i].y >= 2 && dungeon.freeRect(0, rooms[i].x - 1, rooms[i].y - 2, rooms[i].width + 2, 1)) {
dirs.push('up');
}
if (rooms[i].y + rooms[i].height < DHEIGHT - 1 && dungeon.freeRect(0, rooms[i].x - 1, rooms[i].y + rooms[i].height + 1, rooms[i].width + 2, 1)) {
dirs.push('down');
}
// Now expand room in random direction
if (dirs.length > 0) {
dirs.shuffle();
if (dirs[0] == 'left') {
dungeon.dup(0, rooms[i].x - 1, rooms[i].y, 1, rooms[i].height);
rooms[i].x--;
rooms[i].width++;
}
if (dirs[0] == 'right') {
dungeon.dup(0, rooms[i].x + rooms[i].width, rooms[i].y, 1, rooms[i].height);
rooms[i].width++;
}
if (dirs[0] == 'up') {
dungeon.dup(0, rooms[i].x, rooms[i].y - 1, rooms[i].width, 1);
rooms[i].y--;
rooms[i].height++;
}
if (dirs[0] == 'down') {
dungeon.dup(0, rooms[i].x, rooms[i].y + rooms[i].height, rooms[i].width, 1);
rooms[i].height++;
}
} else {
rooms[i].delete = "yes";
}
finalRooms = finalRooms.concat(rooms.filter(o => o.delete == "yes"));
rooms = rooms.filter(o => o.delete == "no");
}
}
var startRoom = finalRooms[0];
startRoom.parentRoom = startRoom;
connectToOtherRooms(dungeon, finalRooms, startRoom);
}
function connectToOtherRooms(dungeon, allRooms, currentRoom) {
var adyacentRoom = connectToAdyacent(dungeon, allRooms, currentRoom);
if (adyacentRoom) {
connectToOtherRooms(dungeon, allRooms, adyacentRoom);
} else {
if (currentRoom.parentRoom == currentRoom) {
return;
} else {
connectToOtherRooms(dungeon, allRooms, currentRoom.parentRoom);
}
}
}
// {x: 9, y: 12, width: 3, height: 6, delete: "yes"}
function connectToAdyacent(dungeon, allRooms, room) {
var nonVisitedRooms = allRooms.filter(function(r) {
return (r != room) && !r.parentRoom;
});
for (var i = 0; i < nonVisitedRooms.length; i++) {
var nonVisitedRoom = nonVisitedRooms[i];
if (connectIfAdyacent(dungeon, room, nonVisitedRoom)) {
nonVisitedRoom.parentRoom = room;
return nonVisitedRoom;
}
}
}
function connectIfAdyacent(dungeon, room1, room2) {
return connectIfOnTop(dungeon, room1, room2) ||
connectIfOnTop(dungeon, room2, room1) ||
connectIfOnRight(dungeon, room1, room2) ||
connectIfOnRight(dungeon, room2, room1);
}
function connectIfOnTop(dungeon, roomBase, room) {
var roomBase_x1 = roomBase.x - 1;
var roomBase_x2 = roomBase.x + roomBase.width;
var roomBase_y1 = roomBase.y - 1;
//var roomBase_y2 = roomBase.y + roomBase.height;
var room_x1 = room.x - 1;
var room_x2 = room.x + room.width;
var room_y1 = room.y - 1;
var room_y2 = room.y + room.height;
if (
room_y2 == roomBase_y1 &&
(room_x1 < (roomBase_x2 - 1)) &&
(room_x2 > (roomBase_x1 + 1))
) {
dungeon[Math.max(room_x1, roomBase_x1) + 1][room_y2] = 0;
return true;
}
}
function connectIfOnRight(dungeon, roomBase, room) {
var roomBase_x1 = roomBase.x - 1;
//var roomBase_x2 = roomBase.x + roomBase.width;
var roomBase_y1 = roomBase.y - 1;
var roomBase_y2 = roomBase.y + roomBase.height;
var room_x1 = room.x - 1;
var room_x2 = room.x + room.width;
var room_y1 = room.y - 1;
var room_y2 = room.y + room.height;
if (
room_x2 == roomBase_x1 &&
(room_y1 < (roomBase_y2 - 1)) &&
(room_y2 > (roomBase_y1 + 1))
) {
dungeon[room_x2][Math.max(room_y1, roomBase_y1) + 1] = 0;
return true;
}
}
// rnd(4): returns 0, 1, 2 or 3
function rnd(ceil) {
return Math.floor(Math.random() * ceil);
}
// Several instruments that I need to work with arrays
function arrayInstruments() {
// Shuffles array in random order
Array.prototype.shuffle = function() {
var j, temp;
for (var i = 0; i < this.length; i++) {
j = rnd(this.length);
temp = this[i];
this[i] = this[j];
this[j] = temp;
}
return (this);
}
// Fills rectangle in 2D-array with filler
Array.prototype.dup = function(filler, startX, startY, lengthX, lengthY) {
for (var x = startX; x < startX + lengthX; x++) {
if (!Array.isArray(this[x])) {
this[x] = new Array();
}
for (var y = startY; y < startY + lengthY; y++) {
this[x][y] = filler;
}
}
}
// Checks whether the specified area of the two-dimensional array is free of filler
// If it is free, it returns true
Array.prototype.freeRect = function(filler, startX, startY, lengthX, lengthY) {
for (var x = startX; x < startX + lengthX; x++) {
for (var y = startY; y < startY + lengthY; y++) {
if (this[x][y] == filler) {
return false;
}
}
}
return true;
}
// Returns the coordinates of the largest empty square.
// If there are several equally large empty squares, returns the coordinates of the random
Array.prototype.biggestFree = function(filler, startX, startY, lengthX, lengthY) {
var found = new Array();
for (biggest = Math.min(lengthX, lengthY); biggest > 0; biggest--) {
for (var x = startX; x <= startX + lengthX - biggest; x++) {
for (var y = startY; y <= startY + lengthY - biggest; y++) {
if (this.freeRect(filler, x, y, biggest, biggest)) {
found.push({
x: x,
y: y
});
}
}
}
if (found.length > 0) {
found.shuffle();
return {
biggest: biggest,
x: found[0].x,
y: found[0].y
};
}
}
}
}* {
padding: 0;
margin: 0;
}
canvas {
background: eee;
display: block;
margin: 0 auto;
}<html>
<head>
<title>Maze Generator</title>
<meta charset="utf-8" />
</head>
<body>
<div style="padding: 15;">
<canvas id="canvas" width="640" height="640" style="background: lightgrey"></canvas>
</div>
</body>
</html>