Copyright © Stephan.Wacker@web.de, 2008–2009
Go to http://www.wacker-muc.de/ for downloading the latest release.
Contents
:: Screen SaverThe Ariadne application builds and solves a variety of maze puzzles. a) When running the regular application Ariadne.exe, you can control the maze layout, its shape, additional content etc. via a "Details" panel. b) The Ariadne.scr file can be installed as a screen saver.
[Ariadne: Figure from Greek mythology. Ariadne helped Theseus escape from the maze where the Minotaurus was held.]
Use the Screen Saver "Settings" panel to configure the options of your screen saver (see the "[Option:]" tags below).
The Screen Saver accepts a few keystroke commands:
All other keystrokes and mouse buttons will terminate the screen saver.
There are several components for specific responsibilities and most of them have many optional features.
The maze fills a rectangular region in a window. In screen saver mode, the display is filled completely.
The maze has a tree-like topological structure. Any square can be reached from every other square by exactly one path. There are no circles (paths leading from a square to itself).
The maze builder algorithm starts at an arbitrary square and adds it to the "visited" region. From then on, walls (whose state is initially undecided) between one visited and one not-visited square are opened until all squares have been reached. The remaining walls are closed.
Only closed walls are painted; open walls (also called "doors") are not painted.
[Option:] Usually, all walls of the empty maze are painted before the solver starts. There is an option by which two alternative modes can be activated: In one mode, no walls are painted at all (they have zero width); in the other mode, only the walls around visited squares are painted.
A plain maze fills the whole area. However, some regions may be reserved for additional controls or images. These reserved areas do not touch directly and the maze flows closely around them.
[Option:] You can specify a folder from which the Screen Saver chooses one or more foreground images (JPG, PNG, GIF) that will be displayed.
[Option:] You can select if a background image (from the same or a different image folder) is drawn behind the maze. Even then, only 20% of the mazes will have a background image (unless the number of foreground images is 0).
[Option:] You can select whether the Screen Saver displays a small info panel showing the maze dimension, solver name and run-time statistics.
Note: When both options for displaying foreground and background images are active, not all mazes will display a foreground image. The chance of having no foreground image is 20% if there is a background image and 5% otherwise.
Usually, the constructed maze is "regular", uniformly random, i.e. the chances that a specific wall between two adjoining squares are evenly distributed.
In an irregular maze, some directions are preferred over other directions when opening the walls. The choice may depend on the square's location and on the opened/closed state of other walls.
[Variants:] There are 20 different methods or patterns of irregular mazes. e.g.:
[Option:] You can select whether irregular mazes may be built. If so, five percent of the mazes built in screen saver mode will be irregular. The irregular choice will be applied to 80% of the walls.
[Variants:] An irregular pattern may also be applied to part of the maze area only; the remainder is regular. That part is defined by the inside (or outside) of an Outline Shape (see next section). If an outline shape is already used for building the maze, that same shape is used for the irregular pattern, as well. Otherwise, a new outline shape may be used for the irregular pattern only. Another variant is a combination of two different irregular patterns on the inside and outside of the outline shape.
This option builds continuous closed walls around invisible shapes, e.g. a circle or a silhouette bitmap image (black on white). Only one wall will be opened so that a path can run into the shape. When the solver (see below) reaches the (closed) outline of the shape, it will run around it and the shape's contour will become visible. When the solver finds the entry into the shape, it will be filled from the inside but the solver cannot leave the shape as there is no second exit.
Usually, an outline shape is one contiguous shape, like a circle, a square or another polygon. However, an outline shape can also be any pattern that defines an inside and an outside. Separate regions are all treated the same way, i.e. each is surrounded by closed walls with a single entry.
[Variants:] There are 72 kinds of outline shapes, most of them with many variants, grouped into twelve mayor types:
While the patterns evoked by an Irregular Maze Builder come from following preferred directions (if possible), the rules defined by an outline shape are very strict. They take precedence over the irregular preferences.
[Option:] You can select whether outline shapes are placed into the maze. If so, 80% of the screen saver mazes will contain an outline shape.
The outline shapes described above can also be used to create another maze within the main maze. These embedded mazes need to be totally connected and will include any area that is totally enclosed. Neither the main maze nor the embedded maze must fall apart into separate areas that are not connected. The two mazes are separated by a contiguous wall.
The embedded maze has its own solver (usually with a different strategy than the main maze solver). The paths in an embedded maze will be painted with different colors than in the main maze.
[Option:] You can select whether embedded mazes are generated. If so, 15% of the screen saver mazes will contain an embedded maze.
The solver tries to find a solution path between the start square and the target square. Some strategies are deterministic, the others make random choices. Some need to know the location of the target square, some don't. Most keep a memory of the squares they have already visited.
There are three general types of strategies: Backtrackers, Flooders and Walkers .
Backtrackers go forwards until they are caught in a dead end. Then they go backwards up to a fork with another door they have not yet passed. There the go forwards, then backwards, and so on. A backtracker can solve any maze.
Flooders follow several concurrent paths in parallel. For every door at a fork, new open paths are created. A flooder can solve any maze without ever going backwards.
Walkers have no memory of visited squares; they decide solely on their current position and direction. Two of these implement a classical maze solver algorithm: "Walk through the maze while always touching the wall at your right/left hand side." This strategy can solve any tree-shaped maze but may be caught in a circle.
The visited paths are painted in two colors: Forward steps are painted in a bright color, backward steps and areas completely covered by a flooder are painted in a dull color. Two colors with clearly different hue are selected. When the solution path is found, it is painted in a brighter variant of the forward color.
[Variants:] There are 21 "normal" maze solver strategies:
Each of these solvers also has an "efficient" variant. These employ an algorithm that detects dead ends and avoids these areas. An area is identified as a dead end if the squares visited by the solver (plus any reserved areas and the maze boundary) form a closed line around it.
Dead end squares are painted with dark gray dots.
There is also a "heuristic" variant of every flooder solver. These try to guess how promising an area examined by any branch is. Basically, when one path reaches a dead end it gives a signal to every neighboring path. Thus, paths with less negative signals from their dead siblings will be preferred. With some strategies, especially those that tend to avoid getting close to the target, this heuristic gives a significant advantage.
There are two additional "extreme" strategies that are, however, not used in screen saver mode or when "any" solver should be selected.
The area visited by the RandomBacktracker (in a regular maze) is a good example of a fractal: The border is self-similar at different scales.
RightHandWalker and LeftHandWalker produce "inverted" paintings: One visits all areas to the right of the solution path, the other all areas to the left.
OppositeBacktracker and OppositeFlooder don't know the location of the target square. But as the start and target squares are always chosen close to opposite borders of the maze, they often produce similar results as the proximity guided solvers.
Outline shapes are completely obliterated when large sections of the maze are visited. An efficient solver will not paint all squares in the same color and the shape will still be visible.
The ThickestBranchFlooder advances on a chosen branch in one run up to the next fork; then another branch is better than the split branches at the fork. The percieved movement is rather "jumpy", even at moderate speed.
ForwardFlooder and BackwardFlooder tend to fill the whole maze, just like a HesitatingFlooder. That is because both solvers assign highest penalties to undesired steps near the target square: the BackwardFlooder assigns an extreme penalty (100%) to the last step onto the target square; the ForwardFlooder assigns very high penalties to backward steps close to the target. In that situation, both solvers will visit the whole rest of the maze before doing the one highly penalized required step.
RandomForwardFlooder and RandomBackwardFlooder are able to overcome these problematic situations because their choice is not fixed. Sometimes they may choose the path with higher penalties and thus make the necessary but locally unfavorable step.
In the SpreadingFlooder, the pair of paths closest to each other advances in parallel. When one path is split or gets closer to a different path, it forms a new partnership with the other closer partner.
Efficient Solvers often run for long stretches without error (i.e. without leaving the correct solution path), especially towards the end. It is not unlikely that such a run spans more than half or two thirds of the solution path. Even perfect runs without any error at all can be observed. Considering that an average path may have several dozens or even hundreds of forks, this is quite amazing.
That gives a very large number of pattern or style combinations:
The exact application of each variant is usually (with a few deterministic exceptions) influenced by random parameter values: outline shapes are generated dynamically, solvers choose arbitrary paths and the maze builder generates random patterns of walls.