I’m designing a system for procedurally generating a dungeon. I’ve come to the point where I need to check if rooms are overlapping.
The dungeon is made up from room prefabs with a number of entry/exit points each. The dungeon is generated linearly which means there is no branching nor are there any looping paths.
The algorithm so far:
Choose an exit point on the current room.
Choose a new room prefab.
Choose an entry point on the new room prefab.
Line up the previous room’s exit with the new room’s entry.
My problem is that the rooms often overlap, as expected, with already placed parts of the dungeon.
I’ve tried a few approaches to check collisions before placing rooms and selecting new rooms and/or connection points until no collision occurs but I’ve just ended up with infinite loops and I’m out of idéas.
Are there any good resources on how this problem can be solved? I assume this is a quite common problem when generating dungeon of this type.
The first is to simply give a maximum time allowed and if you go over that then you cancel the generation and start over from scratch. Technically this can still cause an infinite loop but with some proper planning and design with your pieces you can minimize this likelihood.
The next is to track your generation via a stack of nodes (where each node references the module, it’s parent node, and any child nodes that extend from it). When you hit a failure state but still need to keep generating then you try all possible children of the current module you are trying to place. If none of them work then you need to walk back up to the parent, deleting the current module in the process and picking a different one. This failsafe should be recursive in nature to ensure that you walk back as far as needed. You can also add a max time limit for this to ensure you don’t waste too much time backtracking on a map that was doomed from the very start. This is pretty similar to how your typical maze-solver algorithm might work. The nice part about this is that you can use it to backfill various alternative paths that can lead to deadends or different goals.
In either case one of the best ways to ensure failure is less likely is to use a standard ‘tile’ size for your modules. This makes it easier for pieces to connect together or at the very least sit adjacent to one-another even if they don’t connect. It also opens up a plethora of other generation options such as ‘tunneling’ doors and openings between rooms that share walls or something like the Wave Function Collapse.
The node based approach seems like it would fit my case pretty well. I would like to avoid being tied to a specific ‘tile size’ but I assume I could implement some kind of fail-safe as you mentioned. I’m going to look into some maze-solver stuff now. I didn’t know of a name for this type of problem. When reading your reply I also got an idea where if a current node is doomed to fail, there could be a small chance of placing some kind of teleporter in the parent node. This would then lead the path to continue at some new unconnected location not likely to collide with the previously established nodes. It’s a sci-fi game after all so I assume teleportation could be feasible. I will have to ask the designers lol… Anyway, many thanks for your insights! I think the node based approach will be perfect
