I have been searching for information about how to build a 2d world generator (tilebased) for a platformer game I am developing. The levels should look like dungeons with a ceiling and a floor and they will have a high probability of being just made of horizontal rooms but sometimes they can have exits to a top/down room.
Here is an example of what I would like to achieve. I'm referring only to the caves part. I know level design won't be that great when generated but I think it is possible to have something good enough for people to enjoy the procedural maps (Note: Super Metroid Spoiler!):
http://www.snesmaps.com/maps/SuperMetroid/SuperMetroidMapNorfair.html
An idea I had to accomplish this was to let the computer play a level and carve the dungeon as the "computer player" plays. But don't know how to handle branches in the way, etc... Using this way of carving I could be confident that at least an exit exists in the map and that it is reachable.
Another idea I had was using a cellular automata with some heuristics to do the carving. A problem arises here: how could I make sure that all zones carved are reachable by the player (that is limited by gravity, etc...) ?. I guess I could use some kind of graph that could follow the different dungeon floors the automata is carving and then somehow I could measure if some part would be reachable or not by the player and add platforms or new terrain to make it reachable.