Журнал удивительных идей


Совместный проект учителей и учеников 192 школы

Строим лабиринты

Алгоритмы поиска пути в лабиринте знает практически каждый. А о построении лабиринтов говорят не часто. Можно ли поручить компьютеру это ответственное дело - сгенерировать хороший лабиринт, скажем, для игровой программы?

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

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

Одним из алгоритмов, дающим хорошие результаты в решении нашей задачи, является алгоритм Крускала. Если описывать без подробностей, то получится по-настоящему в двух словах:

  1. Составляем список всех стен (массив) в произвольном порядке.

  2. Проходим по списку, разрушая очередную стенку в том случае, если не существует пути из одной комнаты в другую, которые она разделяет.

Вот, собственно, и все.

Например, в лабиринте

в ходе работы алгоритма уже разрушено несколько стен (они обозначены темно-серым). Синяя стена разрушена не будет: красная стрелка показывает путь из одной комнаты в другую. А вот зеленая или (исключающее) оранжевая стенки будет разрушена. Причем та, которая будет просмотрена раньше. Разрушение одной из этих стен открывает путь из одной комнаты в другую (разделенных второй стенкой).

Остается доказать, что данный алгоритм строит хороший лабиринт, хотя можно сказать, что это очевидно.

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

Каким образом можно "перемешать стены"?

Классическая задача: есть массив, надо перемешать элементы этого массива (тоже, кстати, интересно. О сортировке массива говорится часто, a об обратной задаче - гораздо реже.) Обычно эту задачу пытаются решить так. Заводят дополнительный массив того же размера. Проходят по исходному массиву и для каждого элемента выбирают случайное место в новом массиве. Если оно не занято, то кладут туда текущий элемент и сразу переходят к следующему. Если оно занято - выбирают новое случайное место. Далее дополнительный массив перекладываем в исходный, и задача решена. У такого способа два недостатка. Требуется дополнительный массив, а потом долго (а может быть, очень долго?) алгоритм работает в конце. Представим себе, что надо мы разложили 999999 элементов и осталось положить последний миллионный. Тогда, нам будет надо дождаться, пока датчик псевдослучайных чисел "выкинет" номер единственного свободного места - одно число из миллиона. По правде говоря, реальная такая программа закончит свою работу очень быстро, но все же не стоит злоупотреблять быстродействием современных машин: алгоритм абсолютно неэффективен!

А ведь эффективный алгоритм очень прост: возьмем пару произвольных элементов (два случайных числа-места) и обменяем их местами. Произведем операцию много раз и все - массив перемешан. Работает без простоев.

Каким образом можно узнать, есть ли путь из одной комнаты в другую?

Можно воспользоваться классическим алгоритмом "волновой трассировки". Открываем в исходной комнате кран с водой. По лабиринту бежит волна. Если в результате конечную комнату тоже заливает - путь есть, иначе нет.

Ну а "по-научному", так:

  • Заполняем все ячейки-комнаты нулями, а в исходной комнате ставим единицу (в комнате волна).

  • Проходим многократно по всему лабиринту и во всех комнатах, соседних с теми, в которых 1, проставляем тоже 1.

Если на каком-то шаге мы проставляем единицу в конечную комнату - путь есть.
Если после очередного прохода не проставлено ни одной единицы - пути нет.

Ильин В.В.

М
а
т
е
м
а
т
и
к
а
Ф
и
з
и
к
а
Х
и
м
и
я
Б
и
о
л
о
г
и
я
И
н
ф
о
р
м
а
т
и
к
а