Главная

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

2015-02-06 в 12:31, admin, рубрики: 30 строк js, javascript, алгоритм Прима, Алгоритмы, Лабиринт, ненормальное программирование, метки: лабиринт

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

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

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

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

Начало

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

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

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

Сказано — сделано!.

Поплакав над своим решением, я обратился за помощью к экспертам. К счастью, их советов оказалось Н Е М А Л О.

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

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

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

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

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