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)

"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)

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]

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)