Wikipedia

Wikipedia:Featured picture candidates/Maze Generation 2

< Wikipedia:Featured picture candidates

Animations of maze generation.

edit

Voting period is over. Please don't add any new votes. Voting period ends on 15 Feb 2011 at 02:07:16 (UTC)

Original - The generation of a maze using randomized depth-first search. Starting from the seed cell (in this case the bottom left), the algorithm selects a random unvisited neighbour and marks that as visited and destroys the wall between. The process repeats from that new cell. If all the neighbours are already visited, the algorithm backtracks to the last cell that has unvisited neighbours and proceeds therefrom. Upon backtracking to the seed cell, all the cells have been visited and the maze is complete.
Original - The generation of a maze using randomized Prim's algorithm. Starting from the seed cell (in this case the bottom left), the algorithm selects a random unvisited neighbour and marks that as visited and destroys the wall between. Then the algorithm selects a random visited cell with unvisited neighbours and repeats the process. When all the cells have been visited, the maze is complete.
Reason
Extremely strong encyclopedic value in clearly illustrating maze generation with two very different algorithms. Adds significantly to the maze generation article.
Articles in which this image appears
Maze generation algorithm, Prim's algorithm, Depth-first search.
FP category for this image
Wikipedia:Featured pictures/Sciences/Mathematics
Creator
Purpy Pupple
  • Still too big. Remember, there are people out there with poor eyesight and low resolution monitors. The cells of the maze should be larger and the maze should be smaller. I suggested 4×4 before, and I still think that's a good idea. (Remember, the animation is supposed to be instructive, not generate a good maze.)
  • Still too fast. Someone who doesn't know what's already happening will have trouble keeping up with the algorithm's progress. The animation should go slowly enough that each step of the algorithm is visible. Each algorithm performs several actions to add one cell to the maze: They have a list of possible starting points, they pick one, and then they add it. These steps should be clear to the viewer. (I see that your code doesn't currently make this easy, but I think this is very important.)
  • Both algorithms are graph algorithms, but neither of the animations makes this clear. The animation should display the underlying graph somehow. I still think that the scheme I proposed at your previous FP nomination is a good idea: Show all graph vertices in dark red; highlight the ones that can be added at the current step; add a special highlight to the one that will be added; then add it to the maze; and repeat. Since the depth-first search algorithm maintains a stack of all visited vertices it should include a special color for vertices currently on the stack but not currently reachable. (Again, I realize that your implementation doesn't do this, but you are trying to make an instructive animation here.)
I realize that I'm asking you to make pretty big changes to your code and that it would be somewhat painful to do in C. You might have an easier time in C++ (where you could use STL containers) or in a higher-level language (like Matlab or Python). Ozob (talk) 12:00, 7 February 2011 (UTC)[reply]
  • Thank you for your suggestions. However, an extremely small maze like a 4x4 one may not convey the macroscopic properties of the two algorithms as well. For instance, in the present videos, it is clear that the maze generated using the Prim's algorithm variant has a far larger branching factor compared with the DFS one; whereas the DFS one is characterized with long corridors and low branching factor. Also, I do not consider it necessary to show the graph of the maze separately. The maze itself is the graph and looking at the maze suffices to observe the graph. In the DFS algorithm, the viewer should clearly notice the similarity to a two-dimensional random walk. Maybe the animations can be improved by actually showing the red cursor "backtracking" for the DFS animation, and maybe the "frontier" cells in the Prim animation should be highlighted. Purpy Pupple (talk) 12:36, 7 February 2011 (UTC)[reply]
  • Besides, regarding the argument about people with poor eyesight and low-resolution screens, it would seem to me that in the present placement in the articles, each maze cell is the same size as a character in the surrounding text. If one cannot clearly see the maze, then surely he cannot read the text either, in which case he should not be reading Wikipedia. Purpy Pupple (talk) 12:40, 7 February 2011 (UTC)[reply]
I mostly still disagree:
  • The difference between the mazes generated by the two algorithms is visible even at smaller maze sizes. Maybe 4×4 is too small to make the difference clear, but 8×8 isn't. (Plus, making the animation shorter makes the file smaller. It's an acceptable size already, but making it smaller would be a nice bonus.)
  • I still think that showing the graph is vital. The algorithms are just as applicable to graphs which aren't lattices; you can use them to build a hexagonal maze or a three dimensional maze or a maze inside a complete bipartite graph or anything you like without changing the algorithm at all. If you code it right you won't even have to change your code, just the input you give it. In fact, any algorithm that generates spanning trees will generate mazes; the difference you noted above about the shape of the resulting mazes reflects the fact that they do not give the same probability distribution on the space of spanning trees (and in particular they do not generate uniform spanning trees).
  • Regarding size, I know several people with poor eyesight. It's easy to get a browser to display text in a bigger font—I do this myself on Wikipedia even though my eyes are fine because I think Wikipedia's default font is too small. It's harder to increase the size of a picture because that can't be controlled using CSS. The pictures would be more accessible if the cells were larger.
  • I agree on the backtracking and frontier ideas.
Ozob (talk) 02:56, 8 February 2011 (UTC)[reply]

Promoted File:MAZE 30x20 DFS.ogv --Makeemlighter (talk) 03:02, 15 February 2011 (UTC) Promoted File:MAZE 30x20 Prim.ogv --Makeemlighter (talk) 03:02, 15 February 2011 (UTC)[reply]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Wikipedia:Featured_picture_candidates/Maze_Generation_2&oldid=413998995"