Pre-production
I spent pre-production planning the design of the tool. Let’s break the planning phase up into steps:
How does my reference create their dungeons?
What does my level design think of when creating a dungeon?
How do I create a simple and efficient user interface?
Reference research
I spent some time researching the wiki page of Elder Scrolls : Daggerfall, there is no source code available to the public but looking at the actual end product you can tell that they use some sort of modular generation, pre-made rooms and corridors placed in a specific order as to create a dungeon.
This tool was only used to create the sidequest dungeons, as the main story ones were created by hand.
Interviewing my level design team
In order to write a good tool you need to know your audience, In other words, my level designers. I went to them with a bunch of questions;
What do you look for in a dungeon?
What features would you like in a tool to create dungeons?
What’s your favourite colour? (It’s blue.)
and more.
The interview answered plenty but also left me with plenty more questions. Turns out creating dungeons isn’t as easy as they make it seem, you have to account for story elements, gameplay, feeling, atmosphere, limitations with the engine and plenty more. However! Differently sized rooms was something they unanimously agreed on was one of if not the most important feature.
I now have my work cut out for me; i’ll make a tool that allows for dungeon generation using differently sized modules.
The user interface
A solid algorithm isnt everything, a decent UI is also important, because if theres something I’ve learnt at TGA it is that the difference between a cool, used and appreciated tool and a shitty forgotten tool is how good the UI is. If my leveldesigners think my UI is hard to work with they wont use it.
Alpha
Algorithm work
This iteration of the algorithm uses a recursive function to create the dungeon. Before a tile is placed I check with its surrounding neighbours that it could fit at its location, kindof like a puzzle. If the tile doesn’t fit I try another piece, until I find one that does. A major problem I had during this iteration was that my tiles never ligned up with their parent tile, I would constantly find dead ends created by a tile not being aligned with its parent.
During alpha I spent most of my time implementing the algorithm and creating the interface. I also spent a lot of time ironing out some issues with my original idea.
Code snippet of the recursive function
How will i fix it?
I started looking into ways to solve the rotation issue. In the end I decided on a a system where each parent tile has a couple of exit markers in locations where they want to generate a child tile.
This solves the issue with weirdly rotated objects, as I now can rotate the exit marker and copy that rotation over to the new child tile. This marker system brought more benefits aswell! It makes it very easy for me to place exits on larger, weirdly shaped rooms or stairs, as I now only have to move the exit marker to a position where I would like to generate the next corridor piece.
Sadly, this also comes with the drawback that I now have to dig through a parent tiles hierarchy in order to find the correct place to generate in, convoluting my algorithm a bit.
A dungeon generated with the current iteration
The interface
I decided to stick to the basics of the algorithm for now, using depth, a seed for debugging purposes, a bool for generating things in the y axis and a generation type button, for generating depth first or breadth first.
The save buttons are non functional as of now, I mainly added them in so I wouldn’t forget about them later.
The UI
Beta 1
Beta 1 was further iteration on the algorithm and a bunch of problem solving, major changes to the algorithm and my general thought process for the remainder of the project.
Drastic changes
On the first day of Beta 1 I realised that my large rooms that I was generating weren’t working as intended, since I tried generating them along with all the corridor pieces they often ended up not fitting into an area and thus not get placed. After sleeping on it I realised that I could just generate the rooms first and the corridors later.
Since my corridor pieces are by rule of thumb 1x1 tiles they can easily generate around rooms, which made this solution feasible.
Doing it this way turned out to come with it’s own drawbacks however, with rooms sometimes getting cut off from the rest of the dungeon since corridors stemming from other rooms circled them in and disconnected it from the rest of the dungeon. Something that I didn’t find a solution for until Beta 2.
Saving generated dungeons
By adding all finished tiles to a list and sending it to the editor I can easily write their data down in a json file, storing their position, rotation and object type in order to export the data into other engines.
If the user would want to store the values used to produce a dungeon they can now also save them as a json file.
Beta 2 - Electric boogaloo
Beta 2 was the sprint when it all came together.
I finally reached a stage where I felt I was happy with the algorithm.
Further Iterations on the algorithm
As I mentioned in the Beta 1 log, I had an issue with rooms getting cut off from the surrounding area by their neighbour rooms. I woke up in a cold sweat at 03:00~ during the weekend between Beta 1 and 2 with a single idea in my head, I decided to write it down in my phone:
”Thedungn ccan patgfindin”
Obviously, this is complete gibberish.
I spent an hour on monday morning deciphering it. The translated version is “The dungeon can use pathfinding”. A* will be my saving grace. Saving down the rooms entry points in a list, making pairs out of them and pathfinding in-between them would stop my dungeon from having disconnected rooms. With this, I got to work.
After further iteration I had broken down my algorithm into 4 simple steps.
Place out rooms on the grid.
Create connections between all entry points in the newly created rooms.
Run A* on all the couples created by step 2.
Loop through all the grid slots in the paths created by step 3 and decide what tile type they should be depending on their amount and location of neighbours.
The steps : in detail
1: Placing out the rooms on random places are pretty simple, I just pick a place and make sure it doesn’t overlap with any other rooms by checking that none of the grid slots it tries to claim are already taken.
2: Creating connections between the entry doors are done in two steps. In the first step, the doors pick their partner by prioritizing smaller distances and how many connections their possible partner already has. This makes sure that no entry way is left without a partner.
The second step is the exact same, except for the criteria of a small partner count, this stops the algorithm from creating long, straight corridors by setting up multiple connections between different entries.
3: Running A* is pretty simple, I just save down all the paths in a big pile for later.
4: I count the neighbours of a tile and what cardinal direction (north, south, west and east, up and down) they are in from the current tile and pick a fitting tile and rotation for it to fit in. Once I’ve found a fitting piece I place it and add it to the dungeon list that gets returned back to the tool where they user can store it in a json file.
Gold
The gold sprint is the “Make it fast” part of the iterative process and I spent it doing just that, as well as working on my presentation and website.
I am speed.
The algorithm works as intended, but it can be better. Theres plenty of optimizations I can do in order to cut down generation time, such as pre allocation of objects in order to make it more cache friendly.
Which is what I’ve been spending my time on these last couple of days.
QOL changes
The algorithm being faster is always nice, but the UI of the tool could be improved, as it stands there are some variables that are no longer used in the algorithm, leading to confusion for the user. These will be removed right after I finish this devlog.
I also noticed that the tool is fairly easy to break as it stands, removing an object from the folders used as asset banks is enough to make the generation crash, which is an easy fix.
100x100x2 dungeon generated in 1 minute and 20 s using 100 rooms.