A look at dungeon generation news - Chronicon

Introduction

Since I'm only working on "behind the scenes" stuff currently, I figured I'd provide some (possibly) more interesting reading: dungeon generation.

I've developed my own method for generating dungeons for Chronicon, a method I haven't seen before, but I'm sure someone else is doing it. I wanted a method that allowed me to have large control over the end result, yet still providing highly varying results, while being easy to edit, and fast to compute.

First up: Easy to edit

"What is easy to edit?" I thought, and the first thing that came to mind was.. images. Yes; sprites. So I started experimenting and quickly found that it was easy to link colours in pixels tiles & world data and have the game "scan" images to determine what to spawn, and how to build dungeons. Using this method, I began drawing pieces of dungeons - rooms, if you will - that the generation algorithm would piece together. For the generator to know what was what, I implemented "connection nodes" (a bright green pixel in this case) which I would place on the edges of rooms to tell the generator that this was a viable spot to connect to another piece. Kind of like how a jigsaw puzzle works; you can only connect at the pointy/cut bits. This worked well, but I had little control over the design, as it would randomly place out rooms, and I had no good way of determining where to spawn monsters, chests, detail objects, entrance/exit, etc.

Example of a room piece

Adding Control & Variation

To gain more control over where things went, I quickly started implementing more nodes; monster spawn nodes, detail spawn nodes, secret areas spawn nodes.. etc. A node for every type of entity for the dungeon. These were also just general nodes, they didn't specify which detail object to place there, just that it would be some kind of detail there. This was intentional, I wanted to be able to use the exact same logic for every area in the game. So I started giving the areas unique ID's and making lists of stuff that would spawn there; beds in the dorms, boxes in the storage, gold piles in the treasury, and so on. This worked great, but it wasn't random enough.

Same room piece as above, this time showing node data

All the objects spawned in the same locations of same pieces every time, it was pretty obvious that the dungeons were made from pre-designed rooms. I didn't like that, so I went ahead and added a new type of rule for each area: spawnrates. A very simple thing that did so much. I set a percentage of available nodes to use when spawning, for each type of entity to spawn (breakable objects, monsters, etc). However some required even more control, so I made those into static numbers (chests, shrines, secrets). This meant that I could specify an area to have for example 80% breakable object coverage, 100% light source coverage, spawn 5 chests, 2 shrines, and 1 waypoint portal. And it'd do so, picking the locations of randomly selected nodes. I now had pretty solid control over spawns, but the general outcome of dungeons was still pretty random, and beside tileset & detail, not much separated the various dungeons.

Design

Now how would I do this? It made little sense that an area labelled "The Tunnels" looked pretty much the same as another area called "Temple Halls". Tunnels are generally.. tunnel-y. My solution; A custom algorithm for each area. Perhaps not the best solution, as it adds on a lot of work, but it gives me a large amount of control over the general design & layout of the area. Which is, after all, what I wanted. So after some tweaking, I managed to make separate base algorithms to force certain basic layouts, upon which the old general algorithm later was applied to extend the dungeon further (and randomly) from the controlled base. A little tricky, but here's a gif to explain.

The Hall of Prayer, one of the later areas of the first chapter.

This area first places a central room, always the same room, followed by 8 corridors in all 4 directions. These corridors will always vary in lengths and types of rooms used. That's the "base" algorithm used. After this is done, the general algorithm is applied, placing all those other rooms & making sure they connect. Once enough rooms have been placed, any open connections are sealed off with walls, and then the nodes are checked and the proper objects are spawned. Neat!

Here's a simple "Tunnel" generation algorithm, for good measure.

After this was done, I took an additional step; why should the Halls use the same room designs as the Barracks? That makes no sense, so I made the various areas have access to different types of rooms, giving each area it's own design & feel.

Example of a Barracks area layout:

Now, there was only one thing left, something that those familiar with coding (and GameMaker in particular) might have been concerned with from the time I mentioned sprites...

Performance

The very important and equally annoying obstacle to tackle. Reading pixel data from images is actually pretty slow, and not a good method at all, especially not on the scale I was doing it. So I needed to fix that. The solution? Buffers! I simply read each room sprite that is to be used into buffers, converting them into raw data, and then I read this raw data when generating and building the dungeon. It is lightning fast, relatively speaking, and a completely acceptable speed for a final product.

Conclusion

This method suits all my needs, and I'm quite satisfied with it. I'm excited to start working on algorithms & room pieces for the next areas on Chronicon, as there will be several outdoors & natural areas. It's going to be a lot of fun!

I hope you enjoyed this article, stay tuned for more articles & devlog updates on Chronicon!

In-game dungeon, with the minimap showing the generated layout