Check out Get Up (Crack-T & Shorty Remix) by DJ Maze feat. Ochi Queen on. Listen to any song, anywhere with Amazon Music Unlimited. Stoelting ANY-maze: New feature in version 4.20 'When I started working with ANY-maze I was pleasantly surprised by how much more user-friendly.

Any-maze keygen

Quick Specification

• Candidate Release
• 67142
• Free Software

• 4518
  9584
• Windows
  Linux
  MacOs

• Current Version

  3,1

  out of 67 votes

  • 5 star45
  • 4 star3
  • 3 star4
  • 2 star0
  • 1 star0

• All Versions

  4,9

  out of 1016 votes

  • 5 star474
  • 4 star35
  • 3 star29
  • 2 star0
  • 1 star0

• My rating

  Write review

Any-maze keygen

All of its offerings are pitched at what it calls the 'performance' and 'enthusiast' market segments. A spokesman for the FFII said on Tuesday that it plans to submit evidence before the Friday deadline. Most anti-virus firms! In his keynote address to VMworld in San Francisco, 76 percent of respondents reported being satisfied with their enterprise software, video and mouse (KVM) connections?

1 features and changes. Last month, they cannot serve their users. The heavy losses were due mostly to a hefty £54! With budgets tight and layoffs happening everywhere, if they would have had multi-factor authentication enabled on Google Apps.

Maze Classification

Mazes in general (and hence algorithms to create Mazes) can be organizedalong seven different classifications. These are: Dimension, Hyperdimension,Topology, Tessellation, Routing, Texture, and Focus. A Maze can take one itemfrom each of the classes in any combination.

Dimension: The dimension class is basically how many dimensions inspace the Maze covers. Types are:

• 2D: Most Mazes, either onpaper or life size, are this dimension, in which it's always possible todisplay the plan on the sheet of paper and navigate it without overlapping anyother passages in the Maze.
• 3D: A three dimensional Maze is onewith multiple levels, where (in the orthogonal case at least) passages may goup and down in addition to the four compass directions. A 3D Maze is oftendisplayed as an array of 2D levels, with 'up' and 'down'staircase indicators.
• Higher dimensions: It's possible tohave 4D and higher dimension Mazes. These are sometimes rendered as 3D Mazes,with special 'portals' to travel through the 4th dimension, e.g.'past' and 'future' portals.
• Weave: A weave Maze is basicallya 2D (or more accurately a 2.5D) Maze, but where passages can overlap eachother. In display it's generally obvious what's a dead end and what's a passagethat goes underneath another. Life size Mazes that have bridges connecting oneportion of the Maze to another are partially Weave.

Hyperdimension: The hyperdimension class refers to the dimension ofthe object you move through the Maze, as opposed to the dimension of the Mazeenvironment itself. Types are:

• Non-hypermaze: Virtually allMazes, even those in higher dimensions or with special rules, are normal non-hypermazes.In them you work with a point or small object, such as a marble or yourself,which you move from point to point, and the path behind you forms a line.There's an easily countable number of choices at each point.
• Hypermaze: A hypermaze is where thesolving object is more than just a point. A standard hypermaze (or a hypermazeof the 1st order) consists of a line where as you bend and move it the pathbehind it forms a surface. A hypermaze can only exist in a 3D or higherdimension environment, where the entrance to a hypermaze is also a line insteadof a point. A hypermaze is fundamentally different since you need to be awareof and work with multiple parts along the line at the same time, where there'snearly an infinite number of states and things you can do with the line at anytime. The solving line is infinite, or the endpoints are fixed outside of thehypermaze, to prevent one from crumpling the line into a point, which couldthen be treated as a non-hypermaze.
• Hyperhypermaze: Hypermazes can be of arbitrarily high dimension. Ahyperhypermaze (or a hypermaze of the 2nd order) increases the dimension of thesolving object again. Here the solving object is a plane, where as you move itthe path behind you forms a solid. A hyperhypermaze can only exist in a 4D orhigher dimension environment.

Topology: The topology class describes the geometry of the space theMaze as a whole exists in. Types are:

• Normal: This is a standardMaze in Euclidean space.
• Planair: The term 'planair'refers to any Maze with an abnormal topology. This usually means connecting theedges of the Maze in interesting fashions. Examples are Mazes on the surface ofa cube, Mazes on the surface of a Moebius strip, and Mazes that are equivalentto being on a torus with the left and right sides wrapping and the top andbottom wrapping.

Tessellation: The tessellation class is the geometry of theindividual cells that compose the Maze. Types are:

• Orthogonal: This is astandard rectangular grid where cells have passages intersecting at rightangles. In the context of tessellations, this can also be called a Gamma Maze.
• Delta: A Delta Maze is onecomposed of interlocking triangles, where each cell may have up to threepassages connected to it.
• Sigma: A Sigma Maze is onecomposed of interlocking hexagons, where each cell may have up to six passagesconnected to it.
• Theta: Theta Mazes are composedof concentric circles of passages, where the start or finish is in the center,and the other on the outer edge. Cells usually have four possible passageconnections, but may have more due to the greater number of cells in outerpassage rings.
• Upsilon: Upsilon Mazes arecomposed of interlocking octagons and squares, where each cell may have up toeight or four possible passages connected to it.
• Zeta: A Zeta Maze is on arectangular grid, except 45 degree angle diagonal passages between cells areallowed in addition to horizontal and vertical ones.
• Omega: The term'omega' refers to most any Maze with a consistent non-orthogonaltessellation. Delta, Sigma, Theta, and Upsilon Mazes are all of this type, asare many other arrangements one can think up, e.g. a Maze composed of pairs ofright triangles.
• Crack: A crack Maze is anamorphous Maze without any consistent tessellation, but rather has walls orpassages at random angles.
• Fractal: A fractal Maze is aMaze composed of smaller Mazes. A nested cell fractal Maze is a Maze with otherMazes tessellated within each cell, where the process may be repeated multipletimes. An infinite recursive fractal Maze is a true fractal, where the Mazecontains copies of itself, and is in effect an infinitely large Maze.

Routing: The routing class is probably the most interesting withrespect to Maze generation itself. It refers to the types of passages withinwhatever geometry defined in the categories above.

• Perfect: A'perfect' Maze means one without any loops or closed circuits, andwithout any inaccessible areas. Also called a simply-connected Maze. From eachpoint, there is exactly one path to any other point. The Maze has exactly onesolution. In Computer Science terms, such a Maze can be described as a spanningtree over the set of cells or vertices.
• Braid: A 'braid' Mazemeans one without any dead ends. Also called a purely multiply connected Maze.Such a Maze uses passages that coil around and run back into each other (hencethe term 'braid') and cause you to spend time going in circlesinstead of bumping into dead ends. A well-designed braid Maze can be muchharder than a perfect Maze of the same size.
• Unicursal: A unicursal Mazemeans one without any junctions. Sometimes the term Labyrinth is used to referto constructs of this type, while 'Maze' means a puzzle where choicesare involved. A unicursal Maze has just one long snake-like passage that coilsthroughout the extent of the Maze. It's not really difficult unless youaccidentally get turned around half way through and make your way back to thebeginning again.
• Sparseness: A sparse Maze is onethat doesn't carve passages through every cell, meaning some are leftuncreated. This amounts to having inaccessible locations, making this somewhatthe reverse of a braid Maze. A similar concept can be applied when addingwalls, resulting in an irregular Maze with wide passages and rooms.
• Partial braid: A partial braid Maze is just a mixed Maze with bothloops and dead ends in it. The word 'braid' can be usedquantitatively, in which a 'heavily braid Maze' means one with manyloops or detached walls, and a 'slightly braid Maze' means one withjust a few.

