We describe four separate random dungeon generators, and the A* algorithm for finding paths. This is presented in a simple GUI which makes further development of the generators attractive and easy.
Introduction
Many video games are based on a maze of rooms which the player has to negotiate. Often these are designed by a human designers. However there is also a call for automatic generation, either to assist the human designers, or to fill out minor encounter areas, or if the game has random rather than human-designed levels, to generate dungeons on the fly. And there are many, many ways of designing dungeons, depending on the characteristics you wish your dungeon to have. However virtually always we want the dungeon to be fully connected, and vrtually always we want some characteristic of either a maze or a division into rooms.
This article focuses on binary dungeon generation. So all the dungeons consist of either filled or unfilled pixels. That's not adequate for most games, and you will need additional symbols for doors, staircases, maybe terrain type. But this is highly dependent on the actual game, for instance if the higher level logic allows doors or not. However a GIF allows for 256 colours per cell, and we only use two, so there is plenty of scope for adding other cell types.
And dungeons are no good without monsters to go in them, and the monsters must be able to negotiate the maze of passages to find the players. So the random dungeon generators naturally go with an implementation of the A* path finding algorithm.
And the program has been given a very basic graphical user interface to allow algorithm designers to quickly see their results. However it isn't meant as an end user program. It will however allow you to save your dungeon as a GIF.
Background
For some reason people who are keen computer programmers also tend to be very keen on Dungeons and Dragons. I don't know the correlation coefficient, but I suspect very high. And some of the first computer programs were either text adventures, or raster-based dungeon games like Rogue. Whilst modern games are extremely sophisticated and have millions of dollars thrown at them. But, however cleverly it is hidden from the player, ultimately game logic is usually based on the concept that it is played on a grid where some cells are accessible and some cells are not.
And so we need lots and lots of binary dungeon generators which spit out a binary map of a dungeon, and then it's no good unless we and the monsters can find our way around it, so we also need the A* pathfinding algorithm. Then we build the rest of the game on top of those two core components.
And whilst the generators are all random, they create dungeons with different flavours or characteristics. And again, this is highly dependent on the game. Often the grid is visible to the player, and must look aesthetic. Often we also need a concept of "rooms" for higher level game logic. Some but not all the generators naturally lend themselves to defining rooms.
An important thing to understand is the difference between 8-connection and 4-connection. 4-connection is along the edges (top, bottom, right, left), 8 connection is also along the diagonals (top-left, top-right, bottom-left, bottom-right). Normally dungeon games insist on 4-connection for the accessible cells, as in real life, a player cannot squeeze between two blocks of stone abutting each other on a diagonal. However in reality, it is very rare to come across two blocks of stone positioned like that, So many designers will insist on 4-connection for both the accessible and the inaccessible cells, and reject any dungeons with 8-connected cells.
If you use your own random number generator you can make the dungeons deterministic, from a seed. Which can be extremely useful. Generate a lot of dungeons, choose the best one, and they can be stored as a single seed and recalled.
Using the code
Rooms generator
This is a more or less the state of the art generator used by most random dungeon generator sites. It is not mine and is mostly the work of Bob Nystrom, though I converted it to C. The method is to place rectangular rooms at random first. The areas between the rooms are then filled with maze passages using a recursive maze generator that extends a tree until no pixels are spare. The rooms are then connected to the maze, and the maze culled by eliminating most dead ends.
This algorithm creates the best, most attractive, most usable dungeon. And it has plenty of opportunities for fine tuning. However it creates a dungeon of rooms connected by passages, which is not necessarily what you want.
Cavern generator
For cavern levels, a generator based on square rooms and corridors is no good. So we have a separate cavern generator.
It works on the cellular automaton principle. We start off with all the tiles set to random, except for the borders which are hard-coded to walls. Then we majority filter several times. This creates coherent regions of cavern and wall.
The cavern regions are not connected, so we label the separate regions, then for each one, take the point closest to the centre. The we draw a slightly jagged corridor from cavern to centre until we hit another cavern. This is almost but not quite guaranteed to connect all our caverns. So as a last step we eliminate any unconnected caverns and break any 8-connections in the background we might have introduced.
Note that you can modify the function slightly to retain the labels. That might be useful if you want a notion of caverns as rooms or separate encounter areas.
Seed growing generator
Here's another generator. It works by placing random seeds across the dungeon, then expanding them until they almost touch. The result is a dungeon consisting almost entirely of rectangular rooms, with only a few filled regions. You then connect it, which is very easy, and is just a case of knocking doors in party walls..
It's possible to add corridors first to get some long narrow rectangles, as I have done. This method produces a more realistic division of space than the previous method, but probably less playable dungeons for most Rogue-like games.
So maybe use for house interiors.
Blocks generator
Filing one in three blocks on a raster creates a maze with about the right connectivity for most games. And one very simple algorithm is to do this repeatedly until a dungeon which connects the start point and the end point is generated. As children, we used this method for our own dungeon-based games, coded in Basic.
The current generator is slightly but not much more sophisticated. One in three blocks is filled at random. The 8-connections are broken. Then small disconnected rooms are filled in. Then any disconnected rooms are connected using simple tunnelling. Finally, any small pillars are culled.
A* pathfinding
The A* pathfinding algorithm packaged with the random dungeon generator finds paths on binary images. It allows diagonal moves, which is a good reason the accessible cells must be 4-connected.
The A* is quite easy to use. You call it with a binary image, and it returns a path between the two points, in two parallel arrays to avoid declaring a "Point" type. If it can't find a path, it returns 0.
int astar(unsigned char *binary, int width, int height, int sx, int sy, int ex, int ey, int **pathx, int **pathy)
And this is how it works.
int astar(unsigned char *binary, int width, int height, int sx, int sy, int ex, int ey, int **pathx, int **pathy)
{
unsigned char *img = 0;
HEAP *heap = 0;
int ok;
APOINT a, b, ap, np;
int set, otherset;
unsigned char neighbours[9];
int i, ii;
int j;
int nx, ny;
int targetx, targety;
int Npa, Npb;
int *pathax, *pathay, *pathbx, *pathby;
int *tpathx, *tpathy;
int answer = 0;
img = malloc(width * height);
if (!img)
goto out_of_memory;
for (i = 0; i < width*height; i++)
img[i] = binary[i] ? FILL : 0;
img[sy*width + sx] |= ASET;
img[ey*width + ex] |= BSET;
heap = HeapCreate(100);
if (!heap)
goto out_of_memory;
We start by setting up a raster with flags for FILL, ASET and BSET. FILL tells us if the cell is accessible, and ASET and BSET are used by two bubbles growing from A and B to flag if the cell has been visited. And we also create a priority queue. And we push nodes onto the priority queue, which balances two factors. Nodes which are near to the start and end points and are therefore cheap get priority. But so too do nodes with match the heuristic, which is that the shortest path will be approximately the direct path as the crow flies.
a.x = sx;
a.y = sy;
a.fscore = 0;
a.heuristic = diagonaldistance(sx, sy, ex, ey);
ok = HeapInsert(heap, 0, sizeof(APOINT), &a, heapcompf);
if (ok == 0)
goto out_of_memory;
b.x = ex;
b.y = ey;
b.fscore = 0;
b.heuristic = diagonaldistance(sx, sy, ex, sy);
ok = HeapInsert(heap, 0, sizeof(APOINT), &b, heapcompf);
if (ok == 0)
goto out_of_memory;
Then we set up the two bubble, each initially consisting of a single point, A and B, into the priority queue.
while (HeapGetSize(heap) > 0)
{
HeapDelete(heap, 0, 0, &ap, heapcompf);
get3x3(neighbours, img, width,height, ap.x, ap.y, 0x0);
set = neighbours[4] & SETMASK;
if (set == ASET)
{
otherset = BSET;
targetx = ex;
targety = ey;
}
else
{
otherset = ASET;
targetx = sx;
targety = sy;
}
Nw we extract the first entry from the priorty queue, and work out whether it was from the A-bubble or the B-bubble. otherset is the other set.
for (j = 0; j < 9; j++)
{
nx = ap.x + (j % 3) - 1;
ny = ap.y + (j / 3) - 1;
Iterate over the neighbours, Get the x, y co-ordinates of the neighbour in nx, ny.
if ((neighbours[j] & FILLMASK) && (neighbours[j] & SETMASK) == 0)
{
double cost = 0.0;
switch (j)
{
case 0: cost = 1.414; img[ny*width + nx] |= (set | SOUTHEAST); break;
case 1: cost = 1.0; img[ny*width + nx] |= (set | SOUTH); break;
case 2: cost = 1.414; img[ny*width + nx] |= (set | SOUTHWEST); break;
case 3: cost = 1.0; img[ny*width + nx] |= (set | EAST); break;
case 4: break;
case 5: cost = 1.0; img[ny*width + nx] |= (set | WEST); break;
case 6: cost = 1.141; img[ny*width + nx] |= (set | NORTHEAST); break;
case 7: cost = 1.0; img[ny*width + nx] |= (set | NORTH); break;
case 8: cost = 1.414; img[ny*width + nx] |= (set | NORTHWEST); break;
}
if (j != 4)
{
np.x = nx;
np.y = ny;
np.heuristic = diagonaldistance(np.x, np.y, targetx, targety);
np.fscore = ap.fscore + cost;
ok = HeapInsert(heap, 0, sizeof(APOINT), &np, heapcompf);
if (ok == 0)
goto out_of_memory;
}
}
We then expand into any unexplored cells. A 4-connected neighbour costs 1, an 8-connected sqrt(2). And we also have to recalculate the heuristic.
else if ((neighbours[j] & SETMASK) == otherset)
{
Npa = traceback(img, width, height, ap.x, ap.y, &pathax, &pathay);
Npb = traceback(img, width, height, nx, ny, &pathbx, &pathby);
if (Npa == -1 || Npb == -1)
goto out_of_memory;
reverse(pathax, Npa);
reverse(pathay, Npa);
tpathx = malloc((Npa + Npb) * sizeof(int));
tpathy = malloc((Npa + Npb) * sizeof(int));
if (!tpathx || !tpathy)
goto out_of_memory;
for (ii = 0; ii < Npa; ii++)
{
tpathx[ii] = pathax[ii];
tpathy[ii] = pathay[ii];
}
for (ii = 0; ii < Npb; ii++)
{
tpathx[ii + Npa] = pathbx[ii];
tpathy[ii + Npa] = pathby[ii];
}
On the other hand, if we hit a cell from the other set, the bubbles have joined, and we are done. We need to trace two paths back to sx, sy and ex, sy, and then join them, and that's our answer.
if (tpathx[0] != sx || tpathy[0] != sy)
{
reverse(tpathx, Npa + Npb);
reverse(tpathy, Npa + Npb);
}
free(pathax);
free(pathay);
free(pathbx);
free(pathby);
*pathx = tpathx;
*pathy = tpathy;
answer = Npa + Npb;
goto done;
}
}
}
done:
HeapDestroy(heap);
free(img);
return answer;
out_of_memory:
HeapDestroy(heap);
free(img);
return -1;
}
And just a bit of fiddling about to make sure the path goes in the right direction and clean up memory.
Points of Interest
Random dungeon generators are fun to write, and as long as the dungeon is connnected there is no right or wrong, and you can run wild. However the public random dungeon servers are quite sophisticated, and it will be a while before these algorithms can match them.
History
Random dungeon generators are maintained at the binary image library on GitHub:
http://malcolmmclean.github.io/binaryimagelibrary/
