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)
“Lucretius
Sings his great theory of natural origins and of wise conduct; Plato
smiling carves dreams, bright cells
Of incorruptible wax to hive the Greek honey.”
—Robinson Jeffers (1887–1962)
“I have no acting technique.... I act instinctively. That’s why I can’t play any role that isn’t based on something in my life.”
—Ethel Waters (1900–1977)
“How can you tell if you discipline effectively? Ask yourself if your disciplinary methods generally produce lasting results in a manner you find acceptable. Whether your philosophy is democratic or autocratic, whatever techniques you use—reasoning, a “star” chart, time-outs, or spanking—if it doesn’t work, it’s not effective.”
—Stanley Turecki (20th century)