Jump to content
  • Advertisement
Sign in to follow this  

Procedural Level Generation

This topic is 2184 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am working on creating a procedural dungeon generator. I'm off to a decent start, but it seems that AAA titles like Diablo 3 and Torchlight use some fairly complex systems to achieve their results. For where I am at now, this is very evident when I use my current algorithm in 3D instead of a simple 2D grid.


In the 2D example, the algorithm looks promising - this is deceiving; when viewed in 3D it is obvious that this algorithm will work only for throwback RPG's (think Might & Magic, Doom 98, or more recently Legend of Grimrock). There's nothing wrong with that, but it's not near the level of complexity I want to achieve.


I'm looking into this: http://www.uoguelph.ca/~jbrown16/Vvaltchanov_c3s2e12.pdf


Any suggestions, articles, papers, etc. are greatly appreciated.

Share this post

Link to post
Share on other sites

You hit the jackpot, sir, this is my demesne.
I was /born/ for this.

Okay, first the prototype.
Manually design the type of level you want to create on paper.  Try to make each room as original and unique as possible.  If you feel like there ought to be a throne room in the back, place one there.  If you feel like one of the rooms should have a high ceiling, mark it on the blue print.
Try to contemplate and then visualize what kinds of things you want to have.  Make two or three potential levels if you want better results.

Now the description.

When you're satisfied with your map concept or concepts, try to describe the room to an imaginary person who is completely non-creative.  While doing this picture in your mind only the things you describe.  Try to avoid taking things for granted, like the fact that this dungeon would have brick walls.  Unless you describe it, it doesn't exist.  Don't find yourself saying "of course there would be a throne in the throne room.  Instead, describe it in great length to the imagined person.

Trial by prodding.
Describe the reasons why you would want these things and why you placed them where you did.  Explain and rationalize your decisions.  Parameterize them.  Create a ruleset for why this type of a dungeon would need brick walls and a throne room.  Try to think of exceptions to those rules.  Try to think of other consequences of these rules.  Of other potential outcomes that might function in place of the original design.  Try to think of other similar rules that might apply.  Placing limitations can help.
The throne may or may not sit above a large staircase, for example, or it might instead be a round table.  Try to break the rules and see what happens.
Really, the point here is to push the limitations and establish a firm description of what needs to be created and what needs to be avoided.
Ultimately, your looking to expand your original model.

The final definition.
Finally, convert your thoughts into a written list of room types, frequency, qualities, and variables.  You can teach the computer to generate these with somewhat random parameters.  The more choices you have, the more potential results you'll get.  Try to make everything a range of choices rather than one definite idea.  Give everything wiggle room.  Also, if you create a dumbed-down version of your model, you can roll some dice or something and draw another concept map.  Is it as nice as your lovingly crafted ones?  If not, why not?
You also might want to run your idea for a design by someone, especially after you have a working generator.

Once defined, its a relatively trivial matter to explain this to a computer.  Just use the lists you created and finagle the results.
Don't limit yourself to squares.  Use hexagons, or even circles.  Why not?  You can just as easily prevent collisions.  And why prevent them, anyway?  Merging can make for more interesting layouts.  Or just wall one off from the other.  Whatever.  You can allocate general room locations, build the rooms, create doors and connect them with other rooms or hallways.  I'll leave the details to you to figure out, because it'll change based on every different idea.  But you've already got the idea that will pretty much work.
And measure everything in smaller parts.  Half square meters, maybe.  And make some hallways wide enough to pull a camera through and fight in.  Claustrophobia can be awesome if used correctly, but shouldn't be used all the time.

Other thoughts.
Your focus should be on layout, function, personality, and depth.

Layout means the arrangement of the rooms should be condusive to a fun experience.  The paths the player can take should be generated to be exciting and interesting, and should give a tour of the dungeon.  It should also make sense in a general sort of way.  Remember to think like the builders.

