как строить лабиринты (программистское)

[avva]

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

Алгоритмы описаны по этим двум ссылкам, я просто вкратце перескажу. Наша цель - создать случайный лабиринт заданных размеров, сложный для решения вручную. Оба алгоритма создают лабиринты, в которых нет циклов, и между любыми двумя точками всегда есть маршрут, и он единственный (если без повторов). Для тех, кто знаком с формальном терминологией, достаточно сказать, что они выбирают какое-то spanning tree графа всех комнат лабиринта.

Первый алгоритм следит за разбиением всех комнат на подмножества, в каждом из которых все комнаты соединены между собой путями (connected components). Изначально каждая комната считается запертой от всех остальных, и количество подмножеств равно количеству комнат. Теперь возьмем список всех стен между комнатами, и выберем какую-нибудь случайную его пермутацию. Это даст нам случайный порядок выбора стен; идя по этому порядку, мы будем уничтожать стены одну за другой и объединять подмножества комнат по обе стороны стены, но только в том случае, если удаление стены не соединит две комнаты, которые и так уже считаются соединененными - в таком случае мы эту стену оставляем и переходим к следующей. И так до тех пор, пока не сможем продолжать, все оставшиеся стены нельзя будет удалить.

Второй алгоритм красивым способом обходится очень малыми затратами на память. Он строит лабиринт строка за строкой сверху вниз, и всякий раз хранит только O(N) данных, где N - ширина лабиринта, а все остальное забывает. Он хранит следующее: информацию о том, какие из комнат в текущей строке, которую мы сейчас строим, уже соединены между собой через построенные ранее строки лабиринта. Каждая комната в текущей строке хранит ссылки на другие связанные с ней "через верхнюю часть" комнаты слева и справа, и вместе они образуют связанный список, замкнутый по кругу. Используя эту структуру, мы решаем для каждой из комнат, ставить ли стенку справа от нее и ставить ли стенку вниз. Например, если две соседние комнаты уже соединены "через верхнюю часть", мы должны поставить между ними стенку, чтобы не допустить циклического маршрута; а если не соединены, мы выбираем, что делать, бросая монету. Удобно тут то, что решая, мы одновременно подправляем нашу структуру данных так, что когда мы закончим строить эту строку, она будет описывать правильную информацию уже для следующей строки.

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

В первоначальном тексте программы был баг, на нахождение которого ушло немного времени. В Lua у переменных нет типов, как и во многих других схожих языках, типы есть у значений, и любая переменная может хранить значение любого типа. Кроме того, числа переводятся в строки и наоборот в подходящих контекстах, как в том же Perl; но в отличие от Perl нет такого перевода в операторах сравнения. То есть, например, "4"+5 == 9, но "4" == 4 дает false. Это (для меня) оказалось очень неинтуитивным поведением. Программа читает значения ширины и высоты лабиринта в пвременные width и height, куда они приходят из командной строки и являются строками. При этом нет никакой проблемы, скажем, сделать цикл for j = 1, height, 1 (от 1 до height прибавляя 1 на каждом шаге), т.е. height авто-переводится в число и цикл работает правильно; но если внутри цикла вы захотите проверить, что находитесь в последнем его прогоне, то if j == height будет ошибкой - условие никогда не выполнится, потому что сравниваются число и строка и нет авто-перевода. Это, по-моему, очень неинтуитивно. В Perl сравнение if (4 == "4") проходит. В Lua, чтобы правильно заработало, нужно сравнивать с tonumber(height) или height+0 (или сначала перевести height в число, ясно).

