Вид для печати
В том-то и беда, что в кодах. Кто и когда вознамерится найти точку входа (а может, и параметры)? В MAZIACS проще, BASIC-часть потрепал и готово... Но я попробую всё одно.Цитата:
Сообщение от jerri
Вот Maziacs для тех, кто не обзавёлся:Цитата:
а можно сюда зааттачить Maziaks а то прокся ftp режет
(вложению MAZIACS.ZIP низачот, и с горя оно убило себя об хард, 12.3 Кбайт, 12 просмотров на 19 IX 2006. Поминки на VIRT'е)
еще 3 алгоритма генерации лабиринтов
вот этот мне кажется достаточно абсурдным и перспективным :)
Автор: gunnerq@rambler.ru
Время: 11-05-05 06:55
По-моему можно проще:
1) берем чистую матрицу
2) ставим блоки по
периметру
3) обозначаем случайно вход и выход
4) кидаем случайно блок в
пустое место
6) если от входа до выхода можно дайти блок не убираем
5)
если кинули блоков больше, чем нам нужно (процент заполненности - например
40) выход
7) goto 4
//1
int mas[N][M];
memset(mas,0,M*N*sizeof(int));
//2
for(int i = 0;
i < N; i++)mas[i][0]=1;
for(int i = 0; i < N; i++)mas[i][M-1]=1;
for(int i = 0; i < M; i++)mas[0][i]=1;
for(int i = 0; i < M;
i++)mas[N-1][i]=1;
//3
int exit = random(M);
int enter = random(M);
mas[0][exit] = 0;
mas[N-1][enter] = 0;
//4
double percent = 0.4;
int zapolneno = N*2+(M-2)*2;
while(1)
{
x
= random(N-2);
y = random(M-2);
mas[x][y] = 1;
mas[x][y] =
СanPass(mas,0,exit,N-1,enter,N,M);
zapolneno +=max[x][y];
//5
if(zaploneno/(N*M) > percent)break;
}
bool CanPass(int mas[][],x1,y1,x2,y2,N,M)
{
//Волновой допустим
алгоритм проверки возможности пройти от (x1,y1) до (x2,y2)
}
Ну и чем же он отличается от алгоритма SMT для "комнатного" (вариант 2) лабиринта? Разве что волновой помск связности. Может, это и самый быстрый вариант, но как в памяти волну хранить? Помечать в самом лабиринте байты? Может пределов не хватить 0-255, а иначе будет память жрать.
Цитата:
Сообщение от TomCaT
не знаю :)
остальные смотрел?
тебе не надо путь тебе нужна волна
0 - пустое место
255 - стена
128 - волна
если новых 128 нет и выход недостижим - продолжаем генерить
просто имхо
проверять не каждый раз а раз в 16 точек или более
хорошо, попробую на русском (что не смогу перевести, оставлю на МЯ).
итак, лабиринт - массив A[64,64], причём он закольцован по краям, то есть двигаясь влево, выйдем с правой стороны, а двигаясь вниз - сверху. для упрощения, когда я буду писать A[x,y], будет подразумеваться A[x mod 64, y mod 64], (код, который отслеживает переполнения координат, там присутствует и довольно громоздкий)
итак,ну что, смогёт кто-нить накодить это для windows-графики, чтобы проверить? :)Код:fill(A, 255, 64*64); // все стенки
for x=0 to 2 do
for y=0 to 2 do
A[x,y] = #80; // не знаю, зачем
x=y=1
switch (random(4))
{
case 0: x=x+2; break;
case 1: x=x-2; break;
case 2: y=y+2; break;
case 3: y=y-2; break;
// изменения начальной позиции
// так как координаты закольцованы, начать можем даже снизу или справа
}
for (;;) // вечный цикл
{
ХодилиВлево=ХодилиВправо=ХодилиВверх=ХодилиВниз = нет;
пока не (ХодилиВлево и ХодилиВправо и ХодилиВверх и ХодилиВниз)
{
дистанция = 2+random(4);
выбрать_напр:
напр = random(4);
switch (напр) {
case 0:
если (ХодилиВлево) goto выбрать_напр;
for i=1 to дистанция
{
если (A[x-2,y]!=#FF или A[x-1,y]!=#FF или
A[x-2,y-1]!=#FF или A[x-1,y-1]!=#FF или
A[x-2,y+1]!=#FF или A[x-1,y+1]!=#FF)
{
ХодилиВлево = да;
goto выбрать_напр;
}
иначе
{
x=x-1; A[x,y] = 0;
}
}
break;
case 1:
если (ХодилиВправо) goto выбрать_напр;
for i=1 to дистанция
{
если (A[x+2,y]!=#FF или A[x+1,y]!=#FF или
A[x+2,y-1]!=#FF или A[x+1,y-1]!=#FF или
A[x+2,y+1]!=#FF или A[x+1,y+1]!=#FF)
{
ХодилиВправо = да;
goto выбрать_напр;
}
иначе
{
x=x+1; A[x,y] = 0;
}
}
break;
case 2:
если (ХодилиВверх) goto выбрать_напр;
for i=1 to дистанция
{
если (A[x,y-2]!=#FF или A[x,y-1]!=#FF или
A[x-1,y-2]!=#FF или A[x-1,y-1]!=#FF или
A[x+1,y-2]!=#FF или A[x+1,y-1]!=#FF)
{
ХодилиВверх = да;
goto выбрать_напр;
}
иначе
{
y=y-1; A[x,y] = 0;
}
}
break;
case 3:
если (ХодилиВниз) goto выбрать_напр;
for i=1 to дистанция
{
если (A[x,y+2]!=#FF или A[x,y+1]!=#FF или
A[x-1,y+2]!=#FF или A[x-1,y+1]!=#FF или
A[x+1,y+2]!=#FF или A[x+1,y-+]!=#FF)
{
ХодилиВниз = да;
goto выбрать_напр;
}
иначе
{
y=y+1; A[x,y] = 0;
}
}
break;
}
}
// ходили во все 4 стороны
do {
если ( (#5C78) >= #96 ) полный_стоп!
x = random(64);
y = random(64);
} while (A[x,y] != 0);
}
а почему реализация мне не понравилась? так потому что как будто компилер делал (мало используются регистры, смешные конструкции типа push hl / pop de). но так как алгоритм сверхбыстрый, огрехи в кодинге им компенсируются
Ух, захватывает :) Будет время, закодирую обязательно. Может, на этих выходных. Или раньше.Цитата:
Сообщение от SMT
2jerri: Посмотрел. Первый я пытался ещё Васиком на ZX, так и не перевёл идею рекурс. ходов с ответвлениями из задумки в прогу. А остальные -- вроде уже упоминались, кроме варианта "Жизнь" -- вот это тоже стоит проверить.
Да, а те два цикла от 0 до 2 в начале -- для квадрата старта 3x3. Он не подпадает под правила построения в алгоритме и "вырубается в монолите стенок" с самого начала.
Так, сажусь за Delphi...
немножко наврал в уменьшении переменной "дистанция". на самом деле, это счётчик, который уменьшается после каждого изменения x/y. то есть код внутреннего цикла выглядит как
в принципе, лабиринты тоже будут получаться хорошие, только менее извилистые, т.е. меньше точек, в которых ответвляется корридор. можно попробовать оба варианта :)Код:дистанция = 2+random(4);
выбрать_напр:
напр = random(4);
switch (напр) {
case 0:
если (ХодилиВлево) goto выбрать_напр;
for (;;)
{
если (A[x-2,y]!=#FF или A[x-1,y]!=#FF или
A[x-2,y-1]!=#FF или A[x-1,y-1]!=#FF или
A[x-2,y+1]!=#FF или A[x-1,y+1]!=#FF)
{
ХодилиВлево = да;
goto выбрать_напр;
}
иначе
{
x=x-1; A[x,y] = 0;
дистанция=дистанция-1;
если (дистанция == 0) break; // внутренний for (;;)
}
}
break; // case
// аналогично по остальным направлениям
ещё забыл вставить перед первым for (;;) команды A[x,y]=0, без которой начальный квадрат оказывается отрезан от остального лабиринта
ещё не забудь, что куча обращений типа A[x+1,y-2] на самом деле кишит остатками от деления на размер лабиринта (mod 64)
а насчёт начального квадрата, почему он кодируется кодом #80, а не #00?
а если вот такой алгоритм? тоже должен быть эффективнымЦитата:
еще алгоритм берем непроходимый лабиринт произвольную клетку делаем проходимой далее повторяем следующий шаг: выбираем произвольную непроходимую клетку, имеющую ровно 1 проходимого соседа, и делаем ее проходимой так до тех пор, пока такие клетки есть в результате получится лабиринт-"дерево" (между любыми двумя проходимыми клетками есть ровно один путь)
так в кодах имхо интереснееЦитата:
Сообщение от TomCaT
чего то у мя игра виснет не запускается