Построение лабиринтов. В компьютерных играх действие часто происходит в лабиринте. При этом не важно, как именно этот лабиринт выглядит. Это может быть система соединяющихся подземных пещер или коридоры космической станции. Главное, должно быть какое-то пространство, по которому можно передвигаться, и должны быть стены (или другие препятствия), мешающие прямолинейному движению игровых персонажей. То есть для того, чтобы пройти из одной точки в другую, мы должны сначала дойти до поворота, свернуть направо, затем два раза налево, потом снова направо и ещё три раза налево... Что-то в этом роде. А идти прямо мы не можем, мешают стены. Это и есть лабиринт. В нём даже можно заблудиться. Или искать в нём прячущихся врагов. Словом, лабиринты присутствуют во многих играх. Обычно разработчик компьютерной игры сам придумывает, как именно будут располагаться стены в его лабиринте, то есть рисует лабиринт где-нибудь на бумаге. Если то, что он нарисовал, ему нравится, он записывает этот лабиринт в файл. А компьютер потом каждый раз считывает лабиринт из файла, когда кто-нибудь начинает играть в игру. Главный недостаток этого метода заключается в том, что лабиринт не меняется, он всё время один и тот же, а именно такой, какой записан в файле, и другим он не может быть. И если Вы сто раз будете играть в эту игру, то сто раз у Вас будет один и тот же лабиринт. Я думаю, что, когда Вы выучите все повороты наизусть, Вам играть будет уже не интересно. В самом деле, что это за лабиринт, если выход из него всем известен?

Существует другой способ создания лабиринтов. Нужно, чтобы компьютер сам строил лабиринт случайным образом, а не считывал из файла уже готовый. В этом случае у нас каждый раз будет новый уникальный лабиринт, и играть станет интересно. Можно просто взять пустое пространство и произвольно расположить в нём стены. Но к сожалению, в этом случае у нас могут образоваться замкнутые области, из которых не будет выхода, а нам этого совсем не нужно. Нам-то нужен лабиринт, а не тюрьма. Таким образом, проблема сводится к следующему: так расположить стены в пространстве, чтобы не допустить образования замкнутых областей, то есть, чтобы ИЗ ЛЮБОЙ ТОЧКИ ЛАБИРИНТА МОЖНО БЫЛО ПОПАСТЬ В ЛЮБУЮ ДРУГУЮ ЕГО ТОЧКУ. Для этого откажемся от идеи хаотично располагать стены на пустом месте. Поступим по другому. В качестве основы возьмём любой готовый лабиринт, удовлетворяющий нашему условию. (Под 'условием' подразумевается принцип, что из любой точки существует путь в любую другую точку). Далее случайным образом выберем одну из стен и переставим её на другое место, тоже выбранное случайно. И если мы найдём способ при перестановке стены не нарушить условие, о котором говорилось выше, то задача будет решена. Ведь, выполнив операцию перестановки случайной стены на случайное место много-много раз, мы получим случайный лабиринт, совсем не похожий на исходный. К тому же новый лабиринт также удовлетворял бы нашему условию, поскольку при перестановке стен это условие никогда бы не нарушалось.

Теперь для наглядности представим, что мы рисуем наш лабиринт на листе клетчатой бумаги. Потенциально каждая клетка может быть ограничена стеной слева, справа, сверху, снизу или сразу с нескольких сторон. Клетку будем называть клеткой, стену - стеной, а то место, где могла бы быть стена, но её там нет, назовём 'пустым местом'. Далее выберем одну из клеток (назовём её 'база') и будем считать, что мы ходим по лабиринту и ищем дорогу к этой базе. А чтобы нам это было легче сделать, в каждой клетке поставим указатель, показывающий путь к базе. Таким образом, из любой клетки можно попасть в базу, достаточно лишь идти по указателям. Более того, из любой клетки можно попасть в любую другую клетку. Для этого переместим базу в эту последнюю клетку, и тогда все указатели будут показывать путь уже к ней. А перемещать базу будем так: выберем место для новой базы, пройдём по цепочке указателей от новой базы до старой и развернём их в сторону новой базы. Обратите внимание, мы не разворачиваем каждый указатель на 180 градусов, но новое положение указателя из текущей клетки будет соответствовать старому положению указателя из предыдущей клетки, развёрнутому на 180 градусов.

Кстати эта система указателей может пригодиться потом при программировании поведения игровых персонажей. Раз мы можем, перемещая базу, сделать так, что все указатели лабиринта будут показывать путь к нужной нам клетке, то персонажи игры (например, инопланетные монстры) всегда будут знать дорогу в любую точку лабиринта, а не будут блуждать, натыкаясь на стены. То есть они будут выглядеть 'умными'. Им просто надо будет идти по указателям. Но сейчас указатели нам нужны для другой цели. Напомню, что нам нужно случайным образом переставить стену и при этом не допустить образования замкнутых областей. Выберем любую стену. Эта стена отделяет друг от друга две клетки. Назовём их 'клетка X' и 'клетка Y'. Найдём путь из клетки X в клетку Y. Для этого переместим базу в клетку Y описанным выше способом. Теперь, если из клетки X пойти по указателям, то мы попадём в клетку Y. Это и есть искомый путь. Назовём его 'ПУТЬ'. Если убрать стену, то из клетки X в клетку Y можно будет попасть двумя способами: по ПУТИ и напрямую, через то место, где была стена. То есть ПУТЬ замкнётся, превратится в замкнутый контур. И из любой клетки, принадлежащей ПУТИ можно будет пройти в любую другую клетку, также принадлежащую ПУТИ двумя маршрутами, а именно: по часовой стрелке и против часовой стрелки. Оба эти маршрута будут являться частями образовавшегося контура.

А значит, ПУТЬ можно разорвать, поставив стену на любое пустое место, принадлежащее ПУТИ. При этом замкнутых областей в лабиринте не возникнет, поскольку сохранится один из двух маршрутов, соединяющих любые две клетки ПУТИ. Так, если новая стена перекроет маршрут по часовой стрелке, то останется маршрут против часовой стрелки, и наоборот. Если пройти по указателям из клетки X в клетку Y, то мы увидим, что каждый из них указывает на какое-либо пустое место. В одном из этих пустых мест мы и можем поставить стену. Теперь нужно лишь внести пару изменений в систему указателей. Сейчас получается, что один из указателей показывает прямо на новую стену (раньше здесь было пустое место). Так быть не должно. Вместо указателя в этой клетке разместим базу. Теперь у нас в одном лабиринте две базы. Это тоже не правильно. Поэтому старую базу заменим на указатель. Напомню, что старая база была в клетке Y. Между клеткой Y и клеткой X была стена. Теперь этой стены нет. Значит правильное направление для нового указателя в клетке Y такое, чтобы он показывал в сторону клетки X. Вот и всё. Мы нашли способ случайным образом переставить одну стену лабиринта на новое место, не допустив при этом появления замкнутых областей. Если выполнить это действие, например, 10000 раз, то исходный лабиринт изменится до неузнаваемости. Поэтому для удобства в качестве исходного лабиринта можно взять какую-нибудь простую систему стен и указателей.

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

Когда после перестановки стен окончательный вариант лабиринта будет готов, его можно будет изобразить на экране компьютера различными способами, стены могут быть узкими или широкими. Указатели и базу, конечно, рисовать на экране не нужно, они должны быть скрытыми. Следует отметить, что здесь рассматривался лабиринт, в котором для любых двух клеток существует ОДИН И ТОЛЬКО ОДИН соединяющий их путь. Если Вы не хотите программировать умных монстров, знающих верную дорогу в лабиринте, то есть если система указателей после построения лабиринта Вам больше не нужна, то можно будет убрать ещё несколько случайных стен и получить лабиринт, в котором некоторые клетки будут соединяться более, чем одним путём.