мета-данные страницы
  •  
Загрузка не удалась. Возможно, проблемы с правами доступа?

Различия

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

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

Предыдущая версия справа и слеваПредыдущая версия
Следующая версияСледующая версия справа и слева
pascal4beginners-pathfind [31/01/2012 10:03] – ocapascal4beginners-pathfind [31/01/2012 10:09] – oca
Строка 159: Строка 159:
     При записи в файл служебные локации игнорируются, как было оговорено выше.     При записи в файл служебные локации игнорируются, как было оговорено выше.
  
-    Давайте еще напишем процедуру, которая рисует лабиринт на главной форме приложения, чтобы в дальнейшем не отвлекаться на этот процесс. Я предполагаю, что главная форма называется Form1, а на ней расположены объекты Screen и BackBuffer (оба имеют тип TImage). Как и раньше, объект BackBuffer служит для двойной буферизации (не забывайте, он должен быть невидимым). Я использую этот механизм здесь потому, что кое-какая анимация у нас в дальнейшем будет. В +    Давайте еще напишем процедуру, которая рисует лабиринт на главной форме приложения, чтобы в дальнейшем не отвлекаться на этот процесс. Я предполагаю, что главная форма называется Form1, а на ней расположены объекты Screen и BackBuffer (оба имеют тип TImage). Как и раньше, объект BackBuffer служит для двойной буферизации (не забывайте, он должен быть невидимым). Я использую этот механизм здесь потому, что кое-какая анимация у нас в дальнейшем будет.  
- +     
-    ы, наверное, уже обратили внимание: раньше я использовал элемент TPaintBox для вывода на экран, теперь же решил ограничиться типом TImage. Разница между этими в общем-то похожими компонентами заключается в том, что TImage «запоминает» свой рисунок. Если вы поместите на форму элемент TPaintBox, нарисуете на нем что-нибудь, а потом свернете и снова развернете окно приложения, то рисунок пропадет. Если же использовать TImage, все данные сохранятся. В главе про анимацию я выбрал TPaintBox, потому что подобное «автоматическое сохранение» нам не было нужно, а даром оно не дается, естественно — это все дополнительные затраты времени (а скорость была критическим вопросом). Если же скорость работы не так важна, лучше использовать TImage (хотя, конечно же, готовых рецептов «правильного» подхода не существует).+Вы, наверное, уже обратили внимание: раньше я использовал элемент TPaintBox для вывода на экран, теперь же решил ограничиться типом TImage. Разница между этими в общем-то похожими компонентами заключается в том, что TImage «запоминает» свой рисунок. Если вы поместите на форму элемент TPaintBox, нарисуете на нем что-нибудь, а потом свернете и снова развернете окно приложения, то рисунок пропадет. Если же использовать TImage, все данные сохранятся. В главе про анимацию я выбрал TPaintBox, потому что подобное «автоматическое сохранение» нам не было нужно, а даром оно не дается, естественно — это все дополнительные затраты времени (а скорость была критическим вопросом). Если же скорость работы не так важна, лучше использовать TImage (хотя, конечно же, готовых рецептов «правильного» подхода не существует).
  
     procedure ShowMaze(TheMaze : Maze); { нарисовать лабиринт }     procedure ShowMaze(TheMaze : Maze); { нарисовать лабиринт }
Строка 206: Строка 206:
     Рис. 4.3. Результат работы процедуры ShowMaze()     Рис. 4.3. Результат работы процедуры ShowMaze()
          
-    === Решение лабиринта ===+=== Решение лабиринта ===
          
-    Итак, лабиринт создан и загружен в память компьютера. Теперь надо научиться его решать. Под этим термином я подразумеваю поиск пути из некоторой стартовой локации в некоторую другую (финишную). Стартовая и финишная локации в лабиринте не фиксированы: мы можем попытаться решить лабиринт для любой пары локаций, какой только захотим. Полезно рассмотреть также задачу не просто поиска какого-то пути, а пути самого короткого. Мы остановимся на двух популярных методах решения лабиринтов: рекурсивном обходе и алгоритме волновой трассировки.+Итак, лабиринт создан и загружен в память компьютера. Теперь надо научиться его решать. Под этим термином я подразумеваю поиск пути из некоторой стартовой локации в некоторую другую (финишную). Стартовая и финишная локации в лабиринте не фиксированы: мы можем попытаться решить лабиринт для любой пары локаций, какой только захотим. Полезно рассмотреть также задачу не просто поиска какого-то пути, а пути самого короткого. Мы остановимся на двух популярных методах решения лабиринтов: рекурсивном обходе и алгоритме волновой трассировки.
          