Function, is very similar to layout and should be pondered at the same time.  It means things should have a logical arrangement.  You should see necessary rooms to add realism to the result.  Kitchens and archer windows, for example.  Also, everything should be in a sensible place for what it is.  In a tower?  Why is it labrynthine inside?  Why is it rigged with traps?  Or does it hold some mystical or spiritual artefact?

Personality is a sign of culture.  Did the builders of the dungeon use it frequently?  Did they use it recently?  Are they using it now?  What belief systems do they have?  What taste in art do they have?

Depth is literally depth.  Keep thinking about how the level in relationship to the player would wow them.  Vaulted ceilings, balconies, bridges over the room below.  Latters, ropes, lookout points, and obviously staircases.  Forget 2D and stay as far away from it as possible.  If you struggle with this one, at least think in terms of top down Zelda/Pokemon layouts.

Well that's it.  Knock yourself out.


Edited by MyNameIs

Share this post

Link to post
Share on other sites

While helpful in a general sense, your reply is a little to high level and design oriented. I am asking for a more detailed technical discussion, so if you can expand on your implementation section that would be really helpful.

Share this post

Link to post
Share on other sites

Well what kind of a game level are you making?  For that matter, what kind of genre?
You really should design around mechanics.

Now I'll go ahead and assume you want to build levels like you might see in the Legend of Zelda.

You'll want a few great rooms.  The entrance, the level's hub area, and the boss room are good examples.
You'll want these to wow the player.
You can make them grand but mechanically plain, or you can fill them with a fight or a puzzle or some unique challenge or traps, whatever.
It doesn't really matter.  They just have to look cool.  Probably not traps.

Think of the great rooms as floating in abstract space.  They will eventually connect but right now it doesn't matter where they are.

You want to build them to look grand, so think of interesting shapes and such.  You can hand craft these or build them from variable templates.
Maybe ovular, or perfectly round, or extremely tall.  You usually want them tall.  Maybe cross shaped.

Place doors on them.  Build rooms around that.  Rooms can be any shape but try to build from a conceptual theme.  Rooms can be hallways, or whatever.

Figure out how you want to connect all the rooms.  The boss room should be deep, but direct, usually.  You might consider creating an artificial wall of some kind.  A locked door or a cave in.  Unless the dungeon theme says that the throne room should be absolutely hidden.  Just make some dead ends and fill them with loot or whatever.

Unless your doing a multiplayer game, no dead ends for those, usually.

I don't know man, why don't you explain the map you listed, what your goals are, that kind of thing?

I actually have {this one link for you that will show you one example of level generation}.
Notice how he breaks generation down into a series of objectives and tries to create a solution.

{Here's one on natural cave generation}, but look up Perlin noise too, that seems to be popular.

Think about how you would lovingly hand craft a level design.
At each point where you have to make a non obvious decision, pretend you make two levels, one of which makes both decisions.
Teach the computer how to do that and have it randomly make those decisions.
Explain to the computer how you want it to generate levels for your game and it will.
If you do the room based system you can fill them with anything you want.  Generate a skeleton and fill it with more interesting properties.

I'll answer all of your questions to the best of my abilities but I'm not really sure what you're trying to do or how I can explain this better.

{Markov Chains are nice for random stuff, but might just confuse you worse.}

">{City Generation}

Edited by MyNameIs

Share this post

Link to post
Share on other sites

Thank you for your patience with me. This is the gist of my algorithm so far:

pseudo code:
while rooms.count < number_of_rooms_to_create
set room = new room

set room.sizeW = random()
set room.sizeH = random()

set room.posX = random()
set room.posY = random()

if room fits

end while

start_room = random(rooms)

foreach room in rooms
if room is not start_room
create_path(start_room, room)
end foreach

This works just fine for square tile based 2D maps. This falls apart when trying to create maps that contain rooms of arbitrary shape and size. The first problem is how to check if the room will fit. The second is how to link the rooms together at their respective door/entry-way points. In my original post, this was easy to do since the rooms were all quadrilateral shapes and the walls and floors were individual tiles. Now I want to use whole 3D and 2D chunks instead.


I've attached an image that is derived from the tile set in my original post.



Share this post

Link to post
Share on other sites

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. biggrin.png

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.

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 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.)

