Различия

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

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

Предыдущая версия справа и слева Предыдущая версия
Следующая версия Следующая версия справа и слева
pascal4beginners-pathfind [31/01/2012 10:09]
Олег Альбертович Скворцов
pascal4beginners-pathfind [31/01/2012 10:16]
Олег Альбертович Скворцов
Строка 5: Строка 5:
 === Поиск пути ===  === Поиск пути === 
  
-==== Создание лабиринта ==== +===== Поиск пути на карте =====
-{{:​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