Havenguard: DungeonBuilder
It's been a while since I last posted something, so this is big one. Above is the abstract output of the new procedural DungeonBuilder for Havenguard. This is only one of many possible types of map builders within the game.
How does it work? Well, the concept is relatively simple, however the implementation starts to get complex when the 'Room Graph' (the green and purple nodes/connections) comes into play. Long explanation below, jump to the bottom for the TL;DR version.
Just a regular Graph data structure implementation (see links at the bottom for more information).
What is it good for? Awesome stuff. If we know how the level is structured, we can walk the graph from the starting room and do things like: Lock a door and make sure the key is placed in an 'earlier' room (easy!), add a mini-boss, epic loot chest, random event or NPC in a branch off the critical path or make sure that at least two-thirds of the way down the critical path a level boss is created. There are infinite possibilities, you just have to get creative!
It gives us a great degree of control over how 'fun' the dungeons are, as we can control the balance and pacing of monsters, loot, events, etc and can reward players for exploring the entire map, rather than just rushing from staircase to staircase.
How do we generate interesting Dungeons with it?
Let's start at the beginning, with:
A Room class stores information about each room in the map (id, bounds, connections, etc).
Start by generating a single room anywhere within the bounds of the map. Give it an id and add to the room list.
Generate another room to either the left, right, top or bottom of the this room. If the room doesn't fit (run the room bounds through a validation function), try again until a room is generated that does fit (to avoid an infinite loop, once a predetermined retry count is reached, the loop is broken and we just skip to the next step). Give it an id and add it to the room list.
Select a random room and repeat from previous step using the randomly selected room, until the maximum number of rooms are reached, or the failed placement counter reaches its limit.
Clip the map size to the extents of all rooms (this just reduces the amount of memory required to store the map, since we can dump a bunch of unrequired cells).
Dig out the rooms (this just sets the cell types within the room bounds to 'Ground', and their surrounding cells to 'Wall'). Store the room ids on the Ground cells.
Done! That's the easy part. We have a bunch of rooms, but they're not connected...
Time to create the room graph!
The nodes within the graph represent a each room.
I also store a reference to the graph node on each Room object.
Once all the rooms are generated, we create a new node for each room and add it to the graph, in preparation for...
Pick a random room from the room list, set this to the 'active' room.
Find the closest room (distance from center to center) that currently has zero connections (rooms need to keep track of what rooms they're connected to). This is the 'target' room.
Pick a random cell within each room.
Using an A* search with a special cost function (ask me about this if you want to know more), find a path between the two cells. Assert a path is found - If everything is working correctly, there isn't a reason a path shouldn't be found.
Step through the path, marking the current room id. We don't dig out any cells here yet. If we encounter a wall, create and store (in a list or dictionary) a Door object at this location (Door class stores data for a door (location, state, locked, etc)).
Add any non-room/empty cells to a 'to dig' list.
Once we reach a Ground cell with a different room id, we know we've entered another room. We also know that these two rooms are connected - add an edge (a connection) to the graph between the two room nodes.
For the 'cost' for the edge, I used the number of empty cells between the rooms plus the area of the two rooms (width * height). This cost is used later.
Set the current room id to the newly entered room id, and continue to follow the path, repeating the above steps.
Once we've reached the end of the path, we have populated the edges on the Room Graph and we have a list of cells that require digging. Iterate over the dig list and dig out the rooms.
Set the 'active' room to the 'target' and repeat from step 2 until all rooms are connected.
Done! Now we've populated the Room Graph, marked our doorways, and dug out our corridors. Looking pretty awesome.
The next thing to do is validate all our doors. Even though we created them during the Corridor Generation step, not all of them are going to be valid. I have some rules for doors...
A door must be bordered by exactly two walls, strictly on opposite sides (north and south, or east and west).
A door must not be adjacent to another door on the straight axes (north, south, east, west). Diagonals are fine, but this is down to personal taste and how your levels are rendered. You could exclude diagonals too.
If a door does not satisfy these requirements, it is removed from the door list.
I also specify a 'no door' chance (a number between 0 and 1), which is rolled for each door using the RNG. If it rolls true, the door is removed from the list. This creates empty doorways, which you can do nice things with later (decorative archways, for example).
The final step in the basic map generation (before we start populating it with monsters and sweet loot) is to process the Room Graph.
The Room Graph currently doesn't do anything except tell us which rooms are connected to which and (approximately) how far they are from each other (the edge cost, remember?).
First we should decide on a starting room for the player. We could just pick a random room, but this would mean that rooms in the middle could be chosen too often, making the path to goal room too short.
I find the two rooms that are furthest apart, and then pick one of those two at random as the starting room.
From the start room, we begin walking the graph. I use a recursive function (a 'visitor') on the starting node, which then recursively calls itself on all un-visited neighboring nodes. You can see where this is going...
Each visited room stores its 'Flow Index' - this is a value telling us exactly how many rooms this room is from the starting room. The Flow Index starts at zero for the starting room, then each visited neighbor is the parent's FlowIndex + 1. Because the visitor function is recursive, the value grows by one with each node visited. Beautiful. I also store the total 'distance' from the starting room (similar to the flow index above, but we use the edge cost we set above when building the graph). This tells us approximately how many cells there are between each room and the starting room (it's not exact, but it's a good indication).
There is other information you can store in this step, like: which rooms are dead-ends (no other neighbors), which rooms loop back onto another branch, etc.
Once all nodes have been visited, to find the 'goal' room of the dungeon (the downward staircase in a typical Roguelike), I simply find the room with the highest Flow Index and Distance from the start room. Simple!
To find the 'critical path' of the map (start room to goal room), just run the graph through A* to find the shortest path from the start room to the goal room.
Voilà! Now we have a completed Room Graph, which we can query for extremely useful information to control balance and pacing within each dungeon level, ultimately making a much more fun and rewarding experience for the player.
Generate your rooms and corridors, build a graph representing the connections between rooms, use the graph to place interesting 'things' within the dungeon, off or on the critical path (start to goal room). Use the graph to make the dungeon fun and interesting!
Wikipedia article on the Graph data structure: http://en.wikipedia.org/wiki/Graph_(abstract_data_type)
A very nice MSDN article on building a Graph data structure in C#: http://msdn.microsoft.com/en-us/library/ms379574(v=vs.80).aspx
Roguebasin articles on Roguelike concepts, with lots of examples: http://www.roguebasin.com/index.php?title=Articles
Amit's A* Pages - lots of great information on the A* algorithm: http://theory.stanford.edu/~amitp/GameProgramming/
In fact, check out Amit's excellent game programming information site: http://www-cs-students.stanford.edu/~amitp/gameprog.html
dededos
dailybridgerton
baratheonpilled
kianamaiart