|
|
|
|
Maze
|
| |
|
| |
A maze is a complex tour puzzle in the form of a complex branching passage through which the solver must find a route. In everyday speech, both maze and labyrinth denote a complex and confusing series of pathways, but technically the maze is distinguished from the labyrinth. The labyrinth has a single through-route with twists and turns but without branches; it is not designed to be as difficult to navigate as a maze is.
Discussion
Ask a question about 'Maze' Start a new discussion about 'Maze' Answer questions from other users |
Encyclopedia
A maze is a complex tour puzzle in the form of a complex branching passage through which the solver must find a route. In everyday speech, both maze and labyrinth denote a complex and confusing series of pathways, but technically the maze is distinguished from the labyrinth. The labyrinth has a single through-route with twists and turns but without branches; it is not designed to be as difficult to navigate as a maze is. The pathways and walls in a maze or labyrinth are fixed (pre-determined). Maze-type puzzles where the given walls and paths may change during the game are covered under the main puzzle category of tour puzzles. The Cretan maze is the oldest.
Maze construction
Mazes have been built with walls and rooms, with hedges, turf, corn stocks, hay bales, books or with paving stones of contrasting colors or designs, or in fields of crops such as corn or, indeed, maize. Maize mazes can be very large; they are usually only kept for one growing season, so they can be different every year, and are promoted as seasonal tourist attractions. Indoors, Mirror Mazes are another form of maze, where many of the apparent pathways are imaginary routes seen through multiple reflections in mirrors. Another type of maze consists of a set of rooms linked by doors (so a passageway is just another room in this definition). Players enter at one spot, and exit at another, or the idea may be to reach a certain spot in the maze. Mazes can also be printed or drawn on paper to be followed by a pencil or fingertip. One of the short stories of Jorge Luis Borges featured a book, called The Garden of Forking Paths, that was a literary maze. Various maze generation algorithms exist for building mazes, either by hand or by computer.
Generating mazes
There are many different approaches to automate the generation of mazes.
Stack-based approach
The stack-based approach is one of the simplest ways to generate a maze using a computer. Consider the space for a maze being a large grid of cells (like a large chess board), each cell starting with four walls. Starting from a random cell, the computer then selects a random neighbouring cell that has not yet been visited. The computer removes the 'wall' between the two cells and adds the new cell to a stack (this is analogous to drawing the line on the floor). The computer continues this process, with a cell that has no unvisited neighbours being considered a dead-end. When at a dead-end it backtracks through the path until it reaches a cell with an unvisited neighbour, continuing the path generation by visiting this new, unvisited cell (creating a new junction). This process continues until every cell has been visited, causing the computer to backtrack all the way back to the beginning cell. This approach guarantees that the maze space is completely visited.
As stated, the algorithm is very simple and does not produce overly-complex mazes. More specific refinements to the algorithm can help to generate mazes that are harder to solve.
Solving mazes
The mathematician Leonhard Euler was one of the first to analyze plane mazes mathematically, and in doing so made the first significant contributions to the branch of mathematics known as topology.
Mazes containing no loops are known as "standard", or "perfect" mazes, and are equivalent to a tree in graph theory. Thus many maze solving algorithms are closely related to graph theory. Intuitively, if one pulled and stretched out the paths in the maze in the proper way, the result could be made to resemble a tree .
A few important maze solving algorithms are explained below. The random mouse, wall follower, pledge, and Tremaux algorithms are designed to be used inside the maze by a traveler with no prior knowledge of the maze, whereas the dead-end filling algorithm is designed to be used by a person or computer program that can see the whole maze at once.
Random mouse algorithm
This is a trivial method that can be implemented by a very unintelligent robot or perhaps a mouse. It is simply to proceed in a straight line until an obstruction is reached, and then to make a random decision about the next direction to follow.
Wall follower
The wall follower, the best-known rule for traversing mazes, is also known as either the left-hand rule or the right-hand rule. If the maze is simply connected, that is, all its walls are connected together or to the maze's outer boundary, then by keeping one hand in contact with one wall of the maze the player is guaranteed not to get lost and will reach a different exit if there is one; otherwise, he or she will return to the entrance. This strategy works best when implemented immediately upon entering the maze.
Another perspective into why wall following works is topological. If the walls are connected, then they may be deformed into a loop or circle . Then wall following reduces to walking around a circle from start to finish.
If the maze is not simply connected (i.e. if the start or endpoints are in the center of the structure or the pathways cross over and under each other), this method will not be guaranteed to help the goal to be reached.
Wall-following can be done in 3D or higher dimensional mazes if its higher dimensional passages can be projected onto the 2D plane in a deterministic manner. For example, if in a 3D maze "up" passages can be assumed to lead northwest, and "down" passages can be assumed to lead southeast, then standard wall following rules can then be applied. However, unlike in 2D, this requires that the current orientation be known, to determine which direction is the first on the left or right.
Pledge algorithm
Disjoint mazes can still be solved with the wall follower method, if the entrance and exit to the maze are on the outer walls of the maze. If however, the solver starts inside the maze, it might be on a section disjoint from the exit, and wall followers will continually go around their ring. The Pledge algorithm (named after Jon Pledge of Exeter) can solve this problem (see "Turtle Geometry: the computer as a medium for exploring mathematics", Abelson & diSessa, 1980).
The Pledge algorithm, designed to circumvent obstacles, requires an arbitrarily chosen direction to go toward. When an obstacle is met, one hand (say the right hand) is kept along the obstacle while the angles turned are counted. When the solver is facing the original direction again, and the angular sum of the turns made is 0, the solver leaves the obstacle and continues moving in its original direction.
Note that the use of "total turning" rather than just the "current direction" allows the algorithm to avoid traps shaped like an upper case "G". If one proceeds left into the trap, one gets turned around a full 360 degrees by the walls. A naive "current direction" algorithm gets into a limit cycle as it leaves the lower rightmost wall heading left and runs into the curved section on the left again. The Pledge algorithm does not leave the rightmost wall due to the total turning not being zero at that point. It follows the wall all the way around, finally leaving it heading left on the bottom outside.
This algorithm allows a person with a compass to find his way from any point inside to an outer exit of any finite and fair two-dimensional maze, regardless of the initial position of the solver. However, this algorithm will not work in doing the reverse, namely finding the way from an entrance on the outside of a maze to some end goal within it.
Tremaux's algorithm
Tremaux's algorithm is an efficient method to find the way out of a maze that requires drawing a line on the floor to mark a path, and is guaranteed to work for all mazes that have well-defined passages. On arriving at a junction, pick a direction and mark it and the direction you came from. When arriving at a marked junction pick an unmarked passage if possible. If it is not possible to pick an unmarked passage take a marked one, marking it again (you can pick the path you came from). Never pick a twice marked path, where you will never need to take any passage more than twice. If there is no exit, this method will take you back to the start.
Dead-end filling
Dead-end filling is an algorithm for solving mazes that looks at the entire maze at once. It can be used for solving mazes on paper or with a computer program, but it is not useful to a person inside an unknown maze. The method is to 1) find all of the dead-ends in the maze, and then 2) "fill in" the path from each dead-end until the first junction met. A video of dead-end filling in action can be seen here: .
Dead-end filling cannot accidentally "cut off" the start from the finish since each step of the process preserves the topology of the maze. Furthermore, the process won't stop "too soon" since the end result cannot contain any dead-ends. Thus if dead-end filling is done on a perfect maze (maze with no loops), then only the solution will remain. If it is done on a partially braid maze (maze with some loops), then every possible solution will remain but nothing more.
Mazes in psychology experiments
Mazes are often used in psychology experiments to study spatial navigation and learning. Such experiments typically use rats or mice. Examples are
Mazes in computer games
Mazes have long been a staple element in video games (e.g. the 80's classic Maziacs). In some games the entire objective of the game is to navigate mazes, while in other games the mazes are incorporated as only one element of the gameplay.
Other types of maze
Logic mazes
- See Logic maze. These are like standard mazes except they use rules other than "don't cross the lines" to restrict motion.
Mazes in higher dimensions: It is possible for a maze to have three or more dimensions. A maze with bridges is three dimensional, and some natural cave systems are three dimensional mazes. The computer game Descent utilized fully three dimensional mazes. Any maze can be topologically mapped onto a three-dimensional maze.
Picture maze: See Picture maze. A maze that forms a picture when solved.
Dead end maze: A maze game where the route creates the dead ends.
Turf mazes and Mizmazes: A pattern like a long rope folded up, without any junctions or crossings.
Loops and Traps Maze: A maze that features one-way doors. The doors can lead to the correct path or create traps that divert you from the correct path and lead you to the starting point. You may not return through a door which you have entered. The path is a series of loops interrupted by doors. The maze is not created with dead ends, but dead ends are created by doors that only open from the other side. The Halloween Maze in Ridgewood NJ is an example of this type of maze. Through the use of reciprocal doors, the correct path can intersect the incorrect path on a single plane.
Publications about mazes
Numerous mazes of different kinds have been drawn, painted, published in books and periodicals, used in advertising, in software, and sold as art. In the 1970s there occurred a publishing "maze craze" in which numerous books, and some magazines, were commercially available in nationwide outlets and devoted exclusively to mazes of a complexity that was able to challenge adults as well as children (for whom simple maze puzzles have long been provided both before, during, and since the 1970s "craze").
Some of the best-selling books in the 1970s and early 1980s included those produced by Vladimir Koziakin, Rick and Glory Brightfield, Dave Phillips, Larry Evans, and Greg Bright. Koziakin's works were predominantly of the standard two-dimensional "trace a line between the walls" variety. The works of the Brightfields had a similar two-dimensional form but used a variety of graphics-oriented "path obscuring" techniques - although the routing was comparable to or simpler than Koziakin's mazes, the Brightfield's mazes did not allow the various pathway options to be discerned so easily by the roving eye as it glanced about.
Greg Bright's works went beyond the standard published forms of the time by including "weave" mazes in which illustrated pathways can cross over and under each other. Bright's works also offered examples of extremely complex patterns of routing and optical illusions for the solver to work through. What Bright termed "mutually accessible centers" (The Great Maze Book, 1973) also called "braid" mazes, allowed a proliferation of paths flowing in spiral patterns from a central nexus and, rather than relying on "dead ends" to hinder progress, instead relied on an overabundance of pathway choices. Rather than have a single solution to the maze, Bright's routing often offered multiple equally valid routes from start to finish, with no loss of complexity or diminishment of solver difficulties because the result was that it became difficult for a solver to definitively "rule out" a particular pathway as unproductive. Some of Bright's innovative mazes had no "dead ends" - although some clearly had looping sections (or "islands") that would cause careless explorers to keep looping back again and again to pathways they had already travelled.
The books of Larry Evans focused on 3-D structures, often with realistic perspective and architectural themes, and Bernard Meyers (Supermazes No. 1) produced similar illustrations. Both Greg Bright (The Hole Maze Book) and Dave Phillips (The World's Most Difficult Maze) published maze books in which the sides of pages could be crossed over and in which holes could allow the pathways to cross from one page to another, and one side of a page to the other, thus enhancing the 3-D routing capacity of 2-D printed illustrations.
Adrian Fisher is both the most prolific contemporary author on mazes, and also one of the leading maze designers. His book The Amazing Book of Mazes (2006) contains examples and photographs of numerous methods of maze construction, several of which have been pioneered by Fisher; The Art of the Maze (Weidenfeld and Nicholson, 1990) contains a substantial history of the subject, whilst Mazes and Labyrinths (Shire Publications, 2004) is a useful introduction to the subject.
A recent book by Galen Wadzinski (The Ultimate Maze Book) offers formalized rules for more recent innovations that involve single-directional pathways, 3-D simulating illustrations, "key" and "ordered stop" mazes in which items must be collected or visited in particular orders to add to the difficulties of routing (such restrictions on pathway traveling and re-use are important in a printed book in which the limited amount of space on a printed page would otherwise place clear limits on the amount of choices and pathways that can be contained within a single maze). Although these innovations are not all entirely new with Wadzinski, the book marks a significant advancement in published maze puzzles, offering expansions on the traditional puzzles that seem to have been fully informed by various video game innovations and designs, and adds new levels of challenge and complexity in both the design and the goals offered to the puzzle-solver in a printed format.
Mazes open to the public
Africa
- Serendipity Maze, Mouille Point, Cape Town, South Africa. Hedge maze by the sea.
- , Robertson, Western Cape, South Africa. 13870 m² net area
Asia
- Gardens Shopping Mall, Dubai (World's Largest Indoor Maze )
- , Masuda, Shimane, Japan
- , Kiso, Nagano, Japan
- , Nikko, Tochigi, Japan
- , Sendai, Miyagi, Japan
- , Shirahama, Wakayama, Japan
Australia
Europe
Austria:
- Schönbrunn Palace, Austria (small entrance fee, tower at the center to overlook the hedge maze)
Germany:
- Altjeßnitz, Germany, Sachsen-Anhalt, near Dessau (hedge maze, c.1750)
- Aschaffenburg (Park Schönbusch), Germany, Bavaria (hedge maze, c.1829)
- Berlin (Erholungspark Marzahn), Germany (hedge maze)
- , Bad Salzuflen, Germany, North-Rhine-Westphalia (hedge maze)
Italy:
Spain:
- Amaze'n Laberintos, Spain, Majorca, Alcudia, Playa de Muro (wooden maze, 1998)
- Parc del Laberint d'Horta, Barcelona, Spain (hedge maze)
- Laberinto del Camino de Santiago - España.
Scandinavia:
UK:
- Alnwick Castle Water Gardens Bamboo Maze, Northumberland. Designed by Adrian Fisher
- Blackpool Pleasure Beach Hedge Maze, Lancashire, England. Designed by Adrian Fisher
- Blake House Craft Centre, Braintree, Essex, England (Open July-Sept)
- Blenheim Palace Hedge Maze, Oxfordshire, England. Designed by Minotaur Designs, Adrian Fisher, Randoll Coate and Graham Burgess., 1991
- St Catherines Hill old miz-maze, Winchester.
- Castlewellan, Northern Ireland, world's largest permanent hedge maze
- Chatsworth House, England (hedge maze)
- The Crystal Palace, England. A hedge maze built into a copse
- Greys Court 'Archbishop's Maze', Oxfordshire, England. Designed by Adrian Fisher, 1981
- Hampton Court Palace, England (hedge maze)
- Hoo Hill Maze, Shefford, Bedfordshire, England
- Kentwell Hall, Long Melford, Suffolk, England. Designed Minotaur designs, Adrian Fisher, Randoll Coate and Graham Burgess.
- Leeds Castle, Maidstone, Kent, England. Designed by Minotaur Designs Randoll Caote , Adrian Fisher and Graham Burgess.
- Longleat, Wiltshire, England: hedge maze, designed by Greg Bright, 1978, and mirror maze, designed by Adrian Fisher; Labyrinth of Love, Renaissance style Rose garden labyrinth designed by Graham Burgess. Sun and Moon Maze designed by Randoll Coate.*
- Murray Star Maze, Scone Palace, Perth, Scotland (hedge maze). Designed by Adrian Fisher
- Noah's Ark Zoo Farm, Bristol, England (longest hedge maze in the world, planted 2003)
- Paulton's Park, Hampshire, England (hedge maze)
- Richings Park Amazing Maize Maze, Richings Park, near Heathrow, England (Open July-Sept)
- Saffron Walden, Essex, England (hedge maze) (The town also has an historic turf maze)
- Symonds Yat, Herefordshire, England
- Worden Park, Leyland, Lancashire, England
North America
- , Navy Pier, Chicago, Illinois, USA. Designed by Jack Rouse Associates and Adrian Fisher
- America's Largest Corn Maze Shakopee, Minnesota, USA
- Children's maze (made out of packs of hay), Ashland Berry Farm, Ashland, Virginia, USA.
- Davis' Mega Maze, Sterling, Massachusetts USA (3-D adventure corn maze). Designed by Adrian Fisher
- Dole Plantation, Wahiawa, Hawaii, home to the World's Largest Maze.
- Labyrinthe du Hangar 16, Montreal, Canada.
- Magnolia Plantation and Gardens (Charleston, South Carolina), USA
- is the "Largest Collection of People-Sized Mazes in the World" with mazes made of Fence, Rope, Stone, Turf, Corn, Invisible Dog Fencing, Straw Bales, Tiles, Living Bamboo, and Earthen Mounds. New Park, Pennsylvania, USA
- Mall of Georgia Paving Mazes, Atlanta, Georgia, USA. Designed by Adrian Fisher
- , Garden City, South Carolina USA (Interchangeable fence Maze appropriate for children and adults)
- Mohonk Mountain House hedge maze, New Paltz, New York
- Mystery Maze, Wild Adventures theme park, Valdosta, Georgia - manufactured by Amazin' Mazes
- Noah's Ark Water Park Mirror Maze, Wisconsin Dells, USA. Designed by Adrian Fisher
- Norton Museum of Art West Palm Beach, USA. Pavement Maze, Serpent Mound and Turf Labyrinth. Designed by Adrian Fisher.
- Ridgewood Halloween Maze, Ridgewood, New Jersey, USA (Month of October, Loops and Traps halloween themed maze. Designed by Tyler Stewart.) Free attraction.
- Saunders Farm, Ottawa, Ontario, Canada. The largest collection of full-sized hedge mazes and labrynths in North America (11).
- Skyline Caverns Mirror Maze, Front Royal, Virginia, USA. Designed by Adrian Fisher.
- The Maze at the Governor's Palace, Colonial Williamsburg, Virginia, USA
- The Maze on Centre Island, Toronto, Ontario, was a Centennial gift to the city by its Dutch-Canadian community in 1967 (Topiary maze, open to public, free, year-round)
- Trail of Terror, Minneapolis, Minnesota, USA (Annual event, 3/4 mile indoor Halloween themed maze)
Further reading
- H. Abelson and A. diSessa, Turtle Geometry: The Computer as a Medium for Exploring Mathematics, MIT Press (1980)
- Adrian Fisher, The Amazing Book of Mazes, Thames & Hudson, London / Harry N Abrams Inc, New York (2006) ISBN 978-0500512470
- Adrian Fisher, Armchair Puzzlers: Mad Mazes, University Books, San Francisco, USA (2005) ISBN 978-1575289786
- Adrian Fisher, Mazes and Follies, Jarrold Publishing, UK (2004) ISBN 978-1841651422
- Adrian Fisher, Mazes and Labyrinths, Shire Publications, UK (2003) ISBN 978-0747805618
- Adrian Fisher and Howard Loxton, Secrets of the Maze, Thames & Hudson, London (1997) / Barron’s Educational Series Inc, New York (1998) ISBN 978-0500018118
- Adrian Fisher and Jeff Saward, The British Maze Guide, Minotaur Designs, St Albans, UK (1991) - the definitive guide to British Mazes
- Adrian Fisher and Georg Gerster, The Art of the Maze, Weidenfeld & Nicolson, London (1990) ISBN 0-297-83027-9
- Adrian Fisher and Georg Gerster, Labyrinth - Solving the Riddle of the Maze, Harmony Books USA, New York (1990) ISBN 978-0517580998
- (1927). Includes Dover Publications (1970) ISBN 0-486-22614-X
- Jeff Saward, Magical Paths, Mitchell Beazley (2002) ISBN 1-84000-573-4
See also
External links
- on Silent animation's site (eng.)
- CNN's Barry Neild offers escape routes
- Directory of hundreds of mazes in the USA and Canada
- Real mazes that look like an inkblot portrait
-
- Jeff Saward's website
-
- online version of W.H. Matthew's classic book
- This site explains the different types of mazes and how to generate and solve them
- Flash-based free maze game in 2D
- John McIntosh's Java-based free maze game in 3D and 4D first-perspective
-
- Maze Artist, Yonatan Frimer's page of image mazes that mix art and mazes.
|
| |
|
|
