<p>Say you want a simple maze on an N by M grid, with one path through, and a good number of dead ends, but that looks "right" (i.e. like someone made it by hand without too many little tiny dead ends and all that). Is there a known way to do this?</p>

[{'answer_id': 38507, 'author': 'OysterD', 'author_id': 2638, 'author_profile': 'https://Stackoverflow.com/users/2638', 'pm_score': 3, 'selected': False, 'text': '<p>Strangely enough, by slightly changing the \'canonical\' rules and starting from a random configuration, <a href="http://en.wikipedia.org/wiki/Conway&#39;s_Game_of_Life" rel="nofollow noreferrer">Conway\'s Game of Life</a> seems to generate pretty nice mazes!</p>\n\n<p>(I don\'t remember the exact rule, but it\'s a very simple modification that tends to \'densify\' the population of cells...)</p>\n'}, {'answer_id': 38517, 'author': 'rmmh', 'author_id': 3694, 'author_profile': 'https://Stackoverflow.com/users/3694', 'pm_score': 7, 'selected': True, 'text': '<p>From <a href="http://www.astrolog.org/labyrnth/algrithm.htm" rel="noreferrer">http://www.astrolog.org/labyrnth/algrithm.htm</a></p>\n\n<blockquote>\n  <p>Recursive backtracker: This is somewhat related to the recursive backtracker solving method described below, and requires stack up to the size of the Maze. When carving, be as greedy as possible, and always carve into an unmade section if one is next to the current cell. Each time you move to a new cell, push the former cell on the stack. If there are no unmade cells next to the current position, pop the stack to the previous position. The Maze is done when you pop everything off the stack. This algorithm results in Mazes with about as high a "river" factor as possible, with fewer but longer dead ends, and usually a very long and twisty solution. It runs quite fast, although Prim\'s algorithm is a bit faster. Recursive backtracking doesn\'t work as a wall adder, because doing so tends to result in a solution path that follows the outside edge, where the entire interior of the Maze is attached to the boundary by a single stem. </p>\n</blockquote>\n\n<p>They produce only 10% dead ends</p>\n\n<p><img src="https://i.stack.imgur.com/vWo6P.gif"></p>\n\n<p>is an example of a maze generated by that method.</p>\n'}, {'answer_id': 7611879, 'author': 'Savino Sguera', 'author_id': 346980, 'author_profile': 'https://Stackoverflow.com/users/346980', 'pm_score': 5, 'selected': False, 'text': '<p>A pretty straightforward solution could be to assign random weights to the graph edges and apply <a href="http://en.wikipedia.org/wiki/Kruskal%27s_algorithm" rel="noreferrer">Kruskal\'s algorithm</a> to find a minimum spanning tree.</p>\n\n<p>Best discussion ever on maze generation algorithms: <a href="http://www.jamisbuck.org/presentations/rubyconf2011/index.html" rel="noreferrer">http://www.jamisbuck.org/presentations/rubyconf2011/index.html</a> (was on HN a couple days ago).</p>\n'}, {'answer_id': 23681987, 'author': 'john_science', 'author_id': 1287593, 'author_profile': 'https://Stackoverflow.com/users/1287593', 'pm_score': 6, 'selected': False, 'text': '<p>It turns out there are 11 classic algorithms to generate &quot;perfect&quot; mazes. A maze is perfect if it has one, and only one, solution. Here are some links to each algorithm, in rough order of my preference.</p>\n<ol>\n<li><a href="http://weblog.jamisbuck.org/2011/1/3/maze-generation-kruskal-s-algorithm" rel="noreferrer">Kruskal\'s</a></li>\n<li><a href="http://weblog.jamisbuck.org/2011/1/10/maze-generation-prim-s-algorithm" rel="noreferrer">Prim\'s</a></li>\n<li><a href="http://weblog.jamisbuck.org/2010/12/27/maze-generation-recursive-backtracking" rel="noreferrer">Recursive Backtracker</a></li>\n<li><a href="http://weblog.jamisbuck.org/2011/1/17/maze-generation-aldous-broder-algorithm" rel="noreferrer">Aldous-Broder</a></li>\n<li><a href="http://weblog.jamisbuck.org/2011/1/27/maze-generation-growing-tree-algorithm" rel="noreferrer">Growing Tree</a></li>\n<li><a href="http://weblog.jamisbuck.org/2011/1/24/maze-generation-hunt-and-kill-algorithm" rel="noreferrer">Hunt-and-Kill</a></li>\n<li><a href="http://weblog.jamisbuck.org/2011/1/20/maze-generation-wilson-s-algorithm" rel="noreferrer">Wilson\'s</a></li>\n<li><a href="http://weblog.jamisbuck.org/2010/12/29/maze-generation-eller-s-algorithm" rel="noreferrer">Eller\'s</a></li>\n<li><a href="http://weblog.jamisbuck.org/2011/2/3/maze-generation-sidewinder-algorithm" rel="noreferrer">Recursive Division</a>  (Predictable)</li>\n<li><a href="http://weblog.jamisbuck.org/2011/2/1/maze-generation-binary-tree-algorithm" rel="noreferrer">Sidewinder</a>  (Predictable)</li>\n<li><a href="https://github.com/theJollySin/mazelib" rel="noreferrer">Binary Tree</a>  (Flawed)</li>\n</ol>\n<p>For more info, check out <a href="https://github.com/theJollySin/mazelib" rel="noreferrer">mazelib</a> on GitHub, a Python library implementing all the standard maze generating/solving algorithms.</p>\n'}, {'answer_id': 24014359, 'author': 'user3628041', 'author_id': 3628041, 'author_profile': 'https://Stackoverflow.com/users/3628041', 'pm_score': 2, 'selected': False, 'text': "<p>One of the methods to generate a maze is the randomized version of Prim's algorithm.</p>\n<p>Start with a grid full of walls.\nPick a cell, mark it as part of the maze. Add the walls of the cell to the wall list.\nWhile there are walls in the list:</p>\n<p>Pick a random wall from the list. If the cell on the opposite side isn't in the maze yet:</p>\n<p>(i) Make the wall a passage and mark the cell on the opposite side as part of the maze.</p>\n<p>(ii) Add the neighboring walls of the cell to the wall list.</p>\n<p>If the cell on the opposite side already was in the maze, remove the wall from the list.</p>\n"}, {'answer_id': 29574087, 'author': 'Muhammad Hashim Shafiq', 'author_id': 3164900, 'author_profile': 'https://Stackoverflow.com/users/3164900', 'pm_score': 1, 'selected': False, 'text': "<p>Here's the DFS algorithm written as pseudocode: </p>\n\n<p>create a CellStack (LIFO) to hold a list of cell locations<br>\nset TotalCells = number of cells in grid<br>\nchoose a cell at random and call it CurrentCell<br>\nset VisitedCells = 1  </p>\n\n<p>while VisitedCells &lt; TotalCells \nfind all neighbors of CurrentCell with all walls intact<br>\nif one or more found \nchoose one at random<br>\nknock down the wall between it and CurrentCell<br>\npush CurrentCell location on the CellStack<br>\nmake the new cell CurrentCell<br>\nadd 1 to VisitedCells\nelse \npop the most recent cell entry off the CellStack<br>\nmake it CurrentCell\nendIf\nendWhile  </p>\n"}, {'answer_id': 41656566, 'author': 'Matt Timmermans', 'author_id': 5483526, 'author_profile': 'https://Stackoverflow.com/users/5483526', 'pm_score': 3, 'selected': False, 'text': '<p>My favorite way is to use Kruskal\'s algorithm, but when randomly choosing and edge to remove, weight the choice based on the types of edges it\'s connected to.</p>\n\n<p>By varying the weights for different edge types, you can generate mazes with lots of distinct characteristics or "personalities".  See my example here:</p>\n\n<p><a href="https://mtimmerm.github.io/webStuff/maze.html" rel="noreferrer">https://mtimmerm.github.io/webStuff/maze.html</a></p>\n'}, {'answer_id': 58616773, 'author': 'Joe Schmoe', 'author_id': 12294245, 'author_profile': 'https://Stackoverflow.com/users/12294245', 'pm_score': 1, 'selected': False, 'text': '<p>I prefer a version of the Recursive Division algorithm.  It is described in detail <a href="https://weblog.jamisbuck.org/2015/1/15/better-recursive-division-algorithm.html" rel="nofollow noreferrer">here.</a></p>\n\n<p><strong>I will give a quick overview:</strong><br>\nThe original recursive division algorithm works as follows.  First, start with an empty area for the maze.  Add one straight wall to divide the chamber in two, and put one hole in that wall somewhere.  Then, recursively repeat this process on each of the two new chambers until the desired passage size is reached.  This is simple and works well, but there are obvious bottlenecks which make the maze easy to solve.<br><br>\nThe variant solves this problem by drawing randomized, "curved" walls rather than straight ones, making the bottlenecks less obvious.</p>\n'}, {'answer_id': 61666821, 'author': 'Sihat Afnan', 'author_id': 11837247, 'author_profile': 'https://Stackoverflow.com/users/11837247', 'pm_score': 2, 'selected': False, 'text': "<p>Recursive Backtracking is the easiest algorithm to implement.</p>\n\n<p>Here's a Java implementation:</p>\n\n<p>Here <em>Cell</em> is a class representing a cell in a 2D grid and <strong>cells</strong> is a 2D array of <em>Cell</em> objects. <em>Cell</em> has boolean variables <em>top</em>, <em>bottom</em>, <em>left</em> and <em>right</em> to indicate whether a cell has walls on these sides, a boolean variable <em>visited</em> to check whether we have traversed it and two integer variables <em>row</em> and <em>col</em> to indicate its position in the grid.</p>\n\n<pre><code>Cell current = cells[0][0] , next;\n    current.visited=true;\n    do{\n        next = getNeighbour(current);\n        if(next!=null){\n            removeWall(current , next);\n            st.push(current);\n            current = next;\n            current.visited = true;\n        }\n        else {\n            current = st.pop();\n        }\n    }\n    while (!st.empty());\n\n\n    private Cell getNeighbour(Cell cell){\n    ArrayList&lt;Cell&gt; ara = new ArrayList&lt;&gt;();\n    if(cell.col&gt;0 &amp;&amp; !cells[cell.col-1][cell.row].visited)\n         ara.add(cells[cell.col-1][cell.row]);\n\n    if(cell.row&gt;0 &amp;&amp; !cells[cell.col][cell.row-1].visited)\n         ara.add(cells[cell.col][cell.row-1]);\n\n    if(cell.col&lt;col-1 &amp;&amp; !cells[cell.col+1][cell.row].visited)\n         ara.add(cells[cell.col+1][cell.row]);\n    if(cell.row&lt;row-1 &amp;&amp; !cells[cell.col][cell.row+1].visited)\n         ara.add(cells[cell.col][cell.row+1]); \n\n\n    if(ara.size()&gt;0){\n        return ara.get(new Random().nextInt(ara.size()));\n    }else{\n        return null;\n    }\n}\nprivate void removeWall(Cell curr , Cell nxt){\n    if((curr.col == nxt.col) &amp;&amp; (curr.row == nxt.row+1)){/// top\n        curr.top=nxt.botttom=false;\n    }\n    if(curr.col==nxt.col &amp;&amp; curr.row == nxt.row-1){///bottom\n        curr.botttom = nxt.top = false;\n    }\n    if(curr.col==nxt.col-1 &amp;&amp; curr.row==nxt.row ){///right\n        curr.right = nxt.left = false;\n    }\n    if(curr.col == nxt.col+1 &amp;&amp; curr.row == nxt.row){///left\n        curr.left = nxt.right = false;\n    }\n}\n</code></pre>\n"}]
['https://Stackoverflow.com/questions/38502', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/4123/']