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

Различия

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

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

Предыдущая версия справа и слеваПредыдущая версия
Следующая версия		Предыдущая версия
Следующая версияСледующая версия справа и слева
pascal4beginners-pathfind [31/01/2012 09:57] – ocapascal4beginners-pathfind [31/01/2012 10:03] – oca
Строка 478: Строка 478:
     В последнем действии предполагается, что такие соседи (имеющие атрибут, равный Inside) у текущей локации имеются. Почему? А потому, что атрибут текущей локации изначально был равен Border — это гарантирует выполнение условия. По той же причине между такими локациями (текущей, атрибут которой был равен Border и соседней — с атрибутом Inside) всегда есть стена. Я понимаю, эти утверждения не так очевидны; на самом деле они вытекают из принципа работы алгоритма — попробуйте сделать несколько шагов вручную, на бумаге, и вы убедитесь в их справедливости. Если какая-то клетка имеет атрибут Inside, это означает, что она принадлежит к «внутренней», уже построенной области лабиринта. Любые две Inside-локации косвенно связаны между собой (то есть существует маршрут между ними). Outside-локации никак не связаны с Inside-локациями — их еще только предстоит обработать. Border-локации тоже находятся извне лабиринта, но каждая из них граничит хотя бы с одной Inside-локацией.     В последнем действии предполагается, что такие соседи (имеющие атрибут, равный Inside) у текущей локации имеются. Почему? А потому, что атрибут текущей локации изначально был равен Border — это гарантирует выполнение условия. По той же причине между такими локациями (текущей, атрибут которой был равен Border и соседней — с атрибутом Inside) всегда есть стена. Я понимаю, эти утверждения не так очевидны; на самом деле они вытекают из принципа работы алгоритма — попробуйте сделать несколько шагов вручную, на бумаге, и вы убедитесь в их справедливости. Если какая-то клетка имеет атрибут Inside, это означает, что она принадлежит к «внутренней», уже построенной области лабиринта. Любые две Inside-локации косвенно связаны между собой (то есть существует маршрут между ними). Outside-локации никак не связаны с Inside-локациями — их еще только предстоит обработать. Border-локации тоже находятся извне лабиринта, но каждая из них граничит хотя бы с одной Inside-локацией.
  
-    Листинг 4.3 содержит реализацию алгоритма Прима (далеко не лучшую в плане быстродействия, но прямолинейную и понятную).+Листинг 4.3 содержит реализацию алгоритма Прима (далеко не лучшую в плане быстродействия, но прямолинейную и понятную).
  
-    Листинг 4.3. Генерация лабиринта по алгоритму Прима+<code |Листинг 4.3. Генерация лабиринта по алгоритму Прима>
  
     function PrimGenerateMaze(Width, Height : Integer) : Maze;     function PrimGenerateMaze(Width, Height : Integer) : Maze;
Строка 600: Строка 600:
     PrimGenerateMaze := TheMaze;      PrimGenerateMaze := TheMaze; 
     end;     end;
 +</code>
  
-    Я добавил в конец процедуры вызов ShowMaze(), чтобы отображать в динамике процесс генерации лабиринта — очень интересное зрелище на самом деле (рис. 4.8).  +Я добавил в конец процедуры вызов ShowMaze(), чтобы отображать в динамике процесс генерации лабиринта — очень интересное зрелище на самом деле (рис. 4.8).  
-    В алгоритме постоянно используется идея того, как можно выбрать случайную локацию, помеченную некоторым атрибутом: +     
 +В алгоритме постоянно используется идея того, как можно выбрать случайную локацию, помеченную некоторым атрибутом:  
 + 
 +<code>
     N := количество локаций, помеченных заданным атрибутом      N := количество локаций, помеченных заданным атрибутом 
     n := случайное число от 1 до N      n := случайное число от 1 до N 
     выбрать n-ю по счету локацию, помеченную заданным атрибутом      выбрать n-ю по счету локацию, помеченную заданным атрибутом 
-    Этот метод прост (этим и хорош), зато требует для работы двух циклов, каждый из которых пробегает по всему лабиринту. В трех местах я применил оператор goto — надеюсь, никто не считает дурным тоном его использование для выхода из вложенного цикла?+</code>     
 +     
 +Этот метод прост (этим и хорош), зато требует для работы двух циклов, каждый из которых пробегает по всему лабиринту. В трех местах я применил оператор goto — надеюсь, никто не считает дурным тоном его использование для выхода из вложенного цикла?
  
 +    
 +===  Алгоритм Краскала ===
  
 +Прежде всего, создадим заготовку, аналогичную той, что мы использовали в алгоритме Прима — лабиринт со всеми возможными стенами. Алгоритм Краскала описывается всего семью строками на псевдокоде:
  
-    Рис. 4.8. Алгоритм Прима в процессе работы +<code>
-    Алгоритм Краскала +
-    Прежде всего, создадим заготовку, аналогичную той, что мы использовали в алгоритме Прима — лабиринт со всеми возможными стенами. Алгоритм Краскала описывается всего семью строками на псевдокоде: +
     locations := количество локаций в лабиринте     locations := количество локаций в лабиринте
  
