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

[jerri]

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

не знаю

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

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

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

просто имхо

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

[Advertiser]

[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?

[TomCaT]

ещё не забудь, что куча обращений типа A[x+1,y-2] на самом деле кишит остатками от деления на размер лабиринта (mod 64)

а насчёт начального квадрата, почему он кодируется кодом #80, а не #00?

Ничего не забуду. Общее оформление вот счас сделал, теперь алгоритм странслирую на Pascal, а там и экзешник сюда выложу.

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

игра ок. 20 кб, бейсик-коды в виде блока кодов, с дискеты как обычно грузятся в память повыше, а потом перемещаются на адрес 23296 (16384, не помню в оющем). В процессе перемещения могут быть убиты сиспеременные памяти 128-ых и старше. Поэтому запускайся в режиме 48.

А если и там не будет пахать, то где-то у меня z80-образ завалялся. Подойдёт?

[TomCaT]

а насчёт начального квадрата, почему он кодируется кодом #80, а не #00?

Кстати, понял - чтобы и не стенка, и не проход. Не проход - чтоб из старта не отводить новые пути при случ. поиске начала нового ответвления. Не стенка - чтоб не закрасить его очередным ответвлением.

[SMT]

уже сам понял. если края окантовать кодов #80 и стартовый квадрат переместить в середину, можно генерить лабиринты без циклического зацикливания по краям