Talk:Maze generation algorithm

Randomized Prim's algorithm

The article says "Pick a random wall from the list. If the cell on the opposite side isn't in the maze yet", but doesn't explain what the opposite is the opposite of!

The algorithm specifies to pick arbitrarily. I suggest the section rewritten. —Preceding unsigned comment added by 84.238.88.224 (talk) 21:06, 1 April 2010 (UTC)

So you mean pick a random adjacent cell? Kurtoid (talk) 01:19, 2 December 2014 (UTC)

The confusion comes from 2 different ways how "walls" work. Ultimately, the confusion stems from no one elaborating on the data model implied by the algorithm text. Some use Cells as "type Cell = | Wall | Passage". Others use Cells only as cells and have walls defined as the border between 2 cells. The current version of the article mixes those two approaches, yielding an algorithm which is unclear. — Preceding unsigned comment added by 79.220.96.139 (talk) 08:44, 20 April 2015 (UTC)

"Depth-first search" versus "Recursive Backtracker"

How are these two different? One uses recursion, whilst the other both keeps an explicit stack and uses recursion; other than this (rather pointless, from a programmer's perspective) implementation detail, I can't imagine how the two would produce different results.

Also, is there any reason why the description of the recursive backtracker is in between the description of the randomized Prim's algorithm and its modified version? Is it somehow the intention that the recursive backtracker is a modified Prim's algorithm? Because it doesn't look much like one.

- Anon. 2007-04-02

Indeed, recursive backtracking is merely one way of implementing a depth-first search. (Another way is to use a stack.) Therefore I've merged the "Recursive backtracker" section into the "Depth-first search" section. I also moved the "Modified version" of Prim's algorithm into the Prim's algorithm section proper. Thanks, Cruiser1 22:52, 24 September 2007 (UTC)

WdJ: I think the text still is confusing. Well, confusing enough for me to write this Talk entry. The "depth-first" algo simply equals the recursive backtracker, except that the explanation for "depth-first" is not as clear. As far as the stack-based versus recursion point goes ... any recursive algorithm can be rewritten into a non-recursive form. As a programmer, I suppose the "recursive backtracker" may be implemented in a non-recursive way, whilst not really altering the maze generation method used. (Likewise, depth-first search operations are often implemented recursively (especially in school book examples on programming binary trees)). The recursive backtracker is based on the depth-first search algorithm, or at least, it looks nearly identical and it operates in the same way. But rather than searching for a solution here, it is generating the maze. The Think Labyrinth site does not even mention "depth-first", it calls this method the "recursive backtracker". Therefore I think the paragraph "depth-first search" should be scrapped, and "recursive backtracker" should say that it operates in the same way as the depth-first search operation that is used for solving the maze.

- walter at heiho dot net 2010-07-05 —Preceding unsigned comment added by 145.100.60.106 (talk) 22:21, 5 July 2010 (UTC)

- Armin Reichert 2019-04-27: I tried to clarify the confusion regarding "Randomized DFS" and "Recursive Backtracking". The algorithm is just a randomized DFS traversal of a (full) grid graph. Instead of using two graphs, a full graph that is traversed and the one where you add new edges and that will become the maze (spanning tree), the algorithms just uses a single graph. "Recursive" backtracking is misleading because the backtracking does not necessarily has to be implemented by a recursive procedure. The Java code example shows both implementation variants. — Preceding unsigned comment added by 2A01:5C0:E082:2161:7445:515B:361B:8BB4 (talk) 08:42, 27 April 2019 (UTC)

- Armin Reichert 2019-06-08: I removed all my changes and my Java implementation from Wikipedia again because I do not tolerate the behavior of so called "moderators" that act as censors. Wikipedia should be ashamed of these people. Political articles on Wikipedia are completely controlled by leftists acting like "Blockwarts" in totalitarian regimes. — Preceding unsigned comment added by 2A01:5C0:E094:90C1:9144:BF3:D9FC:8B54 (talk) 13:41, 8 June 2019 (UTC)

Political disputes aside, we're back to there being no obvious difference between recursive backtracking and depth-first search. I'm fairly sure there is no difference, or else one is supposed to be a subset of the other. If the latter case, there is no example given of how the subset would be specified from the general set. LordQwert (talk) 16:08, 5 September 2019 (UTC)

I believe that "recursive backtracker" is normally used to refer to the same algorithm as "randomised depth-first-search", even when it is implemented with a stak rather than recursion. — Preceding unsigned comment added by Pillowe (talk • contribs) 14:46, 9 July 2020 (UTC)

Kruskal's algorithm

The Kruskal's algorithm as stated is/was slow and unnecessarily restrictive! Kruskal's algorithm works on any connected graph, not just rectangular and hexagonal matrices. Kruskal's algorithm does usually take O (E log E) because finding the least costly edge each time costs (log E). In the random Kruskal's algorithm you just need to select a random edge each time, which only costs O(1). So the cost will be number of edges times the cost to join two regions. But it is easy to show that there are disjoint set implementations that can perform the needed union-find operations in constant time, so the total time to generate the maze is only O(E). Kevin Saff 04:21, 7 Feb 2004 (UTC)

Depth First = Straight is not quite right

The comment that a maze generated "depth first" MUST have "many long corridors" is not true, in my experience. A preponderance of long corridors only occur if the random selection among the available paths (ie neighbors) is weighted towards the "directly ahead" neighbor OR recursion ONLY occurs when a change of direction occurs (thus, new branches do not occur within straight corridors, but only from turns, which can create what looks like a straight corridor, later). If the selection is unbiased, and EVERY step is recursed (or the backtracing routine is not biased against straightways) the maze will typically have some, but not a preponderance of straight corridors. Is is possible to add bias to the algorithim so that it generates mazes of varying "curviness" along a continuum from "mostly straight" to "perfectly curvy"

Please see http://ccl.northwestern.edu/netlogo/models/community/maze-maker-2004 for a NetLogo model that generates mazes of varying curviness. (James Steiner[JPS])

I think that line means to say that the algorithm results in fewer dead ends; there are lots of paths without forks — in this sense they are strait. Perhaps it should be clarified. 65.96.153.126 03:41, 10 March 2006 (UTC)

Depth First = start location is obvious is not true

The comment "it will typically be relatively easy to find the way to the square that was first picked at the beginning of the algorithm, since most paths lead to or from there, but hard to find the way out." is not true, in my experience. Any node on maze built as described can have from 1 to 4 exits, and that includes the start-point. For example, if the first branch works it's way around to "surround" the start-point. So, there is no inherent advantage for solving the maze in starting at the same node the maze was originally generated from.

Some statements that _can_ be made about such a maze are:

• A path exists between any two nodes in the maze
  • Therefore Any two nodes on the "outside" of such a maze can be selected as the start and end: a path always exists between them.

[JPS]

I agree: This statement should be deleted because the stating point isn't special. It is true that there's a path from each point in the maze to the starting point but this is the case with any other poin too. 46.114.154.73 (talk) 03:03, 14 June 2014 (UTC)

3D Mazes?

The main article could be improved if somebody would include a picture of a maze that has been mapped onto a 3D surface where proper viewing (and solving) might depend on using the popular red and blue (or red and green) 3D (anaglyphic) glasses. For instance, following a strand of spaghetti through a pile on a plate, for instance, can be just as absorbing as picking the proper path from an aerial shot of a hedge maze.

Mazes and Knots

Can anybody explain the difference between a maze of N nodes, and a knot of X crossings according to Y and Z orientations? If at all possible, could you a wiki link to an article that can introduce a rank beginner to the whole matter of messy complexities?

Example Code on the Image

The example code is extremely difficult to understand because of its use of bitwise operators that make no sense. I am currently working on an implementation of the Depth-first search (with backtracking) method as described here, could I post it here? —Preceding unsigned comment added by 70.134.92.105 (talk) 05:55, 31 January 2009 (UTC)

It's a wiki, you can always post your stuff. I would really love that, since the existing code is an extremely awful piece of Java code.

Tsuihark (talk) 13:46, 24 February 2009 (UTC)

We need a reference to example code in this article, rather than the code itself. If such code is documented in reliable sources then it can be referred to in the text of the article, along with a cited reference. The code itself is not appropriate for inclusion within this article, per WP:NOTHOWTO. Perhaps it should be transwikied to wikibooks:. -- Trevj (talk) 08:55, 19 September 2012 (UTC)

Why the pic is linked?

Why the picture for an example of the amorphous maze is linked isntead of being shown directly in the page?--TiagoTiago (talk) 17:37, 10 February 2009 (UTC)

A open source 4D (and 3D( maze game program

http://www.urticator.net/maze/

is that somthing that should go in the article somewhere? (like on external links or somthing) --TiagoTiago (talk) 17:39, 10 February 2009 (UTC)

Although there are a number of interesting Maze web sites and Maze programs out there, it's important to remember that Wikipedia is not a link farm. Any links must support or expand on in a meaningful way the article purpose, namely algorithms for generating Mazes. (Yes I realize some existing links are inappropriate.) The most unique thing about the site above is how it renders 4D Mazes. Therefore a link to it would be more appropriate on the main Maze article, or better yet a more general article about how to render and interect with 4D environments. Thanks, Cruiser1 (talk) 15:26, 15 February 2009 (UTC)

JavaScript version of sample code

Here's a JavaScript version of the example code given in the article. SharkD  Talk  01:11, 7 January 2011 (UTC)

-What algorithm does this code (and the python code in the article) implement? It doesn't appear to be any discussed in the article as far as I can tell? (Joel, 5/15/11)

function maze(width, height)
{
	var complexity = 0.75
	var density = 0.75
	// Only odd shapes, careful x and y are reversed
	var shapey = Math.floor(height/2) * 2 + 1
	var shapex = Math.floor(width/2) * 2 + 1
	// Adjust complexity and density relative to maze size
	complexity = Math.floor(complexity * 5 * (shapey + shapex))
	density    = Math.floor(density * Math.floor(shapey/2) * Math.floor(shapex/2))
	// Build actual maze
	var Z = []
	for (var i = 0; i < shapey; i++)
	{
		Z[i] = []
		for (var j = 0; j < shapex; j++)
		{
			// Fill borders
			if ((i == 0) || (i == (shapey - 1)) || (j == 0) || (j == (shapex - 1)))
				Z[i][j] = 1
			else
				Z[i][j] = 0
		}
	}
	// Make isles
	for (var i = 0; i < density; i++)
	{
		var x = Math.round(Math.random() * Math.floor(shapex/2)) * 2
		var y = Math.round(Math.random() * Math.floor(shapey/2)) * 2
		Z[y][x] = 1
		for (var j = 0; j < complexity; j++)
		{
			var neighbours = []
			if (x > 1)
				neighbours.push([y,x-2])
			if (x < shapex-2)
				neighbours.push([y,x+2])
			if (y > 1)
				neighbours.push([y-2,x])
			if (y < shapey-2)
				neighbours.push([y+2,x])
			if (neighbours.length > 0)
			{
				var y_x_ = neighbours[Math.round(Math.random() * (neighbours.length - 1))]
				var y_ = y_x_[0]
				var x_ = y_x_[1]
				if (Z[y_][x_] == 0)
				{
					Z[y_][x_] = 1
					Z[Math.floor(y_ + (y - y_)/2)][Math.floor(x_ + (x - x_)/2)] = 1
					x = x_
					y = y_
				}
			}
		}
	}
	return Z
}

var my_maze = maze(80,40)
var maze_string = ""
for (var i = 0; i < my_maze.length; i++)
{
	var my_row = my_maze[i]
	for (var j = 0; j < my_row.length; j++)
		maze_string += my_row[j] ? "#" : " "
	maze_string += "\n"
}

// if inside Windows Scripting Host
//WScript.Echo(maze_string)
// if in a Web page
alert(maze_string)

JavaScript code for two of the images in the articles can be found in their descriptions, here and here. SharkD  Talk  09:33, 8 January 2011 (UTC)

Non-cell-based algorithm

I would like to request reinstating the entry that somebody removed on August 30, 2011, as below:

A maze can also be generated without the use of cells. An amorphous maze creates mazes with walls placed at totally random angles. The algorithm is based on extending the wall by a small segment at a time without crossing over a pre-existing one.

The reason given for the deletion was "spam". Therefore, the new entry removes external links, although the original page referenced by the old entry added significant value to the article because the page described in detail the mathematics behind this very unconventional method of generating mazes. In my opinion, not mentioning the very existence of amorphous mazes is tantamount to a loss of knowledge.

Thank you.

Nbeverly (talk) 01:30, 31 August 2011 (UTC) nbeverly

File:MAZE 30x20 DFS.ogv to appear as POTD soon

Hello! This is a note to let the editors of this article know that File:MAZE 30x20 DFS.ogv will be appearing as picture of the day on September 19, 2012. You can view and edit the POTD blurb at Template:POTD/2012-09-19. If this article needs any attention or maintenance, it would be preferable if that could be done before its appearance on the Main Page so Wikipedia doesn't look bad. :) Thanks! —howcheng {chat} 16:53, 17 September 2012 (UTC)

Picture of the day

An animation of creating a maze using a depth-first search maze generation algorithm, one of the simplest ways to generate a maze using a computer. Mazes generated in this manner have a low branching factor and contain many long corridors, which makes it good for generating mazes in video games. In these mazes, it will typically be relatively easy to find the origin point, since most paths lead to or from there, but it is hard to find the way out.Animation: Purpy Pupple

Python Code Example?

Does the section "Python Code Example" really add anything to the article? I can't even tell which algorithm it's attempting to implement. -- 205.175.124.30 (talk) 01:04, 20 September 2012 (UTC)

I just neatened it up, but yeah, its purpose does seem vague. What really should be provided is *pseudocode* (which ironically enough, is what Python should read like, and this example doesn't.) At least then we could decipher its purpose. --Frizzil (talk) 07:34, 21 October 2012 (UTC)

Cellular automata?

Do the the Life-like cellular automata mentioned really count as maze generators? The both seem to create many, small 'mini-mazes' embedded in a larger space. That is, the generated 'passages' are not fully connected, so that it is not always possible to reach all passages from all other passages. I've tried various starting conditions, generation times and the like, but this always seems to be the case. In fact it doesn't seem to make much difference which state (on/off, 0/1, whatever you want to call the cell values) you choose as 'passages' and 'walls'; you get a very similar result.

Rule B3457/S678 (I don't know if it has a name) seems like a better candidate for a maze generator. Though it does generate some open space in the maze (i.e. 'rooms', 'chambers') it also tends to produce mazes that are more nearly fully connected (though there are still some isolated areas generated). Works well from a 50/50 random initial grid in about 20 or so cycles. — Preceding unsigned comment added by 109.156.183.198 (talk) 17:07, 24 May 2013 (UTC)

I noticed that in some tests I did with those rules, thanks for giving me a rule that actually works — Preceding unsigned comment added by 103.238.195.106 (talk) 23:21, 26 August 2020 (UTC)

Recursive backtracker

Could someone explain the need for the last branch of this algorithm?

Special:PermanentLink/596882443#Recursive_backtracker
(version from 24 February 2014)

If I read the (pseudo)code correctly, each point visited gets pushed onto the stack once we leave the position, breaking the wall to some neighbour location. When the path gets stuck in some corner and there's no way to continue, we pop the previous position from the stack and loop back to the first 'if' which tests if the position has any unvisited neighbours, that is if there's a possibility to fork a corridor at that position. If so we start a new branch of the maze pushing the location back onto the stack for the case we will make yet another fork at the same point. So:

every point, once visited, gets stacked, and remains on the stack until there is no possible new path from it.

Is that right?

If so, then there is no 'unvisited cell' to pick when the stack becomes empty. What is the meaning of the last 'else' then?
--CiaPan (talk) 23:32, 11 March 2014 (UTC)

• I am pretty perplexed by this too. Maybe it's there to guard against cosmic rays. Or maybe the region for the maze to be generated on is not connected. dllu (t,c) 02:20, 12 March 2014 (UTC)

Yea, I'd go with the idea of disconnected portions of the maze. This brings up the Q as to why we should bother with that. I can think of two reasons:

1) Just for "completeness".

2) Because they will later be connected, either physically or, perhaps, with a teleporter ?

Of course, you could also consider the disconnected portions each to be a separate maze and run the program on each separately, eliminating the need for that last else. StuRat (talk) 18:59, 15 March 2014 (UTC)

I think we should bother with that for at least one reason: I'm — obviously — at least the 3rd person that gets confused about it. And an encyclopedia shouldn't be confusing. Correct me if I'm wrong.

About 1) how do you complete something that is already complete? Can I complete the product $a\cdot b$ by writing $a\cdot b\cdot 1$ ?

About 2) If there are two different spaces to build a maze you obviously need to build tow mazes and then connect them (or don't — as you like). But what does it have to do with the algorithm itself?

About 3) Just for completeness.

(No offence. I consider it my weakness that I can not make my point without being sarcastic. Sorry about that.) Mofef (talk) 21:18, 14 August 2015 (UTC)

Why is it recursive?

Also, why is this called recursive? As it currently stands this pseudocode is not recursive. 66.225.134.125 (talk) 16:58, 5 September 2017 (UTC)

Based on the date of the above question I suppose it refers to this version Special:PermanentLink/786021378#Recursive_backtracker from 16 June 2017, which indeed included an iterative implementation with an explicit stack only.
I have added an explicit recursive description of the algorithm in this edit Special:Diff/927108903#Recursive_backtracker on 20 November 2019. Hopefully this is clear now why this approach is 'recursive'. --CiaPan (talk) 21:48, 27 August 2020 (UTC)

Hexagon

A hexagonal maze would be nice. 71.46.106.61 (talk) 04:41, 21 March 2015 (UTC)

MAZE 30x20 Prim.ogv doesn't match algorithm described in the text

The article text describes a modified Prim's algorithm in which for each step you "Pick a random wall from the list". But the image "MAZE 30x20 Prim.ogv" demonstrates the classical Prim's algorithm as run against a graph with random edge weights. There is a difference between the two, as the article text acknowledges the difference, saying "classical Prim's on a graph with random edge weights would create mazes stylistically identical to Kruskal's". It seems to me misleading to use in the animated image a stylistically different algorithm from the one laid out in the accompanying text.

Sbj42 (talk) 23:54, 12 October 2016 (UTC)

The Python Code Examples Have Problems

The python code examples should be removed or replaced. The first (depth-first search) example outputs a maze that only works for small sizes, and at large sizes just looks becomes a grid. The second example doesn't name the algorithm and creates a maze with no start or end. ElThomas (talk) 03:46, 4 November 2017 (UTC)

@ElThomas: One of examples has been removed on 7 November 2017 Special:Diff/809224405 and the other one on 29 January 2020 Special:Diff/938094805 (together with a C language example). --CiaPan (talk) 08:14, 16 September 2020 (UTC)

Recursive division method section unsourced

The SVG image File:Chamber-finished.svg in the 'Recursive division method' section (Special:PermanentLink/979701783#Recursive division method) is wrong - it contains an inaccessible, single-cell area in the lower-left corner.

Additionally the whole section is unsourced.

Should it be deleted? --CiaPan (talk) 08:53, 22 September 2020 (UTC)

The entire article is already flagged with "needs additional citations for verification". The recursive division algorithm is mentioned in many sources, such as published book "Mazes for Programmers", so I wouldn't delete the whole section. The only flaw is in the picture "Illustration of Recursive Division" step 5, which indeed has an isolated cell. However that's not necessarily a bug, since recursive division first subdivides the area (see step 2 picture) and then adds doorways within those walls. Perhaps step 5 is really just near the end, before that last doorway is added? Of course, if that's so then step 5 shouldn't be titled "completed". We could fix step 5, or if we really want to remove something, then since there's already an animated GIF illustrating recursive division, we could potentially remove the set of "Illustration of Recursive Division" pictures. Thanks, Cruiser1 (talk) 23:22, 23 September 2020 (UTC)