[Из песочницы] Случайный лабиринт на JS в сами знаете сколько строк
Начитавшись статей про [все что угодно] на JavaScript в 30 строк кода, я подумал: чем я хуже? Не найдя в перечне своих недостатков пункт «написание плохого кода», решил сделать что-нибудь интересное.Лабиринты всегда веяли в мою сторону некоторой магией и загадками, поэтому поиск «чего-нибудь интересного» закончился достаточно быстро. К сожалению, создание игры затянулось на долгие часы экспериментов над консолью и моими нервами.
Изначально, осознавая размеры праведного гнева адептов непорочного программирования, я не планировал публиковать свои труды, но после того, как игра понравилась коту, паре друзей и моему самолюбию — решил написать статью (благо в нее можно внедрить теоретическую часть).
Для сторонников принципа «меньше знаешь — крепче спишь» предлагается cсылка на JSFiddle (управление стрелочками).
НачалоЧто самое сложное в создании подобной игры? Правильно, генерация самого лабиринта. Именно поэтому сперва я начал не с того, чтобы рассмотреть существующие алгоритмы и выбрать оптимальный, а с создания своего собственного колеса с преферансом и вдовствующими аристократками самых строгих правил.Моя идея была проста, как снег Грегори Галлоуэя: написать рекурсивную функцию, которая бы, начиная с точки [0:0], бегала бы по лабиринту и «выедала» себе путь до тех пор, пока не вылезет наружу. Как только она эта сделает — мы случайным образом выбираем N ячеек из пройденного ей пути и запускаем из этих ячеек эту же самую функцию.
Плюсы: возможность регулировать сложность лабиринта, колибрируя значение N.Минусы: случайность всего и вся.
Сказано — сделано!.
Поплакав над своим решением, я обратился за помощью к экспертам. К счастью, их советов оказалось Н Е М А Л О.
Рандомизированный алгоритм Прима Изучив эти алгоритмы, я остановился на рандомизированном алгоритме Прима (на самом деле, немного переделав и его), посчитав его реализацию самой лаконичной.Итак, сначала немного о лабиринте. Лабиринт — это таблица (конечно, правильней будет назвать его графом), ячейки (вершины) которой должны принадлежать одному из 2 множеств:1) «Стены» (черные блоки), которые и формируют эти причудливые узоры лабиринта;2) «Проходы» (белые блоки) — как раз то, по чему можно передвигаться.
Алгоритм состоит в следующем:
Начинаем с таблицы (графа), все ячейки (вершины) которой принадлежат множеству «Стены»;
Выбираем ячейку. Убираем ее из множества «Стены» и добавлем в множество «Проходы». Все соседствующие с ней стены (по вертикали и горизонтали) добавляем в «Специальный Перечень Стен, утвержденный пленарным заседанием госдумы»;
Берем «Специальный Перечень Стен».Если, он не пуст, то выбираем из него случайную стену1) Если ячейка на противоположной от стенки стороне принадлежит к множеству «Проходы», то удаляем эту стенку из «СПС» (специального перечня стен): 
2) Если ячейка на противоположной стороне принадлежит множеству «Стены», то:
Убираем эту стену из множества «Стены»; Добавляем эту стену в множество «Проходы»; Убираем ячейку на противоположной стороне из множества «Стены»; Добавляем ячейку на противоположной стороне в множество «Проходы»; Добавляем соседние с ячейкой на противоположной стороне стены в «Специальный Перечень Стен»; Возвращаемся к пункту 3. Если он пуст, то генерация лабиринта завершена. (управление стрелочками).Удачи!
P.S. Если при прохождени у вас ничего не выскочило (на экране), значит по каким либо причинам картинка не подгрузилась.
P.P. S Код на JSFiddle слегка изменен (сжат) для того, чтобы уместился в 40 строк (не бейте!).
