Map Generation in Lenna’s Inception
It’s worth taking a deeper look inside the procedural generation of Lenna’s Inception, because Tom Coxon has written a lot about it and given talks.
The generator actually starts with a smooth perlin noise map, which gets posterized into discrete height strata–perfect for the top-down 2D RPG style.
(That’s a useful technique to remember: even if you’re making a map with discrete binary barriers, like an oldschool NES game, you can still use more complex source data for your inputs. Under the hood it’s all math, and harnessing unusual inputs that have a hidden order can help give the map structure.)
The generator is specifically designed to keep the player in a flow state of not-too-hard-not-too-easy challenges. It uses a lock-and-key system to guide players through the game, encountering challenges appropriate to their level. The key’s don’t have to be literal keys; any tool or ability that gives the player access to new areas can be a key, and any terrain or enemy that blocks a player’s progress if they don’t have the right ability can be a lock.
You’re probably familiar with this kind of pattern: it’s been used by games going back to Doom, Metroid, and, yes, Legend of Zelda.
Since it knows what keys are required to reach certain areas, Lenna’s Inception can use this information to guide the placement of enemies, treasure, and other challenges, making them gradually harder and more complex as the player gains new abilities to deal with them.
The lock-and-key principles could theoretically be used to generate a metroidvania, or any other form of action-adventure where open-world content is gradually unlocked. Tom has released the lock-and-key algorithm as the open-source metazelda library, which you can use in your own games.
Lenna’s Inception also uses the lock-and-key information to place the walls and other barriers in the game. Since it knows what order the rooms (or parts of rooms) can be visited, it can place them dynamically in interesting patterns, and plan out the entire overworld.
The action-adventure structure of quests, puzzles, and lock-and-key progression that was pioneered by Legend of Zelda and games like it is the inspiration for entire genres of games, including those that look quite different. It’s be interesting to see what someone could do by taking these techniques and using them to procedurally generate a Metroidvania. Or Doom campaigns. Or a city for Mirror’s Edge.
http://bytten-studio.com/devlog//2014/09/08/overworld-overview-part-1/
http://bytten-studio.com/devlog//2014/09/15/overworld-overview-part-2/
https://github.com/tcoxon/metazelda