Различия

Здесь показаны различия между двумя версиями данной страницы.

Ссылка на это сравнение

pascal4beginners-genlabirint [31/01/2012 10:14] (текущий)
Олег Альбертович Скворцов создано
Строка 1: Строка 1:
 +==== Создание лабиринта ====
 +{{:​mozgovoj.jpg|}}
  
 +[[http://​www.piter-press.ru/​attachment.php?​barcode=978594723853&​at=exc&​n=0|
 +Мозговой Максим Владимирович - Занимательное программирование:​ Самоучитель]]
 +
 +
 +Глава 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), а потом я буду ее критиковать.
 +
 +<code |Листинг 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;
 +    ​
 +</​code> ​   ​
 +
 +На первый взгляд процедура кажется довольно громоздкой,​ но если присмотреться,​ то становится ясно, что ядро у нее не такое уж большое. Для реализации процедуры мне потребовались две дополнительные функции:​ 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 и т. д. Если в процессе определения пути мы нашли две локации,​ откуда можно было попасть в текущую,​ можно выбрать любую из них — оба маршрута будут оптимальными. Разумеется,​ надо следить,​ чтобы между соседними локациями маршрута не было стены. Давайте сначала реализуем этот алгоритм,​ а потом обсудим его сильные и слабые стороны.
 +
 +<code |Листинг 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;
 +</​code>​
 +
 +Главная часть процедуры очень похожа на аналогичный фрагмент из алгоритма рекурсивного обхода:​ инициализация переменных,​ вызов функции поиска решения,​ вывод найденного решения на экран. Функция CanGo() идентична предыдущей реализации,​ а функция Solve() прямолинейно реализует алгоритм,​ который я набросал выше.
 +
 +Итак, поговорим теперь о качествах алгоритма волновой трассировки. Его плюсы налицо:​ он простой (наверное,​ даже проще рекурсивного обхода),​ отлично справляется с залами и находит оптимальное решение (причем очень быстро). Есть у него и существенный минус: на каждой итерации приходится исследовать весь лабиринт целиком,​ определяя,​ каким числом помечена та или иная локация. Если мы имеем дело с большим лабиринтом,​ этот недостаток может быстро стать критическим. Другой недостаток — большой расход памяти:​ приходится содержать двумерный массив с метками локаций. В принципе,​ при рекурсивном обходе мы тоже использовали подобный массив,​ чтобы определить,​ была ли посещена локация раньше или нет; однако здесь ситуация другая. В случае рекурсивного обхода можно просто хранить координаты посещенных локаций в списке,​ экономя тем самым память,​ сейчас же такая уловка не поможет:​ количество меток очень быстро разрастается,​ покрывая существенную часть всего лабиринта. О том, как улучшить алгоритм волновой трассировки,​ я расскажу в конце главы, а пока займемся генерацией лабиринтов.
 +
 +===  Генерация лабиринтов ===
 +
 +Эта часть главы посвящена тому, как научить компьютер создавать лабиринты автоматически,​ без участия человека. Мы рассмотрим два алгоритма:​ Прима и Краскала. Оба они работают вполне удовлетворительно,​ тем не менее алгоритм Краскала считается более совершенным (в том плане, что создает более запутанные лабиринты),​ но работает он медленнее. Лабиринты,​ сгенерированные каждым из этих алгоритмов,​ обладают двумя свойствами:​ во-первых,​ они не содержат залов, а во-вторых,​ из любой локации лабиринта можно попасть в любую другую (то есть не существует замкнутых областей,​ отделенных от остальных частей лабиринта).
 +
 +===  Алгоритм Прима ===
 +
 +Создадим «заготовку» — лабиринт,​ в котором все локации полностью окружены стенами (разумеется,​ далеко от стартовой точки в таком лабиринте не уйдешь). Сопоставим каждой локации переменную-атрибут (соответственно,​ у нас получится двумерный массив атрибутов),​ которая может принимать значения Inside (внутри),​ Outside (снаружи) и Border (на границе). Изначально атрибут каждой локации должен быть равен Outside. Выберем случайную локацию в лабиринте и присвоим ее атрибуту значение Inside. Присвоим также атрибутам соседних с ней локаций значение Border. Теперь надо действовать по алгоритму:​
 +
 +<​code>​
 +    ПОКА атрибут хотя бы одной локации равен Border ​
 +    выберем случайную локацию,​ атрибут которой равен Border, и присвоим ей 
 +    атрибут Inside ​
 +    изменим на Border атрибут всех соседних с текущей локаций,​ атрибут которых ​
 +    равен Outside ​
 +    из всех соседей текущей локации,​ атрибут которых равен Inside, выберем ​
 +    случайную и разрушим стену между ней и текущей локацией
 +</​code> ​   ​
 +
 +В последнем действии предполагается,​ что такие соседи (имеющие атрибут,​ равный Inside) у текущей локации имеются. Почему?​ А потому,​ что атрибут текущей локации изначально был равен Border — это гарантирует выполнение условия. По той же причине между такими локациями (текущей,​ атрибут которой был равен Border и соседней — с атрибутом Inside) всегда есть стена. Я понимаю,​ эти утверждения не так очевидны;​ на самом деле они вытекают из принципа работы алгоритма — попробуйте сделать несколько шагов вручную,​ на бумаге,​ и вы убедитесь в их справедливости. Если какая-то клетка имеет атрибут Inside, это означает,​ что она принадлежит к «внутренней»,​ уже построенной области лабиринта. Любые две Inside-локации косвенно связаны между собой (то есть существует маршрут между ними). Outside-локации никак не связаны с Inside-локациями — их еще только предстоит обработать. Border-локации тоже находятся извне лабиринта,​ но каждая из них граничит хотя бы с одной Inside-локацией.
 +
 +Листинг 4.3 содержит реализацию алгоритма Прима (далеко не лучшую в плане быстродействия,​ но прямолинейную и понятную).
 +
 +<code |Листинг 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;
 +</​code>​
 +
 +Я добавил в конец процедуры вызов ShowMaze(), чтобы отображать в динамике процесс генерации лабиринта — очень интересное зрелище на самом деле (рис. 4.8). 
 +    ​
 +В алгоритме постоянно используется идея того, как можно выбрать случайную локацию,​ помеченную некоторым атрибутом: ​
 +
 +<​code>​
 +    N := количество локаций,​ помеченных заданным атрибутом ​
 +    n := случайное число от 1 до N 
 +    выбрать n-ю по счету локацию,​ помеченную заданным атрибутом ​
 +</​code> ​   ​
 +    ​
 +Этот метод прост (этим и хорош),​ зато требует для работы двух циклов,​ каждый из которых пробегает по всему лабиринту. В трех местах я применил оператор goto — надеюсь,​ никто не считает дурным тоном его использование для выхода из вложенного цикла?
 +
 +    ​
 +===  Алгоритм Краскала ===
 +
 +Прежде всего, создадим заготовку,​ аналогичную той, что мы использовали в алгоритме Прима — лабиринт со всеми возможными стенами. Алгоритм Краскала описывается всего семью строками на псевдокоде:​
 +
 +<​code>​
 +    locations := количество локаций в лабиринте
 +
 +    ПОКА locations > 1 
 +    выбираем случайную стену в лабиринте ​
 +    ЕСЛИ не существует пути между локациями,​ разделенными этой стеной, ​
 +    разбиваем стену ​
 +    locations := locations – 1 
 +    КОНЕЦ ЦИКЛА
 +</​code>​
 +
 +Для того чтобы реализовать его на практике,​ потребуется,​ конечно же, гораздо больше усилий. Во-первых,​ нам понадобится функция,​ которая определяет,​ существует ли путь между двумя заданными локациями или нет. Для этого можно (и нужно) воспользоваться рекурсивным обходом или алгоритмом волновой трассировки,​ которые описаны выше в этой главе. Думаю, вам не составит труда чуть доработать любую из приведенных процедур,​ чтобы получилась функция:​
 +
 +    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, в качестве второго — второй и т. д. Вот и все. Давайте теперь немного уточним алгоритм Краскала с учетом сказанного: ​
 +
 +<​code> ​   ​
 +    locations := количество локаций в лабиринте { Width * Height } записываем все стены лабиринта в массив Walls перемешиваем массив Walls в случайном порядке
 +
 +    i := 0
 +    ПОКА locations > 1
 +    текущая стена := i-й элемент массива Walls 
 +    i := i + 1 
 +    ЕСЛИ не существует пути между локациями,​ разделенными этой стеной ​
 +    разбиваем стену ​
 +    locations := locations – 1 
 +</​code>​
 +
 +Любую стену можно задать четырьмя числами:​ (x, y, dx, dy), то есть с помощью координат локации и смещений (я особо не останавливаюсь на этом, потому что мы не раз уже пользовались таким способом,​ например в функции CanGo() и процедуре BreakWall()). Таким образом,​ «массив стен» — это массив таких четверок. ​
 +
 +Теперь можно заняться реализацией алгоритма. Мой вариант приведен в листинге 4.4, скриншот работающей программы — на рис. 4.9. 
 +    ​
 +<code | Листинг 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;
 +</​code>​
 +
 +
 +1. Помните,​ что алгоритм волновой трассировки фактически моделирует поведение разлитой в лабиринте воды (киселя). Подумайте,​ как можно использовать этот алгоритм в компьютерной графике для закрашивания замкнутых областей.
 +
 +2. Есть два простых способа улучшить алгоритм волновой трассировки:​ • На каждой итерации работы алгоритма происходит поиск локаций,​ помеченных числом N. Чтобы не пробегать по всему лабиринту,​ можно просто хранить их в отдельном списке (разумеется,​ его придется постоянно обновлять).
 +
 +Можно «разлить кисель» не только в стартовой локации,​ но и в финишной. Как только оба потока жидкости пересекутся в некоторой локации,​ маршрут найден.
 +    ​
 +Реализуйте оба варианта на практике.
 +
 +3. Добавьте в процедуры обхода лабиринта код, который позволит наблюдать ход решения. К примеру,​ в алгоритме рекурсивного обхода можно рисовать на экране текущий маршрут,​ а в алгоритме волновой трассировки выделять локации,​ помеченные значением N.
 +
 +4. Подумайте,​ как можно реализовать алгоритм Прима более эффективно. К примеру,​ храните все Border-локации в отдельном списке,​ чтобы не просматривать в их поиске весь лабиринт на каждой итерации.
 +
 +Вы уже умеете генерировать лабиринты и знакомы с трехмерной графикой. Попробуйте написать программу,​ которая генерирует лабиринт и выводит на экран в трехмерном виде его стартовую локацию (как будто путешественник находится внутри нее и видит все своими глазами). Пользователю должны быть доступны хотя бы три действия:​ повернуться налево на 90 градусов,​ повернуться направо на 90 градусов и пройти вперед к следующей локации. Я думаю, в начале 80-х такая нехитрая игра могла бы иметь коммерческий успех.
 +
CC Attribution-Noncommercial 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0