/ Projects / The robot, searching an exit from the maze
(версия для печати)
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)
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 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:
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.