Мой баг был основан на этом обстоятельстве, но еще менее очевиден. Массив line в программе хранит для комнаты номер i ссылки на соединенные с ней "через верхнюю часть" комнаты слева и справа line[i].left и line[i].right. Для того, чтобы не надо было делать отдельный случай для самой правой комнаты (у нее всегда есть правая стенка), я создаю псевдо-комнату номер width+1 и настраиваю ее левую ссылку на width (тогда алгоритм не будет пытаться убрать там стенку). Проблема в том, что width, опять-таки, строка... но, конечно, как и подобает динамическому языку с duck typing, он записывает строку вместо числа, ничего не замечая, и только позже в программе ни с того ни с сего этот мой граничный случай не работает. Я вставляю отладочные print'ы и вижу, что он сравнивает 4 с 4 и говорит, что они не равны... я начинаю подозревать, что кто-то тут сошел с ума. Потом еще немного добавил отладочной мишуры, подумал, и догадался. Мне кажется, что тут дело не только в том, что то, как это делает Perl, мне привычнее, но и в том, что это объективно логичнее. Вот программа и пример лабиринта, который она построила:

-- generate a maze. run with 'lua maze.lua 20 20' or other values for
-- width and height. algorithm from http://homepages.cwi.nl/~tromp/maze.html
-- see also http://www-static.cc.gatech.edu/~shivers/mazes.html for more
-- on maze generation.

-- the algorithm keeps track of which cells in the current horizonal
-- line of the maze are connected to others through the part of the
-- maze already output. line[i] participates, through its left and right
-- fields, in a double-linked ordered list defining its connected component.
line = {}
math.randomseed(os.time())
width, height = arg[1], arg[2]    -- from command line
for i = 1, width, 1 do
 io.write "._"                    -- write the top line
 line[i] = {left = i, right = i } -- init the linked lists
end
print "." -- close the top line
line[width+1] = {left = tonumber(width)} -- secure a border case behavior

for j = 1, height, 1 do
  io.write "|" -- left wall
  for i = 1, width, 1 do
    right, down = "|", " " -- defaults, no change to the list structure
    if line[i+1].left ~= i then
      -- consider skipping a wall here, as that won't make a cycle
      if (j == tonumber(height) and line[i].left == i) or
         math.random() < 0.5 then
        right = "."
        -- join the lists of i and i+1
        -- the combined list will be circularly ordered; that's not true
        -- for such lists in general, but follows here from
        -- nontrivial properties of the two lists deriving from their
        -- meaning (they can't "interleave")
        line[line[i+1].left].right = line[i].right
        line[line[i].right].left = line[i+1].left
        line[i].right, line[i+1].left = i+1, i
      end
    end
    if j == tonumber(height) -- last line
       or (line[i].left ~= i and math.random() < 0.5) then
      down = "_"
      -- tear this cell out of its list
      line[line[i].left].right = line[i].right
      line[line[i].right].left = line[i].left
      line[i].left, line[i].right = i, i
    end
    io.write(down, right)
  end
  io.write "\n"
end

$ lua maze.lua 20 20

._._._._._._._._._._._._._._._._._._._._.
| | | | . |_. |_._. | | . . . ._._| . | |
| . | ._|_._. | ._. ._| |_| |_. . |_| | |
|_| . ._|_. |_._|_. . |_|_._. | |_|_. | |
| |_| | | ._._| |_. |_| . ._|_| | | ._._|
|_. ._. | . ._| |_._._|_| | ._| . . | | |
| | |_. ._|_._| |_. | |_. | | |_| | . . |
| |_| . ._|_._._. | |_._. ._| | |_| | | |
| . ._| . . ._| | ._. ._. ._| | | | | |_|
|_|_|_. | | | ._. | |_|_. ._. | . . | | |
| | | . |_| ._| . ._| | |_| |_| | | | . |
| |_. |_| ._._| |_. ._| | | | . |_|_| |_|
| | . ._|_|_. | | ._| | |_. | | | . . ._|
| |_|_._| | | | |_. |_. |_. | | | | |_._|
| | | |_. . | |_|_. |_. | |_. | |_| . | |
| | | . | | . ._| . | |_. | |_|_._|_| . |
| ._| |_._|_| . . | |_. . . ._| . | | | |
|_._. | | | ._|_|_| | |_|_|_._._|_. | |_|
| | | |_._._| | | |_. ._| ._| . ._. | | |
|_. | | ._._| . . | | ._|_. | | |_. | | |
|_._._._|_._._|_|_._._._._._._|_._|_._._|

Comments

[oxfv.livejournal.com]

А что мешает тебе перевести width и height в целые в самом начале, в первой их инициализации?

[avva.livejournal.com]

Что мешало изначально или что мешало после того, как нашел баг?

Изначально я не хотел, потому что знал, что Lua автопереводит и не хотел об этом задумываться (как не задумывался бы в Перле).

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

[oxfv.livejournal.com]

Поучительно, конечно, но было бы вполне понятно, если бы сразу после присваивания width и height шло бы присваивание типа iheight=tonumber(height) или как-то так, и в дальнейшем бы использовался лишь iheight. Вообще, как же это так, что язык имеет такой дефект? Разве это не делает его непригодным?

[neverlichka.livejournal.com]

На мой взгляд, именно в данном случае для наглядности стоит переводить строку в число как раз именно там, где это непосредственно требуется, что позволяет показать возможность языка оперировать строками как численными типами, пусть и не универсальную)

