Procedural Dungeon Generation #1

[a327ex]

2013-06-30 23:43

This post briefly explains a technique for generating randomized dungeons that is loosely based on the one explained here:

Grid Generation

Generate a grid:

Grid Difficulty Coloring

Color the grid with x red rooms (hard), y blue rooms (medium) and z green rooms (easy) such that x+y+z = n rooms in the grid. x, y and z will be used as controls for difficulty.

1. First color the grid with x red rooms such that no red room has another red neighbor;
2. Then for each red room color one neighbor blue and one neighbor green;
3. Color the rest of the rooms randomly with the remaining number of rooms for each color.

Dungeon Path Creation

Choose two nodes that are far apart enough and then find a path between them while mostly avoiding red rooms. If you choose a proper x, since red rooms can't be neighbors to themselves and the pathfinding algorithm doesn't go for diagonals, it should create a not so direct path from one node to the other.

For all nodes in the path, add their red, blue or green neighbors. This should add the possibility of side paths and overall complexity/difficulty in the dungeon.

Room Creation and Connection

Join smaller grids into bigger ones according to predefined room sizes. Use a higher chances for smaller widths/heights and lower chances for bigger widths/heights.

Generate all possible connections between rooms.

Randomly remove connections until a certain number of connections per room is met. If n = total rooms, then set n*a rooms with >=4 connections, n*b with 3, n*c with 2 and n*d with 1, such that a+b+c+d=1. Controlling a, b, c and d lets you control how mazy the dungeon gets. If c or d are considerably higher than a or b then there won't be many hub rooms that connect multiple different paths, so it's gonna have lots of different thin paths with dead ends. If a or b are higher then the dungeon will be super connected and therefore easier.

Reconnect isolated islands. Since the last step is completely random, there's a big chance that rooms or groups of rooms will become unreachable.

To fix that:

1. Flood fill to figure out how many isolated groups exist;
2. Pick a group at random and go through its rooms. For each room check if it neighbors a room belonging to another group, if it does then connect them and end the search;
3. Repeat the previous steps until there's only one group left (everyone's connected).

END

And that's it, I guess. There's more stuff like adding special rooms, but that's specific to each game, so whatever. But basically I have a few parameters I can control when creating a new dungeon: dungeon width/height; percentage of hard, medium and easy rooms; what color neighbors get added to the original path and the percentage of rooms with >=4, 3, 2 or 1 connections. I think that's enough to have control of how easy/hard the dungeon will be...

[vtlmks]

Thank you for this write up, I've been watching that video a few times and I really like the way you've condensed it.

Just a question that does have with the video to do, not this article, for the out doors level creation, did you understand what they used the voronoi pattern for?

Thanks!

[a327ex]

@vtlmks Not really. They're doing it for a reason but I can't really figure out what it is. He says it's so that nodes aren't moved outside of each cell but I don't really understand why that's necessary or how it prevents nodes from moving out.

[vtlmks]

I actually did send him a message asking about it, didn't want to show his answer before your reply, but I really don't understand the answer, perhaps you do?

--- Quote ---
We generate a voronoi diagram and then generate a random position for each node within the voronoi cell that the node is in. This allows us to randomise the positions of all the nodes while making sure that the actual topology hasn't changed. It's also gives the artists a visualisation to see what the bounds that nodes can move in are, and even give them the ability to add constraints to the random node positions by placing additional nodes that do nothing but affect the voronoi cells.

You may still have to do some collision detection on the edges when moving them around because there are some corner cases where they overlap in unintended ways after doing the voronoi shuffle.
--- End Quote ---

[tversteeg]

@vtlmks I think he means with topology the rooms and halls connecting them, but not the exact position. So if room A is attached to room B & C but not to D he wants to be able to move it around without it reattaching to D or disconnecting from B & C.