Talk:Maze generation algorithm

From Wikipedia, the free encyclopedia

Contents 1 "Depth-first search" versus "Recursive Backtracker" 2 Kruskal's algorithm 3 Depth First = Straight is not quite right 4 Depth First = start location is obvious is not true 5 3D Mazes? 6 Mazes and Knots

[edit] "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)

[edit] 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)

[edit] 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)

[edit] 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]

[edit] 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.

[edit] 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?