I’m back again! This time I’ve decided to write independently about my various projects and work, mostly as a record of what I’ve been working on.
Procedural generation of dungeon maps
I’ve been looking into roguelike games recently, and while a lot of them are fairly impenetrable or just not the kind of game I like to play, I do enjoy the procedural generation aspect, particularly in how terrain and maps are generated.
My motivation for exploring these techniques is to expand on my prototype project Dungeon, which is a concept for a sequencer where items in the field can be picked up and placed in a step sequencer at the base of the field. My current procedural generation technique leaves a little to be desired:
Not the most inspiring terrain. Even when scaled up (as in the prototype Dungeon16), this technique isn’t very interesting, as it is still effectively just a rectangular room with obstacles peppered throughout:
These were created by a simple 50% chance of an empty space becoming a wall, and then carving away at the walls using a few rules (e.g. no large clusters, no shapes that frequently result in unreachable areas). It’s not a bad start, but clearly I needed to research some expanded techniques.
This video was incredibly useful:
A lot of the techniques are somewhat inappropriate for my use case, but the one that stood out most to me was diffusion-limited aggregation, which involves starting with a small open area and firing “particles” at the walls to extend it. My interpretation of the technique may be slightly different to the one explained in the video, but it was surprisingly simple to implement something with a similar outcome.
As mentioned, the inital state is a small open area, in this case 4×4 tiles:
Next, I implemented code that would generate a particle at a random position in the field, and if that position contains a wall, it would try again. If the position is empty, it would start movement, one tile at a time, in a random orthogonal direction. As soon as it hits a wall, it destroys the wall, and then stops. A new particle is generated and the cycle repeats.
My first experiments with this, and 100 particles, weren’t very interesting:
I increased the particle amount to 1000, and.. still too blobby:
It wasn’t giving me the kinds of obstacles I wanted in the middle of the field. It’s good for large open areas, but I’m not really looking for that.
I wrote a rule that would only allow for walls to be removed if tiles next to the target tile contain a wall (currently above/below, left/right, and two diagonal cases). This alone resulted in some much more interesting maps:
At larger sizes, these tend to look much more like the kinds of maps I’d expect from an effective procedurally generated game:
I could probably tune this algorithm a little more (and there will need to be some tuning in order to ensure access to the sequencer row at the bottom of the original version¹) but I’m very happy with this result, which only took me a couple of hours to develop—including the p5js editor crashing and losing my work last night.
Notes
- A possible solution to the access to the sequencer row could be to contain it in a separate screen or menu, but this may detract from the experience due to a disconnect between the game world and the sequencer. There’s a very specific implication that the player is picking up and dropping the objects in the current prototype versions which would be lost if it were treated like an inventory puzzle.