мета-данные страницы
Загрузка не удалась. Возможно, проблемы с правами доступа?
Различия
Показаны различия между двумя версиями страницы.
Предыдущая версия справа и слеваПредыдущая версияСледующая версия | Предыдущая версияСледующая версияСледующая версия справа и слева | ||
pascal4beginners-pathfind [31/01/2012 10:01] – oca | pascal4beginners-pathfind [31/01/2012 10:09] – oca | ||
---|---|---|---|
Строка 159: | Строка 159: | ||
При записи в файл служебные локации игнорируются, | При записи в файл служебные локации игнорируются, | ||
- | Давайте еще напишем процедуру, | + | Давайте еще напишем процедуру, |
- | + | | |
- | ы, наверное, | + | Вы, наверное, |
procedure ShowMaze(TheMaze : Maze); { нарисовать лабиринт } | procedure ShowMaze(TheMaze : Maze); { нарисовать лабиринт } | ||
Строка 206: | Строка 206: | ||
Рис. 4.3. Результат работы процедуры ShowMaze() | Рис. 4.3. Результат работы процедуры ShowMaze() | ||
| | ||
- | | + | === Решение лабиринта === |
| | ||
- | | + | Итак, лабиринт создан и загружен в память компьютера. Теперь надо научиться его решать. Под этим термином я подразумеваю поиск пути из некоторой стартовой локации в некоторую другую (финишную). Стартовая и финишная локации в лабиринте не фиксированы: |
| | ||
- | | + | === Рекурсивный обход === |
| | ||
- | | + | По правде говоря, |
- | | + | Давайте подумаем, |
- | | + | Если на пути встретилась финишная локация — замечательно, |
- | | + | К сожалению, |
- | | + | Давайте сначала рассмотрим процедуру рекурсивного обхода (листинг 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; | ||
+ | | ||
+ | </ | ||
На первый взгляд процедура кажется довольно громоздкой, | На первый взгляд процедура кажется довольно громоздкой, | ||
Строка 331: | Строка 333: | ||
Если текущая локация находится на краю или в углу лабиринта, | Если текущая локация находится на краю или в углу лабиринта, | ||
- | |||
- | |||
- | |||
- | Рис. 4.4. Решение, | ||
Надеюсь, | Надеюсь, | ||
Строка 340: | Строка 338: | ||
Итак, два недостатка алгоритма лежат на поверхности: | Итак, два недостатка алгоритма лежат на поверхности: | ||
- | | + | 1) он обходит лабиринт нерационально: |
- | | + | 2) полученное решение может не быть оптимальным (в примере алгоритм находит оптимальное решение, |
лабиринте другого решения просто нет). | лабиринте другого решения просто нет). | ||
| | ||
Третий недостаток гораздо более существенный, | Третий недостаток гораздо более существенный, | ||
+ | Проход, | ||
+ | === Алгоритм волновой трассировки === | ||
- | Рис. 4.5. Лабиринт, | + | Описание рекурсивного обхода я начал с фразы: «Давайте подумаем, |
- | Проход, | + | Пометим сначала все локации лабиринта нулями (что означает «локация не содержит киселя»). Стартовую локацию пометим единицей (вылили кисель). Теперь выполняем действия: |
- | Алгоритм волновой трассировки | + | |
- | + | ||
- | Описание рекурсивного обхода я начал с фразы: «Давайте подумаем, | + | |
- | + | ||
- | | + | |
1. помечена ли она нулем | 1. помечена ли она нулем | ||
2. есть ли стена между двумя локациями (выбранной и соседней) если оба условия выполнены, | 2. есть ли стена между двумя локациями (выбранной и соседней) если оба условия выполнены, | ||
- | Рисунок 4.6 иллюстрирует сказанное. | + | Из стартовой позиции можно попасть лишь в локацию, |
- | + | ||
- | + | ||
- | + | ||
- | Рис. 4.6. Первая итерация алгоритма волновой трассировки | + | |
- | + | ||
- | | + | |
- | + | ||
- | + | ||
- | + | ||
- | Рис. 4.7. Результат работы алгоритма волновой трассировки | + | |
- | | + | Если на какой-то итерации мы достигли финишной локации (я считаю финишной правую верхнюю локацию лабиринта), |
- | | + | <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; | ||
+ | </ | ||
- | | + | Главная часть процедуры очень похожа на аналогичный фрагмент из алгоритма рекурсивного обхода: |
- | | + | Итак, поговорим теперь о качествах алгоритма волновой трассировки. Его плюсы налицо: |
- | Генерация лабиринтов | + | |
- | Эта часть главы посвящена тому, как научить компьютер создавать лабиринты автоматически, | + | |
- | Алгоритм Прима | + | |
- | Создадим «заготовку» — лабиринт, | + | |
+ | === Генерация лабиринтов === | ||
+ | |||
+ | Эта часть главы посвящена тому, как научить компьютер создавать лабиринты автоматически, | ||
+ | |||
+ | === Алгоритм Прима === | ||
+ | |||
+ | Создадим «заготовку» — лабиринт, | ||
+ | |||
+ | < | ||
ПОКА атрибут хотя бы одной локации равен Border | ПОКА атрибут хотя бы одной локации равен Border | ||
выберем случайную локацию, | выберем случайную локацию, | ||
Строка 475: | Строка 466: | ||
из всех соседей текущей локации, | из всех соседей текущей локации, | ||
случайную и разрушим стену между ней и текущей локацией | случайную и разрушим стену между ней и текущей локацией | ||
+ | </ | ||
- | | + | В последнем действии предполагается, |
Листинг 4.3 содержит реализацию алгоритма Прима (далеко не лучшую в плане быстродействия, | Листинг 4.3 содержит реализацию алгоритма Прима (далеко не лучшую в плане быстродействия, | ||
Строка 600: | Строка 592: | ||
PrimGenerateMaze := TheMaze; | PrimGenerateMaze := TheMaze; | ||
end; | end; | ||
+ | </ | ||
Я добавил в конец процедуры вызов ShowMaze(), чтобы отображать в динамике процесс генерации лабиринта — очень интересное зрелище на самом деле (рис. 4.8). | Я добавил в конец процедуры вызов ShowMaze(), чтобы отображать в динамике процесс генерации лабиринта — очень интересное зрелище на самом деле (рис. 4.8). | ||
Строка 613: | Строка 606: | ||
Этот метод прост (этим и хорош), | Этот метод прост (этим и хорош), | ||
+ | | ||
+ | === Алгоритм Краскала === | ||
- | |||
- | Рис. 4.8. Алгоритм Прима в процессе работы | ||
- | Алгоритм Краскала | ||
Прежде всего, создадим заготовку, | Прежде всего, создадим заготовку, | ||
+ | < | ||
locations := количество локаций в лабиринте | locations := количество локаций в лабиринте | ||
Строка 627: | Строка 620: | ||
locations := locations – 1 | locations := locations – 1 | ||
КОНЕЦ ЦИКЛА | КОНЕЦ ЦИКЛА | ||
+ | </ | ||
Для того чтобы реализовать его на практике, | Для того чтобы реализовать его на практике, |