┌──────────────────────────────┐
│ │
│ ПРОФЕССИОНАЛЬНЫЙ ПОДХОД │
│ │
└──────────────────────────────┘
Music by ZET
(c) Лыхин Д., г.Кемерово
ЛАБИРИНТЫ
"Лабиринты - архитектурные
сооружения со сложными коридора-
ми, которые строились для того,
чтобы приводить в трепет непос-
вященных..."
Мартин Гарднер.
Слово "лабиринт" греческого
происхождения, и переводится как
подземные ходы или подземелье. В
природе существует много подзем-
ных пещер с огромным количес-
твом ходов, перекрестков и тупи-
ков. Есть примеры и других при-
родных лабиринтов, вот скажем,
шхеры - множество мелких остров-
ков, составляющих единую группу.
В шхерах десятки фарватеров,
проливов, заливов, бухточек, в
которых нетрудно заблудиться.
Но существуют лабиринты и ис-
кусственного происхождения, соз-
данные человеком вольно или не-
вольно. Примером невольного соз-
дания лабиринтов являются раз-
личные шахты, рудники, камено-
ломни, называемые общим словом
"Катакомбы". Чаще всего под сло-
вом "Лабиринт" мы подразумеваем
искусственное, специально соз-
данное, чрезвычайно сложное со-
оружение. Происхождение таких
"Лабиринтов" довольно древнее.
Например, Геродот описывает еги-
петский Лабиринт, в котором бы-
ло 5000 комнат. Сначала Лабирин-
ты носили религиозно-мистичес-
кий характер, но в более поз-
дние времена стали предметом
развлечений, перейдя в сады и
парки в виде живой изгороди
сложной конфигурации. В наше
время, по утверждению Мартина
Гарднера, "существует две облас-
ти науки, в которых интерес к
Лабиринтам остается неизменно
высоким: психология и конструи-
рование вычислительных машин."
Однако, существует еще одна
область человеческой деятельнос-
ти, в которой Лабиринты являют-
ся необходимым атрибутом - это
компьютерные игры. Действитель-
но, почти все игры жанров Adven-
ture, Arcade и Arcade/Adventure
используют Лабиринты. Встречают-
ся они и в других жанрах: Puz-
zle, Action, изредка в Simulati-
ons. В связи с этим у пользова-
теля компьютера появляются две
задачи: прохождение Лабиринтов в
игровых программах и создание
Лабиринтов для "своих" программ.
Задача "о прохождении Лаби-
ринта" распадается на пару дру-
гих: Техническую и Логическую.
Техническая часть состоит в том,
чтобы справиться с управлени-
ем своей "марионетки", избежать
столкновений с "бяка-спрайтами"
и не попасть в ловушки. Логичес-
кая часть - отыскание правильно-
го пути.
Коль скоро задача логическая,
то, очевидно, должен существо-
вать алгоритм для ее решения. С
точки зрения математики, путь от
входа до цели есть топологичес-
кий инвариант. Проще говоря, это
означает: план Лабиринта, нари-
сованный на куске резины, мож-
но растянуть таким образом, что
вход и цель соединятся одним
прямым коридором.
Проведя прямую линию по это-
му коридору, мы получим кратчай-
ший путь до цели. Практически
же, если у нас есть план Лаби-
ринта, следует заштриховать (за-
валить) все тупики. Оставшаяся
часть - путь (или несколько пу-
тей) к цели. В некоторых играх
можно видеть весь Лабиринт цели-
ком (иногда его план). Но, обыч-
но, в таких играх цель игры не
прохождение Лабиринта, а собира-
ние предметов (Miss Pocman, Fast
Food, CHUCKE и др.). Или же Ла-
биринт снабжен "переключателями"
в виде закрывающихся-открываю-
щихся дверей, падающих решеток,
разводных мостов и т.д., кото-
рые способны изменять конфигура-
цию Лабиринта. Задача - выбрать
момент для прохождения, когда
"переключатели" в нужном положе-
нии (или переключить их самому),
чтобы достичь цели.
Итак, если на экране весь Ла-
биринт, то отыскание верного пу-
ти не представляет трудностей.
Другое дело, если Лабиринт раз-
бит на множество экранов. Тогда,
чтобы отыскать таким способом
путь, придется составлять план
Лабиринта. А без плана?
Здесь мы вплотную подходим к
вопросу о конфигурациях и видах
Лабиринтов. Прежде всего отме-
тим, что Лабиринты бывают двух
видов: двух или трехмерными,
т.е. одно или многоэтажными. При
этом двухмерная графика игры не
обязательно означает двухмер-
ный Лабиринт, и, наоборот, часто
трехмерная графика совмещена с
двухмерным Лабиринтом. При двух-
мерной графике изображение Лаби-
ринта может быть горизонтальным
(смотрим сверху) или вертикаль-
ным (смотрим сбоку). При трех-
мерной графике тоже существуют
два способа изображения (обычно
только части лабиринта): изомет-
рия и фронтальная проекция.
Теперь о конфигурации Лаби-
ринта. Специалисты различают три
конфигурации: Лабиринты одно-
связные, Лабиринты многосвязные
без "петли" вокруг цели и Лаби-
ринты многосвязные с замкнутой
"петлей" вокруг цели. Односвяз-
ными называются Лабиринты, не
содержащие замкнутых маршрутов и
не имеющие отдельно стоящих сте-
нок. Лабиринты с отдельно стоя-
щими стенками и с замкнутыми
маршрутами называются многосвяз-
ными. При этом, если замкнутый
маршрут не проходит вокруг цели,
то Лабиринт второй конфигурации;
если же цель можно обойти по
замкнутому маршруту, значит, Ла-
биринт третьей конфигурации.
В Лабиринтах первой и второй
конфигурации всегда можно дос-
тичь цели, если двигаться все
время касаясь рукой стенки.
Правда, этот путь не будет са-
мым коротким. В Лабиринте треть-
ей конфигурации таким способом
никогда не достичь цели. Вы
просто обойдете ее по наибольше-
му замкнутому маршруту. Часто мы
вообще не знаем, с Лабиринтом
какой конфигурации имеем дело.
Существует ли универсальный ал-
горитм для прохождения любых Ла-
биринтов?
Существует.
Алгоритм Люка-Тремо:
1. На выходе туннеля к перекрес-
тку и на входе с перекрестка
в туннель всегда делаем от-
метку с одной и той же сторо-
ны (например справа) по ходу
движения.
2. От первого перекрестка идем
по какому угодно пути, пока
не достигнем или нового пе-
рекрестка, или не зайдем в
тупик. Тогда:
3. Если мы зашли в тупик, то
следует вернуться назад, а
пройденный путь отбросить
(пункт 1), отметив его дваж-
ды (вход-выход). От перекрес-
тка идти в другом направле-
нии.
4. Если мы приходим к новому
перекрестку, то двигаемся в
любом направлении, отметив
путь, по которому пришли, и
путь, по которому уходим.
5. Если мы приходим к известно-
му нам перекрестку не тем пу-
тем, которым уходили, то не-
медленно поворачивать назад
(не забыв пункт 1).
6. Никогда не ходите по пути,
отмеченному дважды.
7. Если больше нет путей без от-
меток, следует выбрать путь,
отмеченный одной меткой.
Я думаю, что этот алгоритм
поможет Вам в прохождении Лаби-
ринтов, хотя "ставить" метки на
экранах весьма проблематично.
Теперь перейдем к вопросу о
создании Лабиринтов. Не будем
касаться проблем, связанных с
ручной разработкой и хранением
Лабиринтов в памяти компьютера.
Это очень трудоемкая работа. Мо-
жете в этом убедиться на приме-
ре программы "MUTANT" из книги
ИНФОРКОМа "Игры на Бейсике свои-
ми руками". Восемь простых Лаби-
ринтов записаны в "очень плот-
неньких" строках 2000...2700.
Набирать их довольно "муторно",
даже при использовании готовых
стрингов и их сечений. Значи-
тельно выгодней иметь процедуру,
создающую Лабиринты в ходе рабо-
ты программы по мере их надоб-
ности. Эта мысль не новая. Та-
кую программу можно встретить,
например, в книге "Интерактив-
ная графика". Программа написа-
на не для "SPECTRUM", но легко
адаптируется.
Попробуем смоделировать про-
цесс возникновения Лабиринта.
Как возникает Лабиринт в природ-
ных условиях? Под воздействием
воды, ветра, температурных усло-
вий, эрозии грунт разрушается
в наиболее слабых местах, обра-
зуя ходы, тупики, перекрестки. С
точки зрения географии, направ-
ления создаваемых туннелей со-
вершенно случайны. Обозначим на-
правления "размывания грунта"
цифрами 1-4 и выберем его слу-
чайно, используя функцию RND.
ЛИСТИНГ 1 REM
10 BORDER 0: PAPER 0: INK 7: CLS │ "Исходный грунт"
20 LET Y = INT(RND * 22): │ Координаты "пробившегося
│ источника"
LET X = INT(RND * 32) │
30 FOR N = 0 TO 350 │ Длительность процесса
│ "размывания"
40 LET B = INT(RND * 4) + 1 │ Направление "размывания"
50 IF B = 1 AND Y< > 0 THEN │
LET Y = Y - 1: GO TO 100 │ Подсчет координат
│ "нового туннеля"
60 IF B = 2 AND X< > 31 THEN │
LET X = X + 1: GO TO 100 │
70 IF B = 3 AND X< > 21 THEN │
LET Y = Y + 1: GO TO 100 │
80 IF B = 4 AND X< > 0 THEN │
LET X = X - 1: GO TO 100 │
90 GO TO 40 │
100 PRINT AT Y,X; CHR$ 143 │ " Размываем"
110 NEXT N │
То, что получилось на экране,
мало походит на лабиринт. Как
говорится: "Процесс не пошел".
"Грунт" оказался достаточно
"однородным", и туннелей не воз-
никло. Нарушим "однородность
грунта", заменив в программе
строки 50... 80, 100 на следую-
щие:
50 IF B = 1 AND Y > 1 THEN LET Y1 = Y - 1: LET Y = Y - 2:
LET X1 = X: GO TO 100
60 IF B = 2 AND X < 30 THEN LET X1 = X + 1: LET X = X + 2:
LET Y1 = Y: GO TO 100
70 IF B = 3 AND Y < 20 THEN LET Y1 = Y + 1: LET Y = Y + 2:
LET X1 = X: GO TO 100
80 IF B = 4 AND X > 1 THEN LET X1 = X - 1: LET X = X - 2:
LET Y1 = Y: GO TO 100
90 .......
100 PRINT AT Y1,X1; CHR$ 143; AT Y,X; CHR$ 143
Теперь результат можно счи-
тать удовлетворительным. Если
Вас устроит скорость работы про-
цедуры, то можно воспользоваться
ей, скажем, в той же программе
"MUTANT". Сложность Лабиринта
можно менять, изменяя перемен-
ную цикла "N" и длину проходимо-
го "штрека" за один шаг. Полу-
ченный алгоритм я называю "ал-
горитмом проходки", которую он
действительно напоминает. Выхо-
дящий Лабиринт - многосвязный.
Можно ли с помощью этого алго-
ритма получить односвязный? Оче-
видно, да. Следует наложить ог-
раничения (например, с помощью
функции ATTR), при которых не-
возможно соединение "штреков"
между собой. Но при этом возмо-
жен случай "сходящейся спирали"
(рис. 1),
┌───────┐
│ ┌──┐ │
│ │ │ │
│ │ │
└────┘
рис. 1
в котором дальнейшая "проходка"
невозможна. Тогда следует вер-
нуться назад до того момента,
когда станет это возможным хотя
бы в одном направлении. Поэтому
придется запоминать координаты
предыдущих позиций печати. Если
захотите, то проделайте это са-
ми, а мы рассмотрим другой алго-
ритм генерирования Лабиринтов.
Этот алгоритм используется в
программе из уже упомянутой кни-
ги "Интерактивная графика". На-
зовем его алгоритмом "удаления
перегородок". Принцип работы
ясен из названия. Сначала "стро-
им" некоторое количество изоли-
рованных друг от друга "комнат",
а затем удаляем перегородки меж-
ду ними произвольным образом, но
придерживаясь некоторых ограни-
чений. (см. Листинг 2).
ЛИСТИНГ 2 REM
│
5 BORDER 0: PAPER 0: CLS │
10 FOR N = 1 TO 29 STEP 2 │ "Строим комнаты"
20 FOR M = 1 TO 19 STEP 2 │
30 PRINT PAPER 7: AT M,N; " " │
40 NEXT M: NEXT N │
│ Индексируем вертикальные и
50 DIM A(10,14): DIM B(9,15) │ горизонтальные "перегородки"
60 FOR N = 1 TO 105 │ Количество "удаляемых" вер-
│ тикальных "перегородок"
70 LET I = INT(RND * 10) + 1 │ Определили индексы "удаля-
│ емой" перегородки
80 LET J = INT(RND * 14) + 1 │
│ Проверим, не удалялась ли
90 IF A(I,J) = 1 THEN GO TO 70 │ "перегородка" раньше, и если
│ "удалялась", то назначим
│ другие индексы.
100 LET A(I,J) = 1 │ Отметка об удалении "пере-
│ городки"
110 PRINT PAPER 7; AT I * 2 - 1, │ "Удаление перегородки"
J*2; │
120 NEXT N │ Переход к следующей "пере-
│ городке"
130 FOR N = 1 TO 100 │ Аналогично "удаляем перего-
│ родки", стоящие горизонталь-
│ но
140 LET I = INT(RND * 9 ) + 1 │ Определили индексы "удаля-
│ емой" перегородки
150 LET J = INT(RND * 15) + 1 │
160 IF B(I,J) = 1 THEN GO TO 140 │
170 LET B(I,J) = 1 │
180 PRINT PAPER 7; AT I * 2, │
J*2 - 1;" " │
110 NEXT N │
Ограничения, которые мы на-
кладывали в этой программе, это
количество удаленных вертикаль-
ных и горизонтальных "перегоро-
док". При этом мы также следили,
чтобы ни одна "перегородка" не
удалялась больше одного раза.
Можно наложить и другие ограни-
чения. Например, ограничим чис-
ло входов-выходов в каждой ком-
нате.
ЛИСТИНГ 3 REM
│
10 BORDER 7: PAPER 7: INK 0: CLS │
20 FOR N = 0 TO 30 │ "Строим комнаты"
30 FOR M = 0 TO 20 STEP 2 │
40 PRINT AT M,N; CHR $ 143 │
50 NEXT M: NEXT N │
60 FOR N = 0 TO 30 STEP 2 │
70 FOR M = 0 TO 20 │
80 PRINT AT M,N; CHR $ 143 │
90 NEXT M: NEXT N │
│ Индексирование "перегородок"
100 DIM A(10,15): DIM G(10,14): │ и "комнат"
DIM V(9,15) │
110 FOR N = 1 TO 205 │ Количество "удаляемых"
│ "перегородок"
120 LET B = INT(RND * 2) │ Какую "перегородку" удалять,
│ вертикальную или горизон-
130 GO TO 205 * (B=1) + 140 * │ тальную
(B=0) │
140 LET I = INT(RND * 10) + 1 │ Определили перегородку для
│ удаления.
150 LET J = INT(RND * 14) + 1 │
│ Если она удалена, то будем
160 IF G(I,J) = 1 THEN GO TO 120 │ искать другую.
│
170 IF A(I,J) >=3 OR A(I,J+1)>=3 │ Если соединяемые комнаты
THEN GO TO 120 │ имеют по три входа, то ищем
│ другую перегородку.
180 PRINT AT I * 2 - 1, J*2; │ "Удалили перегородку"
" " │
190 LET G(I,J) = 1: LET A(I,J) = │ Отмечаем удаленную "перего-
A(I,J) + 1: LET A(I,(J+1)) = │ родку" и соединенные "комна-
A(I,(J+1)) │ ты"
200 GO TO 260 │ Переходим к следующему уда-
│ лению.
205 LET I = INT(RND * 9 ) + 1 │ Аналогично действуем при
│ удалении горизонтальных "пе-
210 LET J = INT(RND * 15) + 1 │ регородок"
│ Если она удалена, то будем
220 IF V(I,J) = 1 THEN GO TO 120 │ искать другую.
230 IF A(I,J) >=3 OR A(I+1,J)>=3 │ Если соединяемые комнаты
THEN GO TO 120 │ имеют по три входа, то ищем
│ другую перегородку.
240 PRINT AT I * 2, J * 2 - 1; │ "Удалили перегородку"
" " │
│
250 LET V(I,J) = 1: LET A(I,J) = │
A(I,J) + 1: LET A(I+1,J) = │
A(I + 1,J) + 1 │
260 NEXT N │
Лабиринт, полученный этой
программой, более "изящный", чем
в предыдущем случае, но прог-
рамма работает немного медлен-
нее. А вообще-то, чем больше на-
ложенных ограничений, тем мед-
леннее работает программа. Полу-
ченный алгоритм - многосвязный,
а вот автор книги "Интерактив-
ная графика" строит с помощью
этого алгоритма Лабиринт однос-
вязный. Можете попробовать пов-
торить его опыт. По моему же
мнению, для построения односвяз-
ных Лабиринтов больше подходит
алгоритм "устанавливаемых пере-
городок". Он значительно проще,
а главное, работает намного быс-
трее. Суть алгоритма в следую-
щем: сначала " строим" несколько
изолированных друг от друга "ко-
ридоров", затем ставим в них пе-
регородки, одновременно соединяя
коридоры между собой (Листинг
4).
ЛИСТИНГ 4 REM
│
10 BORDER 7: PAPER 7: INK 1: CLS │
20 FOR N = 1 TO 21 STEP 2 │ "Строим коридоры"
30 FOR M = 1 TO 30 │
40 PRINT AT N,M; CHR $ 143 │
50 NEXT M: NEXT N │
60 FOR N = 1 TO 21 │
70 PRINT AT N,0; CHR $ 143; │
AT N,31; CHR 143 │
80 NEXT N │
90 FOR N = 1 TO 9 │ Количество "перегородок"
│ между "коридорами"
100 LET K = INT(RND * 4) + 1 │ Определим количество уста-
│ навливаемых "перегородок" в
│ одном "коридоре"
110 LET L = INT((30 - K)/K) │ Длина участков между этими
│ "перегородками".
120 FOR M = 1 TO K │ Установка "перегородок" и
│ соединение "коридоров"
130 LET B=(L + 1)*(M - 1) + INT(RND│ между собой.
* (L - 3)) + 1 │
140 IF B > 28 THEN GO TO 130 │
150 PRINT AT N * 2 + 1, B; │ ( 2 пробела )
" " │
160 PRINT AT N + 2,B + 2; CHR $ │
143; AT N*2 - 1,B +2; CHR 143 │
170 IF M = K THEN PRINT AT N * 2 +│
1, B + 3; " " │ ( 2 пробела )
180 NEXT M: NEXT N │
190 LET Y = INT(RND * 10) + 1 │
200 PRINT AT Y * 2, 0; " " │ Делаем вход
210 LET Y = INT(RND * 10) + 1 │
220 PRINT AT Y * 2, 31 │ Делаем выход
Программа (Листинг 4) может
быть использована в играх на
Бейсике типа "Гонки по Лабирин-
ту". Можно ли с помощью алгори-
тма "устанавливаемых перегоро-
док" получить многосвязный "Ла-
биринт"?
Нетрудно увидеть, что если
немного увеличить число устанав-
ливаемых перегородок и сделать
несколько "лишних" соединений
между коридорами, то получится
искомый результат. Оставлю это
Вам.
А вместо этого предлагаю про-
грамму с тем же алгоритмом для
многосвязного Лабиринта, но при-
менительно к векторной графике
(Листинг 5).
Листинг 5
10 BORDER 7: PAPER 7: INK 2: CLS
20 LET M = 1
30 FOR R = 16 TO 80 STEP 16
40 FOR N = 0 TO 19
50 LET B = INT(RND * 4)
60 LET X1 = R * COS(PI/10 * N): LET Y1 = R * SIN(PI/10 * N)
70 IF B = 0 AND M = 0 THEN GO TO 90
80 IF B = 0 THEN GO TO 120
82 IF B = 1 AND (M = 1 OR M = 0) THEN GO TO 90
85 IF B = 1 AND R <> 16 AND R <> 80 THEN GO TO 150
90 LET X2 = R*COS(PI/10 * (N + 1)): LET Y2 = R*SIN(PI/10 *
(N+1))
100 PLOT 128 + X1, 88 + Y1: DRAW X2 - X1, Y2 - Y1, PI/10
110 GO TO 150
120 LET X3 =(R+16) * COS(PI/10 * N): LET Y3 =(R+16)*SIN(PI/10 *
N)
130 IF R = 80 THEN GO TO 150
140 PLOT 128 + X1, 88 + Y1: DRAW X3 - X1, Y3 - Y1
150 LET M = B
160 NEXT N: NEXT R
Я привожу этот листинг без
комментариев. Следует, пожалуй,
только пояснить, что переменная
"M" введена для запоминания пре-
дыдущего результата переменной
по "B", чтобы исключить поста-
новку двух перегородок подряд и
двойное соединение "коридоров"
без перегородки. Цель Лабирин-
та - его центр. Лабиринт многос-
вязный, может получиться второй
или третьей конфигурации. К со-
жалению, тригонометрические фун-
кции и оператор построения дуг -
DRAW - сильно замедляют работу
программы. Для ускорения сове-
тую написать ее в BETA BASIC,
используя быстрые функции COSE и
SINE. А если Вы не не хотите
уходить от "SPECTRUM BASIC", то
можете заменить этот листинг на
следующий (листинг 6). В принци-
пе, он генерирует однотипный Ла-
биринт, заменив окружности на
прямоугольники. Несмотря на свою
длину, работает он с такой же
скоростью, как и листинг 4.
Листинг 6
5 BORDER 0: PAPER 0: INK 6: CLS
10 FOR N = 1 TO 6
20 LET X = 112 - 16 * N: LET Y = 78 + 16 * N
30 LET A = 63 + 32 * (N - 1): LET B = 14 + 32 * (N - 1)
40 PLOT X,Y: DRAW A,0: DRAW 0,-B: DRAW -A,0: DRAW 0,B
50 IF N = G THEN GO TO 200
60 LET C = INT(RND * 5)
70 GO TO 200 - 20 * C
120 LET D = INT(RND *(A - 10))
130 PLOT X + D,Y: DRAW 0,15: PLOT X + D,Y: DRAW OVER 1; 10,0
140 LET D = INT(RND *(A - 10))
150 PLOT X + D,Y: DRAW 0,15: PLOT X + D,Y: DRAW OVER 1; 10,0
160 LET D = INT(RND *(A - 10))
170 PLOT X + D,Y: DRAW 0,15: PLOT X + D,Y: DRAW OVER 1; 10,0
180 LET D = INT(RND *(A - 10))
190 PLOT X + D,Y: DRAW 0,15: PLOT X + D,Y: DRAW OVER 1; 10,0
200 PLOT X + INT(RND * (A - 10)),Y: DRAW OVER 1; 10,0
205 IF N = G THEN GO TO 400
210 LET C = INT(RND * 5)
220 GO TO 400 - 20 * C
320 LET D = INT(RND *(A - 10))
330 PLOT X + D,Y-B: DRAW 0,-15: PLOT X + D,Y - B: DRAW OVER 1;
10,0
340 LET D = INT(RND *(A - 10))
350 PLOT X + D,Y-B: DRAW 0,-15: PLOT X + D,Y - B: DRAW OVER 1;
10,0
360 LET D = INT(RND *(A - 10))
370 PLOT X + D,Y-B: DRAW 0,-15: PLOT X + D,Y - B: DRAW OVER 1;
10,0
380 LET D = INT(RND *(A - 10))
390 PLOT X + D,Y-B: DRAW 0,-15: PLOT X + D,Y - B: DRAW OVER 1;
10,0
400 IF N = 6 OR N = 1 THEN GO TO 500
410 LET C = INT(RND * 4)
420 GO TO 500 - 20 * C
440 LET D = INT(RND *(B - 10))
450 PLOT X,Y-D: DRAW -15,0: PLOT X,Y - D: DRAW OVER 1;0,-10
460 LET D = INT(RND *(B - 10))
470 PLOT X,Y-D: DRAW -15,0: PLOT X,Y - D: DRAW OVER 1;0,-10
480 LET D = INT(RND *(B - 10))
490 PLOT X,Y-D: DRAW -15,0: PLOT X,Y - D: DRAW OVER 1;0,-10
500 PLOT X,Y - INT(RND*(B - 10)): DRAW OVER 1;0,-10
505 IF N = 6 OR N = 1 THEN GO TO 600
510 LET C = INT(RND * 4)
520 GO TO 600 - 20 * C
540 LET D = INT(RND *(B - 10))
550 PLOT X + A,Y-D: DRAW 15,0: PLOT X + A,Y - D: DRAW OVER 1;0,
-10
560 LET D = INT(RND *(B - 10))
570 PLOT X + A,Y-D: DRAW 15,0: PLOT X + A,Y - D: DRAW OVER 1;0,
-10
580 LET D = INT(RND *(B - 10))
590 PLOT X + A,Y-D: DRAW 15,0: PLOT X + A,Y - D: DRAW OVER 1;0,
-10
600 NEXT N
Конечно, длину листинга мож-
но несколько сократить, приме-
нив внутренние циклы, но я хотел
продемонстрировать прием "сту-
пенчатого перехода". Кроме того,
циклы замедляют работу програм-
мы. Как и в предыдущем Лабирин-
те, цель - центр; построенный
Лабиринт второй или третьей кон-
фигурации. Но последствием при-
менения оператора OVER 1 являет-
ся возможность такого случая,
когда цель оказывается отрезан-
ной.
Теперь Вы знаете основные ал-
горитмы генерирования Лабирин-
тов и, конечно, поняли, что
здесь основная проблема - ско-
рость работы программ. Выход из
положения традиционный - приме-
нение машинных кодов. Для приме-
ра привожу программу генерато-
ра Лабиринтов первой конфигура-
ции, сделанную на основе Бейсик-
программы листинга 4. Программа
не релоцируема вследствие ис-
пользования подпрограмм (хотя
все подпрограммы релоцируемы),
ее общая длина - 412 байт, адрес
старта 50210. В своем составе
она содержит четыре подпрограм-
мы и объединяющий "стержневой"
блок.
Подпрограмма печати исходно-
го экрана (листинг 7) "RES", ад-
рес старта с начала процедуры -
5000, длина 99 байт.
Подпрограмма "RND" (листинг
8) служит для получения в акку-
муляторе случайных чисел. Запи-
сана с адреса 5100, длина 12
байт.
Подпрограмма "PRINT" (лис-
тинг 9) печатает "перегородки" и
соединяет между собой "коридо-
ры". Адрес старта 50175, длина
62 байта.
Поцедура "ERASE" (листинг 10)
делает недостающие соединения
"коридоров". Адрес старта 50175,
длина 35 байт.
Блок, объединяющий процедуры
"PROG" (листинг 11), записан с
адреса 50210, длина 202 байта.
Комментариев не привожу, они
есть в листинге 4.
Листинг 7 RES
│ 10 ORG (50000)C350
C350 3E07 │ 20 LD A,07
C352 CD9722 │ 30 CALL 2297
C355 FD02 │ 40 LD (IY+83),39
C359 3E02 │ 50 LD A, 02
C35B CD0116 │ 60 CALL 1601
C35E CD6B0D │ 70 CALL 0D68
C361 0E14 │ 80 LD C,14
C363 0619 │ 90 NEXT 2 LD B,19
C365 C5 │ 100 NEXT 1 PUSH B, C
C366 3E02 │ 110 LD A, 02
C368 CD0116 │ 120 CALL 1601
C36B 3E16 │ 130 LD A, 16
C36D D7 │ 140 RST 10
C36E C1 │ 150 POP BC
C36F 79 │ 160 LD A, C
C370 D7 │ 170 RST 10
C371 78 │ 180 LD A, B
C372 D7 │ 190 RST 10
C373 3E8F │ 200 LD A, 8F
C375 D7 │ 210 RST 10
C376 10ED │ 220 DJNZ NEXT 1
C378 0D │ 230 DEC C
C379 0D │ 240 DEC C
C37A 20E7 │ 250 JR NZ, NEXT 2
C37C 061A │ 260 LD B, 1A
C37E C5 │ 270 NEXT 3 PUSH BC
C37F 3E02 │ 280 LD A, 02
C381 CD0116 │ 290 CALL 1601
C384 3E16 │ 300 LD A, 16
C386 D7 │ 310 RST 10
C387 3E00 │ 320 LD A, 0
C389 D7 │ 330 RST 10
C38A C1 │ 340 POP BC
C38B 78 │ 350 LD B, A
C38C D7 │ 360 RST 10
C38D 3E8F │ 370 LD A, 8F
C38F D7 │ 380 RST 10
C390 10EC │ 390 DJNZ NEXT 3
C392 0614 │ 400 LD B, 14
C394 C5 │ 410 NEXT 4 PUSH BC
C395 3E02 │ 420 LD A, 02
C397 CD0116 │ 430 CALL 1601
C39A 3E16 │ 440 LD A, 16
C39C D7 │ 450 RST 10
C39D C1 │ 460 POP BC
C39E 78 │ 470 LD A, B
C39F D7 │ 480 RST 10
C3A0 3E01 │ 490 LD A, 01
C3A2 D7 │ 500 RST 10
C3A3 3E8F │ 510 LD A, 8F
C3A5 D7 │ 520 RST 10
C3A6 3E16 │ 530 LD A, 16
C3A8 D7 │ 540 RST 10
C3A9 78 │ 550 LD A, AB
C3AA D7 │ 560 RST 10
C3AB 3E1A │ 570 LD A, 1A
C3AD D7 │ 580 RST 10
C3AE 3EF8 │ 590 LD A, 8F
C3B0 D7 │ 600 RST 10
C3B1 10E1 │ 610 DJNZ NEXT 4
C3B3 C9 │ 620 RET
│ 630 END
Листинг 8 RND
│ 10 ORG C3B4
C3B4 2A765C │ 20 LD HL,(5C76)
C3B7 ED5B785C │ 30 LD DE,(5C78)
C3BB 19 │ 40 ADD HL, DE),39
C3BC 22765C │ 50 LD (5C76), HL
C3BF 7D │ 60 LD FL
C3C0 C9 │ 70 RET
│ 80 END
Листинг 9 PRINT
│ 10 ORG C3C1
C3C1 3E02 │ 20 LD A, 02
C3C3 CD0116 │ 30 CALL 1601
C3C3 3E16 │ 40 LD A, 16
C3C8 D7 │ 50 RST 10
C3C9 E1 │ 60 POP HL
C3CA D1 │ 70 POP DE
C3CB C1 │ 80 POP BC
C3CC F1 │ 90 POP AF
C3CD F5 │ 100 PUSH AF
C3CE C5 │ 110 PUSH BC
C3CF D5 │ 120 PUSH DE
C3D0 E5 │ 130 PUSH HL
C3D1 87 │ 140 ADD A, A
C3D2 F5 │ 150 PUSH AF
C3D3 3C │ 160 INC A
C3D4 47 │ 170 LD B, A
C3D5 D7 │ 180 RST 10
C3D6 7A │ 190 LD D, A
C3D7 D7 │ 200 RST 10
C3D8 3E8F │ 210 LD A, 8F
C3DA D7 │ 220 RST 10
C3DB 3E16 │ 230 LD A, 16
C3DD D7 │ 240 RST 10
C3DE 78 │ 250 LD A, B
C3DF 3C │ 260 INC A
C3E0 D7 │ 270 RST 10
C3E1 7A │ 280 LD A, D
C3E2 D7 │ 290 RST 10
C3E3 3E8F │ 300 LD A, 8F
C3E5 D7 │ 310 RST 10
C3E6 3E16 │ 320 LD A, 16
C3E8 D7 │ 330 RST 10
C3E9 F1 │ 340 POP AF
C3EA 47 │ 350 LD B, A
C3EB D7 │ 360 RST 10
C3EC 7A │ 370 LD A, D
C3ED 3C │ 380 INC A
C3EE 57 │ 390 LD D, A
C3EF D7 │ 400 RST 10
C3F0 3E20 │ 410 LD A, 20
C3F2 D7 │ 420 RST 10
C3F3 3E16 │ 430 LD A, 16
C3F5 D7 │ 440 RST 10
C3F6 78 │ 450 LD A, B
C3F7 D7 │ 460 RST 10
C3F8 7A │ 470 LD A, D
C3FA D7 │ 490 RST 10
C3FB 3E20 │ 500 LD A, 20
C3FD D7 │ 510 RST 10
C3FE C9 │ 520 RET
│ 530 END
Листинг 10 ERASE
│ 10 ORG C3FF
C3FF 3E02 │ 20 LD A, 02
C401 CD0116 │ 30 CALL 1601
C404 3E16 │ 40 LD A, 16
C406 D7 │ 50 RST 10
C407 E1 │ 60 POP HL
C408 D1 │ 70 POP DE
C409 F1 │ 80 POP AF
C40A F5 │ 90 PUSH AF
C40B E5 │ 100 PUSH HL
C40C 87 │ 110 ADD A, A
C40D F5 │ 120 PUSH AF
C40E D7 │ 130 RST 10
C40F 7A │ 140 LD A, D
C410 3D │ 150 DEC A
C411 57 │ 160 LD D, A
C412 D7 │ 170 RST 10
C413 3E20 │ 180 LD A, 20
C415 D7 │ 190 RST 10
C416 3E16 │ 200 LD A, 16
C418 D7 │ 210 RST 10
C419 F1 │ 220 POP AF
C41A D7 │ 230 RST 10
C41B 7A │ 240 LD A, D
C41C 3D │ 250 DEC A
C41D D7 │ 260 RST 10
C41E 3E20 │ 270 LD A, 20
C420 D7 │ 280 RST 10
C421 C9 │ 290 RET
│ 300 END
Листинг 11 PROG
│ 10 ORG C422
C422 CD50C3 │ 20 CALL C350 (RES)
C425 0609 │ 30 LD B, 09
C427 C5 │ 40 NEXT PUSH BC
C428 CDB4C3 │ 50 CALL C3B4 (RND)
C42B E603 │ 60 AND 03
C42D FE03 │ 70 CP 03
C42F 301C │ 80 JR NC, FOUR
C431 FE02 │ 90 CP 02
C433 3035 │ 100 JR NC, THREE
C435 FE01 │ 110 CP 01
C437 304E │ 120 JR NC, TWO
C428 CDB4C3 │ 130 CALL C3B4 (RND)
C43C E60F │ 140 AND 0F
C43E C606 │ 150 ADD A, 06
C440 C5 │ 160 PUSH BC
C441 F5 │ 170 PUSH AF
C442 CDC1C3 │ 180 CALL C3C1 (PRINT)
C445 F1 │ 190 POP AF
C446 C1 │ 200 POP BC
C447 F5 │ 210 PUSH AF
C448 CDFFC3 │ 220 CALL C3FF (ERASE)
C44B 1855 │ 230 JR FIN
C44D 0E1C │ 240 FOUR LD C, 1C
C44F 0604 │ 250 LD B, 04
C451 79 │ 260 ST 4 LD A, C
C452 D606 │ 270 SUB 06
C454 4F │ 280 LD C, A
C455 CDB4C3 │ 290 CALL C3B4 (RND)
C458 E601 │ 300 AND 01
C45A 81 │ 310 ADD A, C
C45B C5 │ 320 PUSH BC
C45C F5 │ 330 PUSH AF
C45D CDC1C3 │ 340 CALL C3C1 (PRINT)
C460 F1 │ 350 POP AF
C461 C1 │ 360 POP BC
C462 10ED │ 370 DJNZ ST4
C464 F5 │ 380 PUSH AF
C465 CDFFC3 │ 390 CALL C3FF (ERASE)
C468 1838 │ 400 JR FIN
C46A 0E1C │ 410 THREE LD C, 1C
C46C 0603 │ 420 LD B, 03
C46E 79 │ 430 ST 3 LD A, C
C46F D608 │ 440 SUB 08
C471 4F │ 450 LD C, A
C472 CDB4C3 │ 460 CALL C3B4 (RND)
C475 E603 │ 470 AND 03
C477 81 │ 480 ADD A, C
C478 C5 │ 490 PUSH BC
C479 F5 │ 500 PUSH AF
C47A CDC1C3 │ 510 CALL C3C1 (PRINT)
C47D F1 │ 520 POP AF
C47E C1 │ 530 POP BC
C47F 10ED │ 540 DJNZ ST3
C481 F5 │ 550 PUSH AF
C482 CDFFC3 │ 560 CALL C3FF (ERASE)
C485 181B │ 570 JR FIN
C487 0E1C │ 580 TWO LD C, 1C
C489 0602 │ 590 LD B, 02
C48B 79 │ 600 ST 2 LD A, C
C48C D60C │ 610 SUB 0C
C48E 4F │ 620 LD C, A
C48F CDB4C3 │ 630 CALL C3B4 (RND)
C492 E607 │ 640 AND 07
C494 81 │ 650 ADD A, C
C495 C5 │ 660 PUSH BC
C496 F5 │ 670 PUSH AF
C497 CDC1C3 │ 680 CALL C3C1 (PRINT)
C49A F1 │ 690 POP AF
C49B C1 │ 700 POP BC
C49C 10ED │ 710 DJNZ ST2
C49E F5 │ 720 PUSH AF
C49F CDFFC3 │ 730 CALL C3FF (ERASE)
C4A2 C1 │ 740 FIN POP BC
C4A3 1082 │ 750 DJNZ NEXT
C4A5 CDB4C3 │ 760 REP1 CALL C3B4 (RND)
C4A8 E607 │ 770 AND 07
C4AA 47 │ 780 LD B, A
C4AB CDB4C3 │ 790 CALL C3B4 (RND)
C4AE E603 │ 800 AND 03
C4B0 80 │ 810 ADD A, B
C4B1 FE01 │ 820 CP 01
C4B3 38F0 │ 830 JR C, REP1
C4B5 F5 │ 840 PUSH AF
C4B6 3E02 │ 850 LD A, 02
C4B8 CD0116 │ 860 CALL 1601
C4BB 3E16 │ 870 LD A, 16
C4BD D7 │ 880 RST 10
C4BE F1 │ 890 POP AF
C4BF 87 │ 900 ADD A, A
C4C0 3D │ 910 DEC A
C4C1 D7 │ 920 RST 10
C4C2 3E01 │ 930 LD A, 01
C4C4 D7 │ 940 RST 10
C4C5 3E20 │ 950 LD A, 20
C4C7 D7 │ 960 RST 10
C4C8 CDB4C3 │ 970 REP2 CALL C3B4 (RND)
C4CB E607 │ 980 AND 07
C4CD 47 │ 990 LD B, A
C4CE CDB4C3 │ 1000 CALL C3B4 (RND)
C4D1 E603 │ 1010 AND 03
C4D3 80 │ 1020 ADD A, B
C4D4 FE01 │ 1030 CP 01
C4D6 38F0 │ 1040 JR C, REP2
C4D8 F5 │ 1050 PUSH AF
C4D9 3E02 │ 1060 LD A, 02
C4DB CD0116 │ 1070 CALL 1601
C4DE 3E16 │ 1080 LD A, 16
C4E0 D7 │ 1090 RST 10
C4E1 F1 │ 1100 POP AF
C4E2 87 │ 1110 ADD A, A
C4E3 3D │ 1120 DEC A
C4E4 D7 │ 1130 RST 10
C4E5 3E1A │ 1140 LD A, 1A
C4E7 D7 │ 1150 RST 10
C4E8 3E20 │ 1160 LD A, 20
C4EA D7 │ 1170 RST 10
C4EB C9 │ 1180 RET
│ 1190 END
А теперь еще раз обратимся к
книге ИНФОРКОМА "Игры на Бей-
сике своими руками". Откройте
страницу 55. Здесь находится
описание и программа классичес-
кой компьютерной игры "SNAKMAN".
Надо сказать, что за последние 6
лет она встречалась мне три ра-
за в различных вариантах. Два из
них назывались "PITON", а один -
"KOBRA". "SNAKMAN" тоже исполь-
зует Лабиринт, хоть и один, что
несущественно (их может быть
сколько угодно). Так вот, Лаби-
ринты для "SNAKMAN"а годятся не
любые, а только обладающие необ-
ходимыми свойствами: они или
совсем не должны иметь тупиков,
или тупики должны быть достаточ-
но широки для маневра. Иначе Вам
никогда не собрать всех "ягод"
(лягушек, мышей и пр.). Что ка-
сается "широких" тупиков, то та-
кой Лабиринт построить довольно
легко, сделав все коридоры и
комнаты двойной или тройной ши-
рины. А построить Лабиринт вооб-
ще без тупиков? Я уверен, что
сейчас Вы принялись соображать,
какую систему ограничений сле-
дует наложить на алгоритм и ка-
кой алгоритм подходит больше.
Сразу скажу - этот путь "гиб-
лый". Никакой из выше перечис-
ленных алгоритмов не подойдет
из-за сложности накладываемых
ограничений.
Нужен новый алгоритм.
Коль скоро тупиков не должно
быть вообще, то давайте построим
лабиринт из замкнутых коридоров,
в которых нет тупиков (они за-
кольцованы). Тогда и в Лабирин-
те не могут появиться тупики.
Итак, "Алгоритм замкнутых ко-
ридоров": Листинг 12.
Листинг 12
10 BORDER 0: PAPER 0: CLS
15 FOR M = 1 TO 30
20 LET A = INT(RND * 8) + 3
30 LET X = INT(RND *(32 - A))
40 LET Y = INT(RND *(22 - A))
50 FOR N = 0 TO A
60 PRINT PAPER 5; AT Y + N,X; " "; AT Y + N, X + A; " ";
AT Y + A, X + N; " "; AT Y, X + N; " "
70 NEXT N: NEXT M
Мы использовали в качестве
исходной фигуры замкнутого кори-
дора квадрат, выбирая его разме-
ры и координаты расположения на
плоскости произвольным образом.
Лабиринт имеет свободные "полос-
ти" и некоторые коридоры увели-
ченной ширины. Это дает возмож-
ность свободного маневра. Ве-
роятность того, что какой-либо
квадрат останется "отрезанным",
зависит от переменной цикла "M".
При достаточно большом ее значе-
нии "отрезанных" квадратов не
будет. Конечно, исходной фигу-
рой для коридоров может быть не
только квадрат. Подойдет любая
замкнутая фигура: прямоугольник,
треугольник, любой многоуголь-
ник, окружность и т.п. Возможно,
что в своей программе Вы ис-
пользуете не одну замкнутую фи-
гуру, а некоторое их сочетание.
И вот теперь, никак нельзя
обойти вопрос о "степени свобо-
ды" Лабиринта. До сих пор мы ге-
нерировали Лабиринты с четырь-
мя степенями свободы, то есть с
возможностью движения в четырех
направлениях (исключая Листинг
5, так как для криволинейных фи-
гур число степеней свободы вооб-
ще не определено ( = бесконеч-
ности)). Если в последнем алго-
ритме исходной фигурой коридора
будет треугольник, то степеней
свободы будет не 4, а 6 (см.
рис. 2)
<────
┌─────────┐ ────
│ │
│ │
│ │
└─────────┘ ────────── ────
────────> <───────── ────>
<──────── ─────────>
Рис. 2
Для шестиугольника их тоже бу-
дет 6. Увеличение степени свобо-
ды Лабиринта неизбежно ведет к
усложнению системы управления
"марионеткой", поэтому вряд ли
целесообразно иметь их больше
чем 8. Вопрос о степени свободы
Лабиринта связан напрямую с за-
дачей "о паркетах", то есть, за-
полнением плоскости (для нас эк-
рана) многоугольными плитами.
Если все плитки одинаковые
правильные многоугольники, то
возможно всего три варианта
"паркетов": треугольники, квад-
раты, четырехугольники. Деформи-
руя их, можно получить несколько
иной вид, например, прямоуголь-
ники (рис. 3). Если в качестве
исходного рисунка
┌───────┐ ┌──────┐
├───────┤ │ │
├───────┤ │ │
└───────┘ └──────┘
┌──────┐ ┌──┬───┐
│ │ ├─┬┴─┬─┤
│ │ ├─┴┬─┴─┤
└──────┘ └──┴───┘
Рис. 3
взять "паркет" не из четыреху-
гольников, то, используя алго-
ритм "удаляемых" перегородок",
получим Лабиринт с 6 (шестью)
степенями свободы. Все это отно-
сится к двухмерным Лабиринтам.
Ясно, что в трехмерных Лабирин-
тах степень свободы будет всег-
да на 2 больше (вверх-вниз).
Привожу "программку", запол-
няющую плоскость экрана шестиу-
гольниками (Листинг 13)
Листинг 13
10 FOR N = 65368 TO 65399
20 READ A: POKE N, A
30 NEXT N
40 DATA 1,2,4,8,16,32,64,128,
255,0,0,0,0,0,0,0,
128,64,32,16,8,4,2,1,
0,0,0,0,0,0,0,255
50 FOR N = 0 TO 31 STEP 4
60 FOR M = 0 TO 21 STEP 2
70 PRINT AT M,N; "ABCD"; AT M + 1, N; "C A"; REM (РЕШ. G)
80 NEXT M: NEXT N
Ничего, что шестиугольники
немного деформированы. Зато каж-
дая перегородка находится на от-
дельном знакоместе и может быть
удалена без ущерба для других.
Кроме трех перечисленных одно-
родных "паркетов" существует еще
11 однородных, сочетающих раз-
ные фигуры. Возможно, они тоже
пригодны для наших целей. Тех,
кто этим вопросом заинтересует-
ся, я отсылаю к книге Г.Штейнга-
уза "Математический калейдоскоп"
(Библиотека "Квант", 1981 г.)
Пожалуй, на этом стоит закон-
чить. Думаю, что Вы поняли - Ла-
биринты "такое дело", которое
открывает огромное поле деятель-
ности для пользователей компью-
теров с любым уровнем подготов-
ки, и для исследований, и для
программирования. Остается еще
очень много незатронутых вопро-
сов (например, использование ПЗУ
в качестве таблицы случайных чи-
сел, совмещенный скроллинг и ге-
нерация Лабиринта, генерирование
трехмерных Лабиринтов и т.д.)
На "десерт" приведу еще один
алгоритм генерирования Лабирин-
тов, поражающий своей простотой
и сложностью выходящего многос-
вязного, со степенью свободы 8,
Лабиринта. В среде "Синклерма-
нов", он известен под странным
названием "Комбикорм" (Листинг
14).
Листинг 14
10 FOR N = 65368 TO 65423
20 READ A: POKE N, A
30 NEXT N
40 DATA 128,128,128,128,128,128,128,128,
255, 0, 0, 0, 0, 0, 0, 0,
1, 1, 1, 1, 1, 1, 1, 1,
0, 0, 0, 0, 0, 0, 0, 255,
128, 64, 32, 16, 8, 4, 2, 1,
1, 2, 4, 8, 16, 32, 64, 128,
0, 0, 0, 0, 0, 0, 0, 0
50 FOR N = 1 TO 32
60 LET B = INT( RND * 7 ) + 144
70 PRINT CHR$ B; " "; : REM(;)!
80 NEXT N
90 FOR N = 1 TO 512
100 LET B = INT( RND * 7 ) + 144
110 PRINT CHR$ B; : REM(;)!
120 NEXT N
130 FOR N = 1 TO 32
140 LET B = INT( RND * 7 ) + 144
150 PRINT CHR$ B; " "; : REM(;)!
160 NEXT N
170 PLOT 8,175: DRAW 247,0: PLOT 255,167: DRAW 0,-152:
DRAW -247,0: PLOT 0,15: DRAW 0,160
Конечно, для практики масштаб
изображения мелковат, но введя
пару стринговых массивов размер-
ностью (7,2), Вы легко имитируе-
те печать символами двойной ши-
рины и высоты. А в машинных ко-
дах вообще можно печатать симво-
лами любого размера (см. книгу
Инфоркома "Прикладная графика").
ВСЕ. ЖЕЛАЮ ВАМ УСПЕХОВ.
