In today’s Dev Blog post Asher, a developer at Rabid Troll Studios describes his process for creating the procedural mine generation in Dwindle.
When I was initially handed the task of creating Dwindle’s procedural mines, I wasn’t completely sure where I was going to start, but another member of the team had found a video on creating procedural dungeons, so I went ahead and watched that first. In the video (from Unite 2014), Zach Aikman of 17-BIT described how they created the dungeons in the studio’s game Galak Z. Part of their solution was cellular automata, which I knew of and thought I might end up using, but another part was this thing I had never heard of called a Hilbert curve. A Hilbert curve can fill a two-dimensional grid with a single line that turns at every cell in the grid, obviously an excellent base for mazes, and I immediately decided I was going to use one.
Getting the code tweaked right to generate the curve in one of my graphs was a little tricky, but after a couple of days my team and I got the (incredibly cool, in my opinion) curve to show up. Its two shortfalls for Dwindle’s purposes are that it has a very regular pattern and it only has a single path through it. I started solving these with the same trick 17-BIT used; generate a large curve, and then choose a random sub-section of it, so that the pattern always goes through a slightly different way. I stuck the hub right at the center of my sub-section. After that, I went through all the rest of the cells, and rolled a chance for it to have a room (100% near the hub, lowering as it went outward) and a chance to add an additional edge. All cells started with two edges leaving them, as is the nature of the curve, but with some cells not having rooms and others having a third or potentially fourth edge leaving them (if another cell added an edge to it already), those simple rules created a nicely random-seeming maze after tweaking the constants a bit.
Finally, with my graph of filled-in cells and edges, I filled in the cells with rooms and the edges with hallways, both of random sizes, and removed any rooms and hallways that couldn’t be reached from the hub (easy to check because my graph was built for pathfinding). That code generated the world layout that has survived with only very minor tweaks for the six months since it was written, probably at this point some of the oldest code written specifically for Dwindle that is still left in the project. Since you as the player never really get to see the mine in its full form except by the drawings on the map, here’s a screenshot of one example of the expanse we have created:
Yes, the hub is the tiny lit room in the center. Good luck finding your way through that. Happy exploring!