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.

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.

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/

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

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

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

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

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

> 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

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

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

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.

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.

Needs an Xscreensaver demo. :)

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

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

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

good work