[madfire.livejournal.com]

Я думаю, что не делает. Авва же смог его использовать, после небольших корректив на "особенности".

На Lua пишут довольно-таки много скриптинга в современных игрушках.

[avva.livejournal.com]

Мне многое в нем понравилось. Я не хотел создать впечатление, что вот, я его ругаю. Просто любопытный момент.

[avva.livejournal.com]

Ну как тебе сказать... это не то чтобы дефект, но я вижу в этом определенное непостоянство философии. Но, наверное, люди, которые им часто пользуются, привыкают. Суть в том, что отсутствие автоматического перевода при сравнениях означает, что нужно держать в уме, какой именно тип у тебя сидит в переменной, число или строка. Само по себе это не дефект - в большинстве динамических языков это нужно делать (ну тот же Lisp). Но если уж нужно это держать в уме, то предоставлять авто-перевод в такой основной конструкции языка, как цикл for - "нечестно", путает. Мне кажется, что простым отказом от авто-перевода внутри цикла for язык был бы улучшен - именно этот пример авто-перевода меня так запутал; авто-перевод при арифметических операциях или соединении строк не так страшен, там как бы ощущается, что это косметическое удобство, в любом случае.

[ltwood.livejournal.com]

я вижу в этом определенное непостоянство философии

Думаю, что это утверждение не очень верно. Дело в том, что в Lua (в стандартной сборке) нет целых чисел и все числа представляются вещественными числами. В случае арифметических операций, в которых смешаны строки и числа, особой опсности нет — после преобразования получится тот же ответ, что и при явном преобразовании или при непосредственной записи константы в исходнике. (Раз уж число представлено строкой, то его строковая запись — это все, что мы про него знаем.) Уже при обратном преобразовании (неявное преобразование числа в строку при конкатенации) чаще всего получается не то, чего ожидает пользователь, но это легко заметить и использовать явное форматирование (string.format()). В случае же сравнения автоматическое преобразование сделает это сравнение крайне неустойчивой операцией. Для вещественного числа строка будет содержать приближенное представление (наши знания о числе), а другой операнд будет содержать точное значение числа со всеми накопленными погрешностями. В результате очень во многих случаях результаты сравнения будут непредсказуемыми.

Вот совсем простой пример:

s = 0.1
s = s + 0.1
s = s + 0.1
print( s == 0.3 )

[ringm.livejournal.com]

У второго алгоритма довольно некрасивое распределение, что очевидно при взгляде на картинку - вертикальных стенок гораздо больше, чем горизонтальных. Первый - самое обыкновенное построение случайного spanning tree. На практике я бы пользовался первым.

[ex-ex-annut.livejournal.com]

легко видеть, что прим также легко портируется на задачу генерации лабиринтов
также если мы можем допустить того, что с маленькой вероятностью все же компоненты будут связаны, то мы можем решить задачу с памьятю не ширина лабиринта (корень числа комната), а логарифм числа комната

[avva.livejournal.com]

Распределение можно регулировать, меняя шансы создавать стенки (в тексте программы - две постоянных 0.5). Если заметно повысить шанс создать стенку вниз, длинные вертикальные полосы становятся редкостью. Но на практике я бы тоже пользовался первым.

[moon-aka-sun.livejournal.com]

Do you speak Python? With tk? Некогда я тоже увлекался лабиринтами и сделал такую демонстрашку (http://moon.aka.sun.googlepages.com/PyMaze.zip). (Там и ссылок внутри есть.) Можно часами сидеть и наблюдать, как он строит :)

[oxfv.livejournal.com]

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

[moon-aka-sun.livejournal.com]

Красота!

[avva.livejournal.com]

Официально я Питон не знаю, но, конечно, достаточно простые программы могу прочитать. Спасибо, красиво :)

[zavr.livejournal.com]

Есть простой алгоритм как моделировать loop erased random walk, если я не путаю, то пути в spanning tree устроены как LERW. На этом построен алгоритм Вилсона, который дает случайное (с равномерным распределением) spanning tree

[flaass.livejournal.com]

Что-то не то со вторым алгоритмом. внизу получилось несколько маленьких кусочков, полностью отгороженных (один слева, один справа, один посередке). И не думаю, что это будет легко исправить.

[avva.livejournal.com]

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

[flaass.livejournal.com]

Ага, исправить, чтоб результат был заявленным, легко. Но распределение полученных лабиринтов все равно сильно неравномерное. Уже на 2х2 легко видно: их всего 4.
А вот что рассказал bakhtin, очень интересно. Попробую понять, почему там получается равномерное.

[bakhtin.livejournal.com]

вообще-то очень хороший алгоритм построения случайных остовных деревьев с равномерным распределением на них принадлежит David'у Wilson'у: http://research.microsoft.com/~dbwilson/

Если не ошибаюсь, вот тут: http://research.microsoft.com/~dbwilson/ja/

[bakhtin.livejournal.com]

да, вот на с.28:

RandomTreeWithRoot() (see Figure
8) maintains a ``current tree'', which initially consists of just the root. While there remain
vertices not in the tree, the algorithm does a random walk from one such vertex, erasing
cycles as they are created, until the walk encounters the current tree. Then the cycle-erased
trajectory gets added to the current tree.

Всё!

[avva.livejournal.com]

Красивый алгоритм!

Напишу сейчас и для него программку, спасибо :)

[zavr.livejournal.com]

Самое красивое, что он дает равномерное распределение

[avva.livejournal.com]

Написал! Работает на ура.

._._._._._._._._._._._._._._._._._._._._.
| | |_. |_. ._|_. | . |_. |_. ._. |_. . |
|_._._. |_. ._| |_._| ._| |_. | ._._._| |
| ._| |_. | ._| . |_. | ._._|_| . ._| | |
|_._._. ._| | | |_| | ._|_. | ._|_|_. . |
| ._|_. |_. | ._. | |_._. |_. | | . | |_|
|_. | |_. | ._| |_| ._|_. . . |_._| |_. |
| ._. | . ._| | ._. |_. |_| |_| ._| ._._|
| ._| |_|_. | . | |_| | ._. |_. |_. ._. |
|_._|_. ._._._| . | . | ._| ._| | | . | |
| ._._| ._| |_._| . |_|_| |_._. ._|_| |_|
| | | ._. . | ._|_| ._. ._._| | ._._| ._|
| | |_| . |_| | |_._| ._. ._. |_. | |_. |
|_. . ._|_|_. . |_. ._. | | | | . |_. . |
|_._| | ._. |_| |_._._|_| |_. |_|_|_. |_|
|_. ._._._|_._._| . ._| |_|_. ._._. ._. |
|_._._._._| | | . |_|_. ._|_._._. |_._| |
| . ._| | . ._| |_. ._. ._._. | |_|_. | |
| | ._|_._| . . | | | |_| ._._. ._. ._| |
|_|_. . . |_| |_. |_|_. ._| | |_|_._._| |
|_._._|_|_._._|_._|_._._._._._._._._._._|

