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