...

пятница, 6 февраля 2015 г.

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

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

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


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


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



Начало




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

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


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

Минусы: случайность всего и вся.


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


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


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




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

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

1) «Стены» (черные блоки), которые и формируют эти причудливые узоры лабиринта;

2) «Проходы» (белые блоки) — как раз то, по чему можно передвигаться.


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



  1. Начинаем с таблицы (графа), все ячейки (вершины) которой принадлежат множеству «Стены»;

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

  3. Берем «Специальный Перечень Стен».


    1. Если, он не пуст, то выбираем из него случайную стену

      1) Если ячейка на противоположной от стенки стороне принадлежит к множеству «Проходы», то удаляем эту стенку из «СПС» (специального перечня стен):

      image


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



      • Убираем эту стену из множества «Стены»;

      • Добавляем эту стену в множество «Проходы»;

      • Убираем ячейку на противоположной стороне из множества «Стены»;

      • Добавляем ячейку на противоположной стороне в множество «Проходы»;

      • Добавляем соседние с ячейкой на противоположной стороне стены в «Специальный Перечень Стен»;

      • Возвращаемся к пункту 3.




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




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

    Удачи!


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


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




Recommended article: Chomsky: We Are All – Fill in the Blank.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.


Комментариев нет:

Отправить комментарий