Procedural dungeon generation methods and the role of Unity on them
If you're reading this article you probably know already what are the pros and cons of procedurally generated content for games. If you want an overview of the subject I recommend reading the first chapter of this excellent free book: introduction.
What we'll cover here are what are the most common methods for generating dungeons, their regular use cases and what the final dungeon shape generally look like. After that, we'll tell how Unity can help us when generating these dungeons (tip: not much). And I'll also assume that you already know what is a dungeon, the only thing I'd like to clarify is that the rooms in our dungeons need to be connected to be considered correct dungeons.
When we talk about methods for creating dungeons we are referring to step 2. of the following procedure:
- Create a representational model of the dungeon. This would describe the dungeon size, how the rooms and corridors are laid out, where are the interactable elements and NPCs, in essence, everything that the final game will use.
- Use some constructive method for generating a valid model created on 1.
- A game specific procedure that will use the output from 2. to replace this model with data that's actually used by a game engine like 3d models, textures, etc.
Step 3. could also be used by a tool that allows designers to manually create game content. On most games, steps 1. and 3. are necessary, games that use PCG will also have 2., but a game that don't do number 2. will have this step performed by a person (or a group of level designers).
Binary space partitioning
This is a scary name to a rather simple idea. On that method, a predefined area will be subdivided sequentially (recursively) a specific number of times. There are several ways to subdivide a space, but we are only interested in subdividing it two, hence the binary from its name.
Each of these divisions are made either horizontally or vertically. After a certain number of divisions are made you create smaller areas inside these divisions, call this smaller sections rooms. Finally, these rooms are connected using corridors according to some strategy.
The most interesting fact about the output of this technique is that your dungeons will have a strong sense of hierarchy and there will be no overlapping rooms.
It's also good to know that the traditional use of space partitioning techniques is aimed at fast querying of 2D or 3D data. It's extensively used by game engines (and other software) to do raycasting, collision detection, and frustum culling, among other things.
These are examples of images on different steps of the Binary space partitioning method (BSP) but of different dungeons.
And here an image of the step 3. that a tile-based game will typically do with the output of the BSP method
If you want to learn more about the BSP method in practice, including how to connect corridors and how to paint a tilemap automatically using Unity be sure to subscribe to our list to receive a detailed tutorial on how to do all that as soon as we release it!
This method yields much more chaotic and random results than BSP depending upon the AI created. If your AI has some "look-ahead" it may avoid some cases of room and corridor overlapping, but it's not guaranteed. Use this method if you're looking for a more organic dungeon shape, but have in mind that you could even use techniques from machine learning to create this AI and have a rather organized look.
One aspect of this method is that it's rather easy to implement something. The BSP method is a little more complicated to understand but once it's implemented, the trial and error that is necessary don't come close to what you'll typically need if you choose to use an AI agent based dungeon generation.
Made famous by Conway's game of life, cellular automaton (or more commonly cellular automata in the plural form) is a computational model used in a variety of scientific fields. We'll avoid the general explanation of it here since this is such an important and popular topic that it has already tons of good explanations on the web, see this entry from the Stanford Encyclopedia of Philosophy to learn more or watch this video https://www.youtube.com/watch?v=EyrwOf239M4.
For our intents and purposes, we could start with some random noise and then run the cellular automata simulation a couple of steps only to reach a very interesting result.
Could be used for strategy games, roguelikes and even metroidvanias, it's up to you.
There's no way to guarantee from construction that the cave generated using this method will yield a connected dungeon. It's necessary to run a connectivity test on it if you're thinking in using this generation on real-time, if the dungeon is not connected you can either discard and try again or devise a strategy to make it connected.
Generative grammars come from the field of linguistics where a set of rules produce an output of all the valid (and only valid) sentences of a language. If we're flexible with what a language means, we can define rules and symbols for more visual languages, in our case, dungeons. This is the most flexible and most powerful of the four alternatives since these rules can encompass a big variety of structures.
Grammars have been used to generate levels of platformers based on rhythms, fps levels with gameplay-based parameters like fun, difficulty and global size and a lot more.
You can see how a grammar could be used to generate sentences by taking a look at the https://github.com/sequitur/improv js library.
Which method should I use?
Now that you have a high-level idea of the methods it should be easier to choose your next steps. I'd say that if you've never worked with PCG, the two methods that yield good results with a small effort are BSP and Cellular automata, but that shouldn't stop you from learning more of all these methods.
What's the role of Unity in all that?
Unfortunately, there's not much Unity can do for us regarding the actual generation of the game data. But Unity is certainly an excellent tool to process what you have generated and turning it into a game.
As much as you can try to create your generators with the least amount of Unity framework dependencies possible, it will keep your code simpler and easier to test.
Stay in the line for more
If you want to learn how to create a tool that procedurally generates a dungeon using the BSP method on Unity be sure to subscribe to our newsletter. We are producing a step-by-step tutorial on how to do that, including the often neglected steps like painting your dungeons using a tilemap after the core processes are finished.