9 ms·

Rooms and Mazes: A Procedural Dungeon Generator

332 points by dustinlakin 12y ago

gavanwoolery 12y ago
Looks good! I found this to be a great resource on Maze generation: http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorithm-recap http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorit...
- DrJosiah 12y ago
  Jamis has a lot of great articles on maze generation, was about to post a link :)
akanet 12y ago
I think this article is a fantastic example of how you can blend prose with working interactive examples. The examples make you really trance out watching dungeons being carved out of nothing. I think an often-discounted aspect of JavaScript's appeal is its ability to breathe life into a bunch of fascinating but otherwise dry concepts. Another terrific example is this page by the prolific Mike Bostock: http://bost.ocks.org/mike/algorithms/ http://bost.ocks.org/mike/algorithms/
- munificent 12y ago
  I agree totally. I love the ability to write blog posts with interactive animated content. We take for granted that the web platform can do all this, but it's rare to find content that takes advantage of it. Mike Bostock and Amit Patel's sites are notable counter-examples. I'd like to do more posts like this, but I can see why they aren't common. This one took me forever to finish. Easily eight times as much effort as a regular text + code samples blog post. I think I'd get faster as I did more in this style, but it's really hard to for me to stay energized on a single concept long enough to finish posts like this.
mseepgood 12y ago
Labyrinth generator in a single line of code: http://www.slate.com/articles/technology/books/2012/11/computer_programming_10_print_chr_205_5_rnd_1_goto_10_from_mit_press_reviewed.html http://www.slate.com/articles/technology/books/2012/11/compu...
- tromp 12y ago
  The second example on http://en.wikipedia.org/wiki/Obfuscation_%28software%29 http://en.wikipedia.org/wiki/Obfuscation_%28software%29 is a 7 line maze that generates arbitrary length mazes. Its construction is described at http://tromp.github.io/maze.html http://tromp.github.io/maze.html
fit2rule 12y ago
That was a very pleasant article and fills me with inspiration .. which is what I came here for, mostly, in the first place. I don't have many applications for twisty mazes in my space at the moment, but one thing that I always thought would be interesting is to use the dependency graphs/use-counts of various system libraries as inputs to a maze generator. Sort of like Fsn (http://en.wikipedia.org/wiki/Fsn http://en.wikipedia.org/wiki/Fsn) but with a lot more twisty, bendy mazes between the ldd details .. huh, yet another bit of bait for the bucket ..
doomlaser 12y ago
Another cheap and very effective technique for procedural level and maze generation is to create a "walker" or series of walkers that start at some point, walk in a direction and then turn at random intervals, leaving a path of corridors and occasionally rooms in their wake. This is how Vlambeer's Nuclear Throne generates its levels, and there's a good article from Jan Willem Nijman, it's developer, here: http://www.vlambeer.com/2013/04/02/random-level-generation-in-wasteland-kings/ http://www.vlambeer.com/2013/04/02/random-level-generation-i... If you'd like a more academic look into procedural 2d game generation, there's a nice research paper here, that describes a method and talks about Spelunky a lot (the king of procedural 2d level generation, in my book): http://games.soe.ucsc.edu/sites/default/files/cig10_043CP2_115.pdf http://games.soe.ucsc.edu/sites/default/files/cig10_043CP2_1... Additionally, Derek Yu open sourced the code to the original Spelunky, and Darius Kazemi created a great breakdown of its level generation techniques here, also with interactive examples: http://tinysubversions.com/spelunkyGen/index.html http://tinysubversions.com/spelunkyGen/index.html The action roguelike genre, particularly the roguelike FPS, is a vital new area being explored by indie game developers. It reminds me of the way 2D platformers were mined, explored, and iterated upon starting around 7 or 8 years ago. Right now, it doesn't take much to stand out from the herd, as many of the most popular games in the genre don't do much beyond generating a bunch of square rooms and connecting them with doors and short, straight corridors. In my opinion, developers in the genre should take more cues from Doom, and less from original Zelda dungeons moving forward. And, from a more holistic perspective, nobody really cares about mazes, room placement on a grid, and connective corridors when playing a game, beyond a brute mechanical level. A more useful framework for thinking of generating levels might be to go one level of abstraction higher. Think about a level as a story for your player, and generate setpieces or 'acts' that you want the player to experience as they play. Keep in mind the basics of a good story: an escalation in tension and difficulty, spaced with breathers for rhythm and flow. Place those sets on a path in a map, then figure out a way to connect them together at the lower level with rooms, objects, enemies, and corridors.
- ximeng 12y ago
  Adom is a roguelike that does your "holistic perspective" very well - it mixes an overall story arc and set piece locations with a lot of randomised elements. It's going through a bit of a renaissance after raising 90k on IndieGoGo.
