23.01.2017 11:16
RussDragon 35 11000 Источник


Предисловие


На написание статьи меня сподвигло практически полное отсутствие материалов на русском языке про алгоритмы генерации лабиринтов. На Хабре, из того, что вообще есть по теме, можно отметить две статьи: раз и два. Ценность и пользу из которых несет лишь вторая. В первой – просто перевод формального алгоритма и небольшое его пояснение. Что, конечно, неплохо, но очень скудно и не вызывает желания изучать тему дальше.

Если моя статья Вам понравится, я продолжу писать о различных алгоритмах. Мы рассмотрим два самых примитивных и простых случая – генерация двоичного дерева и Сайдвиндер, который, по своей сути, просто чуть измененная версия двоичного дерева с одним заметным плюсом. ОСТОРОЖНО ТРАФИК.

Дам один совет – не подглядывайте в код до тех пор, пока вы не напишите свою реализацию. Вы получите гораздо больше удовольствия и пользы от исправления багов и поиска ошибок, чем если просто переведете с одного языка на другой.

Серьезно. Прислушайтесь к совету. Вы, верно, потратите больше времени, но оно стоит стоит. У меня, например, из-за пары ошибок появился очень забавный генератор «инопланетных» текстов, который можно использовать в различных Sci-Fi играх для создания текста. Надеюсь, Вы изучаете тему для себя и никуда не спешите.

P.S.:

Я буду использовать термин «смещение», предполагая английский bias. Т.е. пристрастие алгоритма к направленности в какую-либо сторону. Например, правое смещение – алгоритм генерирует лабиринты с длинными правыми проходами.

Раскраска лабиринтов происходит относительно расстояния от крайнего левого угла поля до некоторой клетки. Чем дальше от начальной координаты – тем темнее будет цвет.

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

Про Lua
Когда я только начинал закапываться в тему лабиринтов, я не предполагал, что в итоге буду писать статью и выбрал язык, на котором у меня есть возможность не тратить слишком много времени на рендер и архитектуру и заниматься исключительно логикой. В итоге, между C++ и Lua, выбор пал на Lua и Love2D.

Не стоит переживать, если Вы с Луа незнакомы. Незнание языка никак не помешает Вам понять реализацию, благодаря простоте синтаксиса. Если Вы хотя бы немного умеете программировать, 80% кода не вызовет у Вас проблем с пониманием. Остальные 20% — language specific, про которые я всегда буду писать вначале статьи, объясняя их работу.

Первое, что мне следует сказать:
Lua имеет лишь одну структуру данных – таблицы – ассоциативный массив, при помощи которого мы создаем нужные нам структуры. К примеру, классы, множества, обычные массивы, стаки, очереди и тому подобное. Обращаться к ним мы может либо с помощью строчных-ключей, либо с помощью индексов.
Так же, таблицы не ограничивают нас в хранении только одного типа данных в одном объекте и работают подобно структурам в C/C++. Такой код абсолютно корректен:

ourStructure = {}
ourStructure[“BeautyKey”] = 42
ourStructure[42] = “UltimateAnswer”
ourStructure[1] = false

Присваивание nil удалит поле:
ourStructure[42] = nil


Второе:
Lua не имеет скрытого механизма копирования таблиц. Код, приведенный ниже, не будет копировать и создавать нового объекта SomeNewArray, он лишь скопирует в него ссылку на объект SomeArray, и, следовательно, будет изменять его точно так же, как если Вы передадите значение через неконстантную ссылку или указатель в C/C++:

someArray = {}
someArray[1] = 42
someArray[2] = “ReferencesTest”
someNewArray = someArray 
someNewArray[1] = “42 Is Gone, Now Only the Garbage-String here”


И третье, для тех, кто хорошо знаком с Lua:
Да, я знаю, что в некоторых местах код избыточен. И то, что в некоторых местах всё можно было бы упростить метаметодами тоже. Следует учитывать то, что код писался в первую очередь для того, чтобы разобраться с алгоритмами, а не для использования в реальном проекте. К тому же, отсутствие избытка специфических для языка функций позволяет выкладывать код в том виде, в котором он есть, без нагромождений комментариев.


Алгоритм двоичного дерева








Описание:

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

Такой способ генерации имеет два побочных эффекта:

1. Лабиринты обладают сильным диагональным смещением и отсутствием тупиков в его направлении. Посмотрите на скриншоты выше и Вы увидите, что каждый из коридоров стремится к правой верхней клетке, и, как итог, имеет ровно один путь к ней, и нигде на пути нет тупика:

2. Два пустых коридора по сторонам лабиринта. Когда алгоритм «прокапывается» до конца строки/столбца, ему не остается выбора, кроме как продолжить путь в одном единственном направлении, создавая пустые «границы».

К слову, название не просто так совпадает со структурой данных. Результат его работы – случайное двоичное дерево, в котором из каждой клетки (вершины) есть ровно 1 путь по направлению к корню (родительской вершине), и, соответственно, ровно 1 путь к любой другой клетке. Как следствие, любая клетка имеет не более 3 соединений со своими соседями.

Формальный алгоритм (для северо-восточного смещения):

  1. Выбрать начальную клетку;
  2. Выбрать случайное направление для прокладывания пути. Если соседняя клетка в этом направлении выходит за границы поля, прокопать клетку в единственно возможном направлении;
  3. Перейти к следующей клетке;
  4. Повторять 2-3 до тех пор, пока не будут обработаны все клетки;

Пример работы
Зеленое – текущая рассматриваемая клетка, красное – фронт, клетки, в которые можно переместиться.

Начинаем с координаты (0;0). Наверх в этом ряду пойти не можем, так как иначе выйдем за границы лабиринта. Идем вправо до упора, по пути снося все стены.





Всё, тупик. Идти некуда. Перемещаемся на следующий ряд и видим, что теперь есть возможность пойти наверх и вправо.



Кидаем монетку и выбираем… Верх. Убираем стену и переходим к следующей клетке.


Отлично. Случай подсказывает нам идти направо. Убираем стену и перемещаемся в следующую клетку.







Выбора у нас нет, налево пойти не можем, значит, убираем стену сверху и идем на следующий ряд.





Монета убеждает нас пойти направо. Что же, слушаемся. Убираем стену и переходим к слеудующей клетке.





Прокатившись метр, наш несчастный кусок металла падает и говорит, что пора идти наверх. Сносим стену, шагаем к следующей клетке, и, так как она крайняя в этом ряду, убираем стену сверху. Лабиринт закончен.







Плюсы:
  • Простая реализация;
  • Высокая скорость работы;
  • Возможность генерировать бесконечные лабиринты;

Минусы:
  • Низкая сложность рисунка;
  • Сильное смещение по диагонали;
  • Отсутствие тупиков по смещению;
  • Однообразность сгенерированных лабиринтов;

Реализация

local mod = {}
local aux = {}

aux.width = false
aux.height = false
aux.sx = false
aux.sy = false
aux.grid = false

function aux.createGrid (rows, columns)
  local MazeGrid = {}

  for y = 1, rows do 
    MazeGrid[y] = {}
    for x = 1, columns do
      MazeGrid[y][x] = {bottom_wall = true, right_wall = true} -- Wall grid
    end
  end  
  return MazeGrid
end

-- Binary Tree North-East variant 
function mod.createMaze(x1, y1, x2, y2, grid)
  aux.width, aux.height, aux.sx, aux.sy = x2, y2, x1, y1
  aux.grid = grid or aux.createGrid(aux.height, aux.width)
  aux.binarytree()
  return aux.grid
end

function aux.binarytree() 
  for y = aux.sy, aux.height do 
    for x = aux.sx, aux.width do
      if y ~= aux.sy then 
        if math.random(0, 1) == 0 then 
          if x ~= aux.width then 
            aux.grid[y][x].right_wall = false
          else
            aux.grid[y-1][x].bottom_wall = false
          end
        else
          aux.grid[y-1][x].bottom_wall = false
        end
      else
        if x ~= aux.width then 
          aux.grid[y][x].right_wall = false 
        end
      end
    end
  end
end

return mod


Алгоритм «Sidewinder»








Описание:

Алгоритм с непереводимым названием Sidewinder по своей работе очень похож на алгоритм двоичного дерева, в том отличии, что в нём нет характерного смещения по диагонали, одного пустого коридора и клетки мы рассматриваем не по отдельности, а множествами. Лабиринты получаются с преимущественно вертикальным или горизонтальным смещением (в зависимости от реализации), с отсутствием тупиков в их направлении. В сравнении со своим более примитивным собратом, смещение не так заметно и больше похоже на «спираль», которая плавно сменяет вертикальные и горизонтальные коридоры.

Что касается побочных эффектов, то Sidewinder создает только один пустой коридор на одной стороне, вместо двух. Начиная создание множеств с первого ряда поля, у нас отсутствует возможность прокопать путь наверх, так как мы находимся в самом крайнем вертикальном положении и попытка пойти выше приведет к выходу за границы поля. Но и если мы будем организовывать множества без выхода по вертикали, мы создадим несколько изолированных друг от друга областей.

Для примера: 9 клеток первого ряда можно поделить на три множества, между которыми расположены стены. Каждое множество второго ряда будет прокапывать путь к одному из трех «блоков» выше. Третий ряд проложит путь к «блокам» второго. И так до конца поля. В итоге, у нас получатся 3 разветвленные, изолированные друг от друга вертикальные области, что не подходит для идеального лабиринта, в котором из каждой точки поля есть ровно 1 путь в любую другую.

Формальный алгоритм (для стандартного смещения):

  1. Выбрать начальный ряд;
  2. Выбрать начальную клетку ряда и сделать её текущей;
  3. Инициализировать пустое множество;
  4. Добавить текущую клетку в множество;
  5. Решить, прокладывать ли путь направо;
  6. Если проложили, то перейти к новой клетке и сделать её текущей. Повторить шаги 3-6;
  7. Если не проложили, выбираем случайную клетку множества и прокладываем оттуда путь наверх. Переходим на следующий ряд и повторяем 2-7;
  8. Продолжать, пока не будет обработан каждый ряд;

Пример работы
Красные клетки – члены множества.
Мы начинаем с первого ряда и видим, что выше нас – выход за пределы поля. Сносим все стены и идем сразу во второй ряд, создаем пустое множество.





Так, а вот тут интереснее. Давайте добавим в множество первые две клетки ряда.



Выбираем одну из этих клеток и убираем относящуюся к ней верхнюю стенку в первый ряд.



Обнуляем множество, добавляем в нее следующую клетку ряда.



В этот раз ни с кем не объединяем, просто прокладываем путь наверх прямо из этой единственной клетки.



Повторяем наши действия. Обнуляем множество, переходим в следующую клетку, добавляем её… А так как она осталась последней в ряде, то так же убираем стену сверху и идем в ряд ниже.





А теперь сразу объединяем три первые клетки в одно множество.



Случайно выбираем клетку, в нашем случае, вторую и убираем стену сверху к предыдущему ряду.



Ну, тут у нас опять нет выбора, убираем стену наверху и идем на ряд ниже.





На этот раз, самую перваую клетку мы сделаем единственной. Убираем стену к предыдущему ряду и идем дальше, в следующую клетку.





Предположим, что захотели в конце объединить три клетки.



И снова нам приглянулась средняя клетка из множества, из которой и убираем стену наверх. Всё, наш лабиринт готов.


Плюсы:

  • Возможность генерировать бесконечные лабиринты;
  • Только 1 пустой коридор;
  • Более сложный рисунок, в отличии от алгоритма двоичного дерева;

Минусы:

  • Более запутанная реализация;
  • Отсутствие тупиков по смещению;
  • Сильное вертикальное смещение;

Реализация
local mod = {}
local aux = {}

aux.width = false
aux.height = false
aux.sx = false
aux.sy = false
aux.grid = false

function aux.createGrid (rows, columns)
  local MazeGrid = {}

  for y = 1, rows do 
    MazeGrid[y] = {}
    for x = 1, columns do
      MazeGrid[y][x] = {bottom_wall = true, right_wall = true}
    end
  end  
  return MazeGrid
end

function mod.createMaze(x1, y1, x2, y2, grid)
  aux.height, aux.width, aux.sx, aux.sy = y2, x2, x1, y1
  aux.grid = grid or aux.createGrid(y2, x2)
  aux.sidewinder()
  return aux.grid
end

function aux.sidewinder()
  local cx = aux.sx --[[ cx – координата начала множества по x. У нас нет надобности создавать отдельный массив для сета, так как его элементы всегда располагаются строго в ряд ]]
  for y = aux.sy, aux.height do
    for x = aux.sx, aux.width do 
      if y ~= aux.sy then
        if math.random(0, 1) == 0 and x ~= aux.width then
          aux.grid[y][x].right_wall = false
        else 
          aux.grid[y-1][math.random(cx, x)].bottom_wall = false

          if x ~= aux.width then
            cx = x+1
          else 
            cx = aux.sx
          end
        end
      else 
        if x ~= aux.width then 
          aux.grid[y][x].right_wall = false 
        end
      end
    end
  end
