На уходящей неделе мне попалась симпатичная, хоть и не новая мини‑серия статей на Дзен‑канале @zdgzdgzdg про процедурную генерацию лабиринта методом «коллапса волновой функции». Пока я читал эти статьи и знакомился с кодом, меня осенило: ведь это же вычисления в комонаде, погружённые в монаду! Я не издеваюсь, действительно, речь идёт о композиции двух паттернов функционального программирования: комонады Zipper, превращающей локальные правила в глобальное состояние, и монады Random, позволяющей генерировать случайные объекты.

И вот, в качестве баловства на выходных, я решил реализовать этот «квантовый» алгоритм генерации лабиринтов на Haskell, используя и комонады и монады, и вообще, ни в чëм себе не отказывая. И хотя язык программирования Haskell нужен не только для извращений, но именно для них он подходит идеально!

Проанализируем поиск кратчайшего пути в некотором лабиринте. Из каждой клетки этого лабиринта можно ходить в соседние по горизонтали, по вертикали и по диагонали. Стоимость прохода по горизонтали или по вертикали равна единице. Стоимость прохода по диагонали равна корню квадратному из двух.

При поиске будем использовать только целочисленный тип данных и не допускать никаких погрешностей в вычислениях.

Для поиска кратчайшего пути будет использоваться алгоритм Дейкстры.

Классификация лабиринтов

Первое упоминание термина “maze” датируется тринадцатым веком, а “labyrinth” — к четырнадцатым. Сама концепция лабиринтов восходит к эпохе греческого мифологического героя Тесея — древнего героя, успешно прошедшего Кносский лабиринт и сразившего Минотавра.

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

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

Привет, Хабр!

В этой публикации я расскажу о статье автора Jinmo Kim: "Maze Terrain Authoring System in Immersive Virtual Reality for New Visual Realism". Она была опубликована 4.04.2019. Полный текст статьи можно посмотреть здесь.

Краткое описание системы

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

Предложенная система генерации ландшафта лабиринта состоит из трех основных функций:

• функция автоматической генерации сетки лабиринта различных размеров и узоров, реализованная с помощью классического алгоритма генерации лабиринта;
• функция генерации кругового лабиринта;
• функция преобразования лабиринта из ручного эскиза в 3D объект с помощью алгоритма обработки изображений.

С помощью предложенной системы, состоящей из этих трех функций, можно эффективно создавать различные лабиринты, от однородных до нерегулярных. Эта разработка позволит генерировать лабиринтные ландшафты различных концепций напрямую из расчетов, сделанных через эту же систему. Кроме того, в этой работе проведен анализ улучшения эффекта присутствия и погружения в виртуальную реальность, т.е. визуального реализма. Также, в этой работе был проведен анализ пригодности предложенной авторской системы с помощью опроса.

Привет, Хабр!

Сегодня я хотел бы рассказать о генерации идеального лабиринта - алгоритмом Эллера. Статья подойдёт всем любителям алгоритмов.

Примечание: этот туториал написан для Unity 2017.1.0 и предназначен для опытных пользователей. Подразумевается, что вы уже хорошо знакомы с программирование игр в Unity.

• Процедурно генерировать уровни на примере создания игры про бег в лабиринте.
• Генерировать данные лабиринтов.
• Использовать данные лабиринтов для построения меша.

Приступаем к работе

Учимся использовать и реализовывать на Python алгоритм поиска в ширину (BFS) для решения реальных задач.

Давайте поговорим о популярном алгоритме, который называется «Поиск в ширину» (BFS). Затем реализуем этот алгоритм, чтобы найти решение для реальной задачи: как выбраться из лабиринта.

Алгоритмы поиска применяются для решения таких задач, которые можно смоделировать как графы. Каждый узел графа – это экземпляр задачи. Каждый поисковый алгоритм начинается с узла (исходный экземпляр – состояние) и наращивает вслед за этим узлом новые (то есть, новые экземпляры задачи), решая задачу допустимыми способами. Этот процесс останавливается, как только алгоритм находит решение (успех – конечное состояние) или не может создать ни одного нового узла (провал). Среди самых популярных алгоритмов поиска – поиск в глубину (DFS), поиск в ширину (BFS), жадный алгоритм, поиск по критерию стоимости (UCS), A*-поиск, т.д. В этой статье речь пойдет о поиске в ширину.

Возможно, вы слышали про Micromouse — конкурс для маленьких роботов-мышей, которые должны быстрее всех найти путь в центр лабиринта. Лабиринт не очень большой, его размер 32х32 квадрата (раньше было 16x16) с длиной грани 9 см. Высота стенок каждой ячейки 2,5 см, толщина — 0,6 см.

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

Квантовые алгоритмы могут находить выход из лабиринтов экспоненциально быстрее, чем классические, за счет забывания путей, по которым они шли. Новый результат предполагает, что компромисс может быть неизбежен.  

Представьте, что вы посещаете лабиринт с друзьями. Вы вышли из выхода вскоре после входа и ждёте несколько часов, прежде чем появятся ваши друзья. Естественно, они спрашивают о пути, по которому вы шли — вы ведь можете проследить свои шаги и показать им путь, верно?

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

Исследователи давно задавались вопросом, неизбежен ли этот компромисс. Неужели невозможно быстро найти выход, не забыв дорогу?

Алгоритм Эллера - это алгоритм генерации идеального лабиринта. Лабиринт считается идеальным, если у него нет замкнутых и зацикленных участков, и от любой точки до любой другой точки существует ровно один путь.