Jump to content

  • Log In with Google      Sign In   
  • Create Account


My Procedural Dungeon Generation Algorithm Explained for my game TinyKeep


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
9 replies to this topic

#1 phi6   Members   -  Reputation: 267

Like
14Likes
Like

Posted 03 May 2013 - 06:56 AM

Hey guys,
 
I was originally going to advertise my Kickstarter project TinyKeep here, but as everyone knows spamming a message board is not good etiquette so I thought I'd share some knowledge with the community as well. Hopefully this will somewhat pay for the sin I am about to commit at the end of the post.

Today I'm going to talk about one technical aspect of the game, that is random procedural dungeon generation. It's pretty over-engineered, but hopefully will give anyone who is interested some ideas on generating dungeon layouts for their own games.

The interactive demo can be found here:
dungen.png

Here's how I do it, step by step:

1. First I set the number of cells I want to generate, say 150. This is an arbitrary amount really, but the higher the number the larger the dungeon and in general more complexity.

2. For each "cell" I spawn a Rectangle of random width and length within some radius. Again the radius doesn't matter too much, but it should probably be proportionate to the number of cells.

Instead of using uniformly distributed random numbers (the default Math.random generator in most languages), I'm using Park-Miller Normal Distribution. This skews the size of the cells so that they are more likely to be of a small size (more smaller cells, less larger cells). The reason for this will be explained later!

In addition to this I ensure that the ratio between the width and length of each cell is not too large, we don't want perfectly square rooms but neither do we want really skinny ones, but somewhere in between.

3. At this point we have 150 random cells in a small area, most are overlapping. Next we use simple separation steering behaviour to separate out all of the rectangles so that none are overlapping. This technique ensures that the cells are not overlapping, yet in general remain as tightly packed together as possible.

4. We fill in any gaps with 1x1 sized cells. The result is that we end up with a square grid of differently sized cells, all perfectly packed together.

5. Here is where the fun begins. We determine which of the cells in the grid are rooms - any cell with a width and height above a certain threshold is made into a room. Because of the Park-Miller Normal Distribution described earlier, there will only be a small amount of rooms in comparison to the number of cells, with lots of space between. The remaining cells are still useful however... read on.

6. For the next stage we want to link each room together. To begin we construct a graph of all of the rooms' center points using Delaunay Triangulation. So now all rooms are connected to each other without intersecting lines.

7. Because we don't want every single room to be linked to every other with a corridor (that would make for a very confusing layout), we then construct a Minimal Spanning Tree using the previous graph. This creates a graph that guarantees all rooms are connected (and therefore reachable in the game).

8. The minimal spanning tree looks nice, but again is a boring dungeon layout because it contains no loops, it is the other extreme to the Delaunay Triangulation. So now we re-incorporate a small number of edges from the triangulated graph (say 15% of the remaining edges after the minimal spanning tree has been created). The final layout will therefore be a graph of all rooms, each guaranteed to be reachable and containing some loops for variety.

9. To convert the graph to corridors, for each edge we construct a series of straight lines (or L shapes) going from each room of the graph to its neighbour. This is where the cells we have not yet used (those cells in the grid which are not rooms) become useful. Any cells which intersect with the L shapes become corridor tiles. Because of the variety in cell sizes, the walls of the corridors will be twisty and uneven, perfect for a dungeon.

And here's an example of the finished result!

dungen_example.png

That's it!

 

And here comes the plug:

 

TinyKeep is a 3D Multiplayer Dungeon Crawler with focus on intelligent monster AI, currently being funded on Kickstarter.

We really need your help with pledges or the game will not be made!

 

http://www.kickstarter.com/projects/phidinh/tinykeep


TinyKeep - A 3D Multiplayer Dungeon Crawler with focus on intelligent monster AI

Currently Kickstarting: http://www.kickstarter.com/projects/phidinh/tinykeep

 

http://tinykeep.com


Sponsor:

#2 jbadams   Senior Staff   -  Reputation: 17749

Like
0Likes
Like

Posted 03 May 2013 - 07:34 AM

Thanks for sharing, looks like you get pretty good results from a relatively simple technique! smile.png



#3 NightCreature83   Crossbones+   -  Reputation: 2702

Like
0Likes
Like

Posted 03 May 2013 - 08:21 AM

Some interesting ideas in here to incorporate in to my own generator, which is based more on random generation and A* to create a connected graph.


Worked on titles: CMR:DiRT2, DiRT 3, DiRT: Showdown, GRID 2, Mad Max

#4 warnexus   Prime Members   -  Reputation: 1397

Like
0Likes
Like

Posted 03 May 2013 - 09:00 AM

I really like the dungeon generating technique and how you used animation to demonstrate it. Good luck with your project.



#5 bennettbugs   Members   -  Reputation: 493

Like
0Likes
Like

Posted 03 May 2013 - 10:01 AM

For a school assignment (a simple one, which is why) I added something similar. Of course it was not as good at creating dungeons, it had a similar idea of creating random rooms first then connecting them. Yours is a lot better in the fact that you use some very simple and effective algorithms to achieve a nice balance of distance and size of rooms. Your hallways (or what connects the rooms) are also a lot better, since mine were only straight lines. I also like the fact that there are no flaws, like mine could spawn you into a room with nowhere to go to. 

 

I'll also check out your game, as it seems pretty well thought out.

 

Happy coding!



#6 VladR   Members   -  Reputation: 722

Like
0Likes
Like

Posted 03 May 2013 - 01:00 PM

This is an interesting Top-Down approach.

 

Personally, I am more a fan of a Bottom-Up approach, where I keep adding and connecting rooms one by one, with random amount of smaller leafs - e.g. random depth (a range from 0-5) from the main corridor.

 

 

This way, I am guaranteed that the main quest items can be found easily, since the algorithm doesn't put them in the last leafs (which is frustrating from a player's perspective).

 

Also, since I am adding one main room after another (in a snake-like manner/shape), I keep generating and precomputing the pathfinding - thus making the in-game pathfinding reduced to 5-10 if..else conditions (which is plenty fast for a cell phone, even).

 

I can see, however, that it is pretty hard for you to generate some longer narrow corridors (with nowhere to dodge/escape) - which, personally, seem to be a big part of a dungeon crawler.


VladR    My 3rd person action RPG on GreenLight:    http://steamcommunity.com/sharedfiles/filedetails/?id=92951596

 


#7 Postie   Members   -  Reputation: 884

Like
0Likes
Like

Posted 03 May 2013 - 04:52 PM

It's always interesting to see someone else's take on something like dungeon/connected rooms generation. I'm curious.. is there much overhead in the part of the algorithm which moves the random rooms until they're not overlapping?


Currently working on an open world survival RPG - For info check out my Development blog: ByteWrangler

#8 phi6   Members   -  Reputation: 267

Like
0Likes
Like

Posted 04 May 2013 - 01:07 AM

This is an interesting Top-Down approach.

 

Personally, I am more a fan of a Bottom-Up approach, where I keep adding and connecting rooms one by one, with random amount of smaller leafs - e.g. random depth (a range from 0-5) from the main corridor.

 

 

This way, I am guaranteed that the main quest items can be found easily, since the algorithm doesn't put them in the last leafs (which is frustrating from a player's perspective).

 

Also, since I am adding one main room after another (in a snake-like manner/shape), I keep generating and precomputing the pathfinding - thus making the in-game pathfinding reduced to 5-10 if..else conditions (which is plenty fast for a cell phone, even).

 

I can see, however, that it is pretty hard for you to generate some longer narrow corridors (with nowhere to dodge/escape) - which, personally, seem to be a big part of a dungeon crawler.

 

Hmm, I do agree - Bottom-Up approaches tend to be more natural for gameplay as it almost simulates how one would explore the dungeon! Does your algorithm allow for loops or is it very much a tree? I tried this in the past to create a tree, but found it difficult to create an elegant way to loop back.

 

It's always interesting to see someone else's take on something like dungeon/connected rooms generation. I'm curious.. is there much overhead in the part of the algorithm which moves the random rooms until they're not overlapping?

 

I haven't done any serious tests, but if I turn off all the graphical visualizations the entire generation takes less than a second. There is probably quite a lot of overhead for sure but it's a one-time operation. I'll let you know when I have more specific results.


TinyKeep - A 3D Multiplayer Dungeon Crawler with focus on intelligent monster AI

Currently Kickstarting: http://www.kickstarter.com/projects/phidinh/tinykeep

 

http://tinykeep.com


#9 VladR   Members   -  Reputation: 722

Like
0Likes
Like

Posted 04 May 2013 - 07:58 AM

If it takes under a second, then it is nothing to worry about during level loading. The textures alone will take longer to load than that, for sure. I was asking, since you mentioned using several of the trees, and some types of trees are very intensive - but it is clearly not the case here.

 

As for my loops - it is also more of an hack. it does not work 100%, since the conditions for the loop must be right (and I'd have to pay attention to the "loopability" during creation process - which is still something I need to do).

 

 

 

BTW, did you find an artist willing to work for royalties, or do you have a contracted artist ? I liked the art, for sure !


VladR    My 3rd person action RPG on GreenLight:    http://steamcommunity.com/sharedfiles/filedetails/?id=92951596

 


#10 phi6   Members   -  Reputation: 267

Like
0Likes
Like

Posted 04 May 2013 - 10:03 AM

I think you're right there, making loops I found very difficult.

Here's a really really early test I made in 2011, completely tree based and bottom up approach, and there's no loops.

 

http://phigameslib.org/prototypes/dungeon/

 

An interesting discussion for sure!

 

Regarding the art, it was made by Matthias Andre from bitgem3d.com

The assets I used for the prototype are royalty free from his portfolio, but he has agreed to do more art for me if we get funded.


TinyKeep - A 3D Multiplayer Dungeon Crawler with focus on intelligent monster AI

Currently Kickstarting: http://www.kickstarter.com/projects/phidinh/tinykeep

 

http://tinykeep.com





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS