Before I begin please note that "MyNameIs" is... well me.
I accidentally created two accounts trying to link up my account with my google account,
and now I am now locked out of my google account... account.
But don't worry, this is my main account from back when.
Anyways, lets get started.
Procedural Level Generation is an art form of it's own.
Respect it, and you'll attain replay value for your customers.
Disrespect it, and your levels will be totally lame and people will laugh at you behind your back.
Like they do at Diablo.
Anyway, lucky for you, I am a supreme bad ass at this kind of thing and I want to help you out.
Double lucky for you, I like to listen to myself... type? So I wrote like a five page document here.
It took FOREVER.
Seriously though, its a privilege to be in a position to help, sir.
This is actually super easy for me, but apparently can be quite tricky for many people.
If you're having trouble, Just remember that the goal is to (1) find guidelines that, when followed, produce good levels, and (2) teach them to the computer.
THE DUNGEON BASE
Okay, lets keep the square tile system. It's possible to use other methods, but this seems to be the one you (and most people) are more comfortable with. Don't worry at all, its as good of an approach as any.
An important decision you're going to have to make is "should squares be floors AND walls?"
Dungeon crawls tend use tiles as walls, but in 3D this isn't really necessary.
But it does make certain things easier.
You can actually just place walls between each tile, and work with them that way.
A good strategy for this is to keep an array of North and East walls. Or two arrays, whatever.
Don't worry about South and West walls because they're are somewhere else's North and East walls and you'll let wherever know what you plan to do.
And consider throwing out 1 unit hallways. 2 to 6 unit hallways work just as well. Lets the level seem more flexible.
And if you throw them out you can still use 1 or 2 unit walls, so you get wide halls but thin walls. Nice.
THE ROOM BASE
The first question we can ask ourselves is "how can we describe the kinds of rooms we want to create?"
In your example the rooms you display can be thought of as simply a rectangle, two rectangle, three rectangle, and a circle.
(Don't worry about placement and collisions yet, we're just thinking about moulding some room concepts first.)
IN THE BEGINNING, THE SERPENT OF CHAOS CREATED... A RECTANGLE
So we begin by generating a rectangle. You probably want this to avoid having either length or width as 1 unit.
STAY GAUSSY, BABY
I recommend rolling 2(d5) or 2(d6) for this. This will give you a bit of a "Gaussian distribution", making rooms tend to have an average size.
(Remember to add two random numbers, don't double! )
You can increase the "Gaussiness" of the dungeon by rolling more and more dice, and then getting the average roll and rounding it.
Gaussiness will prevent you from having rooms with a large variation in size.
If you do that, it's better to roll from 0 up, and add a constant minimum after averaging.
And if you want that its better to build it in from the get go, because its a super set of the above method of rolling dice from 1 up and not averaging them.
A THOUGHT ON ROOM SIZEMENT
As you can imagine, room size is very important.
If you want some big rooms and some small rooms, you can add a constant that way to the big rooms, like +2,+2 or +4,+4.
You can also enforce rooms to avoid being square on average by adding something like +2,+0.
Okay, now that we have a rectangle room, how do we make it more interesting?
You have two choices. You can manually build a bunch of interesting rooms, or you can generate them.
I think we're above doing manual labour, lets make the computer generate them!
CLASSIFYING ROOM CONCEPTS
The above examples add a secondary or tertiary square in a number of manners.
The first room does nothing special. It's important to do nothing sometimes. Its easy to forget that and add all the bells and whistles every time. We'll call this a type 1 room.
The second room is arguably the most interesting. We'll call it type 2 and have to come back to this one.
The third room can be thought of as two squares connected in such a way that they share a face smoothly. We'll call this a type 3 and come back to it as well.
The fourth room is a 1x1. We'll call this type 1A, I want to talk specifically about this one as well.
The fifth room is another type 1 room, but unlike its sibling, it is not perfectly square.
The sixth room is simple two squares connected in such a way that they DO NOT share a face smoothly. We'll call this type 3A.
The seventh room is a cross shape. We'll call this type 4.
The eighth room is a T shape, but we're going to call this a type 4A for now.
The ninth room is a doughnut shaped room, a type 5.
The final room is pretty small - we can call it a type 3 I guess.
Now lets go into detail on the properties we're seeing here.
Type 1 rooms are simply squares or rectangles. As I said earlier, they are special because they are not special. Remember that, it's actually extremely important.
Type 1A is the only room of it's type to boast a width or length of 1. It's more of a closet or micro hallway to transition between rooms.
It's important to the authors of that paper, but it can cause problems for us if we try to carelessly populate it later on.
NOT TYPE 2
Type 2 rooms I'll cover in a moment.
Type 3 rooms can be created in two ways.
We can combine two rooms together so that one is aligned with the other's wall.
Alternatively, we can take two rooms, add some constant to the larger of the two, and subtract the smaller room from one of it's corners.
Notice how we can create the same room in more than one way. That's a key thing to remember as well.
The small type 3 should make more sense in this context.
Type 3A can be created in the same two ways.
We can combine two rooms together so that one isn't aligned with the other's wall.
Or we can subtract a room from two corners. In this case it would be prudent to ensure that neither subtraction is larger than half the room.
Types 4 and 4A can be created in more than one way as well.
You can take a square and bevel off it's corners.
You can add a single row that's shorter than a given side along it - either at a constant offset (in this case 1 for each) or a slightly random offset.
TYPE 2, FINALLY
Getting back to type 2, we can do a similar approach for this one as well.
We can add to both edges near each wall.
We can subtract a single row from each wall.
We can connect three squares together.
Type 5 is also arguably the most interesting room. It's the only somewhat round room.
An easy way to do this is to take a square and check the distance of every point in that square from some point.
You can use Pythagoras's theorem to get the hypotenuse, then check if the hypotenuse is greater than the size of the circle.
The circle will come out sloppy if the location of it's center isn't at an x,y value in multiples of 1/2 the tiles.
EXAMPLES OF --ROOM-- FOR IMPROVEMENT
How can we improve upon this last model, the Type 5? We must constantly watch for areas we can improve upon, during planning and during implementation.
1) we could round only one corner at a time. Suddenly, any room might have a rounded corner, and be more interesting for it.
2) We could approximate ellipses instead of limiting ourselves to circles. Ellipses at 45 degrees would be significantly more interesting. And these don't have to be perfect at all. You could merge two parabolas or something cheap like that. Better yet just go with the first method and use variable sized roundness. That will generate approximate-approximate elliptical rooms easily, which is fine because there is nothing significantly more interesting about an ellipse than there is about an approximate-approximate one.
CLOSING THOUGHTS ON ROOMS PT 1 - MANY WAYS TO GET THE JOB DONE
So notice how many ways there are of doing the same things.
If you decide you want to use multiple methods, you must remember that if two methods can create the same room.
If that happens, that type of room is suddenly twice as common as the rest. This can be a problem.
CLOSING THOUGHTS ON ROOMS PT 2 - SYMMETRY AND ASYMMETRY
Also, while setting this up, the focus should be on asymmetry vs symmetry.
Specifically look to be one or the other at random or not, and build around that concept.
Notice the symmetrical properties of rooms 2, 6, and 7.
Notice the asymmetrical properties of room 3.
Notice how rooms 6 and 8 seem to display qualities of both, and are more interesting for it.
CLOSING THOUGHTS ON ROOMS PT 3 - OTHER COOL IDEAS FOR ROOM BUILDING
You might also consider cutting some corners off diagonally, leaving the possibility of triangular rooms and things.
And consider subtracting a room from anywhere inside another room, creating squarish doughnuts as well.
You might subdivide a room in half, or place a room in a room. Make sure these are considered separate rooms afterward, if they are seperate.
Why aren't we worried about generating natural looking caves and the like??
The possibilities are endless lol.
CLOSING THOUGHTS ON ROOMS PT 4 - WARNINGS
One last warning before we move on - you have to be careful with room modifications like these.
Remember to always prevent properties from existing as 0 or as negative numbers.
Also, be careful not to accidentally allow the computer to cut a room in half.
You have to think about how various combinations might cause you problems, and place upper and lower bounds to prevent them.
Or, you might consider running some tests on each room, like a paint can to check if the room was cut in half, etc.
Better to prevent these outright than to watch for them and patch the problem. Treat the cause, not the symptoms.
This is extremely easy, and there are several ways to do it.
You can choose a random face of the bounding box, and a random place in the bounding box, and walk until you collide with the room.
THE OTHER WAY
You can choose random coordinates in the bounding box and walk in a random direction.
Or walk randomly around.
Or get the closest potential door spot using circles or squares.
Think about making this more interesting though.
How many doors should a room have?
If a door gets stuck in a corner, should we give a small chance to move it away from that corner?
If we make a door, maybe we should sometimes make one opposite it.
If two doors are adjacent, shouldn't we get rid of one of them?
CONNECTING THE ROOMS AND BUILDING THE DUNGEON
Now that we have all these rooms and doors, what are some ways we can connect them all together?
There are two methods i would recommend for better room placement and connection.
We're going to call these the "Room by Hall" method and the "Room by Room" method.
CHECKING FOR COLLISIONS
Placing rooms randomly involves checking for collisions. Fortunately for us, checking for collisions is extremely easy, even with all the fancy rooms.
Each room can be held in a bounding box.
If two bounding boxes overlap, there might be a collision.
You can consider that a collision, or do a more thorough check to see if any tiles in one room are overlapping any tiles in the other room.
(I think you're supposed to use a quad-tree for this, but it's probably fine to brute force it.)
It is important to make sure that if tiles are also being used as walls, the tiles are neither overlapping nor adjacent.
Adjacent tiles means no walls between the rooms.
Upon collision, just reroll the room's location, usually.
But, of course, that can potentially end up in an infinite loop of rerolling impossible to place rooms.
A better strategy is to try to displace the room a little bit, and give up if that fails too much.
Pick a diagonal, like north-east. Move randomly in one of those directions until the room fits or a certain number of moves fail.
You can shortcut that easily by checking outward in a square looking for space that isn't in a bounding box.
Or you can check outward in a circle, or look for space that isn't part of a room.
These might be a bit slower, but this whole thing ought to be extremely fast either way so use your favorite method.
ROOM BY HALL METHOD
Room by hall involves placing rooms at random or not-so-random locations, and connecting them with hallways.
When you create a room, add it's door to a list of doors.
Once you're done laying out the rooms, it's time to connect all the doors together via hallways.
My favorite method is pathfinding, with a slightly random path.
We actually don't want quality pathfinding. We want to be able to make mistakes.
First, create a 1x1 hallway out of every door.
We create an imaginary square which connects the two of the 1x1 hallways which we've chosen at random.
(Alternatively, we might choose them based on proximity to one another, or any number of ways! Try mixing randomness with proximity!)
We move in a straight line some random number of spaces either vertically or horizontally from one toward the other.
Along this line we create hallway.
Now while we're doing this, we want to watch for collisions between the hallway and a room, or the hallway and another hallway.
If you feel like the collision with a room would be a nice place for a door, go ahead and settle for that.
Just be sure you keep the door you didn't connect with on the list of doors that need connecting.
Likewise, if you collide with a hallway, just keep it.
Consider continuing straight through the hallway sometimes, or every time. Depending on your taste.
ROOM BY HALL WARNINGS
Be careful when generating hallways to prevent a hallway from running along side another hallway.
While it's nice to have variable width halls, this only ends up looking bad!
This isn't a problem if you're placing walls between tiles, of course. Just make sure to keep the walls.
Once all of the doors have connected there's really only two steps left.
One is to run a smart pathfinder from one room to every room.
If it can get from any one room to any given room, all of the rooms are connected.
For speed, pick the most central room to start with instead of a corner room!
Finally, if you want an entrance do the create-a-door thing but do it on the whole dungeon.
If you hit hallway, you ought to deal with that so it looks good.
Either make a new hallway leading to the hallway.
Or make an entrance room where you hit the hallway.
Or reroll. Whatever you think is best.
And if you didn't manage to get the whole dungeon connected or if you have doors left over, no worries!
You can just run the disconnected parts as whole-dungeon rooms the same way you build an entrance.
Probably want to aim for internal doors instead of external doors like you need for the actual entrance.
Once you've found a door for each half, connect them.
If you run into any problems, you'll have to retry or plow on through rooms and stuff, there shouldn't be too much in your way.
ROOM BY ROOM METHOD
What is room to room?
Room to room is much like the method used in the example you gave.
You begin by building a single base room.
Next, you build another room, this time with a door in it.
Aim to place the door randomly on the dungeon you've made so far.
FITTING THE ROOMS
If they don't fit there are a number of strategies you can use to quickly get them to fit:
Slide in one direction until a fit it made or you 'fall off' the dungeon's 'surface'.
Mirror the room and try again - it might be blocked by some weird outcrop.
Place a new door on the room you're working with and try that one.
Rotate the new room and place a new door on it to try, ya know with a new wall.
Connect them with the shortest hallway required to make it work.
Connect them with a random length hallway.
Try inserting a new room between the two, maybe one designed to be smaller and more round (round usually fits better).
Anything else you can think of, really.
Finally, build the entrance the same way you would for "room to hall".
NOT CHECKING FOR COLLISION
So get this - you aren't really required to check for collisions.
Yes, this is as cool as it sounds.
First of all, you've build fancy rooms out of addition and subtraction of less fancy rooms.
Why not just do that again?
Either fuse the rooms - addition, or keep the walls of the new one but override the old room - subtraction. Or do reverse subtraction by finalizing each idea once placed, and filling new ideas around the old but only replacing unused space. In case your not following, this is where you subtract the old room from the new room instead of the other way around.
Using either room to hall or room to room still works all the same, except room to room is arguably more bad ass with this feature enabled.
It would be wise to ensure that rooms which are thought to collide, actually collide or don't.
If you decided you want to allow your rooms to collide and you want non-square rooms, you might be vulnerable to a specific bug - certain parts of the level will be inaccessible.
You might want to do a paint can check and cull anything not connected to the rest of the dungeon.
And/or purge any rooms that are now significantly smaller than they ought to be, or the smaller halves of any cut in half.
And when placing doors, make sure the door placement algorithm and others know all about all the new changes.
Never take something like this for granted.
These are the kind of potentially game breaking bugs that crop up from detailed generation.
They can be easily dealt with, if you pay attention to the choices you make.
Also, this ends up creating a kind of scaling look, so it's a good idea to start with multiple rooms or one central room.
FILLING IN THE GAPS
For underground dungeons, sprawling randomly and leaving huge gaps is ideal.
For above ground dungeons, it should be fleshed out fully.
Paint can flood from an imaginary border around the level's bounding box so that all of the outside gets filled.
Flood the dungeon itself.
All that will be left is the empty internals.
Either fill them with rooms in a reverse subtraction fashion (preserving the rest of the dungeon).
Or press the walls of surrounding rooms in randomly to fill them.
This can be done by picking a random adjacent room and walking it's wall into the depths a random number of places.
Repeat until there is no depths left.
You will get funky rooms out of this, but that might be nice.
DUNGEON THEME, MAKING TOUGH DECISIONS, AND BUILDING BETTER DUNGEONS
Trying to give a dungeon a particular 'feel'? Trying to make more interesting layouts?
Conflicted between opting for feature A or B?
The beauty about this line of work is that finding yourself debating two tough choices provides the solution to making better dungeons.
Look at a the options I've provided along the way. There are tons of them.
Think about all the variables, constants, choices, directions, shapes, sizes, probabilities, whatever.
Specifically, how many rooms should you have? How large should they be? What shapes should they be?
How many doors? How direct should you get around? How much hallway? How jagged of hallways?
How will you ever know how to make great dungeons with all those dials to be tweaked?
Well it's simple, really.
Each different dungeon you want to design should have a configuration file.
If you don't have different dungeons, each floor should.
If you don't have different floors, each wing should.
If you have just a single wing on a single floor, each game should have a configuration file.
The configuration file will help guide the dungeon generator to creating a consistent theme.
Even if you only generate a single random dungeon, you should generate a consistent theme randomly.
The theme will push the randomness towards consistent randomness, and make the dungeon feel more realistic, even if that theme is randomly selected.
Things can be given a weight value, and you'll have dungeon flavour before you know it.
For example, one dungeon might tend to have rounded walls, another would avoid them entirely.
One dungeon might avoid hallways.
I'm sure you get the idea.
A cool concept is to change your parameters slightly as you descend deeper into the dungeon.
The rooms might get bigger, for example.
CHOOSING BETWEEN ROOM BY HALL AND ROOM BY ROOM
If you are pondering this, you're not paying attention.
It is entirely possible to mix these together freely.
You can build 'wings' in a room to hall style with large, sparsely placed rooms in a large, and then generate smaller rooms room to room style.
This will provide long hallways with lots of side areas to explore.
You can wait to connect everything until the end to make sure the halls won't get you everywhere.
You can limit the number of doors per room to exactly one, and create a very linear dungeon.
You can generate large clusters of room to room style rooms, and connect the clusters with hallways.
You get the idea.
Don't forget, if you're generator supports wings, you can assign themes to each one for bonus points.
Try to stick to an overall theme though.
Or don't! It's your game and I'm sure you'll make it cool!
The point is just do whatever feels right with the theme and such.
If your theme is that wings have different themes, you're being consistent with your theme lol.
A good dungeon generator takes tons of parameters.
A good dungeon picks a small subset of these to adhere to.
Keep your room and door tables around, they might come in handy. And hallway tables if you can.
You ought to be able to build conceptual rooms, like vaults filled with treasure and with only one door, or the boss room deep within.
Traps in hallways, maybe? A big fountain in one room?
Basically later on you can reuse these ideas.
Also, you can generate rooms with room-themes and configure them. Connect a mess hall to a kitchen, that kind of thing.
I don't know but I hope you get the concepts here.
Phew okay I'm 1000% done.
If you show me some progress, I'll consider hooking you up with level 2 of my talents. There's A LOT more to cover.
Also also, I better get a +1 for this.
Edited by Blind Radish, 23 December 2012 - 11:57 PM.