This article is out of date. I’ve redesigned the algorithm for several reasons. There’s an updated post here, albeit with a different writing style.

This is an update to my previous post on procedural generation, where I proposed an algorithm for generating dungeons with puzzles including:

  • Keys and locked doors;

  • Switches that must be used to activate pistons that unblock paths;

  • Items that grant new abilities to the player that permit access to new areas (such as the Roc’s Feather or the Power Bracelet in Link’s Awakening).

These items have very similar properties and an abstraction that treats them all as boolean variables permits levels to be generated in such a way that every room is reachable, and the dungeon is guaranteed to be solvable (see Part I for the details). Purely random placement of keys and locks cannot achieve this.

Lowering, a post-processing phase over the results of this algorithm, generates the exact layout of walls, floor tiles, items and enemies. As this phase will be different for each game that uses the algorithm, I haven’t explained this in detail.

An implementation!

The algorithm took about three hours to implement in Java, including the viewer, and I’ve uploaded it to github. All the important data-structures and the algorithm itself are in the package net.bytten.metazelda.

I’ve added very little tweaking to the probabilities that the algorithm uses, so a lot of the results are garbage, but there are still some very interesting dungeons that come out of it.

How to read these diagrams:

  • Circles are rooms.

  • The player starts at the “Start” room, and tries to get to the “Goal” room.

  • A letter inside a room is an item that the player can get while inside the room.

  • Arrows are unidirectional edges - the player can move from one room to another in the direction of the arrow, but not the other way.

  • Non-arrow edges are bidirectional - the player can move in both directions.

  • Both unidirectional and bidirectional edges may have conditions attached, which are a list of items the player must hold to be able to move along the edge.

Tweaks

There are a lot of ways to improve the implementation without significantly modifying the algorithm, and I intend to keep updating the github project. Here are some ideas I’ve had:

  • Dungeons can be quite strung out at the moment. I could bias the randomness towards keeping near the start node.

  • Producing dungeons within a particular shape would be interesting to try. Dungeons in Zelda are often designed into particular shapes, e.g. skulls, keys.

  • Some dungeons are perhaps too non-linear, and require a lot of backtracking. Tom Vernon linked me to an article about level-design in The Legend of Zelda after I published Part I. Some ideas could be taken from that. Perhaps if I can design a programmatic way to measure “linearity” partway through construction of the dungeon, the algorithm optimized for slight non-linearity.

Bugfixes

In the original algorithm, there was a flaw in the handling of dead-end branches in “backedge”-generation that would allow a player to get trapped in a subset of rooms. It assumed that to reach the current room, all already-placed rooms must have been visited. This is not true for dead-ends, which are optional.

The Java implementation adds unidirectional edges to neighboring rooms in a different way - it actually computes the preconditions for entering each of the rooms as they’re generated and later on checks that the new room’s preconditions imply the neighbor room’s preconditions. When this implication holds, the player is guaranteed to not get trapped. In addition, by testing the implication the other way we can efficiently find out whether a bidirectional edge can be added without creating a short-cut past a locked door.

I recently came across Ashmore’s scientific paper “Key and Lock Puzzles in Procedural Gameplay” that covers similar grounds. Although it doesn’t specify an algorithm that generates solvable key and lock puzzles, it does describe the concept of an evaluator that selects the “best” puzzles, and what characteristics might be selected for. Another interesting note from that research is that the puzzle generator cannot be completely divorced from the “renderer” (which I called the lowering phase) because not all valid abstract puzzles correspond to rendered games (lowered dungeons).

Imported Comments

2012/01/28 » Mike

Hey there,

I saw this on /r/gamedev. This is a really nice bit of code, I like it a lot! You mentioned “Items that grant new abilities to the player that permit access to new areas” – are these procedurally generated also, or designed by you by hand prior to generation?

I’m working on academic research on automated game design, and recently I knocked together a rough-and-ready Metroidvania generator (you can read a bit about it on my site) so I’m really interested to hear about stuff like this.

Cool stuff indeed. Good luck with the dev!

Mike

2012/01/28 » tomc

The equipment items are treated purely abstractly by this algorithm – i.e. exactly the same as keys. For my game, I intend to randomly select the item from a list of pre-programmed ones during lowering, but procedural generation of these items would be a very interesting topic.

I will check out your Metroidvania generator. Thanks :)



blog comments powered by Disqus