I am curious how dungeons like the one in Runescape dungeoneering skill are generated. They basicaly have a 10x10 grid. So theres 100 rooms total. There's starting room and exit room. And each one are conected by open doors or doors that require key of some color. Anyone have idea how to generate something like this? I mean how to place doors and keys to make dungeon doable?
There are many different approaches to this. This also depends whether you always want to fill all your rooms or just a few of them.
Here's one possible approach not using all available rooms.
- Start with a random room, this is your entry point. Add this room to a list
- Repeat the following steps till your dungeon is "complete" (e.g. target number of rooms achieved).
- Pick a random
open endand a random direction.
- Remove the picked room from
- If the room you're "moving" to doesn't exist, create it and add it to
- Mark both rooms to have a connection between them, either unlocked or locked using one of the
- If you've picked a key and keys are one time use only, remove the key from
- If the room you're "moving" to doesn't have treasure, do a random roll to determine whether there is some.
- If there is treasure and it's a key (e.g. red key, blue key, etc.), add that key to
Now your dungeon is almost finished. You're still looking to get some stairs down or a boss room? Easy!
- Pick a random room from
- If there isn't one available, loop through all rooms and try to add a new one.
- Mark the room to be the boss room and remove it from
In a similar fashion, you can add stuff like treasure rooms, shops, libraries, temples, etc. as long as there's still room in your dungeon.
If you always want to use all available rooms, I'd probably use a different approach:
- For each room in your grid set random connections (e.g. left and right, up and right, etc.).
- Pick random rooms for your boss, treasure, etc.
- Set these random rooms to only have one entrance/connection.
- Use some pathfinding (Djikstra's?) algorithm to ensure the player is able to reach these rooms.
- If you add locked doors, make sure there's at least one path from the locked door to a key (mark it as "used") to the player's starting position. Once done, mark the door as "solved" (it can be passed in further iterations for other doors).
This kind of procedural generation is considered extensively at this website dedicated to listing game mechanic ideas. There are several entries on that site that go into quite a bit of detail on how procedural content generation can be done effectively. There are nearly 30 entries related to procedural generation. Reading these entries gave me a better understanding of procedural generation and helped me to fully appreciate what it is capable of.
This early entry seems the most relevant to your question. It details one method of accomplishing what you're asking.