Задача поиска выхода из лабиринта имеет множество известных алгоритмических решений. Одно из них - «правило левой руки». Оно заключается в том, что на каждом повороте следует поворачивать налево. Если возможность повернуть налево отсутствует, то нужно идти прямо. Если и туда нельзя, то направо. Если впереди тупик, то надо развернуться. Такой алгоритм поведения находит выход только из односвязных (не содержащих замкнутых маршрутов) лабиринтов, а также легко описывается описывается как с помощью любого алгоритмического языка, так и с помощью конечного автомата [1]. Целью работы является сравнение этих двух способов описания алгоритма при разработке программы.

Программа Maze – это симулятор произвольного односвязного лабиринта с исполнителем-роботом, который проходит лабиринт. Во время разработки программы был проведен эксперимент, связанный с ее разработкой. Было разработано две версии программы, идентичных по функциональности и интерфейсу, но отличающихся реализацией алгоритма поиска выхода. В первой версии алгоритм был написан вручную, а во второй применен сгенерированный из схемы конечный автомат [2]. Для генерации автомата была использована программа Visio2Auto Л. Столярова [3]. Этот эксперимент был проведен для выяснения того, действительно ли автоматное программирование упрощает разработку.

Как оказалось, представление алгоритма в виде автоматной схемы действительно сильно снижает сложность разработки программы. Для простоты понимания алгоритма работы программы, рано или поздно придется рисовать схему в Microsoft Visio или аналогичных редакторах и заботиться о ее соответствии фактическому коду программы, а в случае автоматного подхода изначально нарисованная схема легко транслируется в код без участия человека. А это значит, что, по сути, нарисованная схема являет собой уже большую часть сделанной работы. Кроме того, автоматическая трансляция исключает человеческий фактор при кодировании логической части алгоритма, являющийся источником ошибок.

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

Программу Maze также можно использовать как небольшое учебное пособие по конечным автоматам на примере данного конечного автомата в данной задаче, благодаря реализованной системе простых сценариев (скриптов) для консоли. Это значит, что написав небольшой сценарий, вы можете оставить пользователя наедине с программой, и она сама объяснит ему, как работают конечные автоматы в данной задаче.

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

Программа разработана на языке С++ в средах Microsoft Visual Studio, KDevelop и Qt Creator в операционных системах Microsoft Windows и Linux с использованием кроссплатформенной библиотеки Qt [4].