New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Procedural Dungeon Generation #2 #7

Open
adnzzzzZ opened this Issue Aug 31, 2015 · 31 comments

Comments

@adnzzzzZ
Owner

adnzzzzZ commented Aug 31, 2015

2015-08-30 22:29

This post explains a technique for generating randomized dungeons that was first described by TinyKeepDev here. I'll go over it in a little more detail than the steps in the original post. The general way the algorithm works is this:


Generate Rooms

First you wanna generate some rooms with some width and height that are placed randomly inside a circle. TKdev's algorithm used the normal distribution for generating room sizes and I think that this is generally a good idea as it gives you more parameters to play with. Picking different ratios between width/height mean and standard deviation will generally result in different looking dungeons.

One function you might need to do this is getRandomPointInCircle:

function getRandomPointInCircle(radius)
  local t = 2*math.pi*math.random()
  local u = math.random()+math.random()
  local r = nil
  if u > 1 then r = 2-u else r = u end
  return radius*r*math.cos(t), radius*r*math.sin(t)
end

You can get more info on how that works exactly here. And after that you should be able to do something like this:

One very important thing that you have to consider is that since you're (at least conceptually) dealing with a grid of tiles you have to snap everything to that same grid. In the gif above the tile size is 4 pixels, meaning that all room positions and sizes are multiples of 4. To do this I wrap position and width/height assignments in a function that rounds the number to the tile size:

function roundm(n, m)
  return math.floor(((n + m - 1)/m))*m
end

-- Now we can change the returned value from getRandomPointInCircle to:
function getRandomPointInCircle(radius)
  ...
  return roundm(radius*r*math.cos(t), tile_size), roundm(radius*r*math.sin(t), tile_size)
end

Separate Rooms

Now we can move on to the separation part. There's a lot of rooms mashed together in one place and they should not be overlapping somehow. TKdev used the separation steering behavior to do this but I found that it's much easier to just use a physics engine. After you've added all rooms, simply add solid physics bodies to match each room's position and then just run the simulation until all bodies go back to sleep. In the gif I'm running the simulation normally but when you're doing this between levels you can advance the physics simulation faster.

The physics bodies themselves are not tied to the tile grid in any way, but when setting the room's position you wrap it with the roundm call and then you get rooms that are not overlapping with each other and that also respect the tile grid. The gif below shows this in action as the blue outlines are the physics bodies and there's always a slight mismatch between them and the rooms since their position is always being rounded:

One issue that might come up is when you want to have rooms that are skewed horizontally or vertically. For instance, consider the game I'm working on:

Combat is very horizontally oriented and so I probably want to have most rooms being bigger in width than they are in height. The problem with this lies in how the physics engine decides to resolve its collisions whenever long rooms are near each other:

As you can see, the dungeon becomes very tall, which is not ideal. To fix this we can spawn rooms initially inside a thin strip instead of on a circle. This ensures that the dungeon itself will have a decent width to height ratio:

To spawn randomly inside this strip we can just change the getRandomPointInCircle function to spawn points inside an ellipse instead (in the gif above I used ellipse_width = 400 and ellipse_height = 20):

function getRandomPointInEllipse(ellipse_width, ellipse_height)
  local t = 2*math.pi*math.random()
  local u = math.random()+math.random()
  local r = nil
  if u > 1 then r = 2-u else r = u end
  return roundm(ellipse_width*r*math.cos(t)/2, tile_size), 
         roundm(ellipse_height*r*math.sin(t)/2, tile_size)
end

Main Rooms

The next step simply determines which rooms are main/hub rooms and which ones aren't. TKdev's approach here is pretty solid: just pick rooms that are above some width/height threshold. For the gif below the threshold I used was 1.25*mean, meaning, if width_mean and height_mean are 24 then rooms with width and height bigger than 30 will be selected.


Delaunay Triangulation + Graph

Now we take all the midpoints of the selected rooms and feed that into the Delaunay procedure. You either implement this procedure yourself or find someone else who's done it and shared the source. In my case I got lucky and Yonaba already implemented it. As you can see from that interface, it takes in points and spits out triangles:

After you have the triangles you can then generate a graph. This procedure should be fairly simple provided you have a graph data structure/library at hand. In case you weren't doing this already, it's useful that your Room objects/structures have unique ids to them so that you can add those ids to the graph instead of having to copy them around.


Minimum Spanning Tree

After this we generate a minimum spanning tree from the graph. Again, either implement this yourself or find someone who's done it in your language of choice.

The minimum spanning tree will ensure that all main rooms in the dungeon are reachable but also will make it so that they're not all connected as before. This is useful because by default we usually don't want a super connected dungeon but we also don't want unreachable islands. However, we also usually don't want a dungeon that only has one linear path, so what we do now is add a few edges back from the Delaunay graph:

This will add a few more paths and loops and will make the dungeon more interesting. TKdev arrived at 15% of edges being added back and I found that around 8-10% was a better value. This may vary depending on how connected you want the dungeon to be in the end.


Hallways

For the final part we want to add hallways to the dungeon. To do this we go through each node in the graph and then for each other node that connects to it we create lines between them. If the nodes are horizontally close enough (their y position is similar) then we create a horizontal line. If the nodes are vertically close enough then we create a vertical line. If the nodes are not close together either horizontally or vertically then we create 2 lines forming an L shape.

The test that I used for what close enough means calculates the midpoint between both nodes' positions and checks to see if that midpoint's x or y attributes are inside the node's boundaries. If they are then I create the line from that midpoint's position. If they aren't then I create two lines, both going from the source's midpoint to the target's midpoint but only in one axis.

In the picture above you can see examples of all cases. Nodes 62 and 47 have a horizontal line between them, nodes 60 and 125 have a vertical one and nodes 118 and 119 have an L shape. It's also important to note that those aren't the only lines I'm creating. They are the only ones I'm drawing but I'm also creating 2 additional lines to the side of each one spaced by tile_size, since I want my corridors to be at least 3 tiles wide in either width or height.

Anyway, after this we check to see which rooms that aren't main/hub rooms that collide with each of the lines. Colliding rooms are then added to whatever structure you're using to hold all this by now and they will serve as the skeleton for the hallways:

Depending on the uniformity and size of the rooms that you initially set you'll get different looking dungeons here. If you want your hallways to be more uniform and less weird looking then you should aim for low standard deviation and you should put some checks in place to keep rooms from being too skinny one way or the other.

For the last step we simply add 1 tile sized grid cells to make up the missing parts. Note that you don't actually need a grid data structure or anything too fancy, you can just go through each line according to the tile size and add grid rounded positions (that will correspond to a 1 tile sized cell) to some list. This is where having 3 (or more) lines happening instead of only 1 matters.

And then after this we're done! 🌀


END

The data structures I returned from this entire procedure were: a list of rooms (each room is just a structure with a unique id, x/y positions and width/height); the graph, where each node points to a room id and the edges have the distance between rooms in tiles; and then an actual 2D grid, where each cell can be nothing (meaning its empty), can point to a main/hub room, can point to a hallway room or can be hallway cell. With these 3 structures I think it's possible to get any type of data you could want out of the layout and then you can figure out where to place doors, enemies, items, which rooms should have bosses, and so on.

@adnzzzzZ adnzzzzZ added the procedural label Aug 31, 2015

@davisdude

This comment has been minimized.

Show comment
Hide comment
@davisdude

davisdude Aug 31, 2015

Very informative! Is there anywhere we can see the source to play around with the values on our own some?

davisdude commented Aug 31, 2015

Very informative! Is there anywhere we can see the source to play around with the values on our own some?

@adnzzzzZ

This comment has been minimized.

Show comment
Hide comment
@adnzzzzZ

adnzzzzZ Aug 31, 2015

Owner

No, code is too messy and it won't work on it's own without my game's code either.

Owner

adnzzzzZ commented Aug 31, 2015

No, code is too messy and it won't work on it's own without my game's code either.

@Zireael07

This comment has been minimized.

Show comment
Hide comment
@Zireael07

Zireael07 Aug 31, 2015

What a pity, this looks amazing, I would love to see the source to play around with the values!

EDIT: Also it looks like you use Lua, I'd love to see at least the hallways code...

Zireael07 commented Aug 31, 2015

What a pity, this looks amazing, I would love to see the source to play around with the values!

EDIT: Also it looks like you use Lua, I'd love to see at least the hallways code...

@davidahines

This comment has been minimized.

Show comment
Hide comment
@davidahines

davidahines Aug 31, 2015

How did you make these gorgeous previews?

davidahines commented Aug 31, 2015

How did you make these gorgeous previews?

@srt19170

This comment has been minimized.

Show comment
Hide comment
@srt19170

srt19170 Aug 31, 2015

Kudos for putting so much effort into writing this up and creating visualizations. Very clear to read and understand!

srt19170 commented Aug 31, 2015

Kudos for putting so much effort into writing this up and creating visualizations. Very clear to read and understand!

@adnzzzzZ

This comment has been minimized.

Show comment
Hide comment
@adnzzzzZ

adnzzzzZ Aug 31, 2015

Owner

@davidahines I used Licecap to record the gifs. Or do you mean something else?

Owner

adnzzzzZ commented Aug 31, 2015

@davidahines I used Licecap to record the gifs. Or do you mean something else?

@davidahines

This comment has been minimized.

Show comment
Hide comment
@davidahines

davidahines Aug 31, 2015

I just mean the great visualizations, or do you just dump your map output?

On Mon, Aug 31, 2015 at 3:38 PM, adn notifications@github.com wrote:

@davidahines https://github.com/davidahines I used Licecap to record
the gifs. Or do you mean something else?


Reply to this email directly or view it on GitHub
#7 (comment).

davidahines commented Aug 31, 2015

I just mean the great visualizations, or do you just dump your map output?

On Mon, Aug 31, 2015 at 3:38 PM, adn notifications@github.com wrote:

@davidahines https://github.com/davidahines I used Licecap to record
the gifs. Or do you mean something else?


Reply to this email directly or view it on GitHub
#7 (comment).

@etler

This comment has been minimized.

Show comment
Hide comment
@etler

etler Aug 31, 2015

That's really cool! As soon as I saw the map though, I thought metroidvania! That'd be an interesting challenge, procedural making sure that all the exits are accessible.

etler commented Aug 31, 2015

That's really cool! As soon as I saw the map though, I thought metroidvania! That'd be an interesting challenge, procedural making sure that all the exits are accessible.

@adnzzzzZ

This comment has been minimized.

Show comment
Hide comment
@adnzzzzZ

adnzzzzZ Aug 31, 2015

Owner

@davidahines Yea I just take the map's output and draw it. On some steps I draw additional stuff to make visualization easier.

@etler That's definitely doable from the layout that this algorithm generally constructs. Since all main rooms (the red ones) are connected you can get from any of them to any other. The hard part would be figuring out the directions in which you can go (the graph so far is not directed) and where to place doors or obstacles that lock out an entire area.

Owner

adnzzzzZ commented Aug 31, 2015

@davidahines Yea I just take the map's output and draw it. On some steps I draw additional stuff to make visualization easier.

@etler That's definitely doable from the layout that this algorithm generally constructs. Since all main rooms (the red ones) are connected you can get from any of them to any other. The hard part would be figuring out the directions in which you can go (the graph so far is not directed) and where to place doors or obstacles that lock out an entire area.

@s-ol

This comment has been minimized.

Show comment
Hide comment
@s-ol

s-ol Aug 31, 2015

Hey @adonaac, I sent you a message about this on the LÖVE forum a while ago; I really like these posts, but don't you want to move them to an actual blog? If you want me to, I'll happily send you a pull request with a jekyll version of all the content; you can keep writing your posts in markdown and github will host it for you, but it would look much nicer and would free up the issues page for actual issues and enhancement ideas.

(also sorry for the derail, but I don't want to mess up your clean issues with this)

s-ol commented Aug 31, 2015

Hey @adonaac, I sent you a message about this on the LÖVE forum a while ago; I really like these posts, but don't you want to move them to an actual blog? If you want me to, I'll happily send you a pull request with a jekyll version of all the content; you can keep writing your posts in markdown and github will host it for you, but it would look much nicer and would free up the issues page for actual issues and enhancement ideas.

(also sorry for the derail, but I don't want to mess up your clean issues with this)

@adnzzzzZ

This comment has been minimized.

Show comment
Hide comment
@adnzzzzZ

adnzzzzZ Aug 31, 2015

Owner

@S0lll0s Nah I like it better this way. I had one at http://psychoky.me but it's much easier to just do everything here

Owner

adnzzzzZ commented Aug 31, 2015

@S0lll0s Nah I like it better this way. I had one at http://psychoky.me but it's much easier to just do everything here

@s-ol

This comment has been minimized.

Show comment
Hide comment
@s-ol

s-ol Aug 31, 2015

@adonaac your blog would still be just a github repo and the posts would be markdown files. All the HTML is generated by the github server at runtime.

s-ol commented Aug 31, 2015

@adonaac your blog would still be just a github repo and the posts would be markdown files. All the HTML is generated by the github server at runtime.

@adnzzzzZ

This comment has been minimized.

Show comment
Hide comment
@adnzzzzZ

adnzzzzZ Aug 31, 2015

Owner

I'm fine thanks 👌

Owner

adnzzzzZ commented Aug 31, 2015

I'm fine thanks 👌

@lebiru

This comment has been minimized.

Show comment
Hide comment
@lebiru

lebiru Sep 1, 2015

sooo cool 👍

lebiru commented Sep 1, 2015

sooo cool 👍

@skullthug

This comment has been minimized.

Show comment
Hide comment
@skullthug

skullthug Sep 1, 2015

This is an incredible writeup. The gifs help explain a ton! Thank you so much for sharing.

skullthug commented Sep 1, 2015

This is an incredible writeup. The gifs help explain a ton! Thank you so much for sharing.

@StefanTudorFlorea

This comment has been minimized.

Show comment
Hide comment
@StefanTudorFlorea

StefanTudorFlorea Sep 1, 2015

Excellent tutorial! Thank you so much for this.

StefanTudorFlorea commented Sep 1, 2015

Excellent tutorial! Thank you so much for this.

@LuizPanariello

This comment has been minimized.

Show comment
Hide comment
@LuizPanariello

LuizPanariello Sep 1, 2015

Nice tutorial!

LuizPanariello commented Sep 1, 2015

Nice tutorial!

@Yonaba

This comment has been minimized.

Show comment
Hide comment
@Yonaba

Yonaba Sep 2, 2015

Seriously, @adonaac , don't laugh, but have you considered submitting this writeup to gamedev.net ?
Also, I am very happy my delaunay implementation served well your purposes. I wrote it as a side project to be reused later on to improve my pathfinding library, Jumper. Anyway, thanks mentionning it!

Yonaba commented Sep 2, 2015

Seriously, @adonaac , don't laugh, but have you considered submitting this writeup to gamedev.net ?
Also, I am very happy my delaunay implementation served well your purposes. I wrote it as a side project to be reused later on to improve my pathfinding library, Jumper. Anyway, thanks mentionning it!

@piotr-j

This comment has been minimized.

Show comment
Hide comment
@piotr-j

piotr-j Sep 6, 2015

Excellent breakdown! Inspired me to make my own version. Still WIP!

piotr-j commented Sep 6, 2015

Excellent breakdown! Inspired me to make my own version. Still WIP!

@icewind

This comment has been minimized.

Show comment
Hide comment
@icewind

icewind Sep 7, 2015

Fantastic! Thanks for sharing this!

icewind commented Sep 7, 2015

Fantastic! Thanks for sharing this!

@piotr-j

This comment has been minimized.

Show comment
Hide comment
@piotr-j

piotr-j Sep 7, 2015

Made a web version if anyone is into that.

piotr-j commented Sep 7, 2015

Made a web version if anyone is into that.

@Bl4ckb0ne

This comment has been minimized.

Show comment
Hide comment
@Bl4ckb0ne

Bl4ckb0ne Sep 15, 2015

Can you tell us more about the separation steering behavior, or the physics you're using to separate the rooms?

Bl4ckb0ne commented Sep 15, 2015

Can you tell us more about the separation steering behavior, or the physics you're using to separate the rooms?

@adnzzzzZ

This comment has been minimized.

Show comment
Hide comment
@adnzzzzZ

adnzzzzZ Sep 16, 2015

Owner

@Bl4ckb0ne

I'm using box2d with LÖVE, more specifically https://github.com/adonaac/hxdx. So what I do is for each room is I create a collider and then after all colliders are created I just step the physics world forward. The physics engine takes care of doing the separation. After all bodies are not awake anymore (it's all in equilibrium) I delete all colliders and destroy the physics world.

Owner

adnzzzzZ commented Sep 16, 2015

@Bl4ckb0ne

I'm using box2d with LÖVE, more specifically https://github.com/adonaac/hxdx. So what I do is for each room is I create a collider and then after all colliders are created I just step the physics world forward. The physics engine takes care of doing the separation. After all bodies are not awake anymore (it's all in equilibrium) I delete all colliders and destroy the physics world.

@Bl4ckb0ne

This comment has been minimized.

Show comment
Hide comment
@Bl4ckb0ne

Bl4ckb0ne Sep 16, 2015

Thanks, I was trying to do it with a homemade AABB system, but the tutorial on tutsplus is shitty so i'll use the box2d binding for C++. At how much did you put the gravity on the world?

Bl4ckb0ne commented Sep 16, 2015

Thanks, I was trying to do it with a homemade AABB system, but the tutorial on tutsplus is shitty so i'll use the box2d binding for C++. At how much did you put the gravity on the world?

@adnzzzzZ

This comment has been minimized.

Show comment
Hide comment
@adnzzzzZ

adnzzzzZ Sep 16, 2015

Owner

0, 0. You don't want your rooms falling in any direction, probably

Owner

adnzzzzZ commented Sep 16, 2015

0, 0. You don't want your rooms falling in any direction, probably

@piotr-j

This comment has been minimized.

Show comment
Hide comment
@piotr-j

piotr-j Sep 16, 2015

You set it to zero or the bodies will just fall down forever. Setting rotation to fixed is also useful.

piotr-j commented Sep 16, 2015

You set it to zero or the bodies will just fall down forever. Setting rotation to fixed is also useful.

@JnyJny

This comment has been minimized.

Show comment
Hide comment
@JnyJny

JnyJny Sep 17, 2015

Chiming in with another kudos and a link to my python implementation based on your article. Any more articles in the pipe?

JnyJny commented Sep 17, 2015

Chiming in with another kudos and a link to my python implementation based on your article. Any more articles in the pipe?

@adnzzzzZ

This comment has been minimized.

Show comment
Hide comment
@adnzzzzZ

adnzzzzZ Sep 18, 2015

Owner

Any more articles in the pipe?

No... When I find something cool to write about I'll probably write something. But right now I'm just doing some boring totally not cool stuff.

Owner

adnzzzzZ commented Sep 18, 2015

Any more articles in the pipe?

No... When I find something cool to write about I'll probably write something. But right now I'm just doing some boring totally not cool stuff.

@robinxb

This comment has been minimized.

Show comment
Hide comment
@robinxb

robinxb Nov 5, 2015

Just create a sample code with unity. here

Replace some codes with which mentioned in this article dungeon-generation

robinxb commented Nov 5, 2015

Just create a sample code with unity. here

Replace some codes with which mentioned in this article dungeon-generation

@gabz123

This comment has been minimized.

Show comment
Hide comment
@gabz123

gabz123 May 19, 2016

question, will this code be able to implemented in ue4 or cryengine?

gabz123 commented May 19, 2016

question, will this code be able to implemented in ue4 or cryengine?

@Lycea

This comment has been minimized.

Show comment
Hide comment
@Lycea

Lycea May 31, 2017

Hi, thank you for that nice post, I started to make my own implementation based on this post and also in lua / löve for further use . I have to say it is a really good description of how to do this 👍 😃

Lycea commented May 31, 2017

Hi, thank you for that nice post, I started to make my own implementation based on this post and also in lua / löve for further use . I have to say it is a really good description of how to do this 👍 😃

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment