мета-данные страницы
Загрузка не удалась. Возможно, проблемы с правами доступа?
Различия
Показаны различия между двумя версиями страницы.
Предыдущая версия справа и слеваПредыдущая версияСледующая версия | Предыдущая версияПоследняя версияСледующая версия справа и слева | ||
pascal4beginners-pathfind [31/01/2012 09:57] – oca | pascal4beginners-pathfind [31/01/2012 10:24] – oca | ||
---|---|---|---|
Строка 5: | Строка 5: | ||
=== Поиск пути === | === Поиск пути === | ||
- | ==== Создание лабиринта ==== | + | ===== Поиск пути на карте ===== |
- | {{: | + | |
- | [[http:// | + | === Генерация карты === |
- | Мозговой Максим Владимирович - Занимательное программирование: | + | |
+ | === Поиск пути === | ||
- | Глава 4 | + | [[http:// |
- | Лабиринты | + | |
- | В лабиринте у вас, по крайней мере, есть цель. | ||
- | |||
- | Евгений Кащеев | ||
- | |||
- | Мне нравится эта тема. С одной стороны, | ||
- | |||
- | Итак, сейчас мы займемся лабиринтами. Если говорить более конкретно, | ||
- | |||
- | 1. определить, | ||
- | 2. договориться, | ||
- | 3. выяснить, | ||
- | |||
- | Представление лабиринтов в памяти | ||
- | |||
- | Толковый словарь русского языка определяет лабиринт как «запутанную сеть дорожек, | ||
- | |||
- | |||
- | |||
- | Рис. 4.1. Пример лабиринта | ||
- | |||
- | Именно с лабиринтами такого типа мы и будем работать. Следующий вопрос — как представить лабиринт в памяти компьютера. Заманчиво просто создать двумерный массив из нулей и единиц: | ||
- | |||
- | |||
- | |||
- | Рис. 4.2. Простое представление лабиринта в памяти | ||
- | |||
- | Надо только при выводе на экран рисовать стенки тонкими линиями (я не стал этого делать для наглядности) — и все. Этот способ, | ||
- | |||
- | В каждой локации лабиринта нас интересует информация о стенах/ | ||
- | |||
- | type Location = record | ||
- | left_wall, right_wall, up_wall, down_wall : Boolean; | ||
- | |||
- | end; | ||
- | |||
- | Если значение поля равно true, значит, | ||
- | |||
- | Location станет еще более простой: | ||
- | |||
- | type Location = record | ||
- | left_wall, up_wall : Boolean; | ||
- | |||
- | end; | ||
- | |||
- | Сам лабиринт будет представлять собой двумерный массив таких записей: | ||
- | type Maze = array of array of Location; | ||
- | |||
- | При этом нельзя забывать о правиле: | ||
- | |||
- | В дальнейшем нам потребуются процедуры загрузки/ | ||
- | |||
- | Поскольку пока еще у нас нет возможности сгенерировать лабиринт автоматически, | ||
- | |||
- | Остается выяснить, | ||
- | |||
- | Для примера можете воспользоваться определением маленького лабиринта (5 ? 4), который я только что набросал на бумаге: | ||
- | 1 1 | ||
- | 1 1 | ||
- | 1 0 | ||
- | 1 1 | ||
- | 1 0 | ||
- | 0 1 | ||
- | 1 0 | ||
- | 0 1 | ||
- | 0 0 | ||
- | 1 1 | ||
- | 0 1 | ||
- | 1 0 | ||
- | 1 0 | ||
- | 0 0 | ||
- | 0 0 | ||
- | 1 1 | ||
- | 0 0 | ||
- | 0 1 | ||
- | 0 1 | ||
- | 0 1 | ||
- | |||
- | Процедура чтения лабиринта приведена целиком ниже: | ||
- | |||
- | { загрузить лабиринт } | ||
- | |||
- | procedure LoadMaze(var TheMaze : Maze; FileName : string); | ||
- | var f : TextFile; { файл с описанием лабиринта } | ||
- | Height, Width : | ||
- | x, y : Integer; { текущая локация } | ||
- | lw, uw : Integer; { временные переменные } | ||
- | |||
- | begin | ||
- | |||
- | AssignFile(f, | ||
- | Reset(f); | ||
- | |||
- | ReadLn(f, Width, Height); { прочитать высоту и ширину } | ||
- | SetLength(TheMaze, | ||
- | |||
- | for y := 0 to Height do { цикл по всем локациям } | ||
- | for x := 0 to Width do | ||
- | if (y = Height) or (x = Width) then { если локация - служебная } | ||
- | begin | ||
- | TheMaze[x, y].left_wall := true; { обе стены существуют } | ||
- | TheMaze[x, y].up_wall := true; | ||
- | end | ||
- | else | ||
- | begin { иначе считываем } | ||
- | ReadLn(f, uw, lw); { из файла } | ||
- | TheMaze[x, y].left_wall := Boolean(lw); | ||
- | TheMaze[x, y].up_wall := Boolean(uw); | ||
- | end; { к типу Boolean } | ||
- | CloseFile(f); | ||
- | end; { закрыть файл } | ||
- | |||
- | Обратите внимание на некоторые тонкости. Во-первых, | ||
- | |||
- | Процедура записи выглядит немного проще: | ||
- | |||
- | { nio?aieou eaae?eio } | ||
- | |||
- | procedure SaveMaze(TheMaze : Maze; FileName : string); | ||
- | var f : TextFile; { файл с описанием лабиринта } | ||
- | Height, Width : Integer; { высота и ширина } | ||
- | x, y : Integer; { координаты текущей локации } | ||
- | begin | ||
- | AssignFile(f, | ||
- | Rewrite(f); | ||
- | Height := High(TheMaze[0]); | ||
- | Width := High(TheMaze); | ||
- | WriteLn(f, Width, ' ', Height); { запись в файл высоты и ширины } | ||
- | for y := 0 to Height - 1 do { запись данных локаций } | ||
- | for x := 0 to Width - 1 do | ||
- | WriteLn(f, Integer(TheMaze[x, | ||
- | Integer(TheMaze[x, | ||
- | CloseFile(f); | ||
- | end; | ||
- | |||
- | Главная «хитрость» здесь — это определение размеров лабиринта. Не забывайте, | ||
- | |||
- | Width := High(TheMaze); | ||
- | |||
- | Функция High(), как вы, надеюсь, | ||
- | |||
- | Чтобы определить высоту, | ||
- | |||
- | При записи в файл служебные локации игнорируются, | ||
- | |||
- | Давайте еще напишем процедуру, | ||
- | |||
- | ы, наверное, | ||
- | |||
- | procedure ShowMaze(TheMaze : Maze); { нарисовать лабиринт } | ||
- | var x, y : Integer; | ||
- | Height, Width : Integer; { высота и ширина лабиринта } | ||
- | begin | ||
- | Width := High(TheMaze); | ||
- | Height := High(TheMaze[0]); | ||
- | |||
- | with Form1.BackBuffer.Canvas do | ||
- | begin { очистка буфера } | ||
- | FillRect(Rect(0, | ||
- | for x := 0 to Width - 1 do | ||
- | for y := 0 to Height - 1 do | ||
- | begin | ||
- | { если в локации есть верхняя стена } | ||
- | if TheMaze[x, y].up_wall then | ||
- | begin | ||
- | MoveTo(x * CellSize, y * CellSize); { рисуем ее } | ||
- | LineTo((x + 1) * CellSize, y * CellSize); | ||
- | end; | ||
- | |||
- | { если в локации есть левая стена } | ||
- | if TheMaze[x, y].left_wall then | ||
- | begin | ||
- | MoveTo(x * CellSize, y * CellSize); { рисуем и ее } | ||
- | LineTo(x * CellSize, (y + 1) * CellSize); | ||
- | end; | ||
- | end; | ||
- | MoveTo(0, Height * CellSize); { рисуем стену снизу и } | ||
- | LineTo(Width * CellSize, Height * CellSize); { справа от лабиринта } | ||
- | LineTo(Width * CellSize, 0); | ||
- | end; | ||
- | { отобразить результат на основном экране } | ||
- | Form1.Screen.Canvas.CopyRect(Rect(0, | ||
- | Form1.Screen.Height), | ||
- | Rect(0, 0, Form1.Screen.Width, | ||
- | end; | ||
- | |||
- | CellSize — это константа, | ||
- | |||
- | |||
- | |||
- | Рис. 4.3. Результат работы процедуры ShowMaze() | ||
- | | ||
- | === Решение лабиринта === | ||
- | | ||
- | Итак, лабиринт создан и загружен в память компьютера. Теперь надо научиться его решать. Под этим термином я подразумеваю поиск пути из некоторой стартовой локации в некоторую другую (финишную). Стартовая и финишная локации в лабиринте не фиксированы: | ||
- | | ||
- | === Рекурсивный обход === | ||
- | | ||
- | По правде говоря, | ||
- | |||
- | Давайте подумаем, | ||
- | |||
- | Если на пути встретилась финишная локация — замечательно, | ||
- | |||
- | К сожалению, | ||
- | |||
- | Давайте сначала рассмотрим процедуру рекурсивного обхода (листинг 4.1), а потом я буду ее критиковать. | ||
- | |||
- | Листинг 4.1. Рекурсивный обход лабиринта | ||
- | |||
- | procedure RecursiveSolve(TheMaze : Maze; xs, ys, xf, yf : Integer); var Visited : array of array of Boolean; { карта посещенных локаций } | ||
- | x, y, xc, yc : Integer; | ||
- | i : Integer; | ||
- | Path : array of TPoint; { результирующий маршрут } | ||
- | Height, Width : Integer; | ||
- | const dx : array[1..4] of Integer = (1, 0, -1, 0); { смещения } | ||
- | dy : array[1..4] of Integer = (0, -1, 0, 1); | ||
- | { служебная функция: | ||
- | |||
- | Листинг 4.1 (продолжение) | ||
- | |||
- | (x, y) в локацию (x + dx, y + dy), то есть нет ли между ними стены } | ||
- | |||
- | function CanGo(x, y, dx, dy : Integer) : Boolean; | ||
- | |||
- | begin | ||
- | if dx = -1 then CanGo := not TheMaze[x, y].left_wall | ||
- | else if dx = 1 then CanGo := not TheMaze[x + 1, y].left_wall | ||
- | else if dy = -1 then CanGo := not TheMaze[x, y].up_wall | ||
- | else CanGo := not TheMaze[x, y + 1].up_wall; | ||
- | end; | ||
- | |||
- | { поиск финишной локации из точки (x, y) } | ||
- | function Solve(x, y, depth : Integer) : Boolean; | ||
- | var i : Integer; | ||
- | begin | ||
- | Visited[x, y] := true; { пометить локацию как посещенную } | ||
- | Path[depth] := Point(x, y); { добавить ее в описание маршрута } | ||
- | Path[depth + 1] := Point(-1, -1); { добавить признак конца маршрута } | ||
- | |||
- | if (x = xf) and (y = yf) then { если финишная локация найдена } | ||
- | begin | ||
- | Solve := true; { конец алгоритма } | ||
- | Exit; | ||
- | end; | ||
- | |||
- | for i := 1 to 4 do | ||
- | { если дорожка свободна, | ||
- | if CanGo(x, y, dx[i], dy[i]) and | ||
- | not Visited[x + dx[i], y + dy[i]] then | ||
- | if Solve(x + dx[i], y + dy[i], depth + 1) then | ||
- | begin | ||
- | Solve := true; { если решение найдено } | ||
- | Exit; { конец алгоритма } | ||
- | end; | ||
- | |||
- | Visited[x, y] := false; { пометить локацию как непосещенную } | ||
- | Solve := false; { решение не найдено } | ||
- | end; | ||
- | |||
- | begin { главная процедура }<> | ||
- | Width := High(TheMaze); | ||
- | Height := High(TheMaze[0]); | ||
- | SetLength(Path, | ||
- | SetLength(Visited, | ||
- | |||
- | for x := 0 to Width - 1 do | ||
- | for y := 0 to Height - 1 do | ||
- | Visited[x, y] := false; { изначально ни одна не посещена } | ||
- | |||
- | if Solve(xs, ys, 0) then { если найдено решение, | ||
- | begin | ||
- | i := 0; | ||
- | while not ((Path[i].X = -1) and (Path[i].Y = -1)) do | ||
- | begin | ||
- | xc := CellSize * (2 * Path[i].X + 1) div 2; | ||
- | yc := CellSize * (2 * Path[i].Y + 1) div 2; | ||
- | Form1.Screen.Canvas.Ellipse(xc - 5, yc - 5, xc + 5, yc + 5); | ||
- | i := i + 1; | ||
- | end; | ||
- | end; end; | ||
- | |||
- | На первый взгляд процедура кажется довольно громоздкой, | ||
- | |||
- | пометить текущую локацию как посещенную | ||
- | |||
- | добавить ее в «бортовой журнал»... | ||
- | |||
- | Обратите внимание на «признак конца». Нам как-то надо отмечать конец журнала. Поскольку локации с координатами (-1, -1) не существует, | ||
- | |||
- | исследуем каждую свободную дорожку Вот здесь я применил небольшую хитрость: | ||
- | |||
- | Чтобы не писать четыре раза | ||
- | |||
- | исследовать_дорожку(x, | ||
- | |||
- | исследовать_дорожку(x – 1, y) | ||
- | |||
- | исследовать_дорожку(x, | ||
- | |||
- | исследовать_дорожку(x + 1, y) | ||
- | |||
- | я воспользовался циклом (не забывайте, | ||
- | |||
- | for i := 1 to 4 do | ||
- | |||
- | enneaaiaaou_ai? | ||
- | |||
- | Если решение найдено, | ||
- | |||
- | Обратите также внимание на строку: | ||
- | |||
- | if CanGo(x, y, dx[i], dy[i]) and | ||
- | |||
- | not Visited[x + dx[i], y + dy[i]] then ... | ||
- | |||
- | Если текущая локация находится на краю или в углу лабиринта, | ||
- | |||
- | |||
- | |||
- | Рис. 4.4. Решение, | ||
- | |||
- | Надеюсь, | ||
- | |||
- | Итак, два недостатка алгоритма лежат на поверхности: | ||
- | |||
- | 1) он обходит лабиринт нерационально: | ||
- | |||
- | 2) полученное решение может не быть оптимальным (в примере алгоритм находит оптимальное решение, | ||
- | лабиринте другого решения просто нет). | ||
- | | ||
- | Третий недостаток гораздо более существенный, | ||
- | |||
- | |||
- | |||
- | Рис. 4.5. Лабиринт, | ||
- | |||
- | Проход, | ||
- | Алгоритм волновой трассировки | ||
- | |||
- | Описание рекурсивного обхода я начал с фразы: «Давайте подумаем, | ||
- | |||
- | Пометим сначала все локации лабиринта нулями (что означает «локация не содержит киселя»). Стартовую локацию пометим единицей (вылили кисель). Теперь выполняем действия: | ||
- | |||
- | 1. помечена ли она нулем | ||
- | 2. есть ли стена между двумя локациями (выбранной и соседней) если оба условия выполнены, | ||
- | |||
- | Рисунок 4.6 иллюстрирует сказанное. | ||
- | |||
- | |||
- | |||
- | Рис. 4.6. Первая итерация алгоритма волновой трассировки | ||
- | |||
- | Из стартовой позиции можно попасть лишь в локацию, | ||
- | |||
- | |||
- | |||
- | Рис. 4.7. Результат работы алгоритма волновой трассировки | ||
- | |||
- | Если на какой-то итерации мы достигли финишной локации (я считаю финишной правую верхнюю локацию лабиринта), | ||
- | |||
- | Листинг 4.2. Алгоритм волновой трассировки | ||
- | |||
- | procedure WaveTracingSolve(TheMaze : Maze; xs, ys, xf, yf : Integer); | ||
- | var Mark : array of array of Integer; { метки локаций } | ||
- | x, y, xc, yc : Integer; | ||
- | N, i : Integer; | ||
- | Height, Width : Integer; | ||
- | const dx : array[1..4] of Integer = (1, 0, -1, 0); { смещения } | ||
- | dy : array[1..4] of Integer = (0, -1, 0, 1); | ||
- | { neo?aaiay ooieoey: ii?aaaeyao, ii?ii ee i?ieoe ec eieaoee | ||
- | (x, y) в локацию (x + dx, y + dy), то есть нет ли между ними стены } | ||
- | function CanGo(x, y, dx, dy : Integer) : Boolean; | ||
- | |||
- | Листинг 4.2 (продолжение) begin | ||
- | if dx = -1 then CanGo := not TheMaze[x, y].left_wall | ||
- | else if dx = 1 then CanGo := not TheMaze[x + 1, y].left_wall | ||
- | else if dy = -1 then CanGo := not TheMaze[x, y].up_wall | ||
- | else CanGo := not TheMaze[x, y + 1].up_wall; | ||
- | end; | ||
- | |||
- | function Solve : Boolean; { поиск решения } | ||
- | var i, N, x, y : Integer; | ||
- | NoSolution : Boolean; | ||
- | begin | ||
- | N := 1; { начинаем с итерации номер 1 } | ||
- | |||
- | repeat | ||
- | NoSolution := true; { пессимистично полагаем, | ||
- | for x := 0 to Width - 1 do | ||
- | for y := 0 to Height - 1 do | ||
- | if Mark[x, y] = N then { найти локации, | ||
- | for i := 1 to 4 do { просмотр соседних локаций } | ||
- | if CanGo(x, y, dx[i], dy[i]) and | ||
- | (Mark[x + dx[i], y + dy[i]] = 0) then | ||
- | begin { локация доступна и помечена нулем } | ||
- | NoSolution := false; { есть шанс найти | ||
- | решение } | ||
- | { помечаем соседнюю локацию числом N + | ||
- | 1 } | ||
- | Mark[x + dx[i], y + dy[i]] := N + 1; | ||
- | if (x + dx[i] = xf) and (y + dy[i] = yf) then | ||
- | begin | ||
- | Solve := true; { дошли до финишной | ||
- | локации } | ||
- | Exit; { конец алгоритма } | ||
- | end; | ||
- | end; | ||
- | N := N + 1; { переход к следующей итерации } | ||
- | until NoSolution; { повторять, | ||
- | Solve := false; { нет, решение не найдено } | ||
- | end; | ||
- | |||
- | begin | ||
- | Width := High(TheMaze); | ||
- | Height := High(TheMaze[0]); | ||
- | SetLength(Mark, | ||
- | |||
- | for x := 0 to Width - 1 do { изначально все заполняется нулями } | ||
- | for y := 0 to Height - 1 do | ||
- | Mark[x, y] := 0; | ||
- | |||
- | Mark[xs, ys] := 1; { стартовой локации соответствует единица } | ||
- | if Solve then { если найдено решение, | ||
- | begin | ||
- | x := xf; y := yf; | ||
- | for N := Mark[xf, yf] downto 1 do | ||
- | begin | ||
- | { рисуем окружность на очередной локации маршрута } | ||
- | xc := CellSize * (2 * x + 1) div 2; | ||
- | yc := CellSize * (2 * y + 1) div 2; | ||
- | Form1.Screen.Canvas.Ellipse(xc - 5, yc - 5, xc + 5, yc + 5); | ||
- | |||
- | for i := 1 to 4 do | ||
- | if CanGo(x, y, dx[i], dy[i]) and | ||
- | (Mark[x + dx[i], y + dy[i]] = N - 1) then | ||
- | begin | ||
- | x := x + dx[i]; { ищем следующую локацию | ||
- | маршрута } | ||
- | y := y + dy[i]; | ||
- | Break; | ||
- | end; | ||
- | end; | ||
- | end; | ||
- | end; | ||
- | |||
- | Главная часть процедуры очень похожа на аналогичный фрагмент из алгоритма рекурсивного обхода: | ||
- | |||
- | Итак, поговорим теперь о качествах алгоритма волновой трассировки. Его плюсы налицо: | ||
- | Генерация лабиринтов | ||
- | Эта часть главы посвящена тому, как научить компьютер создавать лабиринты автоматически, | ||
- | Алгоритм Прима | ||
- | Создадим «заготовку» — лабиринт, | ||
- | |||
- | ПОКА атрибут хотя бы одной локации равен Border | ||
- | выберем случайную локацию, | ||
- | атрибут Inside | ||
- | изменим на Border атрибут всех соседних с текущей локаций, | ||
- | равен Outside | ||
- | из всех соседей текущей локации, | ||
- | случайную и разрушим стену между ней и текущей локацией | ||
- | |||
- | В последнем действии предполагается, | ||
- | |||
- | Листинг 4.3 содержит реализацию алгоритма Прима (далеко не лучшую в плане быстродействия, | ||
- | |||
- | Листинг 4.3. Генерация лабиринта по алгоритму Прима | ||
- | |||
- | function PrimGenerateMaze(Width, | ||
- | |||
- | type AttrType = (Inside, Outside, Border); { тип " | ||
- | |||
- | var TheMaze : Maze; { сам лабиринт } | ||
- | x, y, i : Integer; | ||
- | xc, yc : Integer; | ||
- | xloc, yloc : Integer; | ||
- | Attribute : array of array of AttrType; { карта атрибутов } | ||
- | IsEnd : Boolean; | ||
- | counter : Integer; | ||
- | const dx : array[1..4] of Integer = (1, 0, -1, 0); { смещения } | ||
- | dy : array[1..4] of Integer = (0, -1, 0, 1); | ||
- | |||
- | label ExitFor1, ExitFor2, ExitFor3; { eniieucoaiua iaoee } | ||
- | procedure BreakWall(x, | ||
- | begin { между локациями } | ||
- | if dx = -1 then TheMaze[x, y].left_wall := false | ||
- | else if dx = 1 then TheMaze[x + 1, y].left_wall := false | ||
- | else if dy = -1 then TheMaze[x, y].up_wall := false | ||
- | else TheMaze[x, y + 1].up_wall := false; end; | ||
- | |||
- | begin | ||
- | SetLength(Attribute, | ||
- | SetLength(TheMaze, | ||
- | |||
- | for x := 0 to Width - 1 do { изначально все атрибуты } | ||
- | for y := 0 to Height - 1 do { равны Outside } | ||
- | Attribute[x, | ||
- | |||
- | for y := 0 to Height do { все стены изначально } | ||
- | for x := 0 to Width do { существуют } | ||
- | begin | ||
- | TheMaze[x, y].left_wall := true; | ||
- | TheMaze[x, y].up_wall := true; | ||
- | end; | ||
- | |||
- | Randomize; | ||
- | x := Random(Width); | ||
- | y := Random(Height); | ||
- | Attribute[x, | ||
- | |||
- | for i := 1 to 4 do { всем ее соседям присваиваем } | ||
- | begin { атрибут Border } | ||
- | xc := x + dx[i]; | ||
- | yc := y + dy[i]; | ||
- | if (xc >= 0) and (yc >= 0) and (xc < Width) and (yc < Height) then | ||
- | Attribute[xc, | ||
- | end; | ||
- | |||
- | repeat { главный цикл } | ||
- | IsEnd := true; | ||
- | counter := 0; | ||
- | for x := 0 to Width - 1 do { подсчитываем количество } | ||
- | for y := 0 to Height - 1 do { локаций с атрибутом Border } | ||
- | if Attribute[x, | ||
- | |||
- | counter := Random(counter) + 1; { выбираем из них } | ||
- | for x := 0 to Width - 1 do { одну случайную } | ||
- | for y := 0 to Height - 1 do | ||
- | if Attribute[x, | ||
- | begin | ||
- | counter := counter - 1; | ||
- | if counter = 0 then | ||
- | |||
- | Листинг 4.3 (продолжение) | ||
- | begin | ||
- | xloc := x; { xloc, yloc - ее координаты } | ||
- | yloc := y; | ||
- | goto ExitFor1; { выход из цикла } | ||
- | end; | ||
- | end; | ||
- | ExitFor1: | ||
- | Attribute[xloc, | ||
- | |||
- | counter := 0; | ||
- | for i := 1 to 4 do | ||
- | begin | ||
- | xc := xloc + dx[i]; | ||
- | yc := yloc + dy[i]; | ||
- | if (xc >= 0) and (yc >= 0) and (xc < Width) and (yc < Height) then | ||
- | begin { подсчитать количество локаций с атрибутом Inside } | ||
- | if Attribute[xc, | ||
- | if Attribute[xc, | ||
- | Attribute[xc, | ||
- | end; | ||
- | end; | ||
- | |||
- | counter := Random(counter) + 1; { выбрать случайную Inside-локацию } | ||
- | for i := 1 to 4 do | ||
- | begin | ||
- | xc := xloc + dx[i]; | ||
- | yc := yloc + dy[i]; | ||
- | if (xc >= 0) and (yc >= 0) and (xc < Width) and (yc < Height) | ||
- | and (Attribute[xc, | ||
- | begin | ||
- | counter := counter - 1; | ||
- | if counter = 0 then { разрушить стену между ней и } | ||
- | begin { текущей локацией } | ||
- | BreakWall(xloc, | ||
- | goto ExitFor2; | ||
- | end; | ||
- | end; | ||
- | end; | ||
- | ExitFor2: | ||
- | for x := 0 to Width - 1 do { определить, | ||
- | for y := 0 to Height - 1 do { хоть одна локация с } | ||
- | if Attribute[x, | ||
- | begin | ||
- | IsEnd := false; { если да, продолжаем } | ||
- | goto ExitFor3; { выполнять алгоритм } | ||
- | end; | ||
- | ExitFor3: | ||
- | ShowMaze(TheMaze); | ||
- | Application.ProcessMessages; | ||
- | until IsEnd; | ||
- | PrimGenerateMaze := TheMaze; | ||
- | end; | ||
- | |||
- | Я добавил в конец процедуры вызов ShowMaze(), чтобы отображать в динамике процесс генерации лабиринта — очень интересное зрелище на самом деле (рис. 4.8). | ||
- | В алгоритме постоянно используется идея того, как можно выбрать случайную локацию, | ||
- | N := количество локаций, | ||
- | n := случайное число от 1 до N | ||
- | выбрать n-ю по счету локацию, | ||
- | Этот метод прост (этим и хорош), | ||
- | |||
- | |||
- | |||
- | Рис. 4.8. Алгоритм Прима в процессе работы | ||
- | Алгоритм Краскала | ||
- | Прежде всего, создадим заготовку, | ||
- | |||
- | locations := количество локаций в лабиринте | ||
- | |||
- | ПОКА locations > 1 | ||
- | выбираем случайную стену в лабиринте | ||
- | ЕСЛИ не существует пути между локациями, | ||
- | разбиваем стену | ||
- | locations := locations – 1 | ||
- | КОНЕЦ ЦИКЛА | ||
- | |||
- | Для того чтобы реализовать его на практике, | ||
- | |||
- | function IsConnected(x1, | ||
- | |||
- | Предполагается, | ||
- | |||
- | В процессе построения лабиринта мы только разрушаем существующие стены, поэтому если между какими-то двумя локациями существует путь, он уже никуда не исчезнет. Таким образом, | ||
- | |||
- | Для решения этой задачи существуют, | ||
- | |||
- | 1. | ||
- | |||
- | Запоминать все ранее выбранные генератором случайных чисел значения. Если на очередной итерации выпало какое-то «старое» значение, | ||
- | |||
- | Этот метод прекрасно работает, | ||
- | |||
- | 2. | ||
- | |||
- | Предположим, | ||
- | |||
- | 3. | ||
- | |||
- | Теперь надо отсортировать массив B по возрастанию, | ||
- | |||
- | 4. | ||
- | |||
- | После работы алгоритма сортировки массив A окажется полностью перемешанным в случайном порядке. В качестве первого случайного элемента можно взять первый элемент массива A, в качестве второго — второй и т. д. Вот и все. Давайте теперь немного уточним алгоритм Краскала с учетом сказанного: | ||
- | |||
- | ocations := количество локаций в лабиринте { Width * Height } записываем все стены лабиринта в массив Walls перемешиваем массив Walls в случайном порядке | ||
- | |||
- | i := 0 | ||
- | ПОКА locations > 1 | ||
- | текущая стена := i-й элемент массива Walls | ||
- | i := i + 1 | ||
- | ЕСЛИ не существует пути между локациями, | ||
- | разбиваем стену | ||
- | locations := locations – 1 | ||
- | EIIAO OEEEA | ||
- | |||
- | Любую стену можно задать четырьмя числами: | ||
- | Теперь можно заняться реализацией алгоритма. Мой вариант приведен в листинге 4.4, скриншот работающей программы — на рис. 4.9. | ||
- | | ||
- | <code | Листинг 4.4. Генерация лабиринта по алгоритму Краскала> | ||
- | |||
- | |||
- | function KruskalGenerateMaze(Width, | ||
- | |||
- | type Wall = record { тип " | ||
- | x, y, dx, dy : Integer; | ||
- | end; | ||
- | var TheMaze : Maze; { сам лабиринт } | ||
- | Walls : array of Wall; { массив стен } | ||
- | Temp : array of Real; { временный массив для сортировки стен } | ||
- | i, j : Integer; | ||
- | tempw : Wall; | ||
- | tempr : Real; | ||
- | CurWall : Wall; | ||
- | locations : Integer; | ||
- | counter : Integer; | ||
- | |||
- | procedure BreakWall(x, | ||
- | begin | ||
- | { между локациями } | ||
- | if dx = -1 then TheMaze[x, y].left_wall := false | ||
- | else if dx = 1 then TheMaze[x + 1, y].left_wall := false | ||
- | else if dy = -1 then TheMaze[x, y].up_wall := false | ||
- | else TheMaze[x, y + 1].up_wall := false; | ||
- | end; | ||
- | |||
- | function IsConnected(xs, | ||
- | ... { используется алгоритм волновой трассировки } | ||
- | |||
- | begin | ||
- | { выделение памяти для массива стен } | ||
- | { в лабиринте Width * Height изначально | ||
- | { (Width - 1) * Height + (Height - 1) * Width стен } | ||
- | SetLength(Walls, | ||
- | SetLength(Temp, | ||
- | SetLength(TheMaze, | ||
- | |||
- | for i := 0 to Width do { все стены изначально } | ||
- | for j := 0 to Height do { существуют } | ||
- | begin | ||
- | TheMaze[i, j].left_wall := true; | ||
- | TheMaze[i, j].up_wall := true; | ||
- | end; | ||
- | |||
- | Randomize; | ||
- | for i := 0 to (Width - 1) * Height + (Height - 1) * Width - 1 do | ||
- | Temp[i] := Random; { заполнение массива Temp случайными числами } | ||
- | |||
- | counter := 0; { заполнение массива стен } | ||
- | for i := 1 to Width - 1 do | ||
- | for j := 0 to Height - 1 do | ||
- | begin { сначала все горизонтальные } | ||
- | Walls[counter].x := i; Walls[counter].y := j; | ||
- | Walls[counter].dx := -1; Walls[counter].dy := 0; | ||
- | counter := counter + 1; | ||
- | end; | ||
- | for i := 0 to Width - 1 do | ||
- | for j := 1 to Height - 1 do | ||
- | begin { затем все вертикальные } | ||
- | Walls[counter].x := i; Walls[counter].y := j; | ||
- | Walls[counter].dx := 0; Walls[counter].dy := -1; | ||
- | counter := counter + 1; | ||
- | end; | ||
- | |||
- | for i := 0 to (Width - 1) * Height + (Height - 1) * Width - 1 do | ||
- | for j := i to (Width - 1) * Height + (Height - 1) * Width - 1 do | ||
- | if Temp[i] < | ||
- | begin | ||
- | tempr := Temp[i]; Temp[i] := Temp[j]; Temp[j] := tempr; | ||
- | tempw := Walls[i]; Walls[i] := Walls[j]; Walls[j] := tempw; | ||
- | end; | ||
- | |||
- | locations := Width * Height; | ||
- | i := 0; | ||
- | while locations > 1 do { прямолинейная реализация } | ||
- | begin { алгоритма Краскала } | ||
- | CurWall := Walls[i]; | ||
- | i := i + 1; | ||
- | if not IsConnected(CurWall.x, | ||
- | CurWall.x + CurWall.dx, CurWall.y + CurWall.dy) then | ||
- | begin | ||
- | BreakWall(CurWall.x, | ||
- | locations := locations - 1; | ||
- | ShowMaze(TheMaze); | ||
- | Application.ProcessMessages; | ||
- | end; | ||
- | end; | ||
- | |||
- | KruskalGenerateMaze := TheMaze; | ||
- | end; | ||
- | </ | ||
- | |||
- | |||
- | 1. Помните, | ||
- | |||
- | 2. Есть два простых способа улучшить алгоритм волновой трассировки: | ||
- | |||
- | Можно «разлить кисель» не только в стартовой локации, | ||
- | | ||
- | Реализуйте оба варианта на практике. | ||
- | |||
- | 3. Добавьте в процедуры обхода лабиринта код, который позволит наблюдать ход решения. К примеру, | ||
- | |||
- | 4. Подумайте, | ||
- | |||
- | Вы уже умеете генерировать лабиринты и знакомы с трехмерной графикой. Попробуйте написать программу, | ||
- |