Crypt of the NecroDancer (2015)
Simply the best procedurally generated dance-rhythm roguelike dungeon crawler I’ve ever played.
I mean, it’s not like there are a lot of those. But there are some interesting things going on procedurally. The long-term progression of the game revolves around unlocking new content and tools, which are then seeded into the dungeon generator. There are also procedurally-generated mini-puzzles in the dungeon, in the form of optional characters to rescue by finding the key that will let them out.
It’s more about items than about the terrain (though there are also ways to alter future generation) but it is a very effective coupling of the generator and gameplay, and one that other roguelikes could easily borrow from. Imagine taking it further, with your progression unlocking new rooms or other terrain content for the generator.
But NecroDancer deliberately keeps the dungeon generation itself pretty simple. Each level has a handful of rooms, connected with corridors, and maybe a shop or some hidden chambers. These are not huge levels. But they don’t have to be: NecroDancer is comfortable with letting the main rhythm mechanic dictate the pace, which means the time you spend exploring is more frantic than even a game with time-limited levels like Spelunky. The tight constraints mean that you don’t need a huge open world.
The other reason that the levels work is because you can alter them. Your shovel is nearly as important as your weapon, and smart use of digging combined with items that alter how you dig opens up new tactical options and changes your relationship with the procedurally generated terrain. Effectively, the game mechanics mean that your interactions with each level are operating on several levels.