CODEWITHSUNDEEP
algorithmrandom
templatetypedef
templatetypedef

Reputation: 373022

Why do these maze generation algorithms produce mazes with different properties?

I was browsing the Wikipedia entry on maze generation algorithms and found that the article strongly insinuated that different maze generation algorithms (randomized depth-first search, randomized Kruskal's, etc.) produce mazes with different characteristics. This seems to suggest that the algorithms produce random mazes with different probability distributions over the set of all single-solution mazes (spanning trees on a rectangular grid).

My questions are:

  1. Is this correct? That is, am I reading this article correctly, and is the article correct?
  2. If so, why? I don't see an intuitive reason why the different algorithms would produce different distributions.

Upvotes: 6

Views: 1933

Answers (4)

Antti Huima
Antti Huima

Reputation: 25542

Uh well I think it's pretty obvious different algorithms generate different mazes. Let's just talk about spanning trees of a grid. Suppose you have a grid G and you have two algorithms to generate a spanning tree for the grid:

Algorithm A:

  1. Pick any edge of the grid, with 99% probability choose a horizontal one, otherwise a vertical one
  2. Add the edge to the maze, unless adding it would create a cycle
  3. Stop when every vertex is connected to every other vertex (spanning tree complete)

Algorithm B:

  1. As algorithm A, but set the probability to 1% instead of 99%

"Obviously" algorithm A produces mazes with lots of horizontal passages and algorithm B mazes with lots of vertical passages. That is, there is a statistical correlation between the number of horizontal passages in a maze and the maze being produced by algorithm A.

Of course the differences between the Wikipedia algorithms are more intricate but the principle is the same. The algorithms sample the space of possible mazes for a given grid in a non-uniform, structured way.

LOL I remember a scientific conference where a researcher presented her results about her algorithm that did something "for graphs". The results were statistical and presented for "random graphs". Someone asked from the audience "which distribution of random graphs did you draw the graphs from?" The answer: "uh... they were produced by our graph generation program". Duh!

Upvotes: 6

dfb
dfb

Reputation: 13289

Interesting question. Here my random 2c.

Comparing Prim's to, say, DFS, the latter seems to have a proclivity for producing deeper trees simply due to the fact that the first 'runs' have more space to create deep trees with less branches. Prim's algorithm, on the other hand, appears to create trees with more branching due to the fact that any open branch can be selected at each iteration.

One way to ask this would be to look at what is the probability that each algorithm will produce a tree of depth > N. I have a hunch that they would be different. A more formal approach to do proving this might be to assign some weights to each part of the tree and show it's more likely to be taken or attempt to characterize the space some other way, but I'll be hand wavy and guessing it's correct :). I'm interested in what lead to you think it wouldn't be, because my intuition was the opposite. And no, the Wiki article doesn't give a convincing argument.

EDIT

One simple way to see this to consider an initial tree with two children with a total of k nodes e.g.,

*---* ... *
 \--* ... *

Choose a random node as the start and end. DFS will produce one of two mazes, either the entire tree, or the part of it with the direct path from start to end. Prim's algorithm will produce the 'maze' with the direct path from start to end with secondary paths of length 1 ... k.

Upvotes: 1

Apalala
Apalala

Reputation: 9244

It is not statistical until you request that each algorithm produce every solution it can.

What you are perceiving as statistical bias is only a bias towards the preferred, first solution.

That bias may not be algorithmic (set-theory-wise) but implementation dependent (like the bias in the choice of the pivot in quicksort).

Upvotes: 0

Rasika
Rasika

Reputation: 1998

Yes, it is correct. You can produce different mazes by starting the process in different ways. Some algorithms start with a fully closed grid and remove walls to generate a path through the maze while some start with a empty grid and add walls leaving behind a path. This alone can produce different results.

Upvotes: -1

Related Questions