I want to have a semi-procedural level, where rooms are pre-made but the way they're connected are proc-gen. The connections need to really exist - you can walk between rooms in hallways - not just teleported between rooms like in old games.
Each map will have a set number of rooms. Rooms should be laid into a grid(not necessary fill it) - all rooms and hallways will have the same size. Every room must lead to the exit(no dead end), except for 0 to 2 "secret room"
There can be 1 to 3 paths from start to finish; these paths may intersect. They should be relatively straight(no 180 turn or more).
There can a few rare "secret room" that are dead-end, but can only be one room depth:
+-----+ +-----+
| | | |
| End | | End |
+-----+ +-----+
| | | |
+------+ +-----+ +------+ +------+ +-----+
| +---+ | | +---+ +---+ |
| This +---+ | | Not +---+ This +---+ |
+------+ +-----+ +------+ +------+ +-----+
| | | |
+-----+ +-----+
| | | |
|Start| |Start|
+-----+ +-----+
Is there a popular algorithm can I use to accomplish this?
One that was recommended by some people here is BSP Tree. It doesn't fit my requirement since the path it creates is too spiral, and depend on the number of corridors, it either creates too much path or too many dead-end.
The only thing I can come up with is to just add rooms one after another in random directions. There are 2 problems I can see and don't know how to solve:
How to create multiple natural paths(not just an L shape or straight line) that end up at the same location.
How to make sure the path doesn't become a spiral and block it self from advance further
Edit: I found this that that kinda resembles the structure I need, but with diagonal hallway.
[procedural-generation]
and maybe another term likerooms
ordungeon
into the search bar at top right you'd have found many, many questions on this topic just on this site... let alone googling same terms. Moreover, your question is underspecified, making it impossible to give one correct answer without making numerous assumptions, so I'm voting to close. \$\endgroup\$