Following the recent forest tileset update (see devlog) I had to update the random room generator, so I thought, why not write a bit about it?

Generating a random dungeon room sounds easy at first. Just draw a closed shape, add doors on the respective sides and randomly drop stairs, enemies, loot and decorative objects.

But considering that the player/enemies need to move around objects which occupy space, and that walking into some objects (such as stairs) takes the player elsewhere, complications arise.  In tight rooms, when not careful, some of the objects may end up blocking the way to enemies or loot, and even worse, the room could become untraversable resulting in an inescapable dungeon. This must never happen.

Consider the image below. A staircase leading to a lower level is unfortunately in the way. The 3 doors, loot and upwards staircase cannot be reached by the player, since walking over a staircase leads to a different room. Decorative elements that are blocking (i.e. a pillar, a statue, a tree, etc) could also end up in the wrong place in a similar way.

(note: those are crude graphics used for debugging the layout generator before rendering with a nice tileset)

In other words, the path must never be blocked. A good way to avoid blocking the path is obviously knowing where the path is. In this project, I use path finding between doors (and other elements the player must have access to) to mark some cells as PATH.

Consider this room with 4 doors (up/down/left/right), one secret trap in the lower right, two loot items, two enemies, and two staircases. We must make sure that the player always has access to all those elements and that no door gets blocked by a decorative tree or boulder.

First the required doors are placed, and a path linking them all together is found. Next stairs and secret traps are placed outside the PATH, so it never gets blocked. Loot and enemy spawn locations are also determined (those can be on the path however) . Finally, a complete path linking not only the doors, but also the new elements (stairs, enemies, loot) is computed.

Normally the path is invisible, but I have a debugging mode which  marks PATH cells with the letter P:

At the final display step, as the room gets rendered using nice graphics and decorative objects get added, the area not marked as PATH can be populated with decorative blocking elements without any risk of blocking the path and breaking the game.

The room generator also computes how far the closest wall is for each cell. This is used by the path finding algorithm to bias the path towards or away from the walls, and also helps placing some decorative items (for instances, breakable trees which tend to appear next to walls). I also have a debugging option to reveal the wall distance:

The final result, when using the forest tileset, looks like this: