мета-данные страницы
Загрузка не удалась. Возможно, проблемы с правами доступа?
Различия
Показаны различия между двумя версиями страницы.
Предыдущая версия справа и слеваПредыдущая версияСледующая версия | Предыдущая версияСледующая версияСледующая версия справа и слева | ||
pascal4beginners-pathfind [31/01/2012 09:57] – 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 содержит реализацию алгоритма Прима (далеко не лучшую в плане быстродействия, |
- | | + | <code |Листинг 4.3. Генерация лабиринта по алгоритму Прима> |
function PrimGenerateMaze(Width, | function PrimGenerateMaze(Width, | ||
Строка 600: | Строка 592: | ||
PrimGenerateMaze := TheMaze; | PrimGenerateMaze := TheMaze; | ||
end; | end; | ||
+ | </ | ||
- | | + | Я добавил в конец процедуры вызов ShowMaze(), чтобы отображать в динамике процесс генерации лабиринта — очень интересное зрелище на самом деле (рис. 4.8). |
- | В алгоритме постоянно используется идея того, как можно выбрать случайную локацию, | + | |
+ | В алгоритме постоянно используется идея того, как можно выбрать случайную локацию, | ||
+ | |||
+ | < | ||
N := количество локаций, | N := количество локаций, | ||
n := случайное число от 1 до N | n := случайное число от 1 до N | ||
выбрать n-ю по счету локацию, | выбрать n-ю по счету локацию, | ||
- | | + | </ |
+ | |||
+ | Этот метод прост (этим и хорош), | ||
+ | | ||
+ | === Алгоритм Краскала === | ||
+ | Прежде всего, создадим заготовку, | ||
- | Рис. 4.8. Алгоритм Прима в процессе работы | + | < |
- | Алгоритм Краскала | + | |
- | Прежде всего, создадим заготовку, | + | |
locations := количество локаций в лабиринте | locations := количество локаций в лабиринте | ||
Строка 622: | Строка 620: | ||
locations := locations – 1 | locations := locations – 1 | ||
КОНЕЦ ЦИКЛА | КОНЕЦ ЦИКЛА | ||
+ | </ | ||
- | | + | Для того чтобы реализовать его на практике, |
function IsConnected(x1, | function IsConnected(x1, | ||
- | | + | Предполагается, |
- | | + | В процессе построения лабиринта мы только разрушаем существующие стены, поэтому если между какими-то двумя локациями существует путь, он уже никуда не исчезнет. Таким образом, |
Для решения этой задачи существуют, | Для решения этой задачи существуют, | ||
Строка 649: | Строка 648: | ||
4. | 4. | ||
- | | + | После работы алгоритма сортировки массив A окажется полностью перемешанным в случайном порядке. В качестве первого случайного элемента можно взять первый элемент массива A, в качестве второго — второй и т. д. Вот и все. Давайте теперь немного уточним алгоритм Краскала с учетом сказанного: |
- | ocations | + | < |
+ | locations | ||
i := 0 | i := 0 | ||
Строка 660: | Строка 660: | ||
разбиваем стену | разбиваем стену | ||
locations := locations – 1 | locations := locations – 1 | ||
- | EIIAO OEEEA | + | </ |
+ | |||
+ | Любую стену можно задать четырьмя числами: | ||
- | Любую стену можно задать четырьмя числами: | + | Теперь можно заняться реализацией алгоритма. Мой вариант приведен в листинге 4.4, скриншот работающей программы — на рис. 4.9. |
- | | + | |
| | ||
<code | Листинг 4.4. Генерация лабиринта по алгоритму Краскала> | <code | Листинг 4.4. Генерация лабиринта по алгоритму Краскала> |