Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Categories:

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

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

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

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


Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 43 comments