Skip to content

Instantly share code, notes, and snippets.

@endel
Created November 6, 2020 18:45
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save endel/b42cac8770bcf39c41df983230557e66 to your computer and use it in GitHub Desktop.
Simple Dungeon Generation Algorithm. Used in https://github.com/endel/mazmorra/
// Based on: http://breinygames.blogspot.com/2011/07/random-map-generation.html
// Needs improvment:
// - It is possible with small rooms for it to not be closed (i.e. a wall tile missing)
// - Walls often double up (more room spacing?)
var RoomMaze = srm = {
generate: function(gridSize, minRoomSize, maxRoomSize, maxRooms) {
// 1) Create the grid
var grid = [];
for(var x = 0; x < gridSize.x; ++x) {
grid[x] = [];
for(var y = 0; y < gridSize.y; ++y) {
grid[x][y] = helpers.TILE_TYPE.EMPTY;
}
}
// 2) Create a random sized room in the middle of the grid
// 3) Add the new room to a list of all created rooms.
var rooms = [srm.generateRoom(minRoomSize, maxRoomSize)];
srm.placeRoom(
grid,
rooms[0],
(gridSize.x / 2) - (rooms[0].size.x / 2),
(gridSize.y / 2) - (rooms[0].size.y / 2)
);
var area = gridSize.x * gridSize.y,
roomPos = { x: 0, y: 0 };
for(var i = 0; i < area; ++i) {
if(maxRooms && rooms.length === maxRooms)
break;
// 4) Pick a random room from the list of all created rooms.
// 5) Pick a random wall tile from the selected room.
var branchPos = srm.getBranchPosition(grid, rooms),
direction = branchPos.dir;
// 6) Generate a new random sized room.
var room = srm.generateRoom(minRoomSize, maxRoomSize);
roomPos.x = 0;
roomPos.y = 0;
switch(direction) {
case helpers.DIRECTION.NORTH:
roomPos.x = branchPos.x - (room.size.x / 2);
roomPos.y = branchPos.y - room.size.y;
break;
case helpers.DIRECTION.SOUTH:
roomPos.x = branchPos.x - (room.size.x / 2);
roomPos.y = branchPos.y + 1;
break;
case helpers.DIRECTION.EAST:
roomPos.x = branchPos.x + 1;
roomPos.y = branchPos.y - (room.size.y / 2);
break;
case helpers.DIRECTION.WEST:
roomPos.x = branchPos.x - room.size.x;
roomPos.y = branchPos.y - (room.size.y / 2);
break;
}
roomPos.x = ~~roomPos.x;
roomPos.y = ~~roomPos.y;
// 7) See if there is space for the new room next to the selected wall tile of the selected room.
// 8) If yes, continue. If no, go back to step 4.
if(srm.isSpaceForRoom(grid, gridSize, room, roomPos)) {
// 9) Dig out the new room to add it to part of the dungeon, and add it to list of completed rooms.
rooms.push(room);
srm.placeRoom(grid, room, roomPos.x, roomPos.y);
// 10) Turn the wall tile picked in step 5 into a door way to make our new room accessible.
srm.connectRooms(grid, branchPos);
}
// 11) Go back to step 4 until the dungeon is complete.
}
// 12) Add the up and down staircases inside random rooms of the dungeon.
// 13) Finally, add some monsters, items, and gold in random areas of the dungeon.
return grid;
},
generateRoom: function(minSize, maxSize) {
var room = new helpers.Room(),
sx = room.size.x = helpers.randInt(minSize.x, maxSize.x),
sy = room.size.y = helpers.randInt(minSize.y, maxSize.y),
tiles = room.tiles,
walls = room.walls,
col,
wall;
for(var x = 0; x < sx; ++x) {
tiles.push(col = []);
for(var y = 0; y < sy; ++y) {
if(x === 0 || x === sx - 1 || y === 0 || y === sy - 1) {
var type = helpers.TILE_TYPE.WALL,
dir = helpers.DIRECTION.NONE,
corner = false;
//store position of normal walls (not corners)
if(y !== 0 && y !== sy - 1) {
if(x === 0) {
dir = helpers.DIRECTION.WEST;
} else if(x === sx - 1) {
dir = helpers.DIRECTION.EAST;
}
} else if(x !== 0 && x !== sx - 1) {
if(y === 0) {
dir = helpers.DIRECTION.NORTH;
} else if(y === sy - 1) {
dir = helpers.DIRECTION.SOUTH;
}
}
//add corners
else {
corner = true;
if(x === 0 && y === 0) {
dir = helpers.DIRECTION.NORTH;
} else if(x === 0 && y === sy - 1) {
dir = helpers.DIRECTION.WEST;
} else if(x === sx - 1 && y === 0) {
dir = helpers.DIRECTION.EAST;
} else if(x === sx - 1 && y === sy - 1) {
dir = helpers.DIRECTION.SOUTH;
}
}
walls.push({ x: x, y: y, dir: dir, corner: corner });
col.push(type | dir | (corner ? helpers.CORNER : 0));
} else {
col.push(helpers.TILE_TYPE.FLOOR);
}
}
}
return room;
},
placeRoom: function(grid, room, px, py) {
px = ~~px;
py = ~~py;
room.position.x = px;
room.position.y = py;
var tx = 0,
ty = 0;
//copy the tiles from this room into the grid
for(var x = px; x < (px + room.size.x); ++x) {
for(var y = py; y < (py + room.size.y); ++y) {
grid[x][y] = room.tiles[tx][ty];
ty++;
}
tx++;
ty = 0;
}
},
getBranchPosition: function(grid, rooms) {
var room = helpers.randElm(rooms),
wall = helpers.randElm(room.walls.filter(function(v) { return !v.corner; }));
return { x: wall.x + room.position.x, y: wall.y + room.position.y, dir: wall.dir };
},
isSpaceForRoom: function(grid, gridSize, room, roomPos) {
var mx = roomPos.x + room.size.x,
my = roomPos.y + room.size.y;
//check x size
if(roomPos.x < 0 || mx > gridSize.x)
return false;
//check y size
if(roomPos.y < 0 || my > gridSize.y)
return false;
//check if any tiles of this room intersect another room
for(var x = roomPos.x; x < mx; ++x) {
for(var y = roomPos.y; y < my; ++y) {
if(grid[x][y] !== helpers.TILE_TYPE.EMPTY) {
return false;
}
}
}
return true;
},
connectRooms: function(grid, branchPos) {
grid[branchPos.x][branchPos.y] = helpers.TILE_TYPE.FLOOR;
switch(branchPos.dir) {
case helpers.DIRECTION.NORTH:
grid[branchPos.x][branchPos.y - 1] = helpers.TILE_TYPE.FLOOR;
break;
case helpers.DIRECTION.SOUTH:
grid[branchPos.x][branchPos.y + 1] = helpers.TILE_TYPE.FLOOR;
break;
case helpers.DIRECTION.EAST:
grid[branchPos.x + 1][branchPos.y] = helpers.TILE_TYPE.FLOOR;
break;
case helpers.DIRECTION.WEST:
grid[branchPos.x - 1][branchPos.y] = helpers.TILE_TYPE.FLOOR;
break;
}
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment