- Too see this applet, you must have a JAVA enabled browser -

Click toggles the cell state. Ctrl+Click changes the target. Shift+Click adds a bomb.

ChatChat   Explain The Maze

Genetic Algorithms

Genetic Algorithms (GA) are based on an evolution of random tries by 'individuals', not on logic as regular algorithms. It is a computer simulation of Darwins theories. Though the whole prosess is built on randomness, the effect is not. It seeks towards the 'solution'

The 'God' in a GA is the Objective function, which determines fitness of each individual. Only the better fit 'individuals' survive to breed. Children are bred by combining the traits of the 2 parents. Traits are codings the domain knowledge, i.e. the genes. The Maze Solver knows 4 directions (N)orth, (S)outh, (E)ast and (W)est. A series of these combine to make a path. The path is evaluated, based on how close the end-point is to the target.

Each cycle in the process of: evaluation, selecting survivors, breeding, evaluation, etc. is called a generation. The GA continues the iteration of generations until the goal is found or some other end criterea occurs.

Mutation helps prevent a degenerate population, which tends to settle prematurely at a non-optimum solution.
Optimization can improve both the GAs speed and capability to solve problems.

"GAs do not find the best solution, they find the first". (unknown)

About - Maze Solver

Maze solver is a configurable genetic algorithm.
It does not find the optimal path, but usually finds a path to the target.
Each gene consist of a string of directions ('N', 'E', 'S' & 'W').

The solver starts at coordinate (0,0) and tries to step in the first direction.
If the cell is free, the step is successful, and the current standing point is updated.
Then it repeats the same for the rest of the gene's values.
The standing point after all steps is called the end-point.

The genes fitness is the negative of the distance between the end-point and the maze's target point, i.e. the closer the end-point is to the target point, the better the fitness.

A Maze Solvers generation step consists of

  1. Select survivors, i.e. the genes with the highest fitness
  2. Add new (random) genes to survival population
  3. Cross survivor population to create the next generation1 .
  4. Mutate
  5. 'Optimize'2
  6. Evaluate
  7. Sort according to weight (only to help the survivor selection)
  8. Show best fit genes (only to see how the GA evaluates)
  9. Resolve Crowding3
  10. Mutate Maze4 if option is chosen

1 Best fit genes are over-represented in the mother population.
2 A number of optimizations are applied
3 Crowding occurs in the vicinity of the best-fit gene's end-point.
4 Maze mutation is activated manually, but the mutation parameters are fixed.

New in version 2.1.4

A dead-end detection is added. If the best fitness is the same over several runs, the end-point is marked as a dead-end by placing a bomb on the cell.

The Maze

To start the Maze Solver, press 'Start'. (If nothing happens, the starting position, at the upper left corner, is probably blocked. Free some cells, so it is possible for the genes to 'escape' the starting point).

The Maze Solver attempts to find the path to the target (red dot). The genes are displayed alternate green-blue as they are evaluated. If a gene encounters a bomb (light red dots), it is killed. The target (red dot) can be changed by Ctrl+Click. New bombs (light red dots) can be added by Shift+Click

The maze pattern is generated randomly. You can adjust the number of blocked and free cells by changing the blockRatio. Click toggles the cell state between blocked-free. 'Regular' mazes must be built manually.

After a run is completed, the 3 best fit genes are displayed.

The GA completes when either the target (red dot) is encountered or max number of generation steps is reached.

Solving a maze is easy from above. Here's a Maze applet, by Paul Falstad, that lets you try to solve a Maze at ground level.


  1. Stop the Maze Solver if it is running.
  2. Configure Maze
    - Clicking on a cell toggles the cell state.
    - Clicking on a cell while holding down the Control key changes the target point
    - Clicking on a cell while holding down the Shift key adds a bomb (cannot be removed)
    (Cells can be configured while the Maze Solver is running !)
  3. Configure Parameters

Resizing the Maze

You can resize the maze by adjusting the row and column counts. If so, you should also adjust the gene size, which determines the number of steps in the path. A rule of thumb is,

Gene Size = 2 * (Row Count + Column Count)

Note that if you reduce the maze size, the target point may fall outside the maze. If this happens, use Ctrl+Click to reposition the target.



Keep ratios in the range (0.0 <= r <= 1.0).
Other parameters must be positive integers, except lockCount which can also equal 0.


Maze Solver uses some parameters internally that cannot be configured:

Best-fit gene over-representation = on
The best fit genes are over-represented in the 'mother' population, i.e. the group of genes which are crossed to produce the next generation genes.
Best fit gene - 3 extra instances
2nd best gene - 2 extra instances
3rd best gene - 1 extra instance
Note: The extra instances are only used as a base for crossing.
crowding radius = 1.5
The distance from a gene's end point
to the end point of the best fit gene.
A value of 1.5 hits all genes adjacent to the best fit gene.
Genes within this radius are forced to mutate.
(Note: locked genes never mutate).
Included to help gene pool from becoming degenerate.
Maze Mutation settings
Auto mutation of the maze is activated manually, but the mutation rules/parameters are fixed.
If activated, the following parameters apply to the Maze mutation
Dead-end detection delay = 4 generations
If the best fitness does not progress within the number of generations in the delay, the end point of the best-fit gene is marked as a bomb. Bombs kill genes. This helps the algorithm choose new paths.


Optimization tunes the GA to a specific problem, i.e. the Maze. The Maze Solver applies a number of optimization techniques, e.g. loop truncation and redundant step elimination. Optimization is not necessarily confined to the step indicated above. Disabling optimization leaves the 'pure' GA.

Known Bugs

Maze Solver 2.0 is compiled using JDK 1.1, and tested using Netscape 4.0 for WindowsNT. If you are using an older browser or a browser incompatible with JDK 1.1, this version will not load/run correctly.

Please send an e-mail if you detect other bugs. Remember to include you browser type and version and the platform (Operating System) you are using.

More Information

Some indexes

Solving a maze is easy from above. Here's a Maze applet, by Paul Falstad, that lets you try to solve a Maze at ground level.

Genetic Algorithms are derived from Darwins theory of evolution. Check out Web Sites in General Anthropology, Evolution, and Genetics for more information. The works of Charles Darwin are also available on-line.

'Advantages of Using G.A.s for Game Problems' and more, visit Genetic Algorithms and Games Theory.
Traveling Salesman Solver, by Thomas Pederson., is a GA for the Travelling Salesman Problem.
A Fast TSP Solver from Hitachi.
"The Hitch-Hiker's Guide to Evolutionary Computation". FTP to the FAQ for comp.ai.genetic.


Any comments or suggestions are welcomed !

(Here's a review of Maze Solver v 1.1 in the 1st of September 1996 edition of JavaWorld).

Contact me through: arild@beteco.com

This chat client is intended for chat's about the MazeSolver and GAs

You are visitor number since August 15, 1996
Last updated Dec 02, 1999