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 refering 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: Supermetrod Spoiler!):

http://www.snesmaps.com/maps/SuperMetroid/SuperMetroidMapNorfair.html

Well, after spending some time thinking about this I have some ideas to create the maps that I would like to share with you:

1) I have read about celular automatas and I would like to use them to carve the rooms but instead of carving just a tile at once I would like to carve full columns of tiles. Of course this carving system will have some restrictions like how many tiles must be left for the roof and the ceiling, etc... This way I could get much cleaner rooms than using the ussual automata.

2) I want some branching into the rooms. It will have little probability to happen but I definitely want it. Thinking about carving I came to the conclusion that I could be using some sort of path creation algorithm that the carving system would follow to create a path in the rooms. This could be more noticiable if we make the carving system to carve columns with the height of a corridor or with the height of a wide room (this will be added to the system as a param). This way at some point I could spawn a new automa beside the main one to create braches. This new automata should play side by side with the first one to create dead ends, islands (both paths created by the automatas meet at some point or lead to the same room.

It would be too long to explain here all the tests I have done, etc... just will try to summarize the problems to see if anyone could bring some light to solve them (I don't mind sharing my successes but I think they aren't too relevant):

1) Zone reachability: How can I make sure that the player will be able to reach all zones I created (mainly when branches happen or vertical rooms are created). When branches are created I have to make sure that there will be a way to get onto the new created branch. I mean a bifurcation that the player could follow. Player will follow the main path or jump to a platform to get onto the other way). On the other hand if an island is created by the meeting of both branches I need to make sure the player will be able to get onto the island too.

2) When a branch is created and corridors are generated for each branch how can I make then both merge or repel to create an island or just make them separated corridors.

3) When I create a branch and an island is created becasue both corridors merge at somepoint or they lead to the same room, is there any way to detect this and randomize where to create the needed platforms to get onto the created isle? This platforms could be created at the start of the island or at the end.

I guess part of the problem could be solved using some sort of graph following the created paths but I'm a bit lost in this sea of precedural content creation :). On the other hand I don't expect a solution to the problem but some information to get me moving forward again.

Thanks in advance.