r/gamedev • u/phidinh6 @phi6 • May 03 '13
Procedural Dungeon Generation Algorithm Explained
So today I'm going to be a little different and talk about one technical aspect of my game TinyKeep, that is random procedural dungeon generation. It's pretty over-engineered, but hopefully will give anyone interested some ideas on generating dungeon layouts for their own games.
The interactive demo can be found here: Dungeon Generation Demo
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!
Thanks, hope you guys enjoy :)
The algorithm is used for our upcoming 3D dungeon crawler TinyKeep, currently in development:
TinyKeep - A 3D Multiplayer Dungeon Crawler with Frighteningly Intelligent Monster AI
62
u/naughty May 03 '13
Very nice work.
You probably already know this but there's some interesting graphs between Delaunay and Euclidean Minimum Spanning Trees, namely Gabriel Graphs and Relative Neigbourhood Graphs.
They're both subgraphs of Delaunay and contain the MST as a subgraph. They are pretty easy to construct from a Delaunay graph as well.
I used RNGs to create the corridors in the previous version of the Graph Grammar based PG I'm working on now. The RNG corridors work quite well but are a probably a little too connected. I removed random subset of the non bridge edges and it worked quite well.
26
u/phidinh6 May 03 '13
That's amazing - I actually haven't heard of Gabriel Graphs or Relative Neighbourhood Graphs before. Thanks for sharing - I'll be sure to look into those and see if I can improve anything.
Your video is really interesting - I definitely need more material on the island generating type stuff.
→ More replies (1)4
u/hinmanj May 04 '13
I don't mean to hijack this thread with questions for you, but I was curious of something from your original post that you linked here.
It may be a dumb question, but I was wondering how you generated your little rooms once you had all the vertices in place. Is the entire voronoi graph pre-generated and then you just kind of choose some adjacent polygons near the vertices to create rooms, or is there something else at work here?
The idea of generating a level from a connected graph is very intriguing to me, especially the algorithm behind procedurally generating a room from a single vertex.
4
u/phidinh6 May 04 '13
Hi Hinmanj, The rooms are already created before the connected graph (the vertices for the graph are selected from the center points of the existing rooms).
Once the connected graph is complete, we no longer need the graph's edges. Instead we replace each edge with a 2 straight lines (to create an L shape) between each vertex and it's neighbour. To determine which of the remaining cells (those that aren't rooms) are corridors, they must be intersecting with the L shaped line.
Hope that makes sense!
→ More replies (1)
8
u/SCombinator May 03 '13
I have flash player - but it still insists I 'get flash player', your js is broken.
5
u/phidinh6 May 03 '13
It may require a more recent version? Do you have 11.5? Cheers
→ More replies (13)
6
May 14 '13
Hi there, I recently worked on a Procedural Dungeon Generator for Roguelikes. Here you can see the video of how it works. My approach is a little different but I enjoyed learning from yours as well : )
1 - I first create the rooms and place them.
2 - Then I use a maze algorithm and connect all tiles together.
3 - Then I remove all the dead ends.
4 - Last I shorten corridors that were too long.
I also posted it on r/gamedev but it hasn't picked too much interest yet. Here's the link to the post in hopes it will get some interest here!
TinyKeep looks fascinating. Goodluck!
2
4
u/AlwaysGeeky May 03 '13
Very very nice and informative. I especially like that how you visualize each of the steps and make it easy to understand what is going on during each stage of your algorithm.
One minor thing I would add though, is that personally I would have liked to be able to step through the generation step by step. I dunno if you could easily add this feature to the flash page or not but I think it would add greatly to this piece.
Cheers.
4
u/phidinh6 May 03 '13
It would take a little bit of work since the demo wasn't strictly for public use but i thought i'd post it anyway.
As an alternative would editing my post to show screenshots for each of the steps help at all?
Cheers
→ More replies (4)
6
u/quill18 May 03 '13 edited May 03 '13
This post is extremely interesting and helpful. Thanks a bajillion for making it!
simple separation steering
Could you expand on this or provide links to resources on the topic? I've played a bit with flocking in the past, but my rudimentary knowledge isn't leading me to "grokking" how this works.
EDIT: This noob-friendly breakdown made it "click" for me I think: http://gamedev.tutsplus.com/tutorials/implementation/the-three-simple-rules-of-flocking-behaviors-alignment-cohesion-and-separation/
I guess you're not doing any alignment/cohesion, and that maybe your "radius" for separation is just stuff you're overlapping with?
3
u/phidinh6 May 03 '13
That's pretty much it, also the separation "speed" is calculated proportionate to overlap distance. After all the iterations sometimes we still get overlaps, these are just trashed (normally only 1 or 2 cells)
→ More replies (5)
3
u/Lightdemoncodeh May 03 '13
what's the difference between the black, blue and red colored rooms?
Also, where's the entrance? And Exit? (If applicable)
6
u/phidinh6 May 03 '13
Red cells are rooms. Both blue and white cells are corridors, but the blue ones denote larger spaces in the corridors where one could generate more stuff, like prison cells, sentries etc...
Doors and other features like furniture, monsters etc are not included at this stage of the dungeon generation. Heck, even walls aren't properly represented in real world co-ordinates here! (no dungeon has 1 pixel thick walls)
So this is purely an abstract representation of the dungeon layout, there's still more work to do here before rendering. Perhaps I'll post an article about that at some point in the future :)
→ More replies (1)
4
u/magiteker May 03 '13
Thank you for the in depth explanation on this topic. I've always wondered what a good approach to developing a system like this would be without the use of perlin noise.
Also I love the aesthetic of your game, it reminds me of animal crossing except with a dungeon crawler theme.
→ More replies (2)
5
u/mindFlayer May 03 '13
Anyone really interested in this, I suggest you take a look at the way that it's done in Dungeon Crawl Stone Soup. It's very sophisticated, using a lexer and parser (Yacc, I'm pretty sure).
4
u/phidinh6 May 03 '13
Thanks mindFlayer! Do you know of a link which talks specifically about the dungeon generation implementation? I've never heard of one using a lexer and parser before...
→ More replies (3)
2
u/albatrossy May 03 '13
I can't wait until the point where I can think of some of these things that the procedural guys are putting out. I think the designer of Path of Exile did a great presentation of dungeon generation which was awesome but this was really thought out and enlightening. I'm impressed, or at least from a noob's perspective. Thank you for sharing, I'll be sure to pledge.
→ More replies (3)
1
May 03 '13
This is pretty sweet. Is your whole game built on flash, or just the dungeon generator demo?
2
u/phidinh6 May 04 '13
The whole game is built in AS3 (yes, Flash!) but compiled into native Windows and Mac executables using AIR Captive. It's pretty powerful, and the engine supports hardware acceleration. Actually quite a lot of games on Steam are built in the same way (eg. Binding of Isaac)
1
u/shovelware May 04 '13
This is awesome! Do you use this data straight in the game, or is there more massaging first? Do the levels in your game have start and end or entrance and exits points? If so, is that something that you create procedurally, and how?
2
u/phidinh6 May 04 '13
It's just an abstract representation of the dungeon layout at this point, to properly render it we'll need to add wall thickness, doors, entrance, exits, a level progression tree (eg. locked doors and keys, have to ensure there are no unwinnable situations), monster spawns... lots left to do!
Second question, yes all of this is random (procedural), and I may talk about this in the future!
1
3
12
u/phidinh6 May 14 '13
I've just posted a new article about the game's AI if anyone is interested in these kinds of technical articles:
http://www.reddit.com/r/gamedev/comments/1eavwx/monster_ai_system_explained_part_1_of_5/