So we begin by generating a rectangle. You probably want this to avoid having either length or width as 1 unit.

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! wink.png)

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.

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! biggrin.png

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.

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.

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.

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.

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.

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.

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.

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.
Bam, door.

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?

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.

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 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.

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.

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.

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".

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.

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.

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.

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.  rolleyes.gif

Edited by Blind Radish

Share this post

Link to post
Share on other sites

[quote name='Blind Radish' timestamp='1356326691' post='5013861']
Before I begin please note that "MyNameIs" is... well me.
But don't worry, this is my main account from back when.

Just FYI, I've merged those two accounts for you.  All of the posts and data associated with the "MyNameIs" account should now belong to your "Blind Radish" account, and the other account no longer exists. smile.png

Share this post

Link to post
Share on other sites
Just FYI, I've merged those two accounts for you.  All of the posts and data associated with the "MyNameIs" account should now belong to your "Blind Radish" account, and the other account no longer exists.



+1 bro.  +1.

O.P., if you have any more questions, feel free to ask.  I dumped A LOT of information on you, so I expect /something/.
Also, I know that looks scary but it's really not that complex.  Make rooms, place them using method, check for errors.  Easy.

Edited by Blind Radish

Share this post

Link to post
Share on other sites
Nothing wrong with what Blind Radish posted (OK, I didn't read the whole thing), but I have a different approach that I have found is very flexible.

I am more familiar with the situation where you want to procedurally design a city, so I will use it in my description.

The main idea is to represent the city hierarchically. We start with the problem given as "design a city that fits in this polygon, with roads connecting at these points of the polygon, and a population of about 1,200,000 people". The first task to solve is how to decompose that city into neighborhoods. For instance, you could choose a few points inside the city that represent squares, compute some sort of triangulation of the polygon with those squares as inner vertices, join a few of the triangles into larger polygons. Now let's make those polygons neighborhoods. We have decomposed the original polygon into neighborhoods, avenues (along the edges of the neighborhoods) and squares (are the vertices of the triangulation). Now we have a bunch of problems that look like this: "design a neighborhood that fits in this polygon, with important squares at these points of the polygon, and a population of about 150,000 people". You can of course have different types of neighborhood (residential, commercial, a campus...). You then need to think of how to decompose the problem of designing a neighborhood into sub-problems, like how to design a block, or a park, or a church, or a city hall.

Ultimately you'll be left with problems like "design a park bench that fits in this polygon, facing North". Then you can just plop a mesh from a library there (unless you want to get into the business of designing furniture for public spaces, but you need to stop somewhere).

Now call your top-level function and voilà, instant city.

In my experience, this type of top-down design can be used to design almost anything (cities, airports, jazz standards...). Dungeons sound like a particularly easy case. The paradigm can also be combined with lazy evaluation and then you can render mind-bogglingly large scenes (e.g., the entire Star Wars galaxy) down to little details.

I was very interested in this type of thing about 10 years ago. A couple of friends of mine took some of my ideas and created a little demo. It's not great, but it shows some of the potential of the method: http://www.binaryworlds.com/

Share this post

Link to post
Share on other sites

[quote name='Blind Radish' timestamp='1356348165' post='5013914']
O.P., if you have any more questions, feel free to ask.  I dumped A LOT of information on you, so I expect /something/.
Also, I know that looks scary but it's really not that complex.  Make rooms, place them using method, check for errors.  Easy.


Thank you so much for your help (+1 for sure). I am working on creating shape files that contain meta data about my 3D pre-canned structures. This way I can have an artist create cool art, and then I can randomly place it. For instance:






where non-zeroes are cross checked with the map, and the d's specify doors. 

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!