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), Вы легко имитируе- те печать символами двойной ши- рины и высоты. А в машинных ко- дах вообще можно печатать симво- лами любого размера (см. книгу Инфоркома "Прикладная графика"). ВСЕ. ЖЕЛАЮ ВАМ УСПЕХОВ.
Другие статьи номера:
Похожие статьи:
В этот день... 9 октября