Надпись в лабиринте: четыре алгоритма и своё видео

Где спрятана надпись

Лабиринт занимает всё прямоугольное поле, включая промежутки между буквами. Отдельно хранится маска надписи: для каждой клетки известно, попадает ли она внутрь символа. Когда поиск выбирает клетку для обработки, след внутри буквы получается ярким, а снаружи — приглушённым. До поиска маска не выделена, поэтому увидеть готовое слово среди стен сложно. Алгоритмы не знают о тексте: он влияет на раскраску, а не на доступные проходы.

Кадры опубликованного ролика с маской логотипа. В конструкторе надпись строится выбранным шрифтом.

Попробовать свой текст в конструкторе →

Один лабиринт, четыре правила

У поисков общие стены, вход и выход. Отличается выбор следующей клетки. BFS идёт слоями расстояния от входа. DFS углубляется по одной ветке и возвращается из тупиков. Жадный поиск среди найденных, но ещё не обработанных клеток выбирает минимальную оценку h до выхода. A* учитывает и лучшее найденное расстояние от входа g, и оставшуюся оценку h: f = g + h. Здесь можно двигаться в четырёх направлениях, каждый переход стоит один шаг, а h — манхэттенское расстояние, то есть сумма разностей координат.

Как цвета встречаются на одном поле

Все выбранные алгоритмы рисуют следы в одном лабиринте. На общих клетках цвета смешиваются, на разных ветках остаются различимыми. У BFS вместе показываются независимые клетки одного слоя. У A* — готовые независимые клетки с одинаковой f, идущие подряд в трассе. Клетка ждёт, пока будет обработан её родитель в дереве поиска. Это способ воспроизведения рассчитанных трасс, а не параллельное исполнение поиска на нескольких ядрах.

Что получилось в трёхминутном ролике

Для ролика использовано поле 192 × 108: 20 736 клеток, seed 20261032 и маска букв логотипа. Выход выбран последним в полном обходе BFS — в одной из наиболее удалённых от входа клеток. Поэтому BFS успевает посетить всё поле и полностью проявить надпись. Другие поиски останавливаются, когда находят этот же выход. В таблице ниже длина пути — число переходов, а процент надписи — доля посещённых клеток именно маски логотипа.

С другой надписью может измениться доля её закрашенных клеток. С другим seed или размером поля могут измениться и маршруты.

Что эти результаты говорят об алгоритмах

BFS и A* нашли путь длиной 7 731 переход. Жадный поиск в этом примере тоже попал на кратчайший маршрут, но его правило не даёт такой гарантии в общем случае. DFS вернул более длинный путь. A* обработал почти столько же клеток, сколько BFS: оценка по координатам мало помогла в этих извилистых проходах. Это результаты выбранного сценария, а не случайный бенчмарк. У поисков общий темп обработки клеток, а длительность ролика задаётся отдельно — по ней нельзя сравнивать время работы на процессоре.

Как сделать лабиринт со своей надписью

В конструкторе можно ввести до 60 символов в одну, две или три строки. Выберите шрифт, формат кадра и детализацию, затем один или несколько алгоритмов и нажмите «Построить лабиринт». Зерно, или seed, задаёт повторяемый вариант проходов. При одинаковых размере поля и seed смена текста или шрифта меняет только маску. Другой формат кадра или детализация меняют сетку, а значит, и лабиринт.

1. Введите надпись и выберите шрифт: Geist, Geist Mono, Georgia или Verdana.
2. Выберите 16:9, 9:16 или 1:1, детализацию и seed. Отметьте нужные алгоритмы.
3. Постройте лабиринт и проверьте начало, середину и конец на шкале времени.
4. Выберите музыку и громкость, если нужен звук. Нажмите «Сохранить MP4» и дождитесь готового файла.

Как сохранить видео с музыкой

Проверьте анимацию в предпросмотре: её можно поставить на паузу и перемотать в обе стороны. Затем выберите длительность от 5 секунд до 20 минут. При желании добавьте свой аудиофайл до 100 МБ, прослушайте его и настройте громкость. При записи дорожка начинается сначала и повторяется, если заканчивается раньше ролика. В начале громкость постепенно нарастает, а в конце снижается. Без выбранного файла видео будет без звука. MP4 сохраняется в горизонтальном, вертикальном или квадратном формате; запись идёт примерно в реальном времени, поэтому вкладку нужно оставить видимой до завершения.

С чего начать сравнение

Для первого опыта оставьте одну строку, среднюю детализацию и все четыре поиска. Затем меняйте по одному параметру: только алгоритмы, только шрифт или только seed. Если хотите гарантированно проявить всю надпись, сохраните BFS среди выбранных алгоритмов. Без него непосещённые части могут остаться тёмными: дополнительной декоративной заливки после финиша нет. Для проверки экспорта сначала запишите короткую версию. Музыкальный файл используется в браузере и не отправляется на сервер; готовый ролик остаётся на устройстве.