Робот, ищущий выход из лабиринта

(C) 2003 М.А. Подтопельный, А.А. Чеботарева, А.А. Шалыто

Санкт-Петербургский государственный институт точной механики и оптики (технический университет)

Аннотация

С тех пор, как впервые появилась проблема поиска выхода из лабиринта, было предложено множество способов ее решения. Для алгоритмизации и программирования решения этой задачи, оказалось удобным применить SWITCH-технологию. Подробно ознакомиться с этой технологией и с конкретными примерами ее использования можно на сайтах http://is.ifmo.ru и http://www.softcraft.ru.

Целью настоящей работы является реализация алгоритма обхода лабиринта по правилу "левой руки". Правило "левой руки" состоит в том, что робот идет, постоянно "держась рукой" за левую стену. При этом на каждом шаге выбирается самый левый из существующих коридоров.

При реализации проекта была разработана среда, способная отображать клетчатое поле, на котором для формирования лабиринта могут быть расставлены стены.

Для прохода по лабиринту применяется робот, интеллект которого описывается графом переходов конечного автомата. Действия робота протоколируются.

При использовании среды могут быть построены лабиринты, отвечающие следующим требованиям:

• лабиринт плоский (не имеет третьего измерения);
• все его коридоры параллельны или перпендикулярны друг другу;
• лабиринт не меняется во время его прохода роботом.

Толщина стен и коридоров лабиринта считается одинаковой, так как это не влияет на решение задачи. Кроме того, лабиринт содержит перекрестки, в каждом из которых "встречаются" как минимум два коридора разных направлений.

Входные данные для среды задаются xml-файлом, в котором указаны:

• размеры лабиринта;
• координаты точки входа в лабиринт S;
• координаты точки выхода из лабиринта F;
• конфигурация лабиринта (список пар координат, задающих стены лабиринта).

Для реализации проекта были выбраны технология Flash и язык Action Script, как наиболее перспективные и удобные инструменты для визуализации проектов, работающих в сети Internet. Использование этих средств, а также автоматного подхода, позволило обеспечить удобство разработки и наглядность проекта, а также резко сократить трудоемкость написания программы.