[bakhtin.livejournal.com]

Поздравляю!

[zavr.livejournal.com]

Вообще про такие модели есть большая наука. Про конкретные алгоритмы нало смтреть статьи Tom Kenned, а про теорию у Schramm'а, Sheffild'а, Werner'а и Lawler'а (ну и у многих других)

[bakhtin.livejournal.com]

Хе-хе. Раз уж Вы всех выдающихся SLE-шников мне выдали, что ж вашего шведского Стаса Смирнова забыли? Или раз он переехал в Швейцарию, кажется, то вычёркиваем что ли?

[zavr.livejournal.com]

Я его, конечно, не забыл. Просто он про алгоритмы и моделирование ничего не написал. А все остальные (из вышеперечистенных)приложили к этому руки.

P.S. У меня такое впечатление, что мы с Вами где-то встречались

[bakhtin.livejournal.com]

в связи с чем возникает у меня такой вопрос: а не случалось ли нам вместе есть суши в Торонто?

[zavr.livejournal.com]

Скорее всего, да

[ex-ex-annut.livejournal.com]

Kennedy

[moon-aka-sun.livejournal.com]

Кстати, странно, что расцвечиватель исходника комментарии не перекрашивает. Уж, казалось бы, перево-наперво и прежде всего.

[avva.livejournal.com]

Намаялся я с этим раскрашивателем... раньше никогда большие куски кода не постил, поэтому ничего про них не знал. Несколько найденных гуглем не понравились. SCiTE выдает текст с CSS-ом, который ЖЖ не пропускает (style-таги не пропускает, CSS в атрибутах HTML-тагов пропускает). vim выдает подходящий HTML, но я-то им пользуюсь в режиме белое на черном, поэтому на белом фоне страницы выходит ужас. В конце концов то, что запостил - та из цветных схем vim, которая выглядела наименее ужасно - были другие, которые расцвечивали комменты, но выглядели хуже. Конечно, я мог свои цвета определить, но я ненавижу подбирать цвета и не хотел этим заниматься.

[moon-aka-sun.livejournal.com]

Да, выхлоп SciTE приходится вручную переделывать :)

[nine_k]

Что мешает постить исходники на чёрном фоне?
Вы ведь (как и я) наверняка не от балды чёрный фон выбрали, а потому, что он удобнее для исходников :)

[avva.livejournal.com]

Как-то странно смотрелось бы посреди остального белофонного текста, мне кажется. Но может быть.

[migmit.livejournal.com]

Emacs неплохо раскрашивает на белом фоне. Для примера:

 step       step (( {code   c, env  e})stackHeadstack)    ( {code  c, env  stackHeade})stack
 step (( {code   c1 c2, env  e})stack)    ( {code  c1, env  e})( {code  c2, env  e})stack
 step (( {code   0, env  c})stack)    cstack
 step (( {code   n, env  e})stack)    ( {code   (n1), env  e})stack
 step   

 initStep    
 initStep expr  [ {code  expr, env  }]

[avva.livejournal.com]

Спасибо! Действительно неплохо. А какая команда записывает раскрашенный код в HTML?

Re: Reply to your comment...

[migmit.livejournal.com]

M-x htmlize-buffer. Правда, необходим пакет htmlize.el - где-то на просторах интернета бродит.

[nine_k]

>"4"+5 == 9
Вот это -- действительно неинтуитивно 8-) Мне бинарные операторы такого рода всегда казались лево-ассоциативными, т.е. тип результата должен быть таким же, как у первого операнда. Потому "4"+5 == "45", а 4+"5" == 9.

[avva.livejournal.com]

Это если + работает как соединение строк; в Lua для этого есть другой оператор, .. (двоеточие), а + работает только с числами. В Перле похожим образом для строк используется точка.

[kamarado.livejournal.com]

Да уж, с правилом левой руки, этак часами по такому ходить можно %)

[doppeltes.livejournal.com]

зато выйдешь 100%! :)