Создание лабиринта
Мозговой Максим Владимирович - Занимательное программирование: Самоучитель
Глава 4 Лабиринты
В лабиринте у вас, по крайней мере, есть цель.
Евгений Кащеев
Мне нравится эта тема. С одной стороны, она занимательна, с другой — полезна (я надеюсь, что вы найдете не одно и не два применения алгоритмам, описанным в этой части книги), а с третьей — даже научна. Лабиринты, выражаясь математическим языком — это графы; все алгоритмы, которые мы рассмотрим, соответственно, являются алгоритмами на графах. Графам же посвящена целая теория в математике (она так и называется: теория графов). Недаром два алгоритма, с которыми вы познакомитесь в этой главе, носят имена Прима (Prim) и Краскала (Kruskal) — очень известных в теории графов людей.
Итак, сейчас мы займемся лабиринтами. Если говорить более конкретно, в область наших интересов входят следующие задачи:
1. определить, что такое лабиринт и как представить его в памяти компьютера; 2. договориться, что значит «решить» лабиринт и как это сделать; 3. выяснить, как лабиринт может быть создан компьютером автоматически.
Представление лабиринтов в памяти
Толковый словарь русского языка определяет лабиринт как «запутанную сеть дорожек, ходов, сообщающихся друг с другом помещений». Пожалуй, это определение слишком неконкретное и чересчур общее для наших целей. Сразу скажу, что наши лабиринты — плоские (двумерные, если угодно), поэтому их можно легко нарисовать на бумаге. Кроме того, все помещения (их обычно называют локациями) будут квадратными, а сам лабиринт (естественно) — прямоугольным. У каждого такого помещения есть не более четырех соседних, и в каждое соседнее помещение может вести проход (а может и не вести — в этом случае там будет «стена»). Думаю, проще всего посмотреть на пример (рис. 4.1).
Рис. 4.1. Пример лабиринта
Именно с лабиринтами такого типа мы и будем работать. Следующий вопрос — как представить лабиринт в памяти компьютера. Заманчиво просто создать двумерный массив из нулей и единиц: нуль будет обозначать стену, единица — проход (рис. 4.2).
Рис. 4.2. Простое представление лабиринта в памяти
Надо только при выводе на экран рисовать стенки тонкими линиями (я не стал этого делать для наглядности) — и все. Этот способ, в принципе, позволяет описать любой лабиринт «нашего» типа. К сожалению, есть у него и существенный недостаток: если разрушить любую стену (то есть поменять нуль на единицу), в лабиринте образуется новая локация на месте разрушенной стены. Сейчас это, вроде бы, и не имеет значения, однако для алгоритмов генерации лабиринтов, которые мы изучим, подобное поведение недопустимо. При разрушении стены должен открываться проход, но никак не образовываться новая локация. Поэтому нам придется воспользоваться не столь простым и удобным, зато лишенным этого недостатка методом.
В каждой локации лабиринта нас интересует информация о стенах/проходах. В локации может существовать от одной до четырех стен (сверху, снизу, слева и справа). Поэтому разумно задавать локацию записью:
type Location = record
left_wall, right_wall, up_wall, down_wall : Boolean;
end;
Если значение поля равно true, значит, соответствующая стена существует, иначе — нет. Обратите внимание, что правая стена любой локации и левая стена локации, находящейся справа от нее, — это одна и та же стена. То же самое справедливо для всех остальных стен — любая из них принадлежит одновременно двум разным локациям. Отсюда вывод: нет нужды хранить в каждой записи информацию обо всех четырех стенах. Достаточно выбрать две: горизонтальную (к примеру, верхнюю) и вертикальную (к примеру, левую). Тогда запись
Location станет еще более простой:
type Location = record left_wall, up_wall : Boolean;
end;
Сам лабиринт будет представлять собой двумерный массив таких записей: type Maze = array of array of Location;
При этом нельзя забывать о правиле: лабиринт везде по краям должен быть ограничен стеной. Ничего не стоит «построить» стены сверху и слева — для этого надо лишь следить, чтобы значение поля up_wall у всех локаций, расположенных в самом верху лабиринта, и значение поля left_wall у всех локаций, расположенных по левому его краю, были равны true. Справа и снизу лабиринт не ограничить так просто. Помните, мы исключили поля right_wall и down_wall из типа Location? Самое простое решение проблемы заключается в том, чтобы добавить еще ряд локаций справа и внизу лабиринта. Если установить равными true значения полей up_wall и left_wall у этих, дополнительных, локаций, мы получим как раз те стены, которые нам нужны. Думаю, излишние объяснения только усложняют простую идею. Желаете иметь стену справа? Установите значение поля left_wall равным true у локации, расположенной справа от текущей. Требуется стена снизу? Установите значение поля up_wall равным true у локации, расположенной снизу от текущей.
В дальнейшем нам потребуются процедуры загрузки/сохранения лабиринта. Давайте напишем их сейчас.
Поскольку пока еще у нас нет возможности сгенерировать лабиринт автоматически, я решил, что разумно хранить его в текстовом файле — так, по крайней мере, вы сможете вручную создать какой-нибудь тестовый пример. Структура файла будет простой. В первой строке запишем два числа — ширину и высоту лабиринта. Затем в файле последует еще столько же строк, сколько локаций в лабиринте. В любой из этих строк будет храниться пара чисел, каждое из которых равно либо нулю, либо единице. Первое число показывает наличие стены сверху, а второе — стены слева в текущей локации. Локации хранятся последовательно, строка за строкой.
Остается выяснить, что же делать с дополнительными, «служебными» локациями, которые ограничивают лабиринт справа и снизу. Давайте договоримся, что они все-таки не являются частью лабиринта. Если размеры поля равны 10 ? 20, то и в файле будут записаны эти числа, а общее количество сохраненных локаций окажется равным 10 ? 20 = 200. Реально же в памяти будет храниться матрица 11 ? 21, но в файле служебные локации хранить незачем — мы и так прекрасно знаем, какие стены в них должны существовать (на практике проще всего указать существование обеих стен, чтобы не думать, где именно находится та или иная служебная локация).
Для примера можете воспользоваться определением маленького лабиринта (5 ? 4), который я только что набросал на бумаге: 5 4 1 1 1 1 1 0 1 1 1 0 0 1 1 0 0 1 0 0 1 1 0 1 1 0 1 0 0 0 0 0 1 1 0 0 0 1 0 1 0 1
Процедура чтения лабиринта приведена целиком ниже:
{ загрузить лабиринт }
procedure LoadMaze(var TheMaze : Maze; FileName : string);
var f : TextFile; { файл с описанием лабиринта }
Height, Width : Integer; { высота и ширина лабиринта }
x, y : Integer; { текущая локация }
lw, uw : Integer; { временные переменные }
begin
AssignFile(f, FileName); { открыть файл }
Reset(f);
ReadLn(f, Width, Height); { прочитать высоту и ширину }
SetLength(TheMaze, Width + 1, Height + 1); { изменить размер лабиринта }
for y := 0 to Height do { цикл по всем локациям }
for x := 0 to Width do
if (y = Height) or (x = Width) then { если локация - служебная }
begin
TheMaze[x, y].left_wall := true; { обе стены существуют }
TheMaze[x, y].up_wall := true;
end
else
begin { иначе считываем }
ReadLn(f, uw, lw); { из файла }
TheMaze[x, y].left_wall := Boolean(lw); { прочитанное целое }
TheMaze[x, y].up_wall := Boolean(uw); { число надо привести }
end; { к типу Boolean }
CloseFile(f);
end; { закрыть файл }
Обратите внимание на некоторые тонкости. Во-первых, в качестве размеров сторон при вызове SetLength() указываются значения Width + 1 и Height + 1: как мы и договорились, лабиринт будет на одну локацию выше и на одну локацию шире. Во-вторых, реальные индексы в динамических массивах начинаются с нуля (мы уже сталкивались с этим), поэтому первоначальное значение счетчика каждого цикла тоже равно нулю. В-третьих, не забывайте о преобразовании считанного целого к типу Boolean. Вообще говоря, подобные операции не слишком приветствуются, однако сейчас мы точно уверены, что чисел, кроме нуля и единицы, в файле нет.
Процедура записи выглядит немного проще:
{ nio?aieou eaae?eio }
procedure SaveMaze(TheMaze : Maze; FileName : string);
var f : TextFile; { файл с описанием лабиринта }
Height, Width : Integer; { высота и ширина }
x, y : Integer; { координаты текущей локации }
begin
AssignFile(f, FileName); { открыть файл }
Rewrite(f); { для записи }
Height := High(TheMaze[0]); { определяем высоту }
Width := High(TheMaze); { и ширину лабиринта }
WriteLn(f, Width, ' ', Height); { запись в файл высоты и ширины }
for y := 0 to Height - 1 do { запись данных локаций }
for x := 0 to Width - 1 do
WriteLn(f, Integer(TheMaze[x, y].up_wall), ' ',
Integer(TheMaze[x, y].left_wall));
CloseFile(f); { закрыть файл }
end;
Главная «хитрость» здесь — это определение размеров лабиринта. Не забывайте, что двумерный массив по сути дела является массивом, каждый элемент которого — одномерный массив. Размер этого «супермассива» в данном случае равен ширине лабиринта (потому что мы именно так его описали — как массив, каждый элемент которого есть столбец из локаций). Размер же каждого его элемента (то есть одномерного массива) равен, соответственно, высоте лабиринта. Поэтому, чтобы определить ширину, я использую вызов
Width := High(TheMaze);
Функция High(), как вы, надеюсь, помните, возвращает наибольший возможный индекс в массиве. Если размер массива равен N, то его индексы лежат в пределах [0…N-1]. Однако мы выделили память для одного лишнего элемента (столбца служебных локаций), поэтому в нашем случае этот диапазон равен [0…N]; High(TheMaze) вернет N, что нам, собственно, и требуется.
Чтобы определить высоту, надо взять любой столбец (то есть любой элемент массива TheMaze) и вызвать для него High(). Я взял нулевой.
При записи в файл служебные локации игнорируются, как было оговорено выше.
Давайте еще напишем процедуру, которая рисует лабиринт на главной форме приложения, чтобы в дальнейшем не отвлекаться на этот процесс. Я предполагаю, что главная форма называется Form1, а на ней расположены объекты Screen и BackBuffer (оба имеют тип TImage). Как и раньше, объект BackBuffer служит для двойной буферизации (не забывайте, он должен быть невидимым). Я использую этот механизм здесь потому, что кое-какая анимация у нас в дальнейшем будет.
Вы, наверное, уже обратили внимание: раньше я использовал элемент TPaintBox для вывода на экран, теперь же решил ограничиться типом TImage. Разница между этими в общем-то похожими компонентами заключается в том, что TImage «запоминает» свой рисунок. Если вы поместите на форму элемент TPaintBox, нарисуете на нем что-нибудь, а потом свернете и снова развернете окно приложения, то рисунок пропадет. Если же использовать TImage, все данные сохранятся. В главе про анимацию я выбрал TPaintBox, потому что подобное «автоматическое сохранение» нам не было нужно, а даром оно не дается, естественно — это все дополнительные затраты времени (а скорость была критическим вопросом). Если же скорость работы не так важна, лучше использовать TImage (хотя, конечно же, готовых рецептов «правильного» подхода не существует).
procedure ShowMaze(TheMaze : Maze); { нарисовать лабиринт }
var x, y : Integer;
Height, Width : Integer; { высота и ширина лабиринта }
begin
Width := High(TheMaze); { определить высоту и ширину }
Height := High(TheMaze[0]);
with Form1.BackBuffer.Canvas do
begin { очистка буфера }
FillRect(Rect(0, 0, Form1.BackBuffer.Width, Form1.BackBuffer.Height));
for x := 0 to Width - 1 do
for y := 0 to Height - 1 do
begin
{ если в локации есть верхняя стена }
if TheMaze[x, y].up_wall then
begin
MoveTo(x * CellSize, y * CellSize); { рисуем ее }
LineTo((x + 1) * CellSize, y * CellSize);
end;
{ если в локации есть левая стена }
if TheMaze[x, y].left_wall then
begin
MoveTo(x * CellSize, y * CellSize); { рисуем и ее }
LineTo(x * CellSize, (y + 1) * CellSize);
end;
end;
MoveTo(0, Height * CellSize); { рисуем стену снизу и }
LineTo(Width * CellSize, Height * CellSize); { справа от лабиринта }
LineTo(Width * CellSize, 0);
end;
{ отобразить результат на основном экране }
Form1.Screen.Canvas.CopyRect(Rect(0, 0, Form1.Screen.Width,
Form1.Screen.Height), Form1.BackBuffer.Canvas,
Rect(0, 0, Form1.Screen.Width, Form1.Screen.Height));
end;
CellSize — это константа, которая определяет размер стороны локации в пикселах. Внешний вид маленького лабиринта, текстовое представление которого я привел выше, показан на рис. 4.3 (разумеется, он получен с помощью процедуры ShowMaze(); значение CellSize равно 50).
Рис. 4.3. Результат работы процедуры ShowMaze()
Решение лабиринта
Итак, лабиринт создан и загружен в память компьютера. Теперь надо научиться его решать. Под этим термином я подразумеваю поиск пути из некоторой стартовой локации в некоторую другую (финишную). Стартовая и финишная локации в лабиринте не фиксированы: мы можем попытаться решить лабиринт для любой пары локаций, какой только захотим. Полезно рассмотреть также задачу не просто поиска какого-то пути, а пути самого короткого. Мы остановимся на двух популярных методах решения лабиринтов: рекурсивном обходе и алгоритме волновой трассировки.
Рекурсивный обход
По правде говоря, у этого метода есть только одно достоинство — он простой. А еще он очень популярный (как и далеко не лучшая «пузырьковая» сортировка).
Давайте подумаем, как бы стал решать лабиринт человек. Поскольку у нас нет идей, какой путь может вести к финишной локации, ничего не остается делать, кроме как последовательно изучать лабиринт, пока не наткнемся на нее. Если наш путь проходит по коридору, от которого нет ответвлений, надо идти вперед (а больше просто некуда); «интересности» же начинаются, когда мы оказываемся на перекрестке. Имеет смысл поступить следующим образом. Отметим какой-нибудь из возможных путей (московское время такое-то, выбрали такой-то путь) и будем двигаться по нему. Если нам придется вернуться (зачем — я скажу позже), мы можем выбрать уже другой путь.
Если на пути встретилась финишная локация — замечательно, конец алгоритма. При этом надо не забывать отмечать свой путь (в «бортовом журнале»), чтобы знать, каким именно образом мы сюда попали.
К сожалению, гораздо чаще, чем хотелось бы, мы будем встречаться не с финишной локацией, а с тупиком. Тупик бывает двух видов: либо просто некуда идти (идем по коридору, а в конце ждет глухая стена), либо там, куда можно идти, мы уже были. Второе означает, что в маршруте образовалась петля, а никакого смысла в том, чтобы идти по тем локациям, где уже все изучено, нет. В этом случае проще всего сделать шаг назад, забыв о том, что мы посетили текущую локацию (вычеркнуть ее из «бортового журнала»), и выбрать другой путь. Если шаг назад ничего не дает, надо сделать еще один шаг назад, а если понадобится — и еще несколько, до тех пор, пока не появятся альтернативы. Если все варианты исчерпаны, а решение так и не найдено, это означает, что его попросту не существует. Например, финишная локация полностью окружена сплошной стеной. Вот и весь алгоритм. Может, кто-нибудь вспомнит о простом правиле: если хочешь выйти из лабиринта, всегда, что бы ни случилось, держись рукой правой стены (можно и левой, конечно; главное — не менять решение в середине пути). К сожалению, это правило гарантирует только то, что мы вернемся туда, откуда пришли; при этом существенная часть лабиринта может остаться неисследованной.
Давайте сначала рассмотрим процедуру рекурсивного обхода (листинг 4.1), а потом я буду ее критиковать.
- 4.1. Рекурсивный обход лабиринта
procedure RecursiveSolve(TheMaze : Maze; xs, ys, xf, yf : Integer); var Visited : array of array of Boolean; { карта посещенных локаций } x, y, xc, yc : Integer; i : Integer; Path : array of TPoint; { результирующий маршрут } Height, Width : Integer; const dx : array[1..4] of Integer = (1, 0, -1, 0); { смещения } dy : array[1..4] of Integer = (0, -1, 0, 1); { служебная функция: определяет, можно ли пройти из локации Листинг 4.1 (продолжение) (x, y) в локацию (x + dx, y + dy), то есть нет ли между ними стены } function CanGo(x, y, dx, dy : Integer) : Boolean; begin if dx = -1 then CanGo := not TheMaze[x, y].left_wall else if dx = 1 then CanGo := not TheMaze[x + 1, y].left_wall else if dy = -1 then CanGo := not TheMaze[x, y].up_wall else CanGo := not TheMaze[x, y + 1].up_wall; end; { поиск финишной локации из точки (x, y) } function Solve(x, y, depth : Integer) : Boolean; var i : Integer; begin Visited[x, y] := true; { пометить локацию как посещенную } Path[depth] := Point(x, y); { добавить ее в описание маршрута } Path[depth + 1] := Point(-1, -1); { добавить признак конца маршрута } if (x = xf) and (y = yf) then { если финишная локация найдена } begin Solve := true; { конец алгоритма } Exit; end; for i := 1 to 4 do { если дорожка свободна, идем по ней } if CanGo(x, y, dx[i], dy[i]) and not Visited[x + dx[i], y + dy[i]] then if Solve(x + dx[i], y + dy[i], depth + 1) then begin Solve := true; { если решение найдено } Exit; { конец алгоритма } end; Visited[x, y] := false; { пометить локацию как непосещенную } Solve := false; { решение не найдено } end; begin { главная процедура }<>br Width := High(TheMaze); Height := High(TheMaze[0]); SetLength(Path, Height * Width + 1); { выделяем память для маршрута } SetLength(Visited, Width, Height); { и для списка посещенных локаций } for x := 0 to Width - 1 do for y := 0 to Height - 1 do Visited[x, y] := false; { изначально ни одна не посещена } if Solve(xs, ys, 0) then { если найдено решение, рисуем его } begin i := 0; while not ((Path[i].X = -1) and (Path[i].Y = -1)) do begin xc := CellSize * (2 * Path[i].X + 1) div 2; yc := CellSize * (2 * Path[i].Y + 1) div 2; Form1.Screen.Canvas.Ellipse(xc - 5, yc - 5, xc + 5, yc + 5); i := i + 1; end; end; end;
На первый взгляд процедура кажется довольно громоздкой, но если присмотреться, то становится ясно, что ядро у нее не такое уж большое. Для реализации процедуры мне потребовались две дополнительные функции: CanGo() и Solve(). Функция CanGo() определяет, есть или нет стены между локациями (x, y) и (x + dx, y + dy) (то есть можно ли пройти из одной в другую). При этом предполагается, что локации находятся по соседству — первая расположена сверху, слева, снизу или справа от второй. Функция Solve() более интересна и сложна. Ей передается три параметра — координаты текущей локации и номер шага. Номер нужен для того, чтобы знать, в какую строчку «бортового журнала» записывать текущее движение. Дальше все происходит по алгоритму, о котором мы говорили выше:
пометить текущую локацию как посещенную
добавить ее в «бортовой журнал»…
Обратите внимание на «признак конца». Нам как-то надо отмечать конец журнала. Поскольку локации с координатами (-1, -1) не существует, эту «псевдолокацию» вполне можно использовать. если локация найдена — конец алгоритма
исследуем каждую свободную дорожку Вот здесь я применил небольшую хитрость: всего из каждой локации может вести максимум четыре разные дорожки. Первая начинается от соседней сверху локации, вторая — от левой, третья — от нижней, а четвертая — от правой.
Чтобы не писать четыре раза
исследовать_дорожку(x, y – 1)
исследовать_дорожку(x – 1, y)
исследовать_дорожку(x, y + 1)
исследовать_дорожку(x + 1, y)
я воспользовался циклом (не забывайте, что исследовать_дорожку() — это не вызов процедуры, а фрагмент из нескольких строк кода, поэтому экономия заметная):
for i := 1 to 4 do
enneaaiaaou_ai?i?eo(x + dx[i], y + dy[i])
Если решение найдено, то работа алгоритма заканчивается; в противном случае текущая локация помечается как непосещенная и происходит выход из процедуры. Обратите внимание, что каждый шаг в лабиринте — это рекурсивный вызов. Такое решение позволяет легко вернуться на шаг назад (помните, это важная часть алгоритма) — для этого надо всего лишь выйти из функции, сообщив при этом вызывающей функции, что решение не найдено. Главная процедура делает не так уж и много работы: она инициализирует массивы, затем вызывает Solve() и рисует на экране полученное решение (рис. 4.4). В примере я выбрал верхнюю левую локацию лабиринта как стартовую, а верхнюю правую — как финишную.
Обратите также внимание на строку:
if CanGo(x, y, dx[i], dy[i]) and
not Visited[x + dx[i], y + dy[i]] then ...
Если текущая локация находится на краю или в углу лабиринта, числа x + dx[i] и y + dy[i] могут оказаться некорректными индексами массива Visited (то есть попросту указывать на локацию, лежащую за границами лабиринта). Ошибки не возникает потому, что Delphi по умолчанию использует так называемую сокращенную схему вычисления логических выражений: если значение CanGo() оказалось равно false, нет нужды вычислять правую часть выражения (после and) — и так ясно, что значение всего выражения будет равно false. Если функция CanGo() определит, что мы пытаемся выйти за пределы лабиринта, она, естественно, вернет false, поскольку весь лабиринт ограничен стеной; следовательно, правая часть выражения в таких случаях никогда не будет вычисляться. Мы будем пользоваться этой особенностью Delphi и в дальнейшем.
Надеюсь, принцип работы рекурсивного обхода более или менее ясен. Возможно, стоило подробнее на нем остановиться и постараться объяснить все тонкости более доходчиво (если алгоритм рекурсивен, он уже не слишком прост — по крайней мере, для меня), однако мне просто жаль на него времени. Сейчас я подробно распишу недостатки рекурсивного обхода, а потом мы рассмотрим куда более передовой алгоритм волновой трассировки.
Итак, два недостатка алгоритма лежат на поверхности:
1) он обходит лабиринт нерационально: может пройти достаточное количество времени, прежде чем решение будет найдено;
2) полученное решение может не быть оптимальным (в примере алгоритм находит оптимальное решение, но в приведенном
лабиринте другого решения просто нет).
Третий недостаток гораздо более существенный, хотя и проявляется он не всегда. Посмотрите на лабиринт, изображенный на рис. 4.5.
Проход, ведущий вниз от стартовой локации, заканчивается финишной локацией. Если же пойти направо, мы сначала попадем в «зал» — группу локаций безо всяких стен между ними, а затем дойдем до тупика. Если рекурсивный алгоритм запрограммирован так, что дорожка, ведущая вниз, будет рассмотрена первой — замечательно, решение будет найдено, причем очень быстро. Если же алгоритм сначала пойдет направо, у нас будут большие проблемы. Мы знаем, что движение вправо бесперспективно: в конце ждет тупик. Тем не менее алгоритм устроен так, что отступление идет до ближайшего шага, на котором возможны альтернативы (помните?). Так вот: каждая клетка «зала» — это перекресток из четырех дорожек! На каждом перекрестке алгоритм последовательно постарается перебрать все варианты движений, наивно полагая, что на сей раз повезет, и тупика не будет. Таким образом, в итоге будут перебраны все возможные варианты пересечения «зала»: прямо, по змейке, вдоль стены… только представьте себе масштабы подобного перебора! На перекрестке четырех дорожек у вас есть три варианта, куда пойти (поскольку назад идти нельзя). На каждой из трех новых локаций у вас есть опять же по три варианта на выбор (итого 3*3 = 9); на следующем этапе это число уже будет равно 3*3*3 = 27 и т. д. Количество вариантов растет в геометрической прогрессии, что делает рекурсивный обход совершенно непригодным для лабиринтов с подобными «залами»: программа попросту «зависнет», просчитывая мириады бесперспективных маршрутов.
Алгоритм волновой трассировки
Описание рекурсивного обхода я начал с фразы: «Давайте подумаем, как бы стал решать лабиринт человек». Разумеется, копирование человеческих действий — не единственный способ достижения решения; вполне можно применить и другие модели поведения. К примеру, такую: представьте, что в стартовой локации мы опрокинули бочку воды (а еще лучше, густого киселя). Жидкость начинает растекаться по сторонам, постепенно добираясь даже до самых отдаленных локаций лабиринта. Рано или поздно она достигнет и финишной локации: в этом случае надо проследить, каким путем жидкость туда попала — а это и будет маршрут от старта до финиша (причем, заметьте, кратчайший!). Если киселю уже некуда течь, а финишная локация так и не достигнута, это означает, что решения не существует. Моделированием такого поведения занимается алгоритм волновой трассировки .
Пометим сначала все локации лабиринта нулями (что означает «локация не содержит киселя»). Стартовую локацию пометим единицей (вылили кисель). Теперь выполняем действия: найти в лабиринте локации, помеченные единицами для каждой из четырех соседних с ней локаций проверить два условия:
1. помечена ли она нулем
2. есть ли стена между двумя локациями (выбранной и соседней) если оба условия выполнены, помечаем соседнюю локацию двойкой
Из стартовой позиции можно попасть лишь в локацию, расположенную снизу от нее. Поскольку она помечена нулем, записываем двойку. Вторая итерация алгоритма выглядит так: найти в лабиринте локации, помеченные двойками для каждой из четырех соседних с ней локаций проверить те же условия если оба условия выполнены, помечаем соседнюю локацию тройкой Надеюсь, общая идея алгоритма ясна. На N-й итерации нам придется выполнить действия: найти в лабиринте локации, помеченные числом N для каждой из четырех соседних с ней локаций проверить те же условия если оба условия выполнены, помечаем соседнюю локацию числом N + 1 Результат работы алгоритма после восьмой итерации показан на рис. 4.7.
Если на какой-то итерации мы достигли финишной локации (я считаю финишной правую верхнюю локацию лабиринта), работа алгоритма заканчивается. Если в течение итерации мы не сумели занять ни одной новой клетки, решения не существует. Если решение найдено на N-й итерации (в нашем случае — на восьмой), финишная локация помечена числом N + 1. Теперь осталось лишь определить собственно путь. Сделать это несложно: в финишную локацию (номер N + 1) мы попали из той соседней с ней локации, которая имеет номер N; в свою очередь, в нее можно попасть из локации с номером N – 1 и т. д. Если в процессе определения пути мы нашли две локации, откуда можно было попасть в текущую, можно выбрать любую из них — оба маршрута будут оптимальными. Разумеется, надо следить, чтобы между соседними локациями маршрута не было стены. Давайте сначала реализуем этот алгоритм, а потом обсудим его сильные и слабые стороны.
- 4.2. Алгоритм волновой трассировки
procedure WaveTracingSolve(TheMaze : Maze; xs, ys, xf, yf : Integer); var Mark : array of array of Integer; { метки локаций } x, y, xc, yc : Integer; N, i : Integer; Height, Width : Integer; const dx : array[1..4] of Integer = (1, 0, -1, 0); { смещения } dy : array[1..4] of Integer = (0, -1, 0, 1); { neo?aaiay ooieoey: ii?aaaeyao, ii?ii ee i?ieoe ec eieaoee (x, y) в локацию (x + dx, y + dy), то есть нет ли между ними стены } function CanGo(x, y, dx, dy : Integer) : Boolean; Листинг 4.2 (продолжение) begin if dx = -1 then CanGo := not TheMaze[x, y].left_wall else if dx = 1 then CanGo := not TheMaze[x + 1, y].left_wall else if dy = -1 then CanGo := not TheMaze[x, y].up_wall else CanGo := not TheMaze[x, y + 1].up_wall; end; function Solve : Boolean; { поиск решения } var i, N, x, y : Integer; NoSolution : Boolean; begin N := 1; { начинаем с итерации номер 1 } repeat NoSolution := true; { пессимистично полагаем, что решения нет } for x := 0 to Width - 1 do for y := 0 to Height - 1 do if Mark[x, y] = N then { найти локации, помеченные числом N } for i := 1 to 4 do { просмотр соседних локаций } if CanGo(x, y, dx[i], dy[i]) and (Mark[x + dx[i], y + dy[i]] = 0) then begin { локация доступна и помечена нулем } NoSolution := false; { есть шанс найти решение } { помечаем соседнюю локацию числом N + 1 } Mark[x + dx[i], y + dy[i]] := N + 1; if (x + dx[i] = xf) and (y + dy[i] = yf) then begin Solve := true; { дошли до финишной локации } Exit; { конец алгоритма } end; end; N := N + 1; { переход к следующей итерации } until NoSolution; { повторять, если есть надежда найти решение } Solve := false; { нет, решение не найдено } end; begin Width := High(TheMaze); Height := High(TheMaze[0]); SetLength(Mark, Width, Height); { выделение памяти для пометок } for x := 0 to Width - 1 do { изначально все заполняется нулями } for y := 0 to Height - 1 do Mark[x, y] := 0; Mark[xs, ys] := 1; { стартовой локации соответствует единица } if Solve then { если найдено решение, рисуем его } begin x := xf; y := yf; for N := Mark[xf, yf] downto 1 do begin { рисуем окружность на очередной локации маршрута } xc := CellSize * (2 * x + 1) div 2; yc := CellSize * (2 * y + 1) div 2; Form1.Screen.Canvas.Ellipse(xc - 5, yc - 5, xc + 5, yc + 5); for i := 1 to 4 do if CanGo(x, y, dx[i], dy[i]) and (Mark[x + dx[i], y + dy[i]] = N - 1) then begin x := x + dx[i]; { ищем следующую локацию маршрута } y := y + dy[i]; Break; end; end; end; end;
Главная часть процедуры очень похожа на аналогичный фрагмент из алгоритма рекурсивного обхода: инициализация переменных, вызов функции поиска решения, вывод найденного решения на экран. Функция CanGo() идентична предыдущей реализации, а функция Solve() прямолинейно реализует алгоритм, который я набросал выше.
Итак, поговорим теперь о качествах алгоритма волновой трассировки. Его плюсы налицо: он простой (наверное, даже проще рекурсивного обхода), отлично справляется с залами и находит оптимальное решение (причем очень быстро). Есть у него и существенный минус: на каждой итерации приходится исследовать весь лабиринт целиком, определяя, каким числом помечена та или иная локация. Если мы имеем дело с большим лабиринтом, этот недостаток может быстро стать критическим. Другой недостаток — большой расход памяти: приходится содержать двумерный массив с метками локаций. В принципе, при рекурсивном обходе мы тоже использовали подобный массив, чтобы определить, была ли посещена локация раньше или нет; однако здесь ситуация другая. В случае рекурсивного обхода можно просто хранить координаты посещенных локаций в списке, экономя тем самым память, сейчас же такая уловка не поможет: количество меток очень быстро разрастается, покрывая существенную часть всего лабиринта. О том, как улучшить алгоритм волновой трассировки, я расскажу в конце главы, а пока займемся генерацией лабиринтов.
Генерация лабиринтов
Эта часть главы посвящена тому, как научить компьютер создавать лабиринты автоматически, без участия человека. Мы рассмотрим два алгоритма: Прима и Краскала. Оба они работают вполне удовлетворительно, тем не менее алгоритм Краскала считается более совершенным (в том плане, что создает более запутанные лабиринты), но работает он медленнее. Лабиринты, сгенерированные каждым из этих алгоритмов, обладают двумя свойствами: во-первых, они не содержат залов, а во-вторых, из любой локации лабиринта можно попасть в любую другую (то есть не существует замкнутых областей, отделенных от остальных частей лабиринта).
Алгоритм Прима
Создадим «заготовку» — лабиринт, в котором все локации полностью окружены стенами (разумеется, далеко от стартовой точки в таком лабиринте не уйдешь). Сопоставим каждой локации переменную-атрибут (соответственно, у нас получится двумерный массив атрибутов), которая может принимать значения Inside (внутри), Outside (снаружи) и Border (на границе). Изначально атрибут каждой локации должен быть равен Outside. Выберем случайную локацию в лабиринте и присвоим ее атрибуту значение Inside. Присвоим также атрибутам соседних с ней локаций значение Border. Теперь надо действовать по алгоритму:
ПОКА атрибут хотя бы одной локации равен Border
выберем случайную локацию, атрибут которой равен Border, и присвоим ей
атрибут Inside
изменим на Border атрибут всех соседних с текущей локаций, атрибут которых
равен Outside
из всех соседей текущей локации, атрибут которых равен Inside, выберем
случайную и разрушим стену между ней и текущей локацией
В последнем действии предполагается, что такие соседи (имеющие атрибут, равный Inside) у текущей локации имеются. Почему? А потому, что атрибут текущей локации изначально был равен Border — это гарантирует выполнение условия. По той же причине между такими локациями (текущей, атрибут которой был равен Border и соседней — с атрибутом Inside) всегда есть стена. Я понимаю, эти утверждения не так очевидны; на самом деле они вытекают из принципа работы алгоритма — попробуйте сделать несколько шагов вручную, на бумаге, и вы убедитесь в их справедливости. Если какая-то клетка имеет атрибут Inside, это означает, что она принадлежит к «внутренней», уже построенной области лабиринта. Любые две Inside-локации косвенно связаны между собой (то есть существует маршрут между ними). Outside-локации никак не связаны с Inside-локациями — их еще только предстоит обработать. Border-локации тоже находятся извне лабиринта, но каждая из них граничит хотя бы с одной Inside-локацией.
Листинг 4.3 содержит реализацию алгоритма Прима (далеко не лучшую в плане быстродействия, но прямолинейную и понятную).
- 4.3. Генерация лабиринта по алгоритму Прима
function PrimGenerateMaze(Width, Height : Integer) : Maze; type AttrType = (Inside, Outside, Border); { тип "атрибут локации" } var TheMaze : Maze; { сам лабиринт } x, y, i : Integer; xc, yc : Integer; xloc, yloc : Integer; Attribute : array of array of AttrType; { карта атрибутов } IsEnd : Boolean; counter : Integer; const dx : array[1..4] of Integer = (1, 0, -1, 0); { смещения } dy : array[1..4] of Integer = (0, -1, 0, 1); label ExitFor1, ExitFor2, ExitFor3; { eniieucoaiua iaoee } procedure BreakWall(x, y, dx, dy : Integer); { разрушить стену } begin { между локациями } if dx = -1 then TheMaze[x, y].left_wall := false else if dx = 1 then TheMaze[x + 1, y].left_wall := false else if dy = -1 then TheMaze[x, y].up_wall := false else TheMaze[x, y + 1].up_wall := false; end; begin SetLength(Attribute, Width, Height); { выделение памяти для атрибутов } SetLength(TheMaze, Width + 1, Height + 1); { изменить размер лабиринта } for x := 0 to Width - 1 do { изначально все атрибуты } for y := 0 to Height - 1 do { равны Outside } Attribute[x, y] := Outside; for y := 0 to Height do { все стены изначально } for x := 0 to Width do { существуют } begin TheMaze[x, y].left_wall := true; TheMaze[x, y].up_wall := true; end; Randomize; x := Random(Width); { выбираем начальную локацию } y := Random(Height); Attribute[x, y] := Inside; { и присваиваем ей атрибут Inside } for i := 1 to 4 do { всем ее соседям присваиваем } begin { атрибут Border } xc := x + dx[i]; yc := y + dy[i]; if (xc >= 0) and (yc >= 0) and (xc < Width) and (yc < Height) then Attribute[xc, yc] := Border; end; repeat { главный цикл } IsEnd := true; counter := 0; for x := 0 to Width - 1 do { подсчитываем количество } for y := 0 to Height - 1 do { локаций с атрибутом Border } if Attribute[x, y] = Border then counter := counter + 1; counter := Random(counter) + 1; { выбираем из них } for x := 0 to Width - 1 do { одну случайную } for y := 0 to Height - 1 do if Attribute[x, y] = Border then begin counter := counter - 1; if counter = 0 then Листинг 4.3 (продолжение) begin xloc := x; { xloc, yloc - ее координаты } yloc := y; goto ExitFor1; { выход из цикла } end; end; ExitFor1: Attribute[xloc, yloc] := Inside; { присвоить ей атрибут Inside } counter := 0; for i := 1 to 4 do begin xc := xloc + dx[i]; yc := yloc + dy[i]; if (xc >= 0) and (yc >= 0) and (xc < Width) and (yc < Height) then begin { подсчитать количество локаций с атрибутом Inside } if Attribute[xc, yc] = Inside then counter := counter + 1; if Attribute[xc, yc] = Outside then { заменить атрибуты с } Attribute[xc, yc] := Border; { Outside на Border } end; end; counter := Random(counter) + 1; { выбрать случайную Inside-локацию } for i := 1 to 4 do begin xc := xloc + dx[i]; yc := yloc + dy[i]; if (xc >= 0) and (yc >= 0) and (xc < Width) and (yc < Height) and (Attribute[xc, yc] = Inside) then begin counter := counter - 1; if counter = 0 then { разрушить стену между ней и } begin { текущей локацией } BreakWall(xloc, yloc, dx[i], dy[i]); goto ExitFor2; end; end; end; ExitFor2: for x := 0 to Width - 1 do { определить, есть ли } for y := 0 to Height - 1 do { хоть одна локация с } if Attribute[x, y] = Border then { атрибутом Border } begin IsEnd := false; { если да, продолжаем } goto ExitFor3; { выполнять алгоритм } end; ExitFor3: ShowMaze(TheMaze); { отобразить процесс генерации } Application.ProcessMessages; until IsEnd; PrimGenerateMaze := TheMaze; end;
Я добавил в конец процедуры вызов ShowMaze(), чтобы отображать в динамике процесс генерации лабиринта — очень интересное зрелище на самом деле (рис. 4.8).
В алгоритме постоянно используется идея того, как можно выбрать случайную локацию, помеченную некоторым атрибутом:
N := количество локаций, помеченных заданным атрибутом
n := случайное число от 1 до N
выбрать n-ю по счету локацию, помеченную заданным атрибутом
Этот метод прост (этим и хорош), зато требует для работы двух циклов, каждый из которых пробегает по всему лабиринту. В трех местах я применил оператор goto — надеюсь, никто не считает дурным тоном его использование для выхода из вложенного цикла?
Алгоритм Краскала
Прежде всего, создадим заготовку, аналогичную той, что мы использовали в алгоритме Прима — лабиринт со всеми возможными стенами. Алгоритм Краскала описывается всего семью строками на псевдокоде:
locations := количество локаций в лабиринте
ПОКА locations > 1
выбираем случайную стену в лабиринте
ЕСЛИ не существует пути между локациями, разделенными этой стеной,
разбиваем стену
locations := locations – 1
КОНЕЦ ЦИКЛА
Для того чтобы реализовать его на практике, потребуется, конечно же, гораздо больше усилий. Во-первых, нам понадобится функция, которая определяет, существует ли путь между двумя заданными локациями или нет. Для этого можно (и нужно) воспользоваться рекурсивным обходом или алгоритмом волновой трассировки, которые описаны выше в этой главе. Думаю, вам не составит труда чуть доработать любую из приведенных процедур, чтобы получилась функция:
function IsConnected(x1, y1, x2, y2) : Boolean
Предполагается, что она будет локальной и поэтому сможет получить доступ к лабиринту через переменную TheMaze — мы уже применяли такой подход. Во-вторых (и это более интересно), нам придется решить задачу случайного выбора без повторов.
В процессе построения лабиринта мы только разрушаем существующие стены, поэтому если между какими-то двумя локациями существует путь, он уже никуда не исчезнет. Таким образом, нет никакого резона выбирать два раза одну и ту же стену. Если некоторая стена была выбрана генератором случайных чисел однажды и осталась не разрушенной после текущей итерации алгоритма, путь между соответствующими локациями есть, и он останется в будущем. Похожая ситуация возникает при моделировании игры в русское лото: если некоторый бочонок уже вынут из мешка, его номер больше не должен выпадать.
Для решения этой задачи существуют, по крайней мере, два известных метода.
1.
Запоминать все ранее выбранные генератором случайных чисел значения. Если на очередной итерации выпало какое-то «старое» значение, просто запустить генератор еще раз (а если понадобится, то еще и еще раз).
Этот метод прекрасно работает, если вам надо, к примеру, выбрать десять неповторяющихся чисел из диапазона [1…10 000]. Вероятность того, что одно и то же число выпадет два раза, очень невелика, и нет беды, если пару раз генератор сработает два-три раза вхолостую. А вот в случае вроде русского лото его применять не стоит: когда почти все значения из диапазона исчерпаны, как раз-таки вероятность получить новое, не выбранное ранее число мала. Наш случай, к сожалению, куда ближе к варианту русского лото, поэтому перейдем ко второму методу.
2.
Предположим, что в массиве A[1..N] находятся все значения, которые надо выбрать в случайном порядке. Создадим массив B[1..N] и заполним его произвольными случайными числами. Практически любой универсальный алгоритм сортировки массива основан на операции обмена элементов. Я имею в виду, что основой алгоритма всегда является операция поменять местами B[i] и B[j]
3.
Теперь надо отсортировать массив B по возрастанию, меняя местами каждый раз элементы массива A при обмене элементов из B. Иными словами, вместо кода поменять местами B[i] и B[j] везде будет использоваться поменять местами B[i] и B[j] iiiaiyou ianoaie A[i] e A[j]
4.
После работы алгоритма сортировки массив A окажется полностью перемешанным в случайном порядке. В качестве первого случайного элемента можно взять первый элемент массива A, в качестве второго — второй и т. д. Вот и все. Давайте теперь немного уточним алгоритм Краскала с учетом сказанного:
locations := количество локаций в лабиринте { Width * Height } записываем все стены лабиринта в массив Walls перемешиваем массив Walls в случайном порядке
i := 0
ПОКА locations > 1
текущая стена := i-й элемент массива Walls
i := i + 1
ЕСЛИ не существует пути между локациями, разделенными этой стеной
разбиваем стену
locations := locations – 1
Любую стену можно задать четырьмя числами: (x, y, dx, dy), то есть с помощью координат локации и смещений (я особо не останавливаюсь на этом, потому что мы не раз уже пользовались таким способом, например в функции CanGo() и процедуре BreakWall()). Таким образом, «массив стен» — это массив таких четверок.
Теперь можно заняться реализацией алгоритма. Мой вариант приведен в листинге 4.4, скриншот работающей программы — на рис. 4.9.
- Листинг 4.4. Генерация лабиринта по алгоритму Краскала
function KruskalGenerateMaze(Width, Height : Integer) : Maze; type Wall = record { тип "стена" } x, y, dx, dy : Integer; end; var TheMaze : Maze; { сам лабиринт } Walls : array of Wall; { массив стен } Temp : array of Real; { временный массив для сортировки стен } i, j : Integer; tempw : Wall; tempr : Real; CurWall : Wall; locations : Integer; counter : Integer; procedure BreakWall(x, y, dx, dy : Integer); { разрушить стену } begin { между локациями } if dx = -1 then TheMaze[x, y].left_wall := false else if dx = 1 then TheMaze[x + 1, y].left_wall := false else if dy = -1 then TheMaze[x, y].up_wall := false else TheMaze[x, y + 1].up_wall := false; end; function IsConnected(xs, ys, xf, yf : Integer) : Boolean; ... { используется алгоритм волновой трассировки } begin { выделение памяти для массива стен } { в лабиринте Width * Height изначально { (Width - 1) * Height + (Height - 1) * Width стен } SetLength(Walls, (Width - 1) * Height + (Height - 1) * Width); SetLength(Temp, (Width - 1) * Height + (Height - 1) * Width); SetLength(TheMaze, Width + 1, Height + 1); { указать размер лабиринта } for i := 0 to Width do { все стены изначально } for j := 0 to Height do { существуют } begin TheMaze[i, j].left_wall := true; TheMaze[i, j].up_wall := true; end; Randomize; for i := 0 to (Width - 1) * Height + (Height - 1) * Width - 1 do Temp[i] := Random; { заполнение массива Temp случайными числами } counter := 0; { заполнение массива стен } for i := 1 to Width - 1 do for j := 0 to Height - 1 do begin { сначала все горизонтальные } Walls[counter].x := i; Walls[counter].y := j; Walls[counter].dx := -1; Walls[counter].dy := 0; counter := counter + 1; end; for i := 0 to Width - 1 do for j := 1 to Height - 1 do begin { затем все вертикальные } Walls[counter].x := i; Walls[counter].y := j; Walls[counter].dx := 0; Walls[counter].dy := -1; counter := counter + 1; end; for i := 0 to (Width - 1) * Height + (Height - 1) * Width - 1 do for j := i to (Width - 1) * Height + (Height - 1) * Width - 1 do if Temp[i] <@062> Temp[j] then { перемешиваем массив стен } begin tempr := Temp[i]; Temp[i] := Temp[j]; Temp[j] := tempr; tempw := Walls[i]; Walls[i] := Walls[j]; Walls[j] := tempw; end; locations := Width * Height; i := 0; while locations > 1 do { прямолинейная реализация } begin { алгоритма Краскала } CurWall := Walls[i]; i := i + 1; if not IsConnected(CurWall.x, CurWall.y, CurWall.x + CurWall.dx, CurWall.y + CurWall.dy) then begin BreakWall(CurWall.x, CurWall.y, CurWall.dx, CurWall.dy); locations := locations - 1; ShowMaze(TheMaze); Application.ProcessMessages; end; end; KruskalGenerateMaze := TheMaze; end;
1. Помните, что алгоритм волновой трассировки фактически моделирует поведение разлитой в лабиринте воды (киселя). Подумайте, как можно использовать этот алгоритм в компьютерной графике для закрашивания замкнутых областей.
2. Есть два простых способа улучшить алгоритм волновой трассировки: • На каждой итерации работы алгоритма происходит поиск локаций, помеченных числом N. Чтобы не пробегать по всему лабиринту, можно просто хранить их в отдельном списке (разумеется, его придется постоянно обновлять).
Можно «разлить кисель» не только в стартовой локации, но и в финишной. Как только оба потока жидкости пересекутся в некоторой локации, маршрут найден.
Реализуйте оба варианта на практике.
3. Добавьте в процедуры обхода лабиринта код, который позволит наблюдать ход решения. К примеру, в алгоритме рекурсивного обхода можно рисовать на экране текущий маршрут, а в алгоритме волновой трассировки выделять локации, помеченные значением N.
4. Подумайте, как можно реализовать алгоритм Прима более эффективно. К примеру, храните все Border-локации в отдельном списке, чтобы не просматривать в их поиске весь лабиринт на каждой итерации.
Вы уже умеете генерировать лабиринты и знакомы с трехмерной графикой. Попробуйте написать программу, которая генерирует лабиринт и выводит на экран в трехмерном виде его стартовую локацию (как будто путешественник находится внутри нее и видит все своими глазами). Пользователю должны быть доступны хотя бы три действия: повернуться налево на 90 градусов, повернуться направо на 90 градусов и пройти вперед к следующей локации. Я думаю, в начале 80-х такая нехитрая игра могла бы иметь коммерческий успех.