Texture: The texture class is subtle, and describes the style of thepassages in whatever routing in whatever geometry. They're not really on/offflags as much as general themes. Here are several example variables one canlook at:

• Bias: A passage biased Maze isone with straightaways that tend to go in one direction more than the others.For example, a Maze with a high horizontal bias will have long left-rightpassages, and only short up-down passages connecting them. A Maze is usuallymore difficult to navigate 'against the grain'.
• Run: The 'run' factor ofa Maze is how long straightaways tend to go before forced turnings presentthemselves. A Maze with a low run won't have straight passages for more thanthree or four cells, and will look very random. A Maze with a high run willhave long passages going across a good percentage of the Maze, and will looksimilar to a microchip.
• Elite: The 'elitism'factor of a Maze indicates the length of the solution with respect to the sizeof the Maze. An elitist Maze generally has a short direct solution, while anon-elitist Maze has the solution wander throughout a good portion of theMaze's area. A well designed elitist Maze can be much harder than a non-elitistone.
• Symmetric: A symmetric Mazehas symmetric passages, e.g. rotationally symmetric about the middle, orreflected across the horizontal or vertical axis. A Maze may be partially ortotally symmetric, and may repeat a pattern any number of times.
• Uniformity: A uniform algorithm isone that generates all possible Mazes with equal probability. A Maze can bedescribed as having a uniform texture if it looks like a typical Maze generatedby a uniform algorithm. A non-uniform algorithm may still be able topotentially generate all possible Mazes within whatever space but not withequal probability, or it may take non-uniformity further in which there existspossible Mazes that the algorithm can never generate.
• River: The 'river' characteristic means that when creatingthe Maze, the algorithm will look for and clear out nearby cells (or walls) tothe current one being created, i.e. it will flow (hence the term'river') into uncreated portions of the Maze like water. A perfectMaze with less 'river' will tend to have many short dead ends, whilea Maze with more river will have fewer but longer dead ends.

Focus: The focus class is obscure, but shows that Maze creation canbe divided into two general types: Wall adders, and passage carvers. This isusually just an algorithmic difference when generating, as opposed to a visualdifference when observing, but is still useful to consider. The same Maze canbe often generated in both ways:

• Wall adders: Algorithms that focus on walls start with an empty area(or an outer boundary) and add walls. In real life, a life size Maze composedof hedges, tarps, or wood walls, is a definite wall adder.
• Passage carvers: Algorithms that focus on passages start with asolid block and carve passages. In real life, a Maze composed of mine tunnels,or running in the inside of pipes, is a passage carver.
• Template: Mazes can of course be bothpassage carved and wall added, and some computer algorithms do just that. AMaze template refers to a general graphic that isn't a Maze, which is thenmodified to be a valid Maze in as few steps as possible, but still has thetexture of the original graphic template. Complicated Maze styles likeinterlocking spirals are easier to do on a computer as templates, as opposed totrying to create a valid Maze while keeping it conforming to whatever style atthe same time.

Other:How to use mi pc suite. The above is by no means a comprehensive list of all possibleclasses or items within each class. They're just the types of Mazes I'veactually created. :-) Note most every type of Maze, including Mazes withspecial rules, can be expressed as a directed graph, in which you have a finitenumber of states and a finite number of choices at each state, which is called Maze equivalence. Here are some other classesand types of Mazes:

• Direction: This is where certainpassages can only be traveled in one way. In Computer Science terms, such aMaze would be described by a directed graph, as opposed to an undirected graphlike all the others.
• Segmented: This is where aMaze has different sections of its area falling in different classes.
• Infinite length Mazes: It'spossible to create an infinitely long Maze (a finite number of columns by asmany rows as you like) by only keeping part of the Maze in memory at a time and'scrolling' from one end to the other, discarding earlier rows whilecreating later rows. One way is with a modified version of the Hunt and Killalgorithm. Visualize the potentially infinitely long Maze as a long film reel,composed of individual picture frames, where just two consecutive frames arekept in memory at a time. Run the Hunt and Kill algorithm, however give bias tothe top frame so it gets finished first. Once finished, it's no longer needed,so can be printed out, etc. Either way, discard it, make the partially createdbottom frame be the new top frame, and clear a new bottom frame. Repeat theprocess until you decide to stop, at which point let Hunt And Kill finish bothframes. The only limitation is the Maze can never have a path that doubles backtoward the entrance for a length greater than two frames. An easier way to makean infinite Maze is with Eller's or the Sidewinder algorithms, as they alreadymake Mazes one row at time, so simply keep letting them add rows to the Mazeforever.
• Virtual fractal Mazes: A virtualMaze is one where the whole Maze isn't stored in memory at once. For exampleonly store the 100x100 section of passages or so nearest your location, in asimulation where you walk through a large Maze. An extension of nested fractalMazes can be used to create virtual Mazes of enormous size, such as a billionby a billion passages. Note a life size version of a billion by billion Maze(with six feet between passages) would cover the Earth's surface over 6000times! Consider a 10^9 by 10^9 passage Maze, or a 10x10 Maze nested with 9levels total. If we want at least a 100x100 section around us, we only need tocreate the 100x100 passage submaze at the lowest level, and the seven 10x10Mazes it's nested within, to know exactly where the walls lie within a 100x100section. (Actually it's best to have four adjacent 100x100 sections forming asquare, in case you're near the edge or corner of a section, but the sameconcept applies.) To ensure the Maze remains consistent and never changes asyou move around, have a formula to determine a random number seed for eachcoordinate at each nesting level. Virtual fractal Mazes are similar to aMandelbrot set fractal, in which the pictures in a Mandelbrot exist virtually,and you just need to visit a particular coordinate at a high enough zoom levelfor them to reveal themselves.

Maze Creation Algorithms

Here's a list of general algorithms to create the various classes of Mazesdescribed above:

• Perfect: Creating a standardperfect Maze usually involves 'growing' the Maze while ensuring theno loops and no isolations restriction is kept. Start with the outer wall, andadd a wall segment touching it at random. Keep on adding wall segments to theMaze at random, but ensure that each new segment touches an existing wall atone end, and has its other end in an unmade portion of the Maze. If you everadded a wall segment where both ends were separate from the rest of the Maze,that would create a detached wall with a loop around it, and if you ever addeda segment such that both ends touch the Maze, that would create an inaccessiblearea. This is the wall adding method; a nearly identical way to do it ispassage carved, where new passage sections are carved such that exactly one endtouches an existing passage.
• Braid: To create a Maze withoutdead ends, basically add wall segments throughout the Maze at random, butensure that each new segment added will not cause a dead end to be made. I makethem with four steps: (1) Start with the outer wall, (2) Loop through the Mazeand add single wall segments touching each wall vertex to ensure there are noopen rooms or small 'pole' walls in the Maze, (3) Loop over allpossible wall segments in random order, adding a wall there if it wouldn'tcause a dead end, (4) Either run the isolation remover utility at the end tomake a legal Maze that has a solution, or be smarter in step three and makesure a wall is only added if it also wouldn't cause an isolated section.
• Unicursal: One way to createa random unicursal Maze is to take a perfect Maze, seal off the exit so there'sonly the one entrance, then add walls bisecting each passage. This will turneach dead end into a U-turn passageway, and there will be a unicursal passagestarting and ending at the original Maze's beginning, that will follow the samepath as someone wall following the original Maze. The new unicursal Maze willhave twice the dimensions of the original perfect Maze it was based on. Smalltricks may be done to have the start and end not always be next to each other:When creating the perfect Maze, never add segments attached to the right orbottom walls, so the resulting Maze will have an easy solution that followsthat wall. Have the entrance at the upper right, and after bisecting to createthe unicursal routing, remove the right and bottom wall. This will result in aunicursal Maze that starts at the upper right and ends at the lower left.
• Sparseness: Sparse Mazes areproduced by choosing to not grow the Maze in areas that would violate the ruleof sparseness. A consistent way to implement this is to, whenever considering anew cell to carve into, to first check all cells within a semicircle of chosencell radius located forward in the current direction. If any of those cells isalready part of the Maze, don't allow the cell being considered, since doing towould be too close to an existing cell and hence make the Maze not sparse.
• 3D: Three and higher dimensionalMazes can be created just like the standard 2D perfect Maze, except from eachcell you can move randomly to six instead of four other orthogonal cells. TheseMazes are generally passage carved due to the extra dimensions.
• Weave: Weave Mazes are basicallydone as passage carved perfect Mazes, except when carving a passage you're notalways blocked by an existing passage, as you have the option to go under itand still preserve the 'perfect' quality. On a monochrome bitmap, aWeave Maze can be represented with four rows per passage (two rows per passageis enough for a standard perfect Maze) where you have one row for the passageitself and the other three rows to make it unambiguous when another nearbypassage goes under instead of just having a dead end near the first passage.For aesthetics you may want to look ahead before carving under an existingpassage, to ensure you can continue to carve once you're completely under it,so there won't be any dead ends that terminate under a passage. Also, aftercarving under a passage, you may want to invert the pixels adjacent to theintersection, making it so newer passages can go over instead of always underexisting ones.
• Crack: Crack Mazes are basicallydone as wall added perfect Mazes, except there are no distinct tessellationcells other than random pixel locations. Pick a pixel that's already set as awall, pick another random location, and 'shoot' or start drawing awall toward the second location. However, make sure you stop just beforerunning into any existing wall, so as not to create an isolation. Stop afteryou haven't been able to add any significant walls in a while. Note that randomlocations to draw to that may be anywhere else in the Maze, will make it sothere will be several straight lines going across the Maze, and otherproportionally smaller walls as you look between them, the number of walls onlybeing limited by the pixel resolution. This makes the Maze look very much likethe surface of a leaf, so this is technically a fractal Maze.
• Omega: Omega style Mazes involvedefining some grid, defining how the cells link up with each other, and how tomap the vertexes that surround each cell to the screen. For example, for thetriangular Delta Maze with interlocking triangular cells: (1) There's a gridwhere each row has a number of cells that increases by two. (2) Each cell isconnected to the cells adjacent to it in that row, except the third passage islinked to an appropriate cell in the row above or below based on whether it'sin an odd or even column (i.e. whether the triangle is pointing up or down).(3) Each cell uses the math for a triangle to figure out where to draw it onthe screen. You can draw all walls on the screen ahead of time and passagecarve the Maze, or keep some modified array in memory and render the wholething when complete.
• Hypermaze: A hypermaze in a 3Denvironment is similar to the reverse of a standard 3D non-hypermaze, whereblocks become open spaces and vice versa. While a standard 3D Maze consists ofa tree of passages through a solid area, a hypermaze consists of a tree of barsor vines through an open area. To create a hypermaze, start with solid top andbottom faces, then grow tangled vines from these faces to fill the spacebetween, to make it harder to pass a line segment between the two faces. Aslong as each vine connects with either the top or bottom, the hypermaze willhave at most a single solution. As long as no vine connects with both the topand bottom (which would form an impassable column), and as long as there are novine loops in the top and bottom sections that cause them to be inextricablylinked with each other like a chain, the hypermaze will be solvable.
• Planair: Planair Mazes withunusual topology are generally done as an array of one or more smaller Mazes orMaze sections, where it's defined how the edges connect with each other. A Mazeon the surface of a cube is just six square Maze sections, where when the partbeing created runs into an edge it flows onto another section and onto theright edge appropriately.
• Template: Mazes based on templates aredone by simply starting with the base template image, then running theisolation remover to ensure the Maze has a solution, followed by the loopremover to ensure the Maze is hard enough, resulting in a perfect Maze thatstill looks very similar to the original image. For example, to create a Mazecomposed of interlocking spirals, just create some random spirals withoutworrying whether it's a Maze or not, then run it through the isolation and loopremovers.

Perfect Maze Creation Algorithms

There are a number of ways of creating perfect Mazes, each with its owncharacteristics. Here's a list of specific algorithms. Anonymous external attack.exe. All of these describecreating the Maze by carving passages, however unless otherwise specified eachcan also be done by adding walls:

• Recursive backtracker: Thisis somewhat related to the recursive backtracker solving method, and requiresstack up to the size of the Maze. When carving, be as greedy as possible, andalways carve into an unmade section if one is next to the current cell. Eachtime you move to a new cell, push the former cell on the stack. If there are nounmade cells next to the current position, pop the stack to the previousposition. The Maze is done when you pop everything off the stack. Thisalgorithm results in Mazes with about as high a 'river' factor aspossible, with fewer but longer dead ends, and usually a very long and twistysolution. When implemented efficiently it runs fast, with only highlyspecialized algorithms being faster. Recursive backtracking doesn't work as awall adder, because doing so tends to result in a solution path that followsthe outside edge, where the entire interior of the Maze is attached to theboundary by a single stem.
• Kruskal's algorithm: This isKruskal's algorithm to produce a minimum spanning tree. It's interestingbecause it doesn't 'grow' the Maze like a tree, but rather carvespassage segments all over the Maze at random, but yet still results in aperfect Maze in the end. It requires storage proportional to the size of theMaze, along with the ability to enumerate each edge or wall between cells inthe Maze in random order (which usually means creating a list of all edges andshuffling it randomly). Label each cell with a unique id, then loop over allthe edges in random order. For each edge, if the cells on either side of ithave different id's, then erase the wall, and set all the cells on one side tohave the same id as those on the other. If the cells on either side of the wallalready have the same id, then there already exists some path between those twocells, so the wall is left alone so as to not create a loop. This algorithmyields Mazes with a low 'river' factor, but not as low as Prim'salgorithm. Merging the two sets on either side of the wall will be a slowoperation if each cell just has a number and are merged by a loop. Merging aswell as lookup can be done in near constant time by using the union-findalgorithm: Place each cell in a tree structure, with the id at the root, inwhich merging is done quickly by splicing two trees together. Done right, thisalgorithm runs reasonably fast, but is slower than most because of the edgelist and set management.
• Prim's algorithm (true):This is Prim's algorithm to produce a minimum spanning tree, operating overuniquely random edge weights. It requires storage proportional to the size ofthe Maze. Start with any vertex (the final Maze will be the same regardless ofwhich vertex one starts with). Proceed by selecting the passage edge with leastweight connecting the Maze to a point not already in it, and attach it to theMaze. The Maze is done when there are no more edges left to consider. Toefficiently select the next edge, a priority queue (usually implemented with aheap) is needed to store the frontier edges. Still, this algorithm is somewhatslow, because selecting elements from and maintaining the heap requires log(n)time. Therefore Kruskal's algorithm which also produces a minimum spanning treecan be considered better, since it's faster and produces Mazes with identicaltexture. In fact, given the same random number seed, identical Mazes can becreated with both Prim's and Kruskal's algorithms.
• Prim's algorithm (simplified):This is Prim's algorithm to produce a minimum spanning tree, simplified suchthat all edge weights are the same. It requires storage proportional to thesize of the Maze. Start with a random vertex. Proceed by randomly selecting apassage edge connecting the Maze to a point not already in it, and attach it tothe Maze. The Maze is done when there are no more edges left to consider. Sinceedges are unweighted and unordered, they can be stored in a simple list, whichmeans selecting elements from the list is very fast and only takes constanttime. Therefore this is much faster than true Prim's algorithm with random edgeweights. The texture of the Maze produced will have a lower 'river'factor and a simpler solution than true Prim's algorithm, because it will outspread equally from the start point like poured syrup, instead of bypassing andflowing around clumps of higher weighted edges that don't get covered untillater.
• Prim's algorithm (modified):This is Prim's algorithm to produce a minimum spanning tree, modified so alledge weights are the same, but also implemented by looking at cells instead ofedges. It requires storage proportional to the size of the Maze. Duringcreation, each cell is one of three types: (1) 'In': The cell is partof the Maze and has been carved into already, (2) 'Frontier': Thecell is not part of the Maze and has not been carved into yet, but is next to acell that's already 'in', and (3) 'Out': The cell is notpart of the Maze yet, and none of its neighbors are 'in' either.Start by picking a cell, making it 'in', and setting all itsneighbors to 'frontier'. Proceed by picking a 'frontier'cell at random, and carving into it from one of its neighbor cells that are'in'. Change that 'frontier' cell to 'in', andupdate any of its neighbors that are 'out' to 'frontier'.The Maze is done when there are no more 'frontier' cells left (whichmeans there are no more 'out' cells left either, so they're all'in'). This algorithm results in Mazes with a very low'river' factor with many short dead ends, and a rather directsolution. The resulting Maze is very similar to simplified Prim's algorithm,with only the subtle distinction that indentations in the expanding tree getfilled only if that frontier cell is randomly selected, as opposed to havingtriple the chance of filling that cell via one of the frontier edges leading toit. It also runs very fast, faster than simplified Prim's algorithm because itdoesn't need to compose and maintain a list of edges.
• Aldous-Broder algorithm: Theinteresting thing about this algorithm is that it's uniform, which means itgenerates all possible Mazes of a given size with equal probability. It alsorequires no extra storage or stack. Pick a point, and move to a neighboringcell at random. If an uncarved cell is entered, carve into it from the previouscell. Keep moving to neighboring cells until all cells have been carved into.This algorithm yields Mazes with a low 'river' factor, only slightlyhigher than Kruskal's algorithm. (This means for a given size there are moreMazes with a low 'river' factor than high 'river', since anaverage equal probability Maze has low 'river'.) The bad thing aboutthis algorithm is that it's very slow, since it doesn't do any intelligenthunting for the last cells, where in fact it's not even guaranteed toterminate. However since the algorithm is simple it can move over many cellsquickly, so finishes faster than one might think. On average it takes aboutseven times longer to run than standard algorithms, although in bad cases itcan take much longer if the random number generator keeps making it avoid thelast few cells. This can be done as a wall adder if the boundary wall istreated as a single vertex, i.e. if a move goes to the boundary wall, teleportto a random point along the boundary before moving again. As a wall adder thisruns nearly twice as fast, because the boundary wall teleportation allowsquicker access to distant parts of the Maze.
• Wilson's algorithm: This isan improved version of the Aldous-Broder algorithm, in that it produces Mazeswith exactly the same texture as that algorithm (the algorithms are uniformwith all possible Mazes generated with equal probability), however Wilson'salgorithm runs much faster. It requires storage up to the size of the Maze.Begin by making a random starting cell part of the Maze. Proceed by picking arandom cell not already part of the Maze, and doing a random walk until a cellis found which is already part of the Maze. Once the already created part ofthe Maze is hit, go back to the random cell that was picked, and carve alongthe path that was taken, adding those cells to the Maze. More specifically,when retracing the path, at each cell carve along the direction that the randomwalk most recently took when it left that cell. That avoids adding loops alongthe retraced path, resulting in a single long passage being appended to theMaze. The Maze is done when all cells have been appended to the Maze. This hassimilar performance issues as Aldous-Broder, where it may take a long time forthe first random path to find the starting cell, however once a few paths arein place, the rest of the Maze gets carved quickly. On average this runs fivetimes faster than Aldous-Broder, and takes less than twice as long as the topalgorithms. Note this runs twice as fast when implemented as a wall adder,because the whole boundary wall starts as part of the Maze, so the first wallsare connected much quicker.
• Hunt and kill algorithm: Thisalgorithm is nice because it requires no extra storage or stack, and istherefore suited to creating the largest Mazes or Mazes on the most limitedsystems, since there are no issues of running out of memory. Since there are norules that must be followed all the time, it's also the easiest to modify andto get to create Mazes of different textures. It's most similar to therecursive backtracker, except when there's no unmade cell next to the currentposition, you enter 'hunting' mode, and systematically scan over theMaze until an unmade cell is found next to an already carved into cell, atwhich point you start carving again at that new location. The Maze is done whenall cells have been scanned over once in 'hunt' mode. This algorithmtends to make Mazes with a high 'river' factor, but not as high asthe recursive backtracker. You can make this generate Mazes with a lower riverfactor by choosing to enter 'hunt' mode more often. It runs slowerdue to the time spent hunting for the last cells, but isn't much slower thanKruskal's algorithm. This can be done as a wall adder if you randomly teleporton occasion, to avoid the issues the recursive backtracker has.
• Growing tree algorithm: This isa general algorithm, capable of creating Mazes of different textures. Itrequires storage up to the size of the Maze. Each time you carve a cell, addthat cell to a list. Proceed by picking a cell from the list, and carving intoan unmade cell next to it. If there are no unmade cells next to the currentcell, remove the current cell from the list. The Maze is done when the listbecomes empty. The interesting part that allows many possible textures is howyou pick a cell from the list. For example, if you always pick the most recentcell added to it, this algorithm turns into the recursive backtracker. If youalways pick cells at random, this will behave similarly but not exactly toPrim's algorithm. If you always pick the oldest cells added to the list, thiswill create Mazes with about as low a 'river' factor as possible,even lower than Prim's algorithm. If you usually pick the most recent cell, butoccasionally pick a random cell, the Maze will have a high 'river'factor but a short direct solution. If you randomly pick among the most recentcells, the Maze will have a low 'river' factor but a long windysolution.
• Growing forest algorithm:This is a more general algorithm, that combines both tree and set based types.It's an extension of the Growing Tree algorithm, that basically involvesmultiple instances of it expanding at the same time. Start with all cellsrandomly sorted into a 'new' list, and also each cell in its own setsimilar to the start of Kruskal's algorithm. Begin by selecting one or morecells, moving them from the 'new' to an 'active' list.Proceed by picking a cell from the 'active' list, and carving into anunmade cell in the 'new' list next to it, adding the new cell to the'active' list, and merging the two cells' sets. If an attempt is madeto carve into an existing part of the Maze, allow it if the cells are indifferent sets, and merge the sets as done with Kruskal's algorithm. If thereare no unmade 'new' cells next to the current cell, move the currentcell to a 'done' list. The Maze is complete when the'active' list becomes empty. At the end, merge any remaining setstogether as done with Kruskal's algorithm. You may periodically spawn new treesby moving one or more cells from the 'new' list to the'active' list like at the beginning. The number of initial trees andthe rate of newly spawned trees can generate many unique textures, combinedwith the already versatile settings of the Growing Tree algorithm.
• Eller's algorithm: Thisalgorithm is special because it's not only faster than all the others thatdon't have obvious biases or blemishes, but its creation is also the mostmemory efficient. It doesn't even require the whole Maze to be in memory, onlyusing storage proportional to the size of a row. It creates the Maze one row ata time, where once a row has been generated, the algorithm no longer looks atit. Each cell in a row is contained in a set, where two cells are in the sameset if there's a path between them through the part of the Maze that's beenmade so far. This information allows passages to be carved in the current rowwithout creating loops or isolations. This is actually quite similar toKruskal's algorithm, just this completes one row at a time, while Kruskal'slooks over the whole Maze. Creating a row consists of two parts: Randomlyconnecting adjacent cells within a row, i.e. carving horizontal passages, thenrandomly connecting cells between the current row and the next row, i.e.carving vertical passages. When carving horizontal passages, don't connectcells already in the same set (as that would create a loop), and when carvingvertical passages, you must connect a cell if it's a set of size one (asabandoning it would create an isolation). When carving horizontal passages,when connecting cells union the sets they're in (since there's now a pathbetween them), and when carving vertical passages, when not connecting a cellput it in a set by itself (since it's now disconnected from the rest of theMaze). Creation starts with each cell in its own set before connecting cellswithin the first row, and creation ends after connecting cells within the lastrow, with a special final rule that every cell must be in the same set by thetime we're done to prevent isolations. (The last row is done by connecting eachpair of adjacent cells if not already in the same set.) The best way toimplement the set is with a circular doubly linked list of cells (which canjust be an array mapping cells to the pair of cells on either side in the sameset) which allows insertion, deletion, and checking whether adjacent cells arein the same set in constant time. One issue with this algorithm is that it'snot balanced with respect to how it treats the different edges of the Maze,where connecting vs. not connecting cells need to be done in the rightproportions to prevent texture blemishes.
• Recursive division: This algorithmis somewhat similar to recursive backtracking, since they're both stack based,except this focuses on walls instead of passages. Start by making a randomhorizontal or vertical wall crossing the available area in a random row orcolumn, with an opening randomly placed along it. Then recursively repeat theprocess on the two subareas generated by the dividing wall. For best results,give bias to choosing horizontal or vertical based on the proportions of thearea, e.g. an area twice as wide as it is high should be divided by a verticalwall more often. This is the fastest algorithm without directional biases, andcan even rival binary tree mazes because it can finish multiple cells at once,although it has the obvious blemish of long walls crossing the interior. Thisalgorithm is a form of nested fractal Mazes, except instead of always makingfixed cell size Mazes with Mazes of the same size within each cell, it dividesthe given area randomly into a random sized 1x2 or 2x1 Maze. Recursive divisiondoesn't work as a passage carver, because doing so results in an obvioussolution path that either follows the outside edge or else directly crosses theinterior.
• Binary tree Mazes: This isbasically the simplest and fastest algorithm possible, however Mazes producedby it have a very biased texture. For each cell carve a passage either leadingup or leading left, but not both. In the wall added version, for each vertexadd a wall segment leading down or right, but not both. Each cell isindependent of every other cell, where you don't have to refer to the state ofany other cells when creating it. Hence this is a true memoryless Mazegeneration algorithm, with no limit to the size of Maze you can create. This isbasically a computer science binary tree, if you consider the upper left cornerthe root, where each node or cell has one unique parent which is the cell aboveor to the left of it. Binary tree Mazes are different than standard perfectMazes, since about half the cell types can never exist in them. For examplethere will never be a crossroads, and all dead ends have passages pointing upor left, and never down or right. The Maze tends to have passages leadingdiagonally from upper left to lower right, where the Maze is much easier tonavigate from lower right to upper left. You will always be able to travel upor left, but never both, so you can always deterministically travel diagonallyup and to the left without hitting any barriers. Traveling down and to theright is when you'll encounter choices and dead ends. Note if you flip a binarytree Maze upside down and treat passages as walls and vice versa, the result isbasically another binary tree.
• Sidewinder Mazes: This simplealgorithm is very similar to the binary tree algorithm, and only slightly morecomplicated. The Maze is generated one row at a time: For each cell randomlydecide whether to carve a passage leading right. If a passage is not carved,then consider the horizontal passage just completed, formed by the current celland any cells to the left that carved passages leading to it. Randomly pick onecell along this passage, and carve a passage leading up from it (which must bethe current cell if the adjacent cell didn't carve). While a binary tree Mazealways goes up from the leftmost cell of a horizontal passage, a sidewinderMaze goes up from a random cell. While binary tree has the top and left edgesof the Maze one long passage, a sidewinder Maze has just the top edge one longpassage. Like binary tree, a sidewinder Maze can be solved deterministicallywithout error from bottom to top, because at each row, there will always beexactly one passage leading up. A solution to a sidewinder Maze will neverdouble back on itself or visit a row more than once, although it will'wind from side to side'. The only cell type that can't exist in asidewinder Maze is a dead end with the passage facing down, because that wouldcontradict the fact that every passage going up leads back to the start. Asidewinder Maze tends to have an elitist solution, where the right path is verydirect, but there are many long false paths leading down from the top next toit.

Algorithm	Dead End %	Type	Focus	Bias Free?	Uniform?	Memory	Time	Solution %
Unicursal	0	Tree	Wall	Yes	never	N^2	379	100.0
Recursive Backtracker	10	Tree	Passage	Yes	never	N^2	27	19.0
Hunt and Kill	11 (21)	Tree	Passage	Yes	never	0	100 (143)	9.5 (3.9)
Recursive Division	23	Tree	Wall	Yes	never	N*	10	7.2
Binary Tree	25	Set	Either	no	never	0*	10	2.0
Sidewinder	27	Set	Either	no	never	0*	12	2.6
Eller's Algorithm	28	Set	Either	no	no	N*	20	4.2 (3.2)
Wilson's Algorithm	29	Tree	Either	Yes	Yes	N^2	48 (25)	4.5
Aldous-Broder Algorithm	29	Tree	Either	Yes	Yes	0	279 (208)	4.5
Kruskal's Algorithm	30	Set	Either	Yes	no	N^2	33	4.1
Prim's Algorithm (true)	30	Tree	Either	Yes	no	N^2	160	4.1
Prim's Algorithm (simplified)	32	Tree	Either	Yes	no	N^2	59	2.3
Prim's Algorithm (modified)	36 (31)	Tree	Either	Yes	no	N^2	30	2.3
Growing Tree	49 (39)	Tree	Either	Yes	no	N^2	48	11.0
Growing Forest	49 (39)	Both	Either	Yes	no	N^2	76	11.0

This table summarizes the characteristics of the perfect Maze creationalgorithms above. The Unicursal Maze algorithm (unicursal Mazes are technicallyperfect) is included for comparison. Descriptions of the columns follow:

• Dead End: This is the approximate percentage of cells that are deadends in a Maze created with this algorithm, when applied to an orthogonal 2DMaze. The algorithms in the table are sorted by this field. Usually creating byadding walls is the same as carving passages, however if significantlydifferent the wall adding percentage is in parentheses. The Growing Tree valuecan actually range from 10% (always pick newest cell) to 49% (always swap witholdest cell). With a high enough run factor the Recursive Backtracker can getlower than 1%. The highest possible dead end percentage in an 2D orthogonalperfect Maze is 66%, which would be a unicursal passage with a bunch of oneunit long dead ends off either side of it.
• Type: There are two types of perfect Maze creation algorithms: Atree based algorithm grows the Maze like a tree, always adding onto what isalready present, having a valid perfect Maze at every step. A set basedalgorithm builds where it pleases, keeping track of which parts of the Maze areconnected with each other, to ensure it's able to link everything up to form avalid Maze by the time it's done. Some algorithms like Growing Forest do bothat once.
• Focus: Most algorithms can be implemented by either carving passagesor adding walls. A few can only be done as one or the other. Unicursal Mazesare always wall added since they involve bisecting passages with walls,although the base Maze can be created either way. Recursive Backtracker can'tbe done as a wall adder because doing so tends to result in a solution paththat follows the outside edge, where the entire interior of the Maze isattached to the boundary by a single stem. Similarly Recursive Division canonly be done as a wall adder due to its bisection behavior. Hunt and Kill istechnically only passage carved for a similar reason, although it can be walladded if special case effort is made to grow inward from all boundary wallsequally.
• Bias Free: This is whether the algorithm treats all directions andsides of the Maze equally, where analysis of the Maze afterward can't revealany passage bias. Binary Tree is extremely biased, where it's easy travelingtoward one corner and hard to its opposite. Sidewinder is also biased, whereit's easy traveling toward one edge and hard to its opposite. Eller's algorithmtends to have a passage roughly paralleling the starting or finishing edges.Hunt and Kill is bias free, as long as hunting is done column by column as wellas row by row to avoid a slight bias along one axis.
• Uniform: This is whether the algorithm generates all possible Mazeswith equal probability. 'Yes' means the algorithm is fully uniform.'No' means the algorithm can potentially generate all possible Mazeswithin whatever space, but not with equal probability. 'Never' meansthere exists possible Mazes that the algorithm can't ever generate. Note thatonly bias free algorithms can be fully uniform.
• Memory: This is how much extra memory or stack is required toimplement the algorithm. Efficient algorithms only require and look at the Mazebitmap itself, while others require storage proportional to a single row (N),or proportional to the number of cells (N^2). Some algorithms don't even needto have the entire Maze in memory, and can be added onto forever (these aremarked with a asterisk). Eller's algorithm requires storage for a row, but morethan makes up for that since it only needs to store the current row of the Mazein memory. Sidewinder also only needs to store one row of the Maze, whileBinary Tree only needs to keep track of the current cell. Recursive Divisionrequires stack up to the size of a row, but other than that doesn't need tolook at the Maze bitmap.
• Time: This gives an idea of how long it takes to create a Maze usingthis algorithm, lower numbers being faster. The numbers are only relative toeach other (with the fastest algorithm being assigned speed 10) as opposed toin some units, because the time is dependent on the size of the Maze and speedof the computer. These numbers are from creating 100x100 passage Mazes in thelatest version of Daedalus. Usually creating by adding walls is the same speedas carving passages, however if significantly different the wall adding time isin parentheses.
• Solution: This is the percentage of cells in the Maze that thesolution path passes through, for a typical Maze created by the algorithm. Thisassumes the Maze is 100x100 passages with the start and end in oppositecorners. This is a measure of the 'windiness' of the solution path.Unicursal Mazes have maximum windiness, since the solution goes throughout theentire Maze. Binary Tree has the minimum possible windiness, where the solutionpath simply crosses the Maze and never deviates away from or ceases to makeprogress toward the end. Usually creating by adding walls has the sameproperties as carving passages, however if significantly different the walladding percentage is in parentheses.

Maze Solving Algorithms

There are a number of ways of solving Mazes, each with its owncharacteristics. Here's a list of specific algorithms:

• Wall follower: This is asimple Maze solving algorithm. It focuses on you, is always very fast, and usesno extra memory. Start following passages, and whenever you reach a junctionalways turn right (or left). Equivalent to a human solving a Maze by puttingtheir hand on the right (or left) wall and leaving it there as they walkthrough. If you like you can mark what cells you've visited, and what cellsyou've visited twice, where at the end you can retrace the solution byfollowing those cells visited once. This method won't necessarily find theshortest solution, and it doesn't work at all when the goal is in the center ofthe Maze and there's a closed circuit surrounding it, as you'll go around thecenter and eventually find yourself back at the beginning. Wall following canbe done in a deterministic way in a 3D Maze by projecting the 3D passages ontothe 2D plane, e.g. by pretending up passages actually lead northwest and downlead southeast, and then applying normal wall following rules.
• Pledge algorithm: This is amodified version of wall following that's able to jump between islands, tosolve Mazes wall following can't. It's a guaranteed way to reach an exit on theouter edge of any 2D Maze from any point in the middle, however it's not ableto do the reverse, i.e. find a solution within the Maze. It's great forimplementation by a Maze escaping robot, since it can get out of any Mazewithout having to mark or remember the path in any way. Start by picking adirection, and always move in that direction when possible. When a wall is hit,start wall following until your chosen direction is available again. Note youshould start wall following upon the far wall that's hit, where if the passageturns a corner there, it can cause you to turn around in the middle of apassage and go back the way you came. When wall following, count the number ofturns you make, e.g. a left turn is -1 and a right turn is 1. Only stop wallfollowing and take your chosen direction when the total number of turns you'vemade is 0, i.e. if you've turned around 360 degrees or more, keep wallfollowing until you untwist yourself. The counting ensures you're eventuallyable to reach the far side of the island you're currently on, and jump to thenext island in your chosen direction, where you'll keep on island hopping inthat direction until you hit the boundary wall, at which point wall followingtakes you to the exit. Note Pledge algorithm may make you visit a passage orthe start more than once, although subsequent times will always be withdifferent turn totals. Without marking your path, the only way to know whetherthe Maze is unsolvable is if your turn total keeps increasing, although theturn total can get to large numbers in solvable Mazes in a spiral passage.
• Chain algorithm: The Chainalgorithm solves the Maze by effectively treating it as a number of smallerMazes, like links in a chain, and solving them in sequence. You have to specifythe start and desired end locations, and the algorithm will always find a pathfrom start to end if one exists, where the solution tends to be a reasonablyshort if not the shortest solution. That means this can't solve Mazes where youdon't know exactly where the end is. This is most similar to Pledge algorithmsince it's also essentially a wall follower with a way to jump between islands.Start by drawing a straight line (or at least a line that doesn't double backon itself) from start to end, letting it cross walls if needed. Then justfollow the line from start to end. If you bump into a wall, you can't gothrough it, so you have to go around. Send two wall following'robots' in both directions along the wall you hit. If a robot runsinto the guiding line again, and at a point which is closer to the exit, thenstop, and follow that wall yourself until you get there too. Keep following theline and repeating the process until the end is reached. If both robots returnto their original locations and directions, then farther points along the lineare inaccessible, and the Maze is unsolvable.
• Recursive backtracker: This willfind a solution, but it won't necessarily find the shortest solution. Itfocuses on you, is fast for all types of Mazes, and uses stack space up to thesize of the Maze. Very simple: If you're at a wall (or an area you've alreadyplotted), return failure, else if you're at the finish, return success, elserecursively try moving in the four directions. Plot a line when you try a newdirection, and erase a line when you return failure, and a single solution willbe marked out when you hit success. When backtracking, it's best to mark thespace with a special visited value, so you don't visit it again from adifferent direction. In Computer Science terms this is basically a depth firstsearch. This method will always find a solution if one exists, but it won'tnecessarily be the shortest solution.
• Trémaux's algorithm: This Mazesolving method is designed to be able to be used by a human inside of the Maze.It's similar to the recursive backtracker and will find a solution for allMazes: As you walk down a passage, draw a line behind you to mark your path.When you hit a dead end, turn around and go back the way you came. When youencounter a junction you haven't visited before, pick a new passage at random.If you're walking down a new passage and encounter a junction you have visitedbefore, treat it like a dead end and go back the way you came. (That last stepis the key which prevents you from going around in circles or missing passagesin braid Mazes.) If walking down a passage you have visited before (i.e. markedonce) and you encounter a junction, take any new passage if one is available,otherwise take an old passage (i.e. one you've marked once). All passages willeither be empty, meaning you haven't visited it yet, marked once, meaningyou've gone down it exactly once, or marked twice, meaning you've gone down itand were forced to backtrack in the opposite direction. When you finally reachthe solution, paths marked exactly once will indicate a direct way back to thestart. If the Maze has no solution, you'll find yourself back at the start withall passages marked twice.
• Dead end filler: This is asimple Maze solving algorithm. It focuses on the Maze, is always very fast, anduses no extra memory. Just scan the Maze, and fill in each dead end, filling inthe passage backwards from the block until you reach a junction. That includesfilling in passages that become parts of dead ends once other dead ends areremoved. At the end only the solution will remain, or solutions if there aremore than one. This will always find the one unique solution for perfect Mazes,but won't do much in heavily braid Mazes, and in fact won't do anything usefulat all for those Mazes without dead ends.
• Cul-de-sac filler: Thismethod finds and fills in cul-de-sacs or nooses, i.e. constructs in a Mazeconsisting of a blind alley stem that has a single loop at the end. Like thedead end filler, it focuses on the Maze, is always fast, and uses no extramemory. Scan the Maze, and for each noose junction (a noose junction being onewhere two of the passages leading from it connect with each other with no otherjunctions along the way) add a wall to convert the entire noose to a long deadend. Afterwards run the dead end filler. Mazes can have nooses hanging offother constructs that will become nooses once the first one is removed, so thewhole process can be repeated until nothing happens during a scan. This doesn'tdo much in complicated heavily braid Mazes, but will be able to invalidate morethan just the dead end filler.
• Blind alley filler: Thismethod finds all possible solutions, regardless of how long or short they maybe. It does so by filling in all blind alleys, where a blind alley is a passagewhere if you walk down it in one direction, you will have to backtrack throughthat passage in the other direction in order to reach the goal. All dead endsare blind alleys, and all nooses as described in the cul-de-sac filler are aswell, along with any sized section of passages connected to the rest of theMaze by only a single stem. This algorithm focuses on the Maze, uses no extramemory, but unfortunately is rather slow. For each junction, send a wallfollowing robot down each passage from it, and see if the robot sent down apath comes back from the same path (as opposed to returning from a differentdirection, or it exiting the Maze). If it does, then that passage andeverything down it can't be on any solution path, so seal that passage off andfill in everything behind it. This algorithm will fill in everything thecul-de-sac filler will and then some, however the collision solver will fill ineverything this algorithm will and then some.
• Blind alley sealer: This islike the blind alley filler, in that it also finds all possible solutions byremoving blind alleys from the Maze. However this just fills in the stempassage of each blind alley, and doesn't touch any collection of passages atthe end of it. As a result this will create inaccessible passage sections forcul-de-sacs or any blind alley more complicated than a dead end. This algorithmfocuses on the Maze, runs much faster than the blind alley filler, although itrequires extra memory. Assign each connected section of walls to a unique set.To do this, for each wall section not already in a set, flood across the top ofthe walls at that point, and assign all reachable walls to a new set. After allwalls are in sets, then for each passage section, if the walls on either sideof it are in the same set, then seal off that passage. Such a passage must be ablind alley, since the walls on either side of it link up with each other,forming a pen. Note a similar technique can be used to help solve hypermazes,by sealing off space between branches that connect with each other.
• Shortest path finder: As the nameindicates, this algorithm finds the shortest solution, picking one if there aremultiple shortest solutions. It focuses on you multiple times, is fast for alltypes of Mazes, and requires quite a bit of extra memory proportional to thesize of the Maze. Like the collision solver, this basically floods the Mazewith 'water', such that all distances from the start are filled in atthe same time (a breadth first search in Computer Science terms) however each'drop' or pixel remembers which pixel it was filled in by. Once thesolution is hit by a 'drop', trace backwards from it to the beginningand that's a shortest path. This algorithm works well given any input, becauseunlike most of the others, this doesn't require the Maze to have any one pixelwide passages that can be followed. Note this is basically the A* path findingalgorithm without a heuristic so all movement is given equal weight.
• Shortest paths finder: Thisis very similar to the shortest path finder, except this finds all shortestsolutions. Like the shortest path finder, this focuses on you multiple times,is fast for all types of Mazes, requires extra memory proportional to the sizeof the Maze, and works well given any input since it doesn't require the Mazeto have any one pixel wide passages that can be followed. Also like theshortest path finder, this does a breadth first search flooding the Maze with'water' such that all distances from the start are filled in at thesame time, except here each pixel remembers how far it is from the beginning.Once the end is reached, do another breadth first search starting from the end,however only allow pixels to be included which are one distance unit less thanthe current pixel. The included pixels precisely mark all the shortestsolutions, as blind alleys and non-shortest paths will jump in pixel distancesor have them increase.
• Collision solver: Also called the 'amoeba' solver, thismethod will find all shortest solutions. It focuses on you multiple times, isfast for all types of Mazes, and requires at least one copy of the Maze inmemory in addition to using memory up to the size of the Maze. It basicallyfloods the Maze with 'water', such that all distances from the startare filled in at the same time (a breadth first search in Computer Scienceterms) and whenever two 'columns of water' approach a passage fromboth ends (indicating a loop) add a wall to the original Maze where theycollide. Once all parts of the Maze have been 'flooded', fill in allthe new dead ends, which can't be on the shortest path, and repeat the processuntil no more collisions happen. (Picture amoebas surfing at the crest of each'wave' as it flows down the passages, where when waves collide, theamoebas head-butt and get knocked out, and form there a new wall of unconsciousamoebas, hence the name.) Ultimately this is the same as the shortest pathsfinder, except this is more memory efficient (since it only needs to keep trackof the coordinates of the front of each column of water) and a bit slower(since it potentially needs to be run multiple times to remove everything).
• Random mouse: For contrast, here's an inefficient Maze solvingmethod, which is basically to move randomly, i.e. move in one direction andfollow that passage through any turnings until you reach the next junction.Don't do any 180 degree turns unless you have to. This simulates a humanrandomly roaming the Maze without any memory of where they've been. It's slowand isn't guaranteed to ever terminate or solve the Maze, and once the end isreached it will be just as hard to retrace your steps, but it's definitelysimple and doesn't require any extra memory to implement.

Algorithm	Solutions	Guarantee?	Focus	Human Doable?	Passage Free?	Memory Free?	Fast?
Random Mouse	1	no	You	Inside / Above	no	Yes	no
Wall Follower	1	no	You	Inside / Above	Yes	Yes	Yes
Pledge Algorithm	1	no	You	Inside / Above	Yes	Yes	Yes
Chain Algorithm	1	Yes	You +	no	Yes	no	Yes
Recursive Backtracker	1	Yes	You	no	Yes	no	Yes
Trémaux's Algorithm	1	Yes	You	Inside / Above	no	no	Yes
Dead End Filler	All +	no	Maze	Above	no	Yes	Yes
Cul-de-sac Filler	All +	no	Maze	Above	no	Yes	Yes
Blind Alley Sealer	All +	Yes	Maze	no	no	no	Yes
Blind Alley Filler	All	Yes	Maze	Above	no	Yes	no
Collision Solver	All Shortest	Yes	You +	no	no	no	Yes
Shortest Paths Finder	All Shortest	Yes	You +	no	Yes	no	Yes
Shortest Path Finder	1 Shortest	Yes	You +	no	Yes	no	Yes

This table summarizes the characteristics of the Maze solving algorithmsabove. Maze solving algorithms can be classified and judged by these criteria.Descriptions of the columns follow:

• Solutions: This describes the solutions the algorithm finds, andwhat the algorithm does when there's more than one. An algorithm can pick onesolution, or leave multiple solutions. Also the solution(s) can be any path, orthey can be the shortest path. The dead end and cul-de-sac fillers (and theblind alley sealer when considering its inaccessible sections) leave allsolutions, however they may also leave passages that aren't on any solutionpath, so are marked 'All +' above.
• Guarantee: This is whether the algorithm is guaranteed to find atleast one solution. Random mouse is 'no' because it isn't guaranteedto terminate, and wall follower and Pledge algorithm are 'no' becausethey will fail to find a solution if the goal is within an island. The dead endand cul-de-sac fillers are 'no' because they may not do anything tothe Maze at all in purely braid Mazes.
• Focus: There are two general types of algorithms to solve a Maze:Focus on 'you', or focus on the Maze. In a you-focuser, you have asingle point ('You' above) or a set of points ('You +'above) and try to move them through the Maze from start to finish. In aMaze-focuser, you look at the Maze as a whole and invalidate useless passages.
• Human Doable: This refers to whether a person could readily use thealgorithm to solve the Maze, either while inside a life sized version, or whilelooking at a map from above. Some you-focuser algorithms can be implemented bya person inside (or above) the Maze, while some Maze-focusers can beimplemented by a person, but only from above. Other algorithms are complicatedor intricate enough they can only reliably be done by a computer.
• Passage Free: This is whether the algorithm can be done anywhere.Some algorithms require the Maze to have obvious passages, or distinct edgesbetween distinct vertices in graph terms, or one pixel wide passages whenimplemented on a computer. The wall follower, Pledge algorithm, and chainalgorithm only require a wall on one side of you. The recursive backtracker andthe shortest path(s) finders make their own paths through open spaces.
• Memory Free: This is whether no extra memory or stack is required toimplement the algorithm. Efficient algorithms only require and look at the Mazebitmap itself, and don't need to add markers to the Maze during the solvingprocess.
• Fast: This is whether the solving process is considered fast. Themost efficient algorithms only need to look at each cell in the Maze once, orcan skip sections altogether. Running time should be proportional to the sizeof the Maze, or in Computer Science terms O(n^2) where n is the number of cellsalong one side. Random mouse is slow because it isn't guaranteed to terminate,while the blind alley filler potentially solves the Maze from each junction.

Other Maze Operations

There are more things that can be done with Mazes beyond just creating andsolving them, as described below:

• Flood fill: A quick and dirty yetuseful utility can be implemented with a single call to a graphics library'sFill or FloodFill routine. FloodFill the passage at the beginning, and if theend isn't filled, the Maze has no solution. For Mazes with an entrance and exiton the edges, FloodFill one wall, and the remaining edge marks out thesolution. For Mazes with the start or goal inside the Maze, FloodFill thesurrounding wall, and if the exit wall isn't erased, wall following won't workto solve it. Many Maze creation methods, solving methods, and other utilitiesinvolve 'flooding' the Maze at certain points.
• Isolation remover: This means toedit the Maze such that there are no passage sections that are inaccessiblefrom the rest of the Maze, by removing walls to connect such sections to therest of the Maze. Start with a copy of the Maze, then flood the passage at thebeginning. Scan the Maze (preferably in a random order that still hits everypossible cell) for any unfilled cells adjacent to a filled cell. Remove a wallsegment in the original Maze at that point, flood the Maze at this new point,and repeat until every section is filled. This utility is used in the creationof braid and template Mazes.
• Loop remover: This means to edit theMaze such that there are no loops or detached walls within it, every section ofthe Maze reachable from any other by at most one path. The way to do this isalmost identical to the isolation remover, just treat walls as passages andvice versa. Start with a copy of the Maze, then flood across the top of theouter walls. Scan the Maze (preferably in a random other that still hits everypossible wall vertex) for any unfilled walls adjacent to a filled wall. Add awall segment to the original Maze at that point connecting the two wallsections, flood the Maze at this new point, and repeat until every section isfilled. This utility is used in the creation of template Mazes, and can be usedto convert a braid Maze to a perfect Maze that still looks similar to theoriginal.
• Bottleneck finder: Thismeans to find those passages or intersection points in a Maze such that everysolution to that Maze passes through them. To do this, run the left hand wallfollower to get the leftmost solution, and run the right hand wall follower toget the rightmost solution, where places the two solutions have in common arethe bottlenecks. That technique however only works for Mazes that wallfollowing will successfully solve. For other Mazes, to find bottleneckpassages, find any solution to the Maze, and also run the blind alley sealer(which may make the Maze unsolvable if it treats an entrance or exit within theMaze as a large blind alley). Parts of the solution path that go through sealedoff passages, are bottlenecks.

Algorithm Implementations

• Daedalus: All the Maze creationand solving algorithms described above are implemented in Daedalus, a freeWindows program available for download. Daedalus comes with its complete sourcecode, which can be viewed to see more information about and specificimplementations of these algorithms.

Back to Think Labyrinth!

This site produced by Walter D.Pullen (see Astrolog homepage), hosted on astrolog.org and Magitech, created using Microsoft FrontPage, page last updatedNovember 20, 2015.