ITMO University
“Programming Technologies” Department

The robot, searching an exit from the maze

(C) 2003 M.A. Podtopelny, A.A. Chebotareva, A.A. Shalyto

Saint-Petersburg State Institute of Fine Mechanics and Optics (Technical University)

From here it is possible to download the full text of documentation in Russian in a PDF-format (210 Kb)

Annotation

Many ways of solving the problem of searching an exit from the maze were suggested since it's appearance. Very convenient technology for solving and algorithmizing this problem is SWITCH- technology. You can find more detailed description of this technology and samples at http://is.ifmo.ru and http://www.softcraft.ru.

The purpose of this article is to realize the "left-hand" maze beat algorithm. The idea of this algorithm is to walk holding the left hand on the left wall. This means that every cross you must choose the most left corridor.

The environment able to display the checked field on which may be set some walls forming the maze was developed to realize the project.

The robot whose intellect is described by the finite automata transition graph is used to beat the maze. Robot's actions are recorded.

The limitations for the mazes able to be used are:

• the maze must be two-dimensional;
• all it's corridors must be either parallel or perpendicular to each other;
• the maze mustn't evaluate.

The walls' width and corridors' width are assumed to be a constant through this assumption doesn't influence the problem's solution. Besides the maze contains crosses where at the minimum two corridors of two different directions "meets".

The input data is given in xml-file which contains:

• maze size;
• entrance (point S) coordinates;
• exit (point F) coordinates;
• maze configuration (the list of coordinate pairs which define the maze walls).

The Flash-technology and Action Script language were chosen to realize the project through they are the most perspective and convenient instruments for visualizing Internet-related applications. Using them and automata method made the developing process easy and the project obvious.