#level generation

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.

taking a break from art to work more on the procedural level generation code

overall level is a 2d grid of square rooms, all blank. algorithm picks one random room to start building, and then picks a random direction to move in, "building" a new room as it goes. algorithm continues to move "forward", building new rooms connected by doors, occasionally switching direction or splitting to form a sub-path.

just made it so that some "rooms" are classified as hallways, meaning that they are just a narrow path from each door to the center of the room, rather than having a large open middle

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.

One Page Dungeon generator

This one-page dungeon generator by Oleg Dolya (also known for the Medieval Fantasy City Generator) goes beyond the basic throw-rooms-together dungeon generator to have a focus on content. It includes descriptions and room prompts, often with implied connections between keys and locked doors.

There’s a number of ways to add more structure to content like this, including cyclic dungeon generation, but one of my favorites is a little similar to what appears to be going on here with the keys.

Without looking at the source code, the design pattern behind the keys appears to be: 1. have a locked door 2. place a key in a room that can be reached without crossing that locked door. Pretty simple, but creates interesting structures for the players to discover. This can be elaborated to include a chain of things that the player can encounter and piece together the entire story.

One place I’ve seen this used to great effect is Emily Short’s Annals of the Parrigues, with some of the footnotes: a series of footnotes is written in a way that describes an arc, and then the generator is allowed to include the next element from the arc when it feels like it.

If you wanted to make a dungeon generator like this, you could add pairs or triplets of elements to include. A simple one might be a monster, its lair, and it’s most recent victim. Because you are hand-writing these element groups, you can make sure there’s an implied story or relationship. If you’ve got enough of these, mixed in with the rest of the content, they will still feel interesting even if the player sees them a few times.

Another related form of content to include is a recurring motif. Right now the One Page Dungeon generator creates a lot of dying elves in corners and similar things, which a skilled Dungeon Master could spin into a story. But promoting too much mushroomy content can feel like the generator is making a mistake. Pushing the uniqueness of the elements makes it look deliberate.

One thing that King of Dragon Pass (and Six Ages) has taught me is to not be afraid of being specific! Finding the coral-encrusted Mirror of the Dark Wizard Archronalax and the coral-encrusted throne of the Dark Wizard Archronalax  will make the players start to wonder where the coral-encrusted magic wand of the Dark Wizard Archronalax is. Having some hyper-specific elements that are spread out across many generated maps gives the generator character.

Think in terms of motifs, of aesthetic signals that can tie different parts of the generated level together, of ways to create emergent resonances between independently generated elements. Which brings me to my last point for now: the simplest way to have elements in your generator work with each other is to write them with a lot of suggestion and storyful-ness. One Page Dungeon is pretty good at this already: A reinforced coffin containing a blood-spattered spear and a cursed hammer? There’s clearly a story behind that!

While there are many existing dungeon generators, there’s plenty of room for new generators that have their own character and ways of telling stories.

There’s lots of space for more dungeon generators to explore!

Map Generation in the 7DRL Get Well Soon

I’ll talk about the actual 7-day roguelike game itself eventually, but this dev blog post about using WaveFunctionCollapse to generate levels caught my eye for both the technical results and the description of the process of working with a PCG algorithm.

I’m always interested to see the processes that other developers use: what problems did you run into, how did you approach solving them, why did you make those particular design decisions?

For the use of WFC specifically, the two things that caught my eye here was the emphasis on the image-based pipeline for prototyping with WFC and the use of additional constraints.

In my opinion, one of the most powerful aspects of WFC for PCG development is that the interface can be entirely based on the images you give it. Rather than writing rules or dragging sliders around to find the right numbers, you can use the intuitive interface of painting what you want the thing to look like. In practice it’s a little trickier than just painting an example, since it learns long-distance relationships and particular constraint rules from the image, which can take a little getting used to. But the main point is that an artist, with no understanding of the code, can start playing around with it and gain an intuitive understanding. At the same time, an expert can fine-tune the output with the same image-based interface.

Being able to play with the inputs to a generator is a massive productivity boost. We go from painstaking experiments, moving one knob at a time, to trying whimsical combinations that open new possibilities.

At the same time, the image-based interface does have its limitations: some things are more easily expressed in other ways. We still want to use the image-based interface, but at the same time we want our images to have an additional layer of information: for example, making sure that the rooms we generate are eventually connected with the front door. In this case, some of the added rules were removing the fully-white tile from the adjacency rules and adding some additional border-selection logic. These can be added, and I’ve implemented variations on this myself--but, of course, one of the strengths of WFC is that you don’t need to know the code. (Which is why one of the things I’m working on is trying to find effective ways to express new constraints in WFC, to make it integrate better with a pipeline. But that’s a topic for another day.)

Scanline

“A procedurally generated platformer made for cgajam” - It lives up to the billing. And, of course, the color scheme is gorgeous.

It’s not without its faults--I found it to be brutally hard, which is a common hazard for game jam games. I’m not that great at action games to begin with, and the constant dying made it hard to really appreciate the level generation.

(General rule of thumb for game jams: your game is too fast and too hard. 90% of the games I play from Ludum Dare can be vastly improved by addressing that. Ideally, get someone else to play it and watch them. If you can’t, try giving yourself a handicap, like an off-screen distraction, and see how it affects your performance.)

And it’s prone to lots of rapidly flashing colors, so watch out for that.

Still, putting together a complete, original, procedurally generated platformer in a game jam is quite an accomplishment. It’s the kind of thing that looks easy from the outside, but can be surprisingly tricky to pull off this well. Even research projects that replicate Mario levels take a lot of work, and they’re just borrowing the rules from an existing game.

Procedural 2D Worlds

I recently came across this writeup by Nick Gregory about generating an explorable 2D platformer world.

Metroidvania-style platformers are 2D games that are built around the idea of large, explorable worlds. This presents some interesting challenges for procedural generation, but also some opportunities.

Nick presents a procedure for building rooms within the world that conform to the needed properties: you have to be able to get to the exits, for example. Platforms need to be high enough to be interesting but not so high that you can’t jump onto them.

It’s interesting to contrast this with something like Spelunky, which is in a similar space but takes a very different approach to level generation.