Простенький генератор идеальных прямоугольных лабиринтов

Черпая вдохновение для создания игры для получения зачета на моем любимом Мат-Мехе, наткнулся на статейку на Хабре про алгоритм Эйлера генерации лабиринтов (http://habrahabr.ru/post/176671). После ее прочтения идея появилась: буду писать ходилку по лабиринту, а точнее ездилку.



После пары часов раздумий и попыток я понял, что сам алгоритм Эйлера не совсем мне подходит. Но! Была там строчка

алгоритм очень быстр и использует память эффективнее, чем другие популярные алгоритмы (такие как Prim и Kruskal)

о которой мне пришлось задуматься.

Нужен был идеальный прямоугольный лабиринт (без изолированных зон и зацикливаний), а алгоритм Прима и Краскала, как я всегда думал, строил в графе остов (вес значения не для меня не имел). А как остов стал лабиринтом? Оказалось, что это почти одно и то же.

Решил строить остов в графе-сетке и выдавать это за лабиринт. Причем для этого использовать даже не Прима и Краскала, а просто строить рандомный остов. В общем делать так:
1) образовать прямоугольник заданной ширины и высоты.
2) засунуть хранить его в подобии очереди.
3) вытаскивать рандомом из «подобия очереди» вершину и рандомом к ней прикреплять вершину из вне «подобия очереди».
4) повторять 3, пока в очереди не окажутся все вершины графа-сетки.
5) сделать из того, что получилось лабиринт.


Как оказалось, алгоритм действительно получился не быстрый. Например лабиринт 60x60 генерируется ~30 секунд, что, в принципе, можно списать на загрузку игры. Но самое главное, что получилось то, что нужно!

30х10:



20x20:



Скрипт (перфекционистам не смотреть): pastie.org/8527937#11
Это моя первая статья на Хабре, потому буду благодарен обоснованным обжалованиям и предложениям.