from Hacker News

Rooms and Mazes: A Procedural Dungeon Generator

by dustinlakin on 12/22/14, 6:57 AM with 48 comments

  • by ralfn on 12/22/14, 12:44 PM

    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.

  • by doomlaser on 12/22/14, 9:24 AM

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

    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.

  • by akanet on 12/22/14, 8:47 AM

    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/

  • by otikik on 12/22/14, 11:01 AM

    The best series of maze generation that I know is in Cogmind's dev blog:

    http://www.gridsagegames.com/blog/2014/06/procedural-map-gen...

  • by gavanwoolery on 12/22/14, 8:30 AM

    Looks good! I found this to be a great resource on Maze generation:

    http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorit...

  • by steeve on 12/22/14, 11:07 AM

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

  • by fit2rule on 12/22/14, 9:18 AM

    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) but with a lot more twisty, bendy mazes between the ldd details .. huh, yet another bit of bait for the bucket ..

  • by gus_massa on 12/22/14, 1:11 PM

    > 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

      |          |
  | +-  ==>  +---
  +-+

  • by mseepgood on 12/22/14, 8:52 AM

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

  • by jmartinpetersen on 12/22/14, 11:09 AM

    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.

  • by Pfhreak on 12/23/14, 2:17 AM

    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/

    The results are similar, but allow the developer to inject a little bit of human direction along the way.

  • by rout39574 on 12/22/14, 2:58 PM

    Needs an Xscreensaver demo. :)

  • by pavel_lishin on 12/22/14, 3:51 PM

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

  • by moomin on 12/23/14, 10:37 AM

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

  • by _lce0 on 12/23/14, 4:47 AM

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

    good work