ZX Review #11-12 26 ноября 1997

Профессиональный подход - Алгоритмы построения и прохождения Лабиринтов.

┌──────────────────────────────┐
│                              │
│   ПРОФЕССИОНАЛЬНЫЙ ПОДХОД    │
│                              │
└──────────────────────────────┘

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), Вы легко имитируе-
те печать символами двойной  ши-
рины и высоты. А в машинных  ко-
дах вообще можно печатать симво-
лами  любого размера  (см. книгу
Инфоркома "Прикладная графика").

     ВСЕ. ЖЕЛАЮ ВАМ УСПЕХОВ.