Hey guys! I’m making a top-down RPG-ish like game and I wanted to add randomly generated dungeons. I’ve generated a maze randomly before but I don’t want for all the rooms of the dungeon to be the same size. Basically, what I’m wondering is how to go about generating the dungeon. My previous attempts were all disastrous. So any help or related algorithms would be very much appreciated, thanks!
Oh, that looks interesting. I haven’t learned BSP Trees yet so I’ll go look into more. Thanks!
Hey,
I wrote this article. Feel free to get in touch if you have any questions… More than happy to help out.
Cheers,
Bach
Oh wow, that sounds good. I’ll get in touch if I run into any walls. Though that might be a while since I’m still learning more about trees, still somewhat of a beginner at computer science in general.
Thanks! I’ve implemented the basics of it but the dungeon it makes are pretty ugly, at the moment. I’ll have to work on fixing it up.
Bahahahahahahaha nice unintentional pun ;D
LOLZ!!!
Sorry I haven’t been able to get back to you guys, but I’ve been pretty busy with finals and tennis.
I only recently got some time to work on the dungeon generation and was able to get decently randomized rooms, but I’m wondering what the best way to connect the rooms is, because my last attempt resulted in some bad looking dungeons.
http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorithm-recap documents 11 different algorithms you could use.
Wouldn’t that require rooms to be all the same size?
There might way that I might be able to adapt it to random room sizes though, not sure if it would actually work.
What I was thinking was that you could use the recursive back tracer, since it creates a maze that everywhere in the maze is accessible from everywhere else. Then randomly carve out random sized rooms from the maze.
Hey,
the way I do it (as described in the above linked article) is to create a bsp tree. Once the tree reaches the desired depth (== room size) you just traverse back up the tree and connect neighbouring nodes.
The actual connecting can be very simple: Find centre of node A, decide which direction node B is (N, E, S, W) and create a straight line to the room until you reach an empty tile in node B.
You can obviously do this a lot more complex if desired by using a pathfinding algorithm. However, I’d try the easiest first and see how you go 
Cheers,
Bach
Alright, I’ll give it a shot. Are you using 2d arrays to hold the tile type and just changing the value when you connect them?
Yup, at dungeon generation time I just keep a 2d integer array. Once the dungeon is generated I use more complex types to keep track the individual tiles.
Let me know if you run into any problems, happy to help
Cheers,
Bach