While working on a game (which is currently only a concept), I came to the point at which I wanted to know, how I can generate my dungeon levels. They should not all look the same and I am a one-man team at that project, so I want to procedurally generate the levels.
My dungeons shall have one entry point and multiple exit points. Every point in the dungeon has to be reachable. There are no rooms and no puzzles - only some enemies running around, which can be scattered over the whole dungeon map. The combat system is round-based and if you collide with an enemy, a fight will start. The player can move in four directions at any given time, as long as there is floor he can walk on.
For this article, the code is written in JavaScript but could of course be translated into any other language of your choice.
First, let's create a simple HTML page on which the code can run and add the CSS, so that we can actually see what we are creating.
<!doctype html>
<html>
<head>
<link rel="stylesheet" href="grid.css"/>
</head>
<body>
<div id="grid"></div>
<script src="generator.js"></script>
</body>
</html>
#grid {
height: 600px; /* (tile height + border size * 2) * grid height */
width: 600px; /* (tile width + border size * 2) * grid width */
}
span {
background: #ccc;
border: 2px solid #ddd;
display: inline-block;
height: 20px;
text-align: center;
width: 20px;
}
span.full {background: #e55;}
span.door-n {border-top-color: #009;}
span.door-e {border-right-color: #009;}
span.door-s {border-bottom-color: #009;}
span.door-w {border-left-color: #009;}
span.startdoor {background: #ee5;}
span.startdoor-n {border-top-color: #c99;}
span.startdoor-e {border-right-color: #c99;}
span.startdoor-s {border-bottom-color: #c99;}
span.startdoor-w {border-left-color: #c99;}
Now that we have set up the base, create a new JavaScript file (generator.js).
First we need to define some constants, with which we can later tweak the output.
(function() {
'use strict';
const GRID_WIDTH = 25;
const GRID_HEIGHT = 25;
const PCG_FILLED_TILES = Math.floor((GRID_WIDTH * GRID_HEIGHT) / 2);
const TILE_TYPE_EMPTY = 0;
const TILE_TYPE_FULL = 1;
let gridElement = document.getElementById('grid');
}());
Next we create the grid as a two-dimensional array, in which we later put the information what is on which tile. As a sidenote, it might be actually faster to use a one-dimensional array here, but for this article, it should be fast enough to not do that.
// ...
function createGrid() {
let grid = [];
for (let y = 0; y < GRID_HEIGHT; ++y) {
grid[y] = [];
for (let x = 0; x < GRID_WIDTH; ++x) {
grid[y][x] = TILE_TYPE_EMPTY;
}
}
return grid;
}
//...
Now that we have the grid ready, we can actually draw it:
// ...
function drawMap(map) {
for (let y = 0; y < GRID_HEIGHT; ++y) {
for (let x = 0; x < GRID_WIDTH; ++x) {
let span = document.createElement('span');
span.innerHTML = map[y][x];
gridElement.appendChild(span);
}
let breaking = document.createElement('br');
gridElement.appendChild(breaking);
}
}
// ...
To actually see something, we of course have to call our functions somewhere:
(function() {
// definitions
function createGrid() {/*...*/}
function drawMap(map) {/*...*/}
let map = createGrid();
drawMap(map);
}());
If you open now the HTML page in a browser, you should see something like the following:
As a starting point, we just randomly put "full" tiles on the map as long as PCG_FILLED_TILES is not yet reached. "full" tiles will be later those, on which the player can run around.
// ...
// The minimum is inclusive and the maximum is exclusive
function getRandomInt(min, max) {
min = Math.ceil(min);
max = Math.floor(max);
return Math.floor(Math.random() * (max - min)) + min;
}
function generateFullTiles(map) {
let foundTileCounter = 0;
while(PCG_FILLED_TILES != foundTileCounter) {
let x = getRandomInt(0, GRID_WIDTH);
let y = getRandomInt(0, GRID_HEIGHT);
if (TILE_TYPE_EMPTY != map[y][x]) {
continue;
}
map[y][x] = TILE_TYPE_FULL;
foundTileCounter++;
}
return map;
}
// ...
To be able to see the difference better when drawing the map, we need to change our draw function a little:
// ...
function drawMap(map) {
for (let y = 0; y < GRID_HEIGHT; ++y) {
for (let x = 0; x < GRID_WIDTH; ++x) {
let span = document.createElement('span');
span.innerHTML = map[y][x];
// ! color the tile in a different color to show the difference better
if (TILE_TYPE_FULL == map[y][x]) {
span.classList.add('full');
}
gridElement.appendChild(span);
}
let breaking = document.createElement('br');
gridElement.appendChild(breaking);
}
}
// ...
Just call map = generateFullTiles(map); now before drawing the map and you should get a result similar to:
As you might see on this output, it might be possible now to get tiles which are not connected to other tiles. This can make the player stuck, so he cannot even move at all and is therfor undesired behavior of our generator.
To have every tile at least be connected to one more tile, we will now check the four directions. To do this, we change our generateFullTiles function:
// ...
function generateFullTiles(map) {
let foundTileCounter = 0;
let openTiles = [];
const xStart = getRandomInt(0, GRID_WIDTH);
const yStart = getRandomInt(0, GRID_HEIGHT);
while(PCG_FILLED_TILES != foundTileCounter) {
let x = -1;
let y = -1;
if (openTiles.length > 0) {
let tile = openTiles.shift();
x = tile.x;
y = tile.y;
}
// if x is set then we expect y to be set too, so we do not check at this point for it
if (x < 0) {
x = xStart;
y = yStart;
}
if (TILE_TYPE_EMPTY != map[y][x]) {
continue;
}
map[y][x] = TILE_TYPE_FULL;
foundTileCounter++;
// north
if (y > 0 && map[y - 1][x] == TILE_TYPE_EMPTY) {
let newTile = {x: x, y: y - 1};
openTiles[openTiles.length] = newTile;
}
// east
if (x < GRID_WIDTH - 1 && map[y][x + 1] == TILE_TYPE_EMPTY) {
let newTile = {x: x + 1, y: y};
openTiles[openTiles.length] = newTile;
}
// south
if (y < GRID_HEIGHT - 1 && map[y + 1][x] == TILE_TYPE_EMPTY) {
let newTile = {x: x, y: y + 1};
openTiles[openTiles.length] = newTile;
}
// west
if (x > 0 && map[y][x - 1] == TILE_TYPE_EMPTY) {
let newTile = {x: x - 1, y: y};
openTiles[openTiles.length] = newTile;
}
}
return map;
}
// ...
The results are looking already better, but there is not enough variance in my opinion, because it is mostly a big blob of a map.
To get a more nice looking map, we can reduce the number of used connections. For this the map can be shuffled every time, that we use it and additionally tiles can be removed from the list randomly. Another change to our generateFullTiles can look like this:
// ...
function shuffleArray(array) {
for (let i = array.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[array[i], array[j]] = [array[j], array[i]];
}
}
function generateFullTiles(map) {
let foundTileCounter = 0;
let openTiles = [];
let allOpenTiles = [];
const xStart = getRandomInt(0, GRID_WIDTH);
const yStart = getRandomInt(0, GRID_HEIGHT);
while(PCG_FILLED_TILES != foundTileCounter) {
shuffleArray(openTiles);
shuffleArray(allOpenTiles);
let x = -1;
let y = -1;
if (openTiles.length > 0) {
let tile = openTiles.shift();
x = tile.x;
y = tile.y;
if (openTiles.length > 1 && getRandomInt(0,20) > 4) {
openTiles.shift();
}
if (openTiles.length > 1 && getRandomInt(0,20) > 2) {
openTiles.shift();
}
}
if (x < 0 && allOpenTiles.length > 0) {
let tile = allOpenTiles[0];
x = tile.x;
y = tile.y;
}
if (x < 0) {
x = xStart;
y = yStart;
}
if (TILE_TYPE_EMPTY != map[y][x]) {
continue;
}
map[y][x] = TILE_TYPE_FULL;
foundTileCounter++;
// north
if (y > 0 && map[y - 1][x] == TILE_TYPE_EMPTY) {
let newTile = {x: x, y: y - 1};
openTiles[openTiles.length] = newTile;
allOpenTiles[allOpenTiles.length] = newTile;
}
// east
if (x < GRID_WIDTH - 1 && map[y][x + 1] == TILE_TYPE_EMPTY) {
let newTile = {x: x + 1, y: y};
openTiles[openTiles.length] = newTile;
allOpenTiles[allOpenTiles.length] = newTile;
}
// south
if (y < GRID_HEIGHT - 1 && map[y + 1][x] == TILE_TYPE_EMPTY) {
let newTile = {x: x, y: y + 1};
openTiles[openTiles.length] = newTile;
allOpenTiles[allOpenTiles.length] = newTile;
}
// west
if (x > 0 && map[y][x - 1] == TILE_TYPE_EMPTY) {
let newTile = {x: x - 1, y: y};
openTiles[openTiles.length] = newTile;
allOpenTiles[allOpenTiles.length] = newTile;
}
}
return map;
}
// ...
So here is the end result of creating tiles on which the player can move.
For the attention-keeping reader, you might have noticed, that in the beginning I also spoke about entry and exit points on the map. For this, we now should also look at where we can create doors to our map.
As first step, we need to find every possible entry point, which is in this case every tile that has at least one empty neighbour or is at the edge of the map.
// ...
function getPossibleDoorTiles(map) {
let doorTiles = [];
for (let y = 0; y < GRID_HEIGHT; ++y) {
for (let x = 0; x < GRID_WIDTH; ++x) {
const isTileFull = map[y][x] == TILE_TYPE_FULL;
const isNorthEmpty = y == 0 || map[y - 1][x] == TILE_TYPE_EMPTY;
const isEastEmpty = x == GRID_WIDTH - 1 || map[y][x + 1] == TILE_TYPE_EMPTY;
const isSouthEmpty = y == GRID_HEIGHT - 1 || map[y + 1][x] == TILE_TYPE_EMPTY;
const isWestEmpty = x == 0 || map[y][x - 1] == TILE_TYPE_EMPTY;
if (isTileFull && (isNorthEmpty || isEastEmpty || isSouthEmpty || isWestEmpty))
{
doorTiles[doorTiles.length] = {
x: x, y: y,
n: isNorthEmpty,
e: isEastEmpty,
s: isSouthEmpty,
w: isWestEmpty
};
}
}
}
return doorTiles;
}
// ...
To be able to see the found possible doors, we add another draw method, which mainly marks the possible doors in a different border color.
// ...
function getSpanForGridPos(x, y) {
const spanNumber = y * GRID_HEIGHT + x;
return gridElement.getElementsByTagName('span')[spanNumber];
}
function drawPossibleDoors(possibleDoorTiles) {
for (let i = 0; i < possibleDoorTiles.length; ++i) {
let span = getSpanForGridPos(possibleDoorTiles[i].x, possibleDoorTiles[i].y);
if (possibleDoorTiles[i].n) {
span.classList.add('door-n');
}
if (possibleDoorTiles[i].e) {
span.classList.add('door-e');
}
if (possibleDoorTiles[i].s) {
span.classList.add('door-s');
}
if (possibleDoorTiles[i].w) {
span.classList.add('door-w');
}
}
}
// ...
The output of this might then look like this:
Now that we have all possible doors, we simply have to pick a door randomly from the list and mark it as our entry point. Additionally we add another draw method to mark the entrance.
// ...
function getStartDoor(possibleDoorTiles) {
const doorTile = possibleDoorTiles[getRandomInt(0, possibleDoorTiles.length - 1)];
let directions = ['n', 'e', 's', 'w'];
while(true) {
const pickedDirection = directions[getRandomInt(0, directions.length - 1)];
if (doorTile[pickedDirection]) {
return {tile: doorTile, dir: pickedDirection};
}
let index = directions.indexOf(pickedDirection);
if (index > -1) {
directions.splice(index, 1);
}
}
}
function drawStartDoor(startDoor) {
let span = getSpanForGridPos(startDoor.tile.x, startDoor.tile.y);
if (startDoor.dir == 'n') {
span.classList.add('startdoor-n');
}
if (startDoor.dir == 'e') {
span.classList.add('startdoor-e');
}
if (startDoor.dir == 's') {
span.classList.add('startdoor-s');
}
if (startDoor.dir == 'w') {
span.classList.add('startdoor-w');
}
span.classList.add('startdoor');
span.innerHTML = 'S';
}
// ...
This is now the end result for this article:
We have a generated dungeon level with an entry point on a 2D grid. Now the question is, how does a player leave a dungeon level. There are multiple possibilities here - for example creating one or more exit doors based on the distance of the entry, getting a staircase when the player killed all enemies on the map or simply using the entry door also as the exit.
Speaking of enemies - they have to be placed randomly somewhere on the map and probably should have at least some distance to each other.
You might also want to add some collectable items, so that the player can heal in between fights, or get for example some iron for somewhere else in the game to craft items.
Last but not least, there are probably performance improvements possible. Depending on at which moment the code has to run (during the game loop or just for generating the maps and using them as a starting point to design hand-crafted ones out of them), you should try to make it as fast as possible.
But I leave these tasks to your imagination.