Вы любили в детстве разгадывать лабиринты? Искать выход из сложных переплетений, напечатанных в журналах с головоломками? Может быть, вы помните легенду о нити Ариадны или игру с пространством в фильме «Начало»? У всех этих лабиринтов был один минус. После того, как путь найден, уже не составляло труда пройти по нему снова.
Поэтому разработчики уже давно озаботились вопросом того, чтобы создавать лабиринты «на лету» и использовать их в своих проектах. Только представьте, что перед вами каждый раз – совершенно новый мир, в котором проверенная схема уже не действует и нужно искать новый путь.
Для этих целей я написал собственную программную библиотеку Mazeraptor. По-русски это слово звучало бы как-то навроде «Лабиринторатопс». Знаю, выглядит ужасно, а произнесение вслух может разбудить каких-нибудь древних богов, поэтому оставлю его, как есть, в своём изначальном варианте.
Что же нужно для создания лабиринта? Нужна некая структура, которая будет описывать положение его «комнат» относительно друг друга. Это может быть просто прямоугольная сетка с клетками, как в тетради, где каждая клетка исполняет роль такой комнаты. А может быть и множество колец друг в друге, разделённых на ячейки. Здесь всё ограничено только вашей фантазией. Главное, чтобы вы смогли объяснить логику своей структуры на понятном языке.
Бамс 
Бамс
Как видите, моя библиотека умеет выдумывать и по-ньюйоркски прямоугольные лабиринты, и по-московски кольцевые. Скажу больше, в ней ещё реализована возможность создавать лабиринты в виде пчелиных сот или треугольной плитки. А на десерт – структуры из своих собственных изображений. Как, например, эта.
(Не)удивительно, но помимо формы и структуры лабиринтов теоретики также выдумали немало способов непосредственно его создания. Ведь мало организовать отдельные ячейки в структуру, нужно рассказать им, из какой в какую существует проход, а какие закрыты друг от друга глухой стеной. Все вышеприведённые примеры были созданы с помощью алгоритма обратного прохода. Но есть и другие. Например, алгоритм растущего дерева или алгоритм Prim.
Алгоритм растущего дерева 
Алгоритм Prim
Понимаю, в целом всё выгядит одинаково запутанно. Поэтому я добавил цветовую индикацию того, в каком порядке обрабатываются ячейки. От тёмных к светлым. Видите разницу? На картинке справа прослеживается характерная черта Prim – множество коротких тупиковых ответвлений. Можете вернуться к первым двум картинкам и взглянуть на ход работы алгоритма обратного прохода (его характерная особенность – длинные закрученные ходы).
Не составляет также труда для моей программы найти путь из ячейки А в ячейку Б. Причём начальную и конечную точку вы можете указать абсолютно любую. А для поиска использовать различные алгоритмы, в том числе и A Star. Надо сказать, что в среде компьютерных игр это, пожалуй, один из самых распространённых способов поиска пути. Играете ли вы в стратегии или шутеры, будьте уверены, где-то там под корпусом вашего ПК или консоли маленькие единицы и нули скачут под его управлением. Уже не удивлю вас, сказав, что придумано и множество других алгоритмов, решающих ту же задачу. Всем заинтересованным могу намекнуть, что смотреть стоит в сторону теории графов, о которой я вам как-нибудь обязательно расскажу.
Если же вы в целом интересуетесь темой создания лабиринтов, обратите внимание на книгу Jamis Buck «Mazes for Programmers», которая невероятно помогла мне в работе. На этом, пожалуй, достаточно слов. Оставляю ссылку на архив со своим генератором здесь. А также ссылку на github для тех, кому нужен функционал библиотеки. Играйтесь, ищите, создавайте и не забывайте делиться со мной своими впечатлениями.