мета-данные страницы
Загрузка не удалась. Возможно, проблемы с правами доступа?
Различия
Показаны различия между двумя версиями страницы.
Следующая версия | Предыдущая версия | ||
pascal4beginners-algorithm [24/01/2012 11:15] – создано oca | pascal4beginners-algorithm [27/01/2012 12:48] (текущий) – oca | ||
---|---|---|---|
Строка 3: | Строка 3: | ||
=== Поиск в неупорядоченном массиве === | === Поиск в неупорядоченном массиве === | ||
+ | Источник [[http:// | ||
+ | |||
+ | Рассмотрим сначала нюансы реализации “технических” задач поиска, | ||
< | < | ||
+ | a: | ||
</ | </ | ||
+ | |||
+ | при этом собственно элементы массива, | ||
+ | < | ||
+ | i:=0; | ||
+ | repeat | ||
+ | i:=i+1 | ||
+ | until (i=N) or (a[i]=K); | ||
+ | |||
+ | if a[i]=K then write(i) | ||
+ | else write(0) | ||
+ | |||
+ | {следующее неверно (!!!): | ||
+ | if i=N then write(0) | ||
+ | else write(i) } | ||
+ | </ | ||
+ | |||
+ | |||
+ | При отсутствии в массиве элемента с искомым значением K печатается значение нулевого индекса. Оказывается, | ||
+ | < | ||
+ | a[0]:=K; | ||
+ | i:=N; | ||
+ | |||
+ | while (a[i]<> | ||
+ | i:=i-1; | ||
+ | | ||
+ | write(i) | ||
+ | </ | ||
+ | |||
+ | |||
+ | Эта программа не просто проще и эффективней. В ней практически невозможно сделать ошибку. | ||
+ | Другой полезный прием можно показать на задаче поиска максимального и минимального значения в массиве. Состоит он в том, что при любом поиске в массиве искать следует не значение искомого элемента, | ||
+ | < | ||
+ | imax:=1; | ||
+ | |||
+ | imin:=1; | ||
+ | |||
+ | for i:=2 to N do | ||
+ | |||
+ | if a[i]< | ||
+ | |||
+ | if a[i]> | ||
+ | </ | ||
+ | |||
+ | |||
+ | Заметим, | ||
+ | < | ||
+ | max: | ||
+ | min: | ||
+ | |||
+ | for i:=1 to N do | ||
+ | if a[i] | ||
+ | if a[i]>max then max:=i | ||
+ | </ | ||
+ | |||
+ | |||
+ | Казалось бы на этом рассмотрение алгоритмов поиска в неупорядоченном массиве можно завершить. Однако именно с одновременного поиска минимума и максимума можно начать класс алгоритмов поиска, | ||
+ | |||
+ | Еще большей эффективности можно добиться при одновременном поиске максимального и второго по величине числа. Для этого организуем поиск максимума по схеме “теннисного турнира”, | ||
+ | |||
+ | В данном контексте можно поставить также задачу поиска i-го по счету элемента, | ||
+ | |||
+ | Алгоритм Выбор(A, | ||
+ | {выбирает между L-ым и R-ым элементами массива A | ||
+ | i-ый по счету в порядке возрастания элемент} | ||
+ | 1. if L=R then результат – A[L], конец; | ||
+ | 2. Q: | ||
+ | {Q – случайный элемент между L и R} | ||
+ | 3. Переставляем элементы от L до R в A так, чтобы сначала шли элементы, | ||
+ | 4. if i<=(K-L) then Выбор(A, | ||
+ | else Выбор(A, | ||
+ | 5. конец. | ||
+ | |||
+ | Оптимальную реализацию пункта 3 можно заимствовать из алгоритма так называемой быстрой сортировки. | ||
+ | Наконец, | ||
+ | < | ||
+ | S:=0; | ||
+ | for i:=1 to N do | ||
+ | begin | ||
+ | read(a); S:=S+a | ||
+ | end; | ||
+ | writeln(N*(N + 1) div 2 – S) | ||
+ | </ | ||
+ | |||
+ | |||
+ | Данную программу легко переписать так, чтобы она работала и для значений N, превосходящих максимальное представимое целое число. Для этого следует использовать переменные типа extended, а цикл for заменить на while. Используя аналогичный прием попробуйте решить следующую задачу. Пусть N — количество чисел, нечетно и известно, | ||
+ | |||
+ | Сноски: | ||
+ | Обозначение [] соответствует для неотрицательных чисел округлению до ближайшего целого числа, большего или равного выражению в указанных скобках, | ||
+ | |||
+ | ==== Создание лабиринта ==== | ||
+ | {{: | ||
+ | |||
+ | [[http:// | ||
+ | Мозговой Максим Владимирович - Занимательное программирование: | ||
+ | |||
+ | |||
+ | Глава 4 | ||
+ | Лабиринты | ||
+ | |||
+ | В лабиринте у вас, по крайней мере, есть цель. | ||
+ | |||
+ | Евгений Кащеев | ||
+ | |||
+ | Мне нравится эта тема. С одной стороны, | ||
+ | |||
+ | Итак, сейчас мы займемся лабиринтами. Если говорить более конкретно, | ||
+ | |||
+ | 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. | ||
+ | Листинг 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, | ||
+ | ... { используется алгоритм волновой трассировки } | ||
+ | |||
+ | Листинг 4.4 (продолжение) | ||
+ | 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; | ||
+ | |||
+ | |||
+ | |||
+ | Рис. 4.9. Алгоритм Краскала в процессе работы | ||
+ | I?iaeou aey naiiniaa? | ||
+ | |||
+ | 1. Помните, | ||
+ | |||
+ | 2. Есть два простых способа улучшить алгоритм волновой трассировки: | ||
+ | • Можно «разлить кисель» не только в стартовой локации, | ||
+ | • Реализуйте оба варианта на практике. | ||
+ | |||
+ | 3. Добавьте в процедуры обхода лабиринта код, который позволит наблюдать ход решения. К примеру, | ||
+ | |||
+ | 4. Подумайте, | ||
+ | |||
+ | Вы уже умеете генерировать лабиринты и знакомы с трехмерной графикой. Попробуйте написать программу, | ||
+ |