In the previous post, I started programming using the Unreal Engine for the first time. I learnt the basics of projects, some of the UE4 class Hierarchy (useful) and I randomly generated floor or wall. A good start but a long way away from random dungeon layout.
To create a dungeon layout I want to reset all the floor, create some rooms, determine which rooms should connect to which other rooms and then finally carve some corridors between them.
void InitialiseBlocks(); void CreateRooms(); void ConnectRooms(); void CarveCorridors();
The CreateRooms is where it starts to get interesting. There are some really fascinating articles on the Internet about different approaches to go for. The Quadtree approach basically uses quadtrees to divide the area into the various levels of recursion and randomise room creation at each level.
I wrote a quick quadtree class to help me do this. Really it is a room generator that uses quadtrees to prevent overlapping rooms from being generated. It is a badly named class.
The Quadtree is initialised with an axis aligned bounding box (AABB) and then asked to generate rooms. Each Quadtree can either:
- Generate room
- Subdivide (and then in turn ask each of the child quadtrees to recursively perform the same function)
- Stop because the depth of recursion would make any resultant rooms a bit small.
My rules are:
- The first two levels (0 = whole, 1 = quarters) quadtrees can’t turn into a room and will always subdivide.
- Then the percentage chance of creating a room is 30%, 45% and 65%. This seems to work well. The maximum depth actually disallows this last size but the maximum depth is really a property of the absolute size of the dungeon. This may need some tweaks if I start supporting very large dungeon sizes.
- Each room that should be generated is then placed into the quadtree AABB. The width is between 1/2 and 2/3 of the AABB width (and similarly for the height). This guarantees that rooms won’t overlap but adds variety to the sizes and also the “centres” of the room. Filling the quadtree AABB gives far too much uniformity to the rooms.
- Any room that is less than 5 in width or height is inflated slightly.
The rooms then need to be connected. Ian Shadden suggested a simple algorithm. Start with first room and connect it to the nearest room that doesn’t already have a connection. When you get to the last room it won’t have anybody that it can connect to.
This is a simple idea but pretty effective. Then all you have to do is carve the corridors between the connected rooms. Simple!