pvigier's blog

computer science, programming and other ideas

Vagabond – Dungeon and Cave Generation – Part 3

Few weeks ago, I released the version alpha 2 of Vagabond. One of the new features is the ability to mine ore veins in caves. This article is the follow-up of the two previous parts on dungeon generation (part 1, part 2) where I explained how the structure of the caves were generated. However, the rooms were completely empty. In this article, I will explain how the rooms are filled with monsters, bosses, ore veins and treasures.

If you want to try the game and explore the procedurally generated caves presented here, you can play the free demo available on Steam. If you have any feedback, do not hesitate to send me a message, I would be delighted to read it.

Current State

To quickly recap where I stopped my dungeon generation algorithm, I use a BSP algorithm to create rooms, then I select a subset of the room edges as corridors, and I run a constrained cellular automaton to create walls with an organic shape. Finally, I run several post-processing steps to clean the result. You can see all this steps in the animation above.

So, as we can see on the image below, I have a clean abstract structure of the dungeon: clearly delimited rooms, a graph of rooms and a 2D array of booleans that represents the obstacles.

Assigning Room Types

My first step is to assign a type to each room. The type will then determine what the room will look like. I do that just before the cellular automaton pass to be able to add specific constraints if necessary.

Firstly, I choose the entrance room. There is a specific constraint: the door needs a wall on which it can be placed on as in the image below.

To achieve this, I randomly choose a room with no corridor on its north edge and a constraint is added in the cellular automaton. You can see this constraint in the example below: it is the little black square in the north western room:

Then, when tiles are generated a door is placed there:

Secondly, I randomly choose a room to be the boss room but I give more weight to the rooms far from the entrance so that the boss is rarely next to the entrance.

Finally, for the other rooms, a random type is chosen among the types for “normal” rooms.

Nothing fancy here, but if you have a large pool of room types and different types of dungeons with different subsets of room types, you can already have interesting results.

In the future, I may choose to use a more complex algorithm to choose room types. For instance, I can use the graph structure to place keys and locks.

Decorating the Rooms

To decorate the rooms, I reuse the room generator I originally created for the building generator. It takes as input an abstract representation of the room as an array of booleans and a list of objects with their constraints, and it uses a CSP solver to place the objects in the room. If you want to read more there is an entire section about it in this article.

For now, as there is only caves in the world, the normal rooms are pretty simple: they are filled with monsters and ore veins. The entrance room only contains the door. The boss room contains a chest filled with a procedurally generated loot. But beware, it is protected by a boss which have boosted stats and a unique name procedurally generated by handcrafted grammars.

The only subtlety was that the room generator can only place objects in rooms not monsters. So I created an object “monster spawner” whose only purpose is to spawn monster to circumvent the issue.

Here is the final result:

Conclusion

That’s all for this quick update on the dungeon generator. The dungeons are now fully playable!

In the future, I would like to make the dungeons more interesting, I have several avenues to explore in mind. On the one hand, I would like to work on the lore of dungeons: to generate stories and quests for each dungeons. On the other hand, I would like to make dungeons more interesting by theirself: maybe by adding keys, locks and puzzles, by having several stairs, and also by adding some special objects in corners and dead ends to encourage the players to explore.

If you are interested in my adventures during the development of Vagabond, you can follow me on Twitter.

Tags: vagabond pcg