Случайный лабиринт на JS в сами знаете сколько строк

Начитавшись статей про [все что угодно] на JavaScript в 30 строк кода, я подумал: чем я хуже? Не найдя в перечне своих недостатков пункт «написание плохого кода», решил сделать что-нибудь интересное.

Лабиринты всегда веяли в мою сторону некоторой магией и загадками, поэтому поиск «чего-нибудь интересного» закончился достаточно быстро. К сожалению, создание игры затянулось на долгие часы экспериментов над консолью и моими нервами.

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

Для сторонников принципа «меньше знаешь — крепче спишь» предлагается cсылка ^[1] на JSFiddle (управление стрелочками).

Начало

Что самое сложное в создании подобной игры? Правильно, генерация самого лабиринта. Именно поэтому сперва я начал не с того, чтобы рассмотреть существующие алгоритмы и выбрать оптимальный, а с создания своего собственного колеса с преферансом и вдовствующими аристократками самых строгих правил.

Моя идея была проста, как снег Грегори Галлоуэя: написать рекурсивную функцию, которая бы, начиная с точки [0:0], бегала бы по лабиринту и «выедала» себе путь до тех пор, пока не вылезет наружу. Как только она эта сделает — мы случайным образом выбираем N ячеек из пройденного ей пути и запускаем из этих ячеек эту же самую функцию.

Плюсы: возможность регулировать сложность лабиринта, колибрируя значение N.
Минусы: случайность всего и вся.

Сказано — сделано! ^[2].

Поплакав над своим решением, я обратился за помощью к экспертам. К счастью, их советов оказалось Н ^[3] Е ^[4] М ^[5] А ^[6] Л ^[7] О ^[8].

Рандомизированный алгоритм Прима

Изучив эти алгоритмы, я остановился на рандомизированном алгоритме Прима (на самом деле, немного переделав и его), посчитав его реализацию самой лаконичной.

Итак, сначала немного о лабиринте. Лабиринт — это таблица (конечно, правильней будет назвать его графом), ячейки (вершины) которой должны принадлежать одному из 2 множеств:
1) «Стены» (черные блоки), которые и формируют эти причудливые узоры лабиринта;
2) «Проходы» (белые блоки) — как раз то, по чему можно передвигаться.

Алгоритм состоит в следующем:

1. Начинаем с таблицы (графа), все ячейки (вершины) которой принадлежат множеству «Стены»;
2. Выбираем ячейку. Убираем ее из множества «Стены» и добавлем в множество «Проходы». Все соседствующие с ней стены (по вертикали и горизонтали) добавляем в «Специальный Перечень Стен, утвержденный пленарным заседанием госдумы»;
3. Берем «Специальный Перечень Стен».
   1. Если, он не пуст, то выбираем из него случайную стену
      1) Если ячейка на противоположной от стенки стороне принадлежит к множеству «Проходы», то удаляем эту стенку из «СПС» (специального перечня стен):

      

      2) Если ячейка на противоположной стороне принадлежит множеству «Стены», то:

      • Убираем эту стену из множества «Стены»;
      • Добавляем эту стену в множество «Проходы»;
      • Убираем ячейку на противоположной стороне из множества «Стены»;
      • Добавляем ячейку на противоположной стороне в множество «Проходы»;
      • Добавляем соседние с ячейкой на противоположной стороне стены в «Специальный Перечень Стен»;
      • Возвращаемся к пункту 3.

   2. Если он пуст, то генерация лабиринта завершена.

(управление стрелочками).

Удачи!

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

P.P.S Код на JSFiddle слегка изменен (сжат) для того, чтобы уместился в 40 строк (не бейте!).

Автор: universome

Источник ^[9]