Генерация лабиринтов

[TomCaT]

он в кодах и там задается лабиринт почти любого размера

http://trd.speccy.cz/gamez/123/3DLABYR_.ZIP

В том-то и беда, что в кодах. Кто и когда вознамерится найти точку входа (а может, и параметры)? В MAZIACS проще, BASIC-часть потрепал и готово... Но я попробую всё одно.

а можно сюда зааттачить Maziaks а то прокся ftp режет

Вот Maziacs для тех, кто не обзавёлся:

(вложению MAZIACS.ZIP низачот, и с горя оно убило себя об хард, 12.3 Кбайт, 12 просмотров на 19 IX 2006. Поминки на VIRT'е)

[Advertiser]

[jerri]

еще 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)
}

[TomCaT]

Ну и чем же он отличается от алгоритма SMT для "комнатного" (вариант 2) лабиринта? Разве что волновой помск связности. Может, это и самый быстрый вариант, но как в памяти волну хранить? Помечать в самом лабиринте байты? Может пределов не хватить 0-255, а иначе будет память жрать.

[jerri]

Ну и чем же он отличается от алгоритма SMT для "комнатного" (вариант 2) лабиринта? Разве что волновой помск связности. Может, это и самый быстрый вариант, но как в памяти волну хранить? Помечать в самом лабиринте байты? Может пределов не хватить 0-255, а иначе будет память жрать.

не знаю

остальные смотрел?

тебе не надо путь тебе нужна волна

0 - пустое место
255 - стена
128 - волна
если новых 128 нет и выход недостижим - продолжаем генерить

просто имхо

проверять не каждый раз а раз в 16 точек или более

[SMT]

хорошо, попробую на русском (что не смогу перевести, оставлю на МЯ).
итак, лабиринт - массив A[64,64], причём он закольцован по краям, то есть двигаясь влево, выйдем с правой стороны, а двигаясь вниз - сверху. для упрощения, когда я буду писать A[x,y], будет подразумеваться A[x mod 64, y mod 64], (код, который отслеживает переполнения координат, там присутствует и довольно громоздкий)
итак,

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);
}

ну что, смогёт кто-нить накодить это для windows-графики, чтобы проверить?

[SMT]

а почему реализация мне не понравилась? так потому что как будто компилер делал (мало используются регистры, смешные конструкции типа push hl / pop de). но так как алгоритм сверхбыстрый, огрехи в кодинге им компенсируются

[TomCaT]

хорошо, попробую на русском (что не смогу перевести, оставлю на МЯ).
итак, лабиринт - массив A[64,64], причём он закольцован по краям, то есть двигаясь влево, выйдем с правой стороны, а двигаясь вниз - сверху. для упрощения, когда я буду писать A[x,y], будет подразумеваться A[x mod 64, y mod 64], (код, который отслеживает переполнения координат, там присутствует и довольно громоздкий)
итак,

fill(A, 255, 64*64); // все стенки
for x=0 to 2 do
for y=0 to 2 do
A[x,y] = #80; // не знаю, зачем

--- Cut ---
...
алгоритм
...
--- Cut ---

ну что, смогёт кто-нить накодить это для windows-графики, чтобы проверить?

Ух, захватывает Будет время, закодирую обязательно. Может, на этих выходных. Или раньше.

2jerri: Посмотрел. Первый я пытался ещё Васиком на ZX, так и не перевёл идею рекурс. ходов с ответвлениями из задумки в прогу. А остальные -- вроде уже упоминались, кроме варианта "Жизнь" -- вот это тоже стоит проверить.

Да, а те два цикла от 0 до 2 в начале -- для квадрата старта 3x3. Он не подпадает под правила построения в алгоритме и "вырубается в монолите стенок" с самого начала.

Так, сажусь за Delphi...

[SMT]

немножко наврал в уменьшении переменной "дистанция". на самом деле, это счётчик, который уменьшается после каждого изменения 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?

[jerri]

еще алгоритм берем непроходимый лабиринт произвольную клетку делаем проходимой далее повторяем следующий шаг: выбираем произвольную непроходимую клетку, имеющую ровно 1 проходимого соседа, и делаем ее проходимой так до тех пор, пока такие клетки есть в результате получится лабиринт-"дерево" (между любыми двумя проходимыми клетками есть ровно один путь)

а если вот такой алгоритм? тоже должен быть эффективным

[jerri]

В том-то и беда, что в кодах. Кто и когда вознамерится найти точку входа (а может, и параметры)? В MAZIACS проще, BASIC-часть потрепал и готово... Но я попробую всё одно.

Вот Maziacs для тех, кто не обзавёлся:

так в кодах имхо интереснее

чего то у мя игра виснет не запускается