Objective: A full-scale random map generator that is indistinguishable from a hand-crafted experience. Will we get there? Who knows!

Analysis:
Metroidvania games are based around tight hand-crafted experience. Levels are built in a way that encourage backtracking, to show improvement in the player's avatar and skill over time, a lock-and-key system to gate progression, and repeat playthroughs tend to change the way the game is experienced though advanced tricks or sequence breaking.

Procedural generation has the opposite promise. Every playthrough and experience has been shuffled, randomized, or otherwise changed. Each run is novel and unique. The world itself is unknown until explored and discarded at the end.

These two experiences are fundamentally incompatible. Combining the two will end up compromising on the promise of one or both experiences. This may be a small way, but

I believe the incompatibility exists on an experiential level. Super Metroid is a masterpiece of gaming; a randomly generated Super Metroid game is the holy grail of game design. Attempting to make a randometroidvania game requires a high level of design skill. The idea has been attempted, but it's hard. Let's take a look at why.

Problem 1: Randomized games are a lot less memorable

The core promise behind randomizing a game is that it is novel and unique. Seeing something for the first time is exciting; imagine seeing everything for the first time every time you started up a game. It would truly be a unique experience that can be shared and related to other people. There might be some common thread running through the gameplay, such as building a dirt house in Minecraft, but that common thread could happen on top of a mountain or next to a river or even inside a cave.

Experiences have narratives. Anyone who plays a game becomes the main character in their story. If the story is about making a tree, then it might involve research, a sketchbook to draw out a rough design, scanning, painting, and eventually taking the finished piece and putting it in a game. It might be about pulling up the dictionary in Scribblenauts and dropping a tree on a vampire. It might just involve bone meal to magically sprout a full size tree out of a sapling. The story itself is how we share games, and "random" games tend to be bad at this.

Trying to build something "random" makes building up the story of the world difficult. It's a lot easier to describe a single tree in a field than a single tree in a forest. It's also a lot easier to describe a forest in space than a forest next to a plain next to another forest next to a lake next to another forest. Differentiating the first forest from the last is difficult enough when the game is static; when the game constantly shifts around under its own weight, you miss the forest for the stars.

Procedural games tend to make everything into the forest: level elements are cookie cutter, bland, and can be shuffled around or inserted at any given point. Every piece in the story needs to be self contained and inserted into an experience at any given point. Relative difficulty over a scale becomes impossible to pin down, and the closest thing you'll see is that an area is more difficult because the monsters in it have more health and damage.

Cookie-cutter rooms are a design trap. If every piece needs to fit everywhere, then every piece needs to be more-or-less the same. Sure, the level might have some difference in the way it looks, and later parts of the game may have more traps or features to traverse, but they still can't have much variation.

If every piece is generic, then every piece is the same. If you're doing the same thing again and again for a few minutes, it's going to get boring. Why would you do a repetitive task that merely has slight variations? It's almost like the designer lost part of the design in the process or didn't know how to handle this to begin with.

Many games treat procedural generation as a blank check to replace what would be interesting and engaging content with novelty. The systems can be the best technical gameplay ever made and they will still be disappointing if there is no challenge or variation to use it on.

This problem rears its face again and again across any game with a randomized system. The problem can be solved; the best randomly generated games have a particular idea or experience they're going for. The randomness may blend into the background, or it may become the centerpiece of what the game is trying to express.

Random generation done right can can be better than hand-crafting everything. When it's done poorly... well. Let's just say that the results don't speak for themselves.

Problem 2: Procedural levels do not tell a cohesive story.

If we define a dungeon as a series of traps and pathways full of loot and danger, then Super Metroid becomes one of the greatest dungeon crawlers of all time. Its platforming system is quirky and floaty. The game is easy enough that a random person could pick it up and have a fun time over a 10-20 hour experience, but the skill ceiling is high enough that the human limit may not be reached. The game even has the same constraints as a lot of modern procedural counterparts: the entire game is a series of rooms and tubes connected up at doorways.

Super Metroid's greatest strength is in the way player skill is handled. A new player will find themselves fumbling through the entire world looking for the next upgrade. They will stumble into areas that show that Samus has skills that the player doesn't know about: running, wall jumping, and the shinespark. Once the player has mastered each of these skills, a new game opens up. Suddenly you can go where you hadn't before, beating the game "out of sequence", and with enough practice the common experience that everyone had when they started gets shattered into a wide variety of routes and choices.

(Above this plant is an item that needs a shinespark to access)

The unchanging map also lends itself towards mastery over the game itself. There are tiles placed strategically around the level to show where certain tricks or borders are. The level may seem a bit dull at first, but every tile, enemy, and doorway is placed in a way that notes "I am here". Even the smallest detail can be used as a visual cue. Combine that with completing the game out of order - sequence breaking - and eventually you can go anywhere in the game at any time provided you have the personal skill to do so. 

Super Metroid's story is something that can be explained as "I accidentally found a new area, got an upgrade, and then went back and did it again. The varia suit lets you run in super hot rooms to find a speed booster that turns you into the flash, and there was a boss the size of the entire screen, pools of acid to burn your face off, and the planet exploded!"

You'd be forgiven for missing out on the details of your journey. I'm sure each area was memorable, and subsequent trips will make all the little things shine.