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