end

return mod


Эпилог


Надеюсь, Вам понравилась статья и Вы почерпнули новые знания о примитивной процедурной генерации лабиринтов. Я выбрал два самых простых в реализации и работе алгоритма, чтобы новичкам было проще «пощупать» тему и понять, хотят ли они изучать её дальше. Мне важно знать, интересны ли такие статьи людям на Хабрахабре и стоит ли продолжать их писать. Для читателей у меня есть еще минимум 9 классических алгоритмов, которые стоит рассмотреть. Какие-то представляют из себя случайное блуждание по полю, как, например, алгоритм Прима или Уилсона, какие-то требуют больше ресурсов для работы, так как работают с графами, например, Эллер и Крускал, а какие-то выдерживают золотую середину. Но и это не конец – у меня в рукаве есть такие вещи, как: полярные (круглые) лабиринты, генерация лабиринтов на различной сетке (гексы, треугольник и пр.), маскинг лабиринтов в надписи и формы, 2.5Д лабиринты и 3Д, теория лабиринтов, статистическое сравнение алгоритмов, комбинированные алгоритмы генерации. В конце концов, у нас есть еще огромное множество вариаций типов лабиринтов. Например, сейчас мы рассматриваем идеальные алгоритмы, в которых из каждой точки есть ровно один путь в любую другую. Но ведь есть еще и те, которые позволяют одной клетке иметь несколько путей для любой другой! Например, Quake, Doom и прочие шутеры в только-только зарождающемся жанре использовали такие алгоритмы для генерации уровней, по некоторым слухам.

Поэтому, если Вам понравилась статья, тема, и Вы хотите видеть их дальше – то, пожалуйста, напишите об этом в комментарии. Так же, буду очень рад любой критике, как в техническом плане, так и в лингвистическом и стилистическом.
Поделиться с друзьями
-->

Комментарии (35)


  1. Pinsky
    23.01.2017 14:42
    #10029222
    +7

    Очень хорошая статья!
    Я бы не отказался от продолжения!

    Интересны хорошие алгоритмы генерации карт с комнатами.
    И карты с произвольными дорогами и областями(не квадратными), но доступными к прохождению из любого «ходимого» куска карты к любому.


    1. RussDragon
      23.01.2017 15:08
      #10029268
      +1

      Приятно слышать :)
      Алгоритмы генерации помещений, боюсь, немного выходят за рамки цикла, но, при возможности, я с радостью о них напишу. Единственное, что подойдет для таких целей, я думаю, алгоритм рекурсивного деления, который при должной настройке способен создавать планы помещений.

      Насчет карт с произвольными дорогами… Тут сложнее. Прежде, чем увлечься лабиринтами, я замышлял написать свой генератор процедурных городов, со всеми правилами строительства: выбором роста города и дорог (прямые дороги, радиальные, хаотичные...), выбором различных городских занятий (туристический город/промышленный), от которых бы зависели типы и размеры районов, и всё в таком духе. К сожалению, пока до реализации такого не дошло, но, может быть, ради Хабра что-нибудь да напишу.

      Пример рекурсивного деления


    1. edge790
      24.01.2017 12:12
      #10030796
      +1

      По картам с комнатами была статья:.
      Также видел алгоритмы по генерации карт в туториалах по Юнити (ссылка). Если примерно, то алгоритм выглядит так:
      1) Берём двумерный массив и рандомом заполняем его(в туториале использовалась переменная — % заполнения — генерим число от 0 до 100 и если оно меньше % заполнения, то ставим тут стенку)
      2) Делаем несколько итераций «сглаживания» (берём каждую клетку, если это стенка если её окружает < N стенок то делаем её пустой. Если это не стена, но её окружает < M стенок, то делаем стенку). В итоге «одинокие» стенки и «дырки» пропадают. Повторяем эту процедуру X — раз. (N, M и X — то же переменные, с которыми можно играться и от них будет сильно зависить результат)
      3) Делаем два лист листов: один — коллекция областей(область — коллекция клеток) в которых стены, второй — коллекция областей без стен. Таким образом у нас есть N — комнат, которые мы теперь можем просто соединить между собой или просто сдвинуть.

      Играясь с переменными будет получаться совершенно разный результат. Тут ещё стоит учитывать что «сглаживание» увеличивает разрыв между пустыми клетками и клетками со стенами. В моём случае в 45-48% заполнения получались большие пустые области с несколькими комнатками, а в случае 52-55% — много небольших-средних комнатушек.


    1. wladyspb
      24.01.2017 18:32
      #10031878

      Хорошая статья на хабре про генерацию помещений( на примере карт подземелий для рогалика)


  1. zloddey
    23.01.2017 15:16
    #10029294
    +1

    Спасибо за статью!


    Помнится, в детстве развлекался тем, что рисовал подобные лабиринты на бумаге, а потом пытался пройти их, используя карманный микроскоп с небольшим увеличением (до чего только не дойдёшь, когда нет компьютера). Вот тогда бы мне точно пригодился Sidewinder!


    1. Deosis
      24.01.2017 07:32
      #10030376
      +1

      Думаю, тут трудно найти человека, который не рисовал в детстве лабиринты.
      Я рисовал лабиринт с цветными дверьми и одноразовыми ключами. Там надо было дважды пройти через одну клетку, чтобы собрать нужный набор ключей.


  1. Durimar123
    23.01.2017 15:45
    #10029348
    +6

    Что скажите о таком лабиринте?
    image


    1. RussDragon
      23.01.2017 15:51
      #10029358
      +1

      Ну, могу сказать, что он какой-то некрасивый =)

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


      1. Durimar123
        23.01.2017 16:03
        #10029384
        +1

        Зато принцип прикольный. Подскажите как видео залить попроще?


        1. RussDragon
          23.01.2017 16:04
          #10029388
          +1

          Ну, Вы можете залить видео на Youtube и кинуть сюда ссылку. Или гифку записать. На ум ничего другого как-то не приходит.


          1. MrCheater
            23.01.2017 16:15
            #10029424
            +1

            YouTube-видео через тег <oembed>...</oembed> вставляется в статьи


            1. RussDragon
              23.01.2017 16:16
              #10029428
              +1

              Не очень понимаю, к чему Вы. В комментариях тег тоже поддерживается, а в статье я не вижу причин вставлять видео.


          1. Durimar123
            23.01.2017 16:56
            #10029510
            +1

            Попробую видео построения лабиринта методом взрыва.

            https://www.youtube.com/watch?v=tVDl2Tj_vmw

            ps
            через oembed не хочет


            1. MrCheater
              23.01.2017 17:17
              #10029536
              +1

              "Это видео недоступно."
              UPD: было недоступно — стало доступно


              1. Durimar123
                23.01.2017 17:19
                #10029546
                +5

                Сорри, а сейчас?


                1. RussDragon
                  23.01.2017 18:18
                  #10029616
                  +1

                  Интересно. Расскажите, пожалуйста, немного больше о вашем методе.


  1. valemak
    23.01.2017 19:02
    #10029696
    +1

    Есть ещё крайне простой способ генерации лабиринта, методом цикады.

    Демка.


    1. RussDragon
      23.01.2017 19:17
      #10029714
      +2

      Красиво, но, как и сообщением выше, это не идеальный лабиринт :(
      О лабиринтах Вашего типа, возможно, поговорим попозже.

      UPD: А еще у вас там изолированные области встречаются, что точно нехорошо.


  1. Danik-ik
    23.01.2017 19:28
    #10029720
    +2

    Обязательно пишите!


    Мне очень интересно, вылезет ли где-то алгоритм на графе, который я придумывал буквально незадолго до первой статьи на эту тему на Хабре (таки надо его запрограммировать :) )


    Графы чем хороши — так это тем, что построение лабиринта в принципе отвязано от его геометрии. Долой квадратность!


  1. pavelpp
    23.01.2017 22:36
    #10029986
    +6


  1. pestilent
    24.01.2017 09:37
    #10030510
    +2

    Не понимаю, что все так зациклены на идеальных лабиринтах. Даже Лосяш туда же — чем больше тупиков, тем лучше :) Но такие лабиринты самые скучные, их сложность только в длине, нельзя назвать их по-настоящему сложными. Для меня «идеальный» лабиринт,— наоборот, лабиринт без тупиков (и без петель).


    1. RussDragon
      24.01.2017 09:48
      #10030528

      Лабиринты без тупиков зовутся Braid-mazes и, как Вы верно подметили, они гораздо сложнее для решения человеком. Обязательно посвящу им отдельный цикл статей, если наберется материала. Но, лично по-моему, идеальные лабиринты красивее, хотя по своей сути и являются остовным деревом.


      1. olekl
        24.01.2017 13:44
        #10030964

        Что-то не понял, почему сложнее? Идешь, за правую стеночку держишься и все…


        1. wladyspb
          24.01.2017 18:35
          #10031882

          Угу. А выход, например, в центре)


        1. pestilent
          25.01.2017 22:48
          #10034846

          Это как раз для идеальных лабиринтов алгоритм. Потому что в них только одна стена на весь лабиринт.


  1. jimmyjonezz
    24.01.2017 20:43
    #10032162
    +1

    Очень ждал подобную статью. Информативная и понятная. Жду продолжения.


    1. RussDragon
      24.01.2017 21:08
      #10032226
      +1

      Сейчас уже готовлю материалы про алгоритм Алдоса-Бродера и Уилсона. Надеюсь уложиться в неделю. Единственое, что может задержать – необходимость переписать реализацию Уилсона на Луа, потому что в нынешнем виде мне немного стыдно её выкладывать.


      1. jimmyjonezz
        24.01.2017 21:53
        #10032334
        +1

        Я так понял Вы хотите пройтись по следующим распространенным алгоритмам:


        1. Алгоритм бинарного дерева (есть)
        2. Алгоритм Эллера (есть)
        3. Алгоритм Прима
        4. Алгоритм Олдоса-Бродера
        5. Алгоритм Уилсона
        6. Алгоритм Крускала
        7. Алгоритм рекурсивного деления
        8. Алгоритм рекурсивного поиска с возвратом?

        Кстати, могу ошибаться, но алгоритм «Sidewinder это Алгоритм Эллера, он же Simple algorithms (когда в памяти храниться текущая и предыдущая строки лабиринта).


        1. RussDragon
          24.01.2017 22:02
          #10032360

          Нет, Сайдвиндер и Эллер хоть и похожи по работе, всё-таки, это разные алгоритмы. У Эллера совсем иная работа с сетами и логика их использования. Если в Сайдвиндере мы всегда работает исключительно с одним множеством в единицу времени, то Эллер манипулирует неограниченным количнством одновременно, в том числе и объединяя некоторые из них.

          А так в вашем списке не хватает еще 2-3 алгоритмов:
          Алгоритм Уилсона,
          Алгоритм HuntandKill,
          Алгоритм растущего дерева (по сути, рекурсивный поиск с возвратом при одном из вариантов реализации)


          1. jimmyjonezz
            24.01.2017 22:28
            #10032398
            +1

            Эллер манипулирует неограниченным количнством одновременно, в том числе и объединяя некоторые из них

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


            1. RussDragon
              24.01.2017 22:38
              #10032414
              +1

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

              Эллер работает с ограниченным количеством множеств, вплоть до размерности строки.
              То есть, если у Вас строка состоит из десяти клеток, то, теоретически, Эллер может работать с 10 отдельными множествами и не объединить ни одного. Sidewinder же всегда работает исключительно с одним.


  1. Piter_Y
    24.01.2017 21:57
    #10032352
    +1

    Когда то, еще на Спектруме делал лабиринты, которые можно было пройти используя правило правой руки. Только не стирал стенки а наоборот, строил их. Упрощенно алгоритм выглядел так: Имелся массив узлов сетки. Выбиралась случайная точка на границе сетки и из нее рисовалась стенка. Если стенка попадала на непустой узел, то она не прорисовывалась. Если на пустой, то рисовалась. Далее с помощью некоторых коэффициентов и генератора случайных чисел решалось продолжать ли рисовать стенку в том же направлении, изменить направление или выбрать для генерации другую точку. Новой точкой мог быть любой непустой узел сетки из которого можно было построить новую стенку, которая заканчивалась на пустом узле. Меняя коэффициенты можно было получить самые разные лабиринты. С прямыми длинными коридорами, наоборот, с извилистыми. Петли получались, если заранее прорисовывать участки стены не прикасающиеся к границам лабиринта. Все это было написано на Бейсике много, много лет назад)))


  1. jimmyjonezz
    27.01.2017 19:24
    #10038910
    +1

    Тема оказалась очень увлекательной и интересной. В поисках «большего» набрел на удивительную книжку по алгоритмам — Mazes for Programmers. Советую.


    1. RussDragon
      27.01.2017 19:32
      #10038938

      Согласен, замечательная книжка. Хотя местами чересчур тщательно разжевываются самые основы-основ программирования.


      1. jimmyjonezz
        27.01.2017 19:55
        #10038970

        и неплохое подспорье для тех, кто изучает Ruby