Строка 622: Строка 628:
     locations := locations – 1      locations := locations – 1 
     КОНЕЦ ЦИКЛА     КОНЕЦ ЦИКЛА
 +</code>
  
-    Для того чтобы реализовать его на практике, потребуется, конечно же, гораздо больше усилий. Во-первых, нам понадобится функция, которая определяет, существует ли путь между двумя заданными локациями или нет. Для этого можно (и нужно) воспользоваться рекурсивным обходом или алгоритмом волновой трассировки, которые описаны выше в этой главе. Думаю, вам не составит труда чуть доработать любую из приведенных процедур, чтобы получилась функция:+Для того чтобы реализовать его на практике, потребуется, конечно же, гораздо больше усилий. Во-первых, нам понадобится функция, которая определяет, существует ли путь между двумя заданными локациями или нет. Для этого можно (и нужно) воспользоваться рекурсивным обходом или алгоритмом волновой трассировки, которые описаны выше в этой главе. Думаю, вам не составит труда чуть доработать любую из приведенных процедур, чтобы получилась функция:
  
     function IsConnected(x1, y1, x2, y2) : Boolean     function IsConnected(x1, y1, x2, y2) : Boolean
  
-    Предполагается, что она будет локальной и поэтому сможет получить доступ к лабиринту через переменную TheMaze — мы уже применяли такой подход. Во-вторых (и это более интересно), нам придется решить задачу случайного выбора без повторов.+Предполагается, что она будет локальной и поэтому сможет получить доступ к лабиринту через переменную TheMaze — мы уже применяли такой подход. Во-вторых (и это более интересно), нам придется решить задачу случайного выбора без повторов.
  
-    В процессе построения лабиринта мы только разрушаем существующие стены, поэтому если между какими-то двумя локациями существует путь, он уже никуда не исчезнет. Таким образом, нет никакого резона выбирать два раза одну и ту же стену. Если некоторая стена была выбрана генератором случайных чисел однажды и осталась не разрушенной после текущей итерации алгоритма, путь между соответствующими локациями есть, и он останется в будущем. Похожая ситуация возникает при моделировании игры в русское лото: если некоторый бочонок уже вынут из мешка, его номер больше не должен выпадать.+В процессе построения лабиринта мы только разрушаем существующие стены, поэтому если между какими-то двумя локациями существует путь, он уже никуда не исчезнет. Таким образом, нет никакого резона выбирать два раза одну и ту же стену. Если некоторая стена была выбрана генератором случайных чисел однажды и осталась не разрушенной после текущей итерации алгоритма, путь между соответствующими локациями есть, и он останется в будущем. Похожая ситуация возникает при моделировании игры в русское лото: если некоторый бочонок уже вынут из мешка, его номер больше не должен выпадать.
  
     Для решения этой задачи существуют, по крайней мере, два известных метода.     Для решения этой задачи существуют, по крайней мере, два известных метода.
Строка 649: Строка 656:
     4.     4.
  
-    После работы алгоритма сортировки массив A окажется полностью перемешанным в случайном порядке. В качестве первого случайного элемента можно взять первый элемент массива A, в качестве второго — второй и т. д. Вот и все. Давайте теперь немного уточним алгоритм Краскала с учетом сказанного: l+После работы алгоритма сортировки массив A окажется полностью перемешанным в случайном порядке. В качестве первого случайного элемента можно взять первый элемент массива A, в качестве второго — второй и т. д. Вот и все. Давайте теперь немного уточним алгоритм Краскала с учетом сказанного: 
  
-    ocations := количество локаций в лабиринте { Width * Height } записываем все стены лабиринта в массив Walls перемешиваем массив Walls в случайном порядке+<code>     
 +    locations := количество локаций в лабиринте { Width * Height } записываем все стены лабиринта в массив Walls перемешиваем массив Walls в случайном порядке
  
     i := 0     i := 0
Строка 660: Строка 668:
     разбиваем стену      разбиваем стену 
     locations := locations – 1      locations := locations – 1 
-    EIIAO OEEEA+</code> 
 + 
 +Любую стену можно задать четырьмя числами: (x, y, dx, dy), то есть с помощью координат локации и смещений (я особо не останавливаюсь на этом, потому что мы не раз уже пользовались таким способом, например в функции CanGo() и процедуре BreakWall()). Таким образом, «массив стен» — это массив таких четверок. 
  
-    Любую стену можно задать четырьмя числами: (x, y, dx, dy), то есть с помощью координат локации и смещений (я особо не останавливаюсь на этом, потому что мы не раз уже пользовались таким способом, например в функции CanGo() и процедуре BreakWall()). Таким образом, «массив стен» — это массив таких четверок.  +Теперь можно заняться реализацией алгоритма. Мой вариант приведен в листинге 4.4, скриншот работающей программы — на рис. 4.9. 
-    Теперь можно заняться реализацией алгоритма. Мой вариант приведен в листинге 4.4, скриншот работающей программы — на рис. 4.9. +
          
 <code | Листинг 4.4. Генерация лабиринта по алгоритму Краскала> <code | Листинг 4.4. Генерация лабиринта по алгоритму Краскала>