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