otikik 12y ago
The best series of maze generation that I know is in Cogmind's dev blog: http://www.gridsagegames.com/blog/2014/06/procedural-map-generation/ http://www.gridsagegames.com/blog/2014/06/procedural-map-gen...
steeve 12y ago
Pretty neat is also Laurent Victorino's maze generator that can generate mazes with patterns: http://www.gamasutra.com/blogs/LaurentVictorino/20141202/231321/Mazes_hidden_beauty.php http://www.gamasutra.com/blogs/LaurentVictorino/20141202/231...
jmartinpetersen 12y ago
It is an amazing article. The "fluff" prose is well written and the visualizations are awesome. Kudos. An honest question, though, is maze generation generally useful? Other than for generating mazes and dungeons, obviously, not that isn't a worthy goal in and of it self.
- dirkk0 12y ago
  I think some of the ideas behind maze generation can be applied to procedural level generation in general, whith some clever tweaks at least. Here is an approach in Python albeit not as interactive as the mentioned article: http://pixelenvy.ca/wa/ca_cave.html http://pixelenvy.ca/wa/ca_cave.html In case people didn't recognize, the author of the articel is also the author of this book which is for free (kudos!) on the interwebs and can be bought as a eBook. http://gameprogrammingpatterns.com/ http://gameprogrammingpatterns.com/
  - jmartinpetersen 12y ago
    But what about something completely different? I get that generation of "content" is (going to be) a big thing, but I'm curious if there's something about it that was applicable in a completely different setting (medicine, finance, whatever).
- applekor 12y ago
  Last time I needed a maze I implemented Kruskal's algorithm, which is generally useful for finding the minimum spanning tree of a graph. You just run it on a lattice graph where all edge weights are the same and you have yourself a perfect maze.
rashid1233 12y ago
http://eocean.pk/sms-services/short-code-management/ http://eocean.pk/sms-services/short-code-management/
rashid1233 12y ago
http://eocean.pk/sms-services/short-code-management/ http://eocean.pk/sms-services/short-code-management/ EOCEAN provide Short Code sms services. Short codes are 4 or 5 digit numbers which provide a 2 way communication
ralfn 12y ago
A long time ago i also wrote a maze generator. It's helpfull to understand the algebra of (fully accessible) mazes: 1. Every wall may intersect with some other wall at most once. (this includes the outer wall) With the above rule in mind, you can create mazes with any type of random proccess (without the need for backtracking or bookkeeping). You don't have to check wether places are still accessible -- they just always are and will be. Back in those days (qbasic on a 268) just drawing randomly from some point in random directions was about ten times faster than the common path walking (backtracking) style algorithms. Taking two seconds instead of a full minute. Don't take my word for it. Grab a pencil. Start drawing random lines. They may only cross some other line at most once. You'll end up with a fully accessible maze. The maze may be complicated -- the walls in a proper maze are not. Its a great example of how understanding the invariants and rules that govern your problem domain will help you write faster and simpler code.
- tiglionabbit 12y ago
  I can't quite figure out how to carry out your instructions.
  - jfoutz 12y ago
    Two walls interact in only 3 ways - first, they don't touch. you get hallways: ||, second one intersects ends at the other like a T (which is a kind of degenerate version of 3). Third, they cross over, like a +. if you don't let walls touch multiple times, say like a D you'll never have a closed off space like the center of that D.
    - dsp1234 12y ago
      Start drawing random lines. I got this on my first try: +------------------+--+---+ | - | | | -| | | + | | |- -| | | + | | |- -| | + + | -| | | - | | | - | | | - | +----------------+----+---+ I got that by drawing an exterior square with a single entrance in the bottom right hand corner. I then drew a line from the top wall to the bottom wall parallel to the left and right walls. I then drew a diagonal line from about a quarter of the way down the right wall left and downwards towards the bottom wall. I then drew a diagonal line from about three quarters of the way down the right wall, up and to left towards the top wall. This blocks off most of the maze. So I'm not sure the algorithm works as has been described.
gus_massa 12y ago
> It’s not perfect, though. It tends to produce annoyingly windy passages between rooms. One possibility is to straight some corridors in a new final step, but I don't know how well this work in the actual mazes. For example, transform: -+ +- ==> ----- +-+ and | | | +- ==> +--- +-+
- kibwen 12y ago
  Amusingly, I think this demonstrates one of the problems with classic roguelike dungeon generation: single-tile corridors are rarely very interesting, and usually much less interesting than the rooms they connect. To cop a quote from the OP itself: "Fundamentally, games are about making decisions from a set of alternatives." In a hallway, your alternatives are reduced to moving forward and moving backward. When confronted with enemies, you can choose from at most two to attack (ignoring AOE for a moment, since it's usually also strictly less interesting in narrow corridors, as the article mentions as well). Instead of passageways, I prefer a technique I've seen in Dungeon Crawl Stone Soup: start with an enormous open level (often in a more interesting shape than a square, such as a randomly-generated blob), and generate enclosed rooms within that level. At the limit, you can recursively partition the entire level until it's a series of small interconnected rooms, doing away with passageways altogether.
rout39574 12y ago
Needs an Xscreensaver demo. :)
- munificent 12y ago
  Left as an exercise for the reader!
pavel_lishin 12y ago
Any thoughts on letting the rooms overlap sometimes, to generate dungeons that have non-rectangular rooms?
- munificent 12y ago
  Yes, that would work fine. You just have to track when that happens so that you know those two rooms are already merged. Another option is to generate non-overlapping bounding boxes for rooms, but then don't fill in that entire box. Instead, you can draw whatever shape you want in there. The maze generator will then fill in the cracks you leave.
Pfhreak 12y ago
Maze generators are a lot of fun to play with, but don't always come up with the most compelling gameplay environments. One of the techniques I've heard works well is to step up the abstraction level one click, and create interesting environments and set pieces, then combine those to create a compelling environment for your players. One approach to do this uses herringbone Wang tiles to place various precreated environment tiles in a random, pathable way. http://nothings.org/gamedev/herringbone/ http://nothings.org/gamedev/herringbone/ The results are similar, but allow the developer to inject a little bit of human direction along the way.
- jpasden 12y ago
  Another good example of this approach is indie 2D platformer Spelunky. Here's an illustration of the method: http://tinysubversions.com/spelunkyGen/ http://tinysubversions.com/spelunkyGen/
_lce0 12y ago
man it broke both my phone and tablet every time I opened .. but it worth taking the time to looking at desktop! good work
moomin 12y ago
One of the developers of DCSS said that the hardest problem of procedural dungeon creation was avoiding generating a swastika by accident.

332 points by dustinlakin 12y ago

Looks good! I found this to be a great resource on Maze generation: http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorithm-recap http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorit...

DrJosiah 12y ago
Jamis has a lot of great articles on maze generation, was about to post a link :)

akanet 12y ago

I think this article is a fantastic example of how you can blend prose with working interactive examples. The examples make you really trance out watching dungeons being carved out of nothing. I think an often-discounted aspect of JavaScript's appeal is its ability to breathe life into a bunch of fascinating but otherwise dry concepts. Another terrific example is this page by the prolific Mike Bostock: http://bost.ocks.org/mike/algorithms/ http://bost.ocks.org/mike/algorithms/

munificent 12y ago
I agree totally. I love the ability to write blog posts with interactive animated content. We take for granted that the web platform can do all this, but it's rare to find content that takes advantage of it. Mike Bostock and Amit Patel's sites are notable counter-examples. I'd like to do more posts like this, but I can see why they aren't common. This one took me forever to finish. Easily eight times as much effort as a regular text + code samples blog post. I think I'd get faster as I did more in this style, but it's really hard to for me to stay energized on a single concept long enough to finish posts like this.

mseepgood 12y ago

Labyrinth generator in a single line of code: http://www.slate.com/articles/technology/books/2012/11/computer_programming_10_print_chr_205_5_rnd_1_goto_10_from_mit_press_reviewed.html http://www.slate.com/articles/technology/books/2012/11/compu...

tromp 12y ago
The second example on http://en.wikipedia.org/wiki/Obfuscation_%28software%29 http://en.wikipedia.org/wiki/Obfuscation_%28software%29 is a 7 line maze that generates arbitrary length mazes. Its construction is described at http://tromp.github.io/maze.html http://tromp.github.io/maze.html

fit2rule 12y ago

That was a very pleasant article and fills me with inspiration .. which is what I came here for, mostly, in the first place. I don't have many applications for twisty mazes in my space at the moment, but one thing that I always thought would be interesting is to use the dependency graphs/use-counts of various system libraries as inputs to a maze generator. Sort of like Fsn (http://en.wikipedia.org/wiki/Fsn http://en.wikipedia.org/wiki/Fsn) but with a lot more twisty, bendy mazes between the ldd details .. huh, yet another bit of bait for the bucket ..

doomlaser 12y ago

Another cheap and very effective technique for procedural level and maze generation is to create a "walker" or series of walkers that start at some point, walk in a direction and then turn at random intervals, leaving a path of corridors and occasionally rooms in their wake. This is how Vlambeer's Nuclear Throne generates its levels, and there's a good article from Jan Willem Nijman, it's developer, here: http://www.vlambeer.com/2013/04/02/random-level-generation-in-wasteland-kings/ http://www.vlambeer.com/2013/04/02/random-level-generation-i... If you'd like a more academic look into procedural 2d game generation, there's a nice research paper here, that describes a method and talks about Spelunky a lot (the king of procedural 2d level generation, in my book): http://games.soe.ucsc.edu/sites/default/files/cig10_043CP2_115.pdf http://games.soe.ucsc.edu/sites/default/files/cig10_043CP2_1... Additionally, Derek Yu open sourced the code to the original Spelunky, and Darius Kazemi created a great breakdown of its level generation techniques here, also with interactive examples: http://tinysubversions.com/spelunkyGen/index.html http://tinysubversions.com/spelunkyGen/index.html The action roguelike genre, particularly the roguelike FPS, is a vital new area being explored by indie game developers. It reminds me of the way 2D platformers were mined, explored, and iterated upon starting around 7 or 8 years ago. Right now, it doesn't take much to stand out from the herd, as many of the most popular games in the genre don't do much beyond generating a bunch of square rooms and connecting them with doors and short, straight corridors. In my opinion, developers in the genre should take more cues from Doom, and less from original Zelda dungeons moving forward. And, from a more holistic perspective, nobody really cares about mazes, room placement on a grid, and connective corridors when playing a game, beyond a brute mechanical level. A more useful framework for thinking of generating levels might be to go one level of abstraction higher. Think about a level as a story for your player, and generate setpieces or 'acts' that you want the player to experience as they play. Keep in mind the basics of a good story: an escalation in tension and difficulty, spaced with breathers for rhythm and flow. Place those sets on a path in a map, then figure out a way to connect them together at the lower level with rooms, objects, enemies, and corridors.

ximeng 12y ago
Adom is a roguelike that does your "holistic perspective" very well - it mixes an overall story arc and set piece locations with a lot of randomised elements. It's going through a bit of a renaissance after raising 90k on IndieGoGo.

otikik 12y ago

The best series of maze generation that I know is in Cogmind's dev blog: http://www.gridsagegames.com/blog/2014/06/procedural-map-generation/ http://www.gridsagegames.com/blog/2014/06/procedural-map-gen...

steeve 12y ago

Pretty neat is also Laurent Victorino's maze generator that can generate mazes with patterns: http://www.gamasutra.com/blogs/LaurentVictorino/20141202/231321/Mazes_hidden_beauty.php http://www.gamasutra.com/blogs/LaurentVictorino/20141202/231...

jmartinpetersen 12y ago

It is an amazing article. The "fluff" prose is well written and the visualizations are awesome. Kudos. An honest question, though, is maze generation generally useful? Other than for generating mazes and dungeons, obviously, not that isn't a worthy goal in and of it self.

dirkk0 12y ago
I think some of the ideas behind maze generation can be applied to procedural level generation in general, whith some clever tweaks at least. Here is an approach in Python albeit not as interactive as the mentioned article: http://pixelenvy.ca/wa/ca_cave.html http://pixelenvy.ca/wa/ca_cave.html In case people didn't recognize, the author of the articel is also the author of this book which is for free (kudos!) on the interwebs and can be bought as a eBook. http://gameprogrammingpatterns.com/ http://gameprogrammingpatterns.com/
- jmartinpetersen 12y ago
  But what about something completely different? I get that generation of "content" is (going to be) a big thing, but I'm curious if there's something about it that was applicable in a completely different setting (medicine, finance, whatever).
applekor 12y ago
Last time I needed a maze I implemented Kruskal's algorithm, which is generally useful for finding the minimum spanning tree of a graph. You just run it on a lattice graph where all edge weights are the same and you have yourself a perfect maze.

rashid1233 12y ago

http://eocean.pk/sms-services/short-code-management/ http://eocean.pk/sms-services/short-code-management/

rashid1233 12y ago

http://eocean.pk/sms-services/short-code-management/ http://eocean.pk/sms-services/short-code-management/ EOCEAN provide Short Code sms services. Short codes are 4 or 5 digit numbers which provide a 2 way communication

ralfn 12y ago

A long time ago i also wrote a maze generator. It's helpfull to understand the algebra of (fully accessible) mazes: 1. Every wall may intersect with some other wall at most once. (this includes the outer wall) With the above rule in mind, you can create mazes with any type of random proccess (without the need for backtracking or bookkeeping). You don't have to check wether places are still accessible -- they just always are and will be. Back in those days (qbasic on a 268) just drawing randomly from some point in random directions was about ten times faster than the common path walking (backtracking) style algorithms. Taking two seconds instead of a full minute. Don't take my word for it. Grab a pencil. Start drawing random lines. They may only cross some other line at most once. You'll end up with a fully accessible maze. The maze may be complicated -- the walls in a proper maze are not. Its a great example of how understanding the invariants and rules that govern your problem domain will help you write faster and simpler code.

tiglionabbit 12y ago
I can't quite figure out how to carry out your instructions.
- jfoutz 12y ago
  Two walls interact in only 3 ways - first, they don't touch. you get hallways: ||, second one intersects ends at the other like a T (which is a kind of degenerate version of 3). Third, they cross over, like a +. if you don't let walls touch multiple times, say like a D you'll never have a closed off space like the center of that D.
  - dsp1234 12y ago
    Start drawing random lines. I got this on my first try: +------------------+--+---+ | - | | | -| | | + | | |- -| | | + | | |- -| | + + | -| | | - | | | - | | | - | +----------------+----+---+ I got that by drawing an exterior square with a single entrance in the bottom right hand corner. I then drew a line from the top wall to the bottom wall parallel to the left and right walls. I then drew a diagonal line from about a quarter of the way down the right wall left and downwards towards the bottom wall. I then drew a diagonal line from about three quarters of the way down the right wall, up and to left towards the top wall. This blocks off most of the maze. So I'm not sure the algorithm works as has been described.

gus_massa 12y ago

> It’s not perfect, though. It tends to produce annoyingly windy passages between rooms. One possibility is to straight some corridors in a new final step, but I don't know how well this work in the actual mazes. For example, transform: -+ +- ==> ----- +-+ and | | | +- ==> +--- +-+

kibwen 12y ago
Amusingly, I think this demonstrates one of the problems with classic roguelike dungeon generation: single-tile corridors are rarely very interesting, and usually much less interesting than the rooms they connect. To cop a quote from the OP itself: "Fundamentally, games are about making decisions from a set of alternatives." In a hallway, your alternatives are reduced to moving forward and moving backward. When confronted with enemies, you can choose from at most two to attack (ignoring AOE for a moment, since it's usually also strictly less interesting in narrow corridors, as the article mentions as well). Instead of passageways, I prefer a technique I've seen in Dungeon Crawl Stone Soup: start with an enormous open level (often in a more interesting shape than a square, such as a randomly-generated blob), and generate enclosed rooms within that level. At the limit, you can recursively partition the entire level until it's a series of small interconnected rooms, doing away with passageways altogether.

rout39574 12y ago

Needs an Xscreensaver demo. :)

munificent 12y ago
Left as an exercise for the reader!

pavel_lishin 12y ago

Any thoughts on letting the rooms overlap sometimes, to generate dungeons that have non-rectangular rooms?

munificent 12y ago
Yes, that would work fine. You just have to track when that happens so that you know those two rooms are already merged. Another option is to generate non-overlapping bounding boxes for rooms, but then don't fill in that entire box. Instead, you can draw whatever shape you want in there. The maze generator will then fill in the cracks you leave.

Pfhreak 12y ago

Maze generators are a lot of fun to play with, but don't always come up with the most compelling gameplay environments. One of the techniques I've heard works well is to step up the abstraction level one click, and create interesting environments and set pieces, then combine those to create a compelling environment for your players. One approach to do this uses herringbone Wang tiles to place various precreated environment tiles in a random, pathable way. http://nothings.org/gamedev/herringbone/ http://nothings.org/gamedev/herringbone/ The results are similar, but allow the developer to inject a little bit of human direction along the way.

jpasden 12y ago
Another good example of this approach is indie 2D platformer Spelunky. Here's an illustration of the method: http://tinysubversions.com/spelunkyGen/ http://tinysubversions.com/spelunkyGen/

_lce0 12y ago

man it broke both my phone and tablet every time I opened .. but it worth taking the time to looking at desktop! good work

moomin 12y ago

One of the developers of DCSS said that the hardest problem of procedural dungeon creation was avoiding generating a swastika by accident.