Graph Theory Based Methods
A maze can be generated by starting with a predetermined arrangement of cells (most commonly a rectangular grid but other arrangements are possible) with wall sites between them. This predetermined arrangement can be considered as a connected graph with the edges representing possible wall sites and the nodes representing cells. The purpose of the maze generation algorithm can then be considered to be making a subgraph where it is challenging to find a route between two particular nodes.
If the subgraph is not connected, then there are regions of the graph that are wasted because they do not contribute to the search space. If the graph contains loops, then there may be multiple paths between the chosen nodes. Because of this, maze generation is often approached as generating a random spanning tree. Loops which can confound naive maze solvers may be introduced by adding random edges to the result during the course of the algorithm.
Read more about this topic: Maze Generation Algorithm
Famous quotes containing the words graph, theory, based and/or methods:
“In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.”
—W.N.P. Barbellion (1889–1919)
“Frankly, these days, without a theory to go with it, I can’t see a painting.”
—Tom Wolfe (b. 1931)
“Both magic and religion are based strictly on mythological tradition, and they also both exist in the atmosphere of the miraculous, in a constant revelation of their wonder-working power. They both are surrounded by taboos and observances which mark off their acts from those of the profane world.”
—Bronislaw Malinowski (1884–1942)
“We can best help you to prevent war not by repeating your words and following your methods but by finding new words and creating new methods.”
—Virginia Woolf (1882–1941)