#map generation

Some nicer screenshots from maps I found while I was debugging other stuff. Water still needs a lot of tweaks, but it already looks pretty good.

Better Constraints for Better Dungeons -

Aran P. Ink has been making a procedurally-generated metroidvania, and has been dealing with a specific problem: the generation wasn't serving the design pillar of exploration. Procgen should be perfect for giving the player new things to explore, but the common way to structure a generator wasn't working.

The maps were too predictable and obviously repeated the same structure, the exact opposite of what you want in an exploration game. Since the rooms were all the same size, it made it much harder to make them feel different enough to be memorable. Basically, not enough contrast.

The solution? Relax the constraints. Or, to put it another way, rethink the constraints from a different point-of-view. This led to a solution that's unique to their particular game.

The same idea might also work for your game, but I think a better way to approach this is to learn from the process and goals, rather than just the solution. Maybe think about the map design from an entirely different point of view, or generate history backwards, or introduce a mechanic that uses the generator's weakness, or set up the framing to make the generator's result feel natural.

Oh by the way: If you plan on continuing your old save file, expect to see some sillyness like this, when uncovering new terrain!

Adding in some more height interpolation, so there are fewer giant cliffs all over the place. Sometimes you do want a giant cliff. But not all the time.

Also there's still a big sheet of debug water under the ground, it's just mostly hidden now since all the additional noise is raising up the average height. But sometimes there's a big pit right next to the town that happens to reveal it.

Procedural Map Generation Techniques (Roguelike Celebration 2020)

This is a great survey of roguelike map generation techniques by Herbert Wolverson, covering a ton of different techniques. He uses animated illustrations to demonstrate how different algorithms work: random room placement, BSP subdivision (used by Nethack), cellular automata (good for caves), drunkard’s walk (aka random walk), diffusion limited aggregation (including adding attractors and symmetry for more control), Voronoi cells (plus using different distance algorithms), Perlin noise (commonly used for landscapes, but Ken Perlin’s invention is useful for a lot of stuff), and the use of prefabs (or “vaults”). He proposes the use of a Dijkstra map as a way of reading the map so you can do things like remove unreachable areas, or place the starting point in a reasonable spot, or figure out which parts of the map are on the golden path.

One important thing Herbert highlights is the importance of context and control in designing a level generator: the randomness is “fed into an algorithm that that approximates what you want to get but ensures that it is different every time.” 

He also talks about combining generators, which is something that can get lost when cataloging different techniques: there’s no one perfect algorithm for generating a roguelike map, and combining multiple techniques can result in something much more interesting than a single generative operation could make on its own.

His tutorial for making a roguelike in Rust has a lot of universally applicable algorithmic stuff, including even more map generation algorithms, so there’s also lots of material if you want to go beyond the already information-dense talk itself.