-    === Рекурсивный обход ===+=== Рекурсивный обход ===
          
-    По правде говоря, у этого метода есть только одно достоинство — он простой. А еще он очень популярный (как и далеко не лучшая «пузырьковая» сортировка).+По правде говоря, у этого метода есть только одно достоинство — он простой. А еще он очень популярный (как и далеко не лучшая «пузырьковая» сортировка).
  
-    Давайте подумаем, как бы стал решать лабиринт человек. Поскольку у нас нет идей, какой путь может вести к финишной локации, ничего не остается делать, кроме как последовательно изучать лабиринт, пока не наткнемся на нее. Если наш путь проходит по коридору, от которого нет ответвлений, надо идти вперед (а больше просто некуда); «интересности» же начинаются, когда мы оказываемся на перекрестке. Имеет смысл поступить следующим образом. Отметим какой-нибудь из возможных путей (московское время такое-то, выбрали такой-то путь) и будем двигаться по нему. Если нам придется вернуться (зачем — я скажу позже), мы можем выбрать уже другой путь.+Давайте подумаем, как бы стал решать лабиринт человек. Поскольку у нас нет идей, какой путь может вести к финишной локации, ничего не остается делать, кроме как последовательно изучать лабиринт, пока не наткнемся на нее. Если наш путь проходит по коридору, от которого нет ответвлений, надо идти вперед (а больше просто некуда); «интересности» же начинаются, когда мы оказываемся на перекрестке. Имеет смысл поступить следующим образом. Отметим какой-нибудь из возможных путей (московское время такое-то, выбрали такой-то путь) и будем двигаться по нему. Если нам придется вернуться (зачем — я скажу позже), мы можем выбрать уже другой путь.
  
-    Если на пути встретилась финишная локация — замечательно, конец алгоритма. При этом надо не забывать отмечать свой путь (в «бортовом журнале»), чтобы знать, каким именно образом мы сюда попали.+Если на пути встретилась финишная локация — замечательно, конец алгоритма. При этом надо не забывать отмечать свой путь (в «бортовом журнале»), чтобы знать, каким именно образом мы сюда попали.
  
-    К сожалению, гораздо чаще, чем хотелось бы, мы будем встречаться не с финишной локацией, а с тупиком. Тупик бывает двух видов: либо просто некуда идти (идем по коридору, а в конце ждет глухая стена), либо там, куда можно идти, мы уже были. Второе означает, что в маршруте образовалась петля, а никакого смысла в том, чтобы идти по тем локациям, где уже все изучено, нет. В этом случае проще всего сделать шаг назад, забыв о том, что мы посетили текущую локацию (вычеркнуть ее из «бортового журнала»), и выбрать другой путь. Если шаг назад ничего не дает, надо сделать еще один шаг назад, а если понадобится — и еще несколько, до тех пор, пока не появятся альтернативы. Если все варианты исчерпаны, а решение так и не найдено, это означает, что его попросту не существует. Например, финишная локация полностью окружена сплошной стеной. Вот и весь алгоритм. Может, кто-нибудь вспомнит о простом правиле: если хочешь выйти из лабиринта, всегда, что бы ни случилось, держись рукой правой стены (можно и левой, конечно; главное — не менять решение в середине пути). К сожалению, это правило гарантирует только то, что мы вернемся туда, откуда пришли; при этом существенная часть лабиринта может остаться неисследованной.+К сожалению, гораздо чаще, чем хотелось бы, мы будем встречаться не с финишной локацией, а с тупиком. Тупик бывает двух видов: либо просто некуда идти (идем по коридору, а в конце ждет глухая стена), либо там, куда можно идти, мы уже были. Второе означает, что в маршруте образовалась петля, а никакого смысла в том, чтобы идти по тем локациям, где уже все изучено, нет. В этом случае проще всего сделать шаг назад, забыв о том, что мы посетили текущую локацию (вычеркнуть ее из «бортового журнала»), и выбрать другой путь. Если шаг назад ничего не дает, надо сделать еще один шаг назад, а если понадобится — и еще несколько, до тех пор, пока не появятся альтернативы. Если все варианты исчерпаны, а решение так и не найдено, это означает, что его попросту не существует. Например, финишная локация полностью окружена сплошной стеной. Вот и весь алгоритм. Может, кто-нибудь вспомнит о простом правиле: если хочешь выйти из лабиринта, всегда, что бы ни случилось, держись рукой правой стены (можно и левой, конечно; главное — не менять решение в середине пути). К сожалению, это правило гарантирует только то, что мы вернемся туда, откуда пришли; при этом существенная часть лабиринта может остаться неисследованной.
  
-    Давайте сначала рассмотрим процедуру рекурсивного обхода (листинг 4.1), а потом я буду ее критиковать.+Давайте сначала рассмотрим процедуру рекурсивного обхода (листинг 4.1), а потом я буду ее критиковать.
  
-    Листинг 4.1. Рекурсивный обход лабиринта+<code |Листинг 4.1. Рекурсивный обход лабиринта>
  
     procedure RecursiveSolve(TheMaze : Maze; xs, ys, xf, yf : Integer); var Visited : array of array of Boolean; { карта посещенных локаций }     procedure RecursiveSolve(TheMaze : Maze; xs, ys, xf, yf : Integer); var Visited : array of array of Boolean; { карта посещенных локаций }
Строка 295: Строка 295:
     end;      end; 
     end; end;     end; end;
 +    
 +</code>    
  
 На первый взгляд процедура кажется довольно громоздкой, но если присмотреться, то становится ясно, что ядро у нее не такое уж большое. Для реализации процедуры мне потребовались две дополнительные функции: CanGo() и Solve(). Функция CanGo() определяет, есть или нет стены между локациями (x, y) и (x + dx, y + dy) (то есть можно ли пройти из одной в другую). При этом предполагается, что локации находятся по соседству — первая расположена сверху, слева, снизу или справа от второй. Функция Solve() более интересна и сложна. Ей передается три параметра — координаты текущей локации и номер шага. Номер нужен для того, чтобы знать, в какую строчку «бортового журнала» записывать текущее движение. Дальше все происходит по алгоритму, о котором мы говорили выше:  На первый взгляд процедура кажется довольно громоздкой, но если присмотреться, то становится ясно, что ядро у нее не такое уж большое. Для реализации процедуры мне потребовались две дополнительные функции: CanGo() и Solve(). Функция CanGo() определяет, есть или нет стены между локациями (x, y) и (x + dx, y + dy) (то есть можно ли пройти из одной в другую). При этом предполагается, что локации находятся по соседству — первая расположена сверху, слева, снизу или справа от второй. Функция Solve() более интересна и сложна. Ей передается три параметра — координаты текущей локации и номер шага. Номер нужен для того, чтобы знать, в какую строчку «бортового журнала» записывать текущее движение. Дальше все происходит по алгоритму, о котором мы говорили выше: 
Строка 331: Строка 333:
  
 Если текущая локация находится на краю или в углу лабиринта, числа x + dx[i] и y + dy[i] могут оказаться некорректными индексами массива Visited (то есть попросту указывать на локацию, лежащую за границами лабиринта). Ошибки не возникает потому, что Delphi по умолчанию использует так называемую сокращенную схему вычисления логических выражений: если значение CanGo() оказалось равно false, нет нужды вычислять правую часть выражения (после and) — и так ясно, что значение всего выражения будет равно false. Если функция CanGo() определит, что мы пытаемся выйти за пределы лабиринта, она, естественно, вернет false, поскольку весь лабиринт ограничен стеной; следовательно, правая часть выражения в таких случаях никогда не будет вычисляться. Мы будем пользоваться этой особенностью Delphi и в дальнейшем. Если текущая локация находится на краю или в углу лабиринта, числа x + dx[i] и y + dy[i] могут оказаться некорректными индексами массива Visited (то есть попросту указывать на локацию, лежащую за границами лабиринта). Ошибки не возникает потому, что Delphi по умолчанию использует так называемую сокращенную схему вычисления логических выражений: если значение CanGo() оказалось равно false, нет нужды вычислять правую часть выражения (после and) — и так ясно, что значение всего выражения будет равно false. Если функция CanGo() определит, что мы пытаемся выйти за пределы лабиринта, она, естественно, вернет false, поскольку весь лабиринт ограничен стеной; следовательно, правая часть выражения в таких случаях никогда не будет вычисляться. Мы будем пользоваться этой особенностью Delphi и в дальнейшем.
- 
- 
- 
-Рис. 4.4. Решение, найденное с помощью рекурсивного обхода 
  
 Надеюсь, принцип работы рекурсивного обхода более или менее ясен. Возможно, стоило подробнее на нем остановиться и постараться объяснить все тонкости более доходчиво (если алгоритм рекурсивен, он уже не слишком прост — по крайней мере, для меня), однако мне просто жаль на него времени. Сейчас я подробно распишу недостатки рекурсивного обхода, а потом мы рассмотрим куда более передовой алгоритм волновой трассировки. Надеюсь, принцип работы рекурсивного обхода более или менее ясен. Возможно, стоило подробнее на нем остановиться и постараться объяснить все тонкости более доходчиво (если алгоритм рекурсивен, он уже не слишком прост — по крайней мере, для меня), однако мне просто жаль на него времени. Сейчас я подробно распишу недостатки рекурсивного обхода, а потом мы рассмотрим куда более передовой алгоритм волновой трассировки.
Строка 340: Строка 338:
 Итак, два недостатка алгоритма лежат на поверхности: Итак, два недостатка алгоритма лежат на поверхности:
  
-    1)    он обходит лабиринт нерационально: может пройти достаточное количество времени, прежде чем решение будет найдено;+1)    он обходит лабиринт нерационально: может пройти достаточное количество времени, прежде чем решение будет найдено;
  
-    2)    полученное решение может не быть оптимальным (в примере алгоритм находит оптимальное решение, но в приведенном  +2)    полученное решение может не быть оптимальным (в примере алгоритм находит оптимальное решение, но в приведенном  
     лабиринте другого решения просто нет).      лабиринте другого решения просто нет). 
          
 Третий недостаток гораздо более существенный, хотя и проявляется он не всегда. Посмотрите на лабиринт, изображенный на рис. 4.5. Третий недостаток гораздо более существенный, хотя и проявляется он не всегда. Посмотрите на лабиринт, изображенный на рис. 4.5.
  
 +Проход, ведущий вниз от стартовой локации, заканчивается финишной локацией. Если же пойти направо, мы сначала попадем в «зал» — группу локаций безо всяких стен между ними, а затем дойдем до тупика. Если рекурсивный алгоритм запрограммирован так, что дорожка, ведущая вниз, будет рассмотрена первой — замечательно, решение будет найдено, причем очень быстро. Если же алгоритм сначала пойдет направо, у нас будут большие проблемы. Мы знаем, что движение вправо бесперспективно: в конце ждет тупик. Тем не менее алгоритм устроен так, что отступление идет до ближайшего шага, на котором возможны альтернативы (помните?). Так вот: каждая клетка «зала» — это перекресток из четырех дорожек! На каждом перекрестке алгоритм последовательно постарается перебрать все варианты движений, наивно полагая, что на сей раз повезет, и тупика не будет. Таким образом, в итоге будут перебраны все возможные варианты пересечения «зала»: прямо, по змейке, вдоль стены… только представьте себе масштабы подобного перебора! На перекрестке четырех дорожек у вас есть три варианта, куда пойти (поскольку назад идти нельзя). На каждой из трех новых локаций у вас есть опять же по три варианта на выбор (итого 3*3 = 9); на следующем этапе это число уже будет равно 3*3*3 = 27 и т. д. Количество вариантов растет в геометрической прогрессии, что делает рекурсивный обход совершенно непригодным для лабиринтов с подобными «залами»: программа попросту «зависнет», просчитывая мириады бесперспективных маршрутов.
  
 +===  Алгоритм волновой трассировки ===
  
-    Рис. 4.5. Лабиринт, проблематичный для процедуры рекурсивного обхода+Описание рекурсивного обхода я начал с фразы: «Давайте подумаем, как бы стал решать лабиринт человек». Разумеется, копирование человеческих действий — не единственный способ достижения решения; вполне можно применить и другие модели поведения. К примеру, такую: представьте, что в стартовой локации мы опрокинули бочку воды (а еще лучше, густого киселя). Жидкость начинает растекаться по сторонам, постепенно добираясь даже до самых отдаленных локаций лабиринта. Рано или поздно она достигнет и финишной локации: в этом случае надо проследить, каким путем жидкость туда попала — а это и будет маршрут от старта до финиша (причем, заметьте, кратчайший!). Если киселю уже некуда течь, а финишная локация так и не достигнута, это означает, что решения не существует. Моделированием такого поведения занимается алгоритм волновой трассировки .
  
-    Проход, ведущий вниз от стартовой локации, заканчивается финишной локацией. Если же пойти направо, мы сначала попадем в «зал» — группу локаций безо всяких стен между ними, а затем дойдем до тупика. Если рекурсивный алгоритм запрограммирован так, что дорожка, ведущая вниз, будет рассмотрена первой — замечательно, решение будет найдено, причем очень быстро. Если же алгоритм сначала пойдет направо, у нас будут большие проблемы. Мы знаем, что движение вправо бесперспективно: в конце ждет тупик. Тем не менее алгоритм устроен так, что отступление идет до ближайшего шага, на котором возможны альтернативы (помните?). Так вот: каждая клетка «зала» — это перекресток из четырех дорожек! На каждом перекрестке алгоритм последовательно постарается перебрать все варианты движений, наивно полагая, что на сей раз повезет, и тупика не будет. Таким образом, в итоге будут перебраны все возможные варианты пересечения «зала»: прямо, по змейке, вдоль стены… только представьте себе масштабы подобного перебора! На перекрестке четырех дорожек у вас есть три варианта, куда пойти (поскольку назад идти нельзя). На каждой из трех новых локаций у вас есть опять же по три варианта на выбор (итого 3*3 = 9); на следующем этапе это число уже будет равно 3*3*3 = 27 и т. д. Количество вариантов растет в геометрической прогрессии, что делает рекурсивный обход совершенно непригодным для лабиринтов с подобными «залами»: программа попросту «зависнет», просчитывая мириады бесперспективных маршрутов. +Пометим сначала все локации лабиринта нулями (что означает «локация не содержит киселя»). Стартовую локацию пометим единицей (вылили кисель). Теперь выполняем действия: найти в лабиринте локации, помеченные единицами для каждой из четырех соседних с ней локаций проверить два условия:
-    Алгоритм волновой трассировки +
- +
-    Описание рекурсивного обхода я начал с фразы: «Давайте подумаем, как бы стал решать лабиринт человек». Разумеется, копирование человеческих действий — не единственный способ достижения решения; вполне можно применить и другие модели поведения. К примеру, такую: представьте, что в стартовой локации мы опрокинули бочку воды (а еще лучше, густого киселя). Жидкость начинает растекаться по сторонам, постепенно добираясь даже до самых отдаленных локаций лабиринта. Рано или поздно она достигнет и финишной локации: в этом случае надо проследить, каким путем жидкость туда попала — а это и будет маршрут от старта до финиша (причем, заметьте, кратчайший!). Если киселю уже некуда течь, а финишная локация так и не достигнута, это означает, что решения не существует. Моделированием такого поведения занимается алгоритм волновой трассировки . +
- +
-    Пометим сначала все локации лабиринта нулями (что означает «локация не содержит киселя»). Стартовую локацию пометим единицей (вылили кисель). Теперь выполняем действия: найти в лабиринте локации, помеченные единицами для каждой из четырех соседних с ней локаций проверить два условия:+
  
        1. помечена ли она нулем        1. помечена ли она нулем
        2. есть ли стена между двумя локациями (выбранной и соседней) если оба условия выполнены, помечаем соседнюю локацию двойкой        2. есть ли стена между двумя локациями (выбранной и соседней) если оба условия выполнены, помечаем соседнюю локацию двойкой
  
-    Рисунок 4.6 иллюстрирует сказанное. +Из стартовой позиции можно попасть лишь в локацию, расположенную снизу от нее. Поскольку она помечена нулем, записываем двойку. Вторая итерация алгоритма выглядит так: найти в лабиринте локации, помеченные двойками для каждой из четырех соседних с ней локаций проверить те же условия если оба условия выполнены, помечаем соседнюю локацию тройкой Надеюсь, общая идея алгоритма ясна. На N-й итерации нам придется выполнить действия: найти в лабиринте локации, помеченные числом N для каждой из четырех соседних с ней локаций проверить те же условия если оба условия выполнены, помечаем соседнюю локацию числом N + 1 Результат работы алгоритма после восьмой итерации показан на рис. 4.7.
- +
- +
- +
-    Рис. 4.6. Первая итерация алгоритма волновой трассировки +
- +
-    Из стартовой позиции можно попасть лишь в локацию, расположенную снизу от нее. Поскольку она помечена нулем, записываем двойку. Вторая итерация алгоритма выглядит так: найти в лабиринте локации, помеченные двойками для каждой из четырех соседних с ней локаций проверить те же условия если оба условия выполнены, помечаем соседнюю локацию тройкой Надеюсь, общая идея алгоритма ясна. На N-й итерации нам придется выполнить действия: найти в лабиринте локации, помеченные числом N для каждой из четырех соседних с ней локаций проверить те же условия если оба условия выполнены, помечаем соседнюю локацию числом N + 1 Результат работы алгоритма после восьмой итерации показан на рис. 4.7. +
- +
- +
- +
-    Рис. 4.7. Результат работы алгоритма волновой трассировки+
  
-    Если на какой-то итерации мы достигли финишной локации (я считаю финишной правую верхнюю локацию лабиринта), работа алгоритма заканчивается. Если в течение итерации мы не сумели занять ни одной новой клетки, решения не существует. Если решение найдено на N-й итерации (в нашем случае — на восьмой), финишная локация помечена числом N + 1. Теперь осталось лишь определить собственно путь. Сделать это несложно: в финишную локацию (номер N + 1) мы попали из той соседней с ней локации, которая имеет номер N; в свою очередь, в нее можно попасть из локации с номером N – 1 и т. д. Если в процессе определения пути мы нашли две локации, откуда можно было попасть в текущую, можно выбрать любую из них — оба маршрута будут оптимальными. Разумеется, надо следить, чтобы между соседними локациями маршрута не было стены. Давайте сначала реализуем этот алгоритм, а потом обсудим его сильные и слабые стороны.+Если на какой-то итерации мы достигли финишной локации (я считаю финишной правую верхнюю локацию лабиринта), работа алгоритма заканчивается. Если в течение итерации мы не сумели занять ни одной новой клетки, решения не существует. Если решение найдено на N-й итерации (в нашем случае — на восьмой), финишная локация помечена числом N + 1. Теперь осталось лишь определить собственно путь. Сделать это несложно: в финишную локацию (номер N + 1) мы попали из той соседней с ней локации, которая имеет номер N; в свою очередь, в нее можно попасть из локации с номером N – 1 и т. д. Если в процессе определения пути мы нашли две локации, откуда можно было попасть в текущую, можно выбрать любую из них — оба маршрута будут оптимальными. Разумеется, надо следить, чтобы между соседними локациями маршрута не было стены. Давайте сначала реализуем этот алгоритм, а потом обсудим его сильные и слабые стороны.
  
-    Листинг 4.2. Алгоритм волновой трассировки+<code |Листинг 4.2. Алгоритм волновой трассировки>
  
     procedure WaveTracingSolve(TheMaze : Maze; xs, ys, xf, yf : Integer);     procedure WaveTracingSolve(TheMaze : Maze; xs, ys, xf, yf : Integer);
Строка 459: Строка 444:
     end;     end;
     end;     end;
 +</code>
 +
 +Главная часть процедуры очень похожа на аналогичный фрагмент из алгоритма рекурсивного обхода: инициализация переменных, вызов функции поиска решения, вывод найденного решения на экран. Функция CanGo() идентична предыдущей реализации, а функция Solve() прямолинейно реализует алгоритм, который я набросал выше.
 +
 +Итак, поговорим теперь о качествах алгоритма волновой трассировки. Его плюсы налицо: он простой (наверное, даже проще рекурсивного обхода), отлично справляется с залами и находит оптимальное решение (причем очень быстро). Есть у него и существенный минус: на каждой итерации приходится исследовать весь лабиринт целиком, определяя, каким числом помечена та или иная локация. Если мы имеем дело с большим лабиринтом, этот недостаток может быстро стать критическим. Другой недостаток — большой расход памяти: приходится содержать двумерный массив с метками локаций. В принципе, при рекурсивном обходе мы тоже использовали подобный массив, чтобы определить, была ли посещена локация раньше или нет; однако здесь ситуация другая. В случае рекурсивного обхода можно просто хранить координаты посещенных локаций в списке, экономя тем самым память, сейчас же такая уловка не поможет: количество меток очень быстро разрастается, покрывая существенную часть всего лабиринта. О том, как улучшить алгоритм волновой трассировки, я расскажу в конце главы, а пока займемся генерацией лабиринтов.
 +
 +===  Генерация лабиринтов ===
 +
 +Эта часть главы посвящена тому, как научить компьютер создавать лабиринты автоматически, без участия человека. Мы рассмотрим два алгоритма: Прима и Краскала. Оба они работают вполне удовлетворительно, тем не менее алгоритм Краскала считается более совершенным (в том плане, что создает более запутанные лабиринты), но работает он медленнее. Лабиринты, сгенерированные каждым из этих алгоритмов, обладают двумя свойствами: во-первых, они не содержат залов, а во-вторых, из любой локации лабиринта можно попасть в любую другую (то есть не существует замкнутых областей, отделенных от остальных частей лабиринта).
  
-    Главная часть процедуры очень похожа на аналогичный фрагмент из алгоритма рекурсивного обхода: инициализация переменных, вызов функции поиска решения, вывод найденного решения на экран. Функция CanGo() идентична предыдущей реализации, а функция Solve() прямолинейно реализует алгоритм, который я набросал выше.+===  Алгоритм Прима ===
  
-    Итак, поговорим теперь о качествах алгоритма волновой трассировки. Его плюсы налицо: он простой (наверное, даже проще рекурсивного обхода), отлично справляется с залами и находит оптимальное решение (причем очень быстро). Есть у него и существенный минус: на каждой итерации приходится исследовать весь лабиринт целиком, определяя, каким числом помечена та или иная локация. Если мы имеем дело с большим лабиринтом, этот недостаток может быстро стать критическим. Другой недостаток — большой расход памяти: приходится содержать двумерный массив с метками локаций. В принципе, при рекурсивном обходе мы тоже использовали подобный массив, чтобы определить, была ли посещена локация раньше или нет; однако здесь ситуация другая. В случае рекурсивного обхода можно просто хранить координаты посещенных локаций в списке, экономя тем самым память, сейчас же такая уловка не поможет: количество меток очень быстро разрастается, покрывая существенную часть всего лабиринта. О том, как улучшить алгоритм волновой трассировки, я расскажу в конце главы, а пока займемся генерацией лабиринтов. +Создадим «заготовку» — лабиринт, в котором все локации полностью окружены стенами (разумеется, далеко от стартовой точки в таком лабиринте не уйдешь). Сопоставим каждой локации переменную-атрибут (соответственно, у нас получится двумерный массив атрибутов), которая может принимать значения Inside (внутри), Outside (снаружи) и Border (на границе). Изначально атрибут каждой локации должен быть равен Outside. Выберем случайную локацию в лабиринте и присвоим ее атрибуту значение Inside. Присвоим также атрибутам соседних с ней локаций значение Border. Теперь надо действовать по алгоритму:
-    Генерация лабиринтов +
-    Эта часть главы посвящена тому, как научить компьютер создавать лабиринты автоматически, без участия человека. Мы рассмотрим два алгоритма: Прима и Краскала. Оба они работают вполне удовлетворительно, тем не менее алгоритм Краскала считается более совершенным (в том плане, что создает более запутанные лабиринты), но работает он медленнее. Лабиринты, сгенерированные каждым из этих алгоритмов, обладают двумя свойствами: во-первых, они не содержат залов, а во-вторых, из любой локации лабиринта можно попасть в любую другую (то есть не существует замкнутых областей, отделенных от остальных частей лабиринта). +
-    Алгоритм Прима +
-    Создадим «заготовку» — лабиринт, в котором все локации полностью окружены стенами (разумеется, далеко от стартовой точки в таком лабиринте не уйдешь). Сопоставим каждой локации переменную-атрибут (соответственно, у нас получится двумерный массив атрибутов), которая может принимать значения Inside (внутри), Outside (снаружи) и Border (на границе). Изначально атрибут каждой локации должен быть равен Outside. Выберем случайную локацию в лабиринте и присвоим ее атрибуту значение Inside. Присвоим также атрибутам соседних с ней локаций значение Border. Теперь надо действовать по алгоритму:+
  
 +<code>
     ПОКА атрибут хотя бы одной локации равен Border      ПОКА атрибут хотя бы одной локации равен Border 
     выберем случайную локацию, атрибут которой равен Border, и присвоим ей      выберем случайную локацию, атрибут которой равен Border, и присвоим ей 
Строка 475: Строка 466:
     из всех соседей текущей локации, атрибут которых равен Inside, выберем      из всех соседей текущей локации, атрибут которых равен Inside, выберем 
     случайную и разрушим стену между ней и текущей локацией     случайную и разрушим стену между ней и текущей локацией
 +</code>    
  
-    В последнем действии предполагается, что такие соседи (имеющие атрибут, равный Inside) у текущей локации имеются. Почему? А потому, что атрибут текущей локации изначально был равен Border — это гарантирует выполнение условия. По той же причине между такими локациями (текущей, атрибут которой был равен Border и соседней — с атрибутом Inside) всегда есть стена. Я понимаю, эти утверждения не так очевидны; на самом деле они вытекают из принципа работы алгоритма — попробуйте сделать несколько шагов вручную, на бумаге, и вы убедитесь в их справедливости. Если какая-то клетка имеет атрибут Inside, это означает, что она принадлежит к «внутренней», уже построенной области лабиринта. Любые две Inside-локации косвенно связаны между собой (то есть существует маршрут между ними). Outside-локации никак не связаны с Inside-локациями — их еще только предстоит обработать. Border-локации тоже находятся извне лабиринта, но каждая из них граничит хотя бы с одной Inside-локацией.+В последнем действии предполагается, что такие соседи (имеющие атрибут, равный Inside) у текущей локации имеются. Почему? А потому, что атрибут текущей локации изначально был равен Border — это гарантирует выполнение условия. По той же причине между такими локациями (текущей, атрибут которой был равен Border и соседней — с атрибутом Inside) всегда есть стена. Я понимаю, эти утверждения не так очевидны; на самом деле они вытекают из принципа работы алгоритма — попробуйте сделать несколько шагов вручную, на бумаге, и вы убедитесь в их справедливости. Если какая-то клетка имеет атрибут Inside, это означает, что она принадлежит к «внутренней», уже построенной области лабиринта. Любые две Inside-локации косвенно связаны между собой (то есть существует маршрут между ними). Outside-локации никак не связаны с Inside-локациями — их еще только предстоит обработать. Border-локации тоже находятся извне лабиринта, но каждая из них граничит хотя бы с одной Inside-локацией.
  
 Листинг 4.3 содержит реализацию алгоритма Прима (далеко не лучшую в плане быстродействия, но прямолинейную и понятную). Листинг 4.3 содержит реализацию алгоритма Прима (далеко не лучшую в плане быстродействия, но прямолинейную и понятную).