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)
“We have our little theory on all human and divine things. Poetry, the workings of genius itself, which, in all times, with one or another meaning, has been called Inspiration, and held to be mysterious and inscrutable, is no longer without its scientific exposition. The building of the lofty rhyme is like any other masonry or bricklaying: we have theories of its rise, height, decline and fall—which latter, it would seem, is now near, among all people.”
—Thomas Carlyle (1795–1881)
“Foster the labor of our country by an undeviating metallic currency ... always recollecting that if labor is depressed neither commerce nor manufactures can flourish, as they are both based upon the production of labor, produced from the earth, or the mineral world.”
—Andrew Jackson (1767–1845)
“It would be some advantage to live a primitive and frontier life, though in the midst of an outward civilization, if only to learn what are the gross necessaries of life and what methods have been taken to obtain them.”
—Henry David Thoreau (1817–1862)