Лабиринты использовались в видеоиграх с момента их появления. Первой видеоигрой с процедурно генерируемым лабиринтом была Beneath Apple Manor, выпущенная в 1978 году. Лабиринт в ней генерировался методом деления на комнаты и коридоры, из-за этого лабиринт часто выглядел однообразным и предсказуемым, что портило впечатление от игры. Для того, чтобы лабиринт выглядел естественнее разработчики стали использовать различные алгоритмы на графах. В этой статье мы рассмотрим реализации генерации идеального лабиринта с помощью алгоритма Прима.
Рубрика «Лабиринт»
Создание идеального лабиринта с помощью упрощённого алгоритма Прима
2026-02-28 в 10:46, admin, рубрики: алгоритм Прима, Алгоритмы, алгоритмы и структуры данных, Лабиринт, лабиринтостроительство, ЛабиринтыГенерация лабиринтов с использованием алгоритма Recursive backtracker
2026-02-23 в 17:00, admin, рубрики: Recursive backtracker, алгоритм, визуализация, как написать, Лабиринт, рандомная генерацияВ этой статье я расскажу о том как генерировать рандомные лабиринты, используя рекурсивный алгоритм с возвратом. Этот алгоритм также может использоваться для решения других задач, которые связанны с неявными графами: судоку, комбинаторика и другие головоломки (например, задача о n ферзях).
Описание алгоритма в общих чертах:
Алгоритм Recursive backtracker - это метод систематического перебора всех возможных вариантов решения задачи, основанный на поиске в глубину (DFS).
Поэтапно, что делает алгоритм на примере графа:
-
Выбираем начальную вершину и делаем ее текущей.
Решение головоломки из университетского квеста с помощью Python
2024-08-20 в 18:25, admin, рубрики: python, головоломка, игра, квест, Лабиринт, поиск пути, Программирование
Cat Walk — одна из интересных головоломок игры Puzzle HuntЧитать полностью »
Генерация лабиринтов: алгоритм Эллера
2022-05-24 в 13:51, admin, рубрики: c++, Gamedev, алгоритм генерации, алгоритм эллера, Алгоритмы, генерация лабиринтов, Лабиринт, С++
Вступление
Как оказалось, что тема генерации лабиринтов не сильно раскрывается в русско- и англоязычном сообществе. На хабре существует одна статья Алгоритм Эллера для генерации лабиринтов. Статья, является переводом англоязычной статьиЧитать полностью »
Гениальный алгоритм создания лабиринтов в игре Entombed, который до сих пор не могут разгадать
2020-07-09 в 9:13, admin, рубрики: Алгоритмы, Блог компании RUVDS.com, Дизайн игр, игровая механика, игры, Лабиринт, логические игры, разработка игр
В 2017 двое ученых, канадец John Aycock и британка Tara Copplestone, опубликовали анализ классической игры Entombed для игровой приставки Atari 2600. Механика этой игры, выпущенной в 1982, крайне проста: археолог, управляемый игроком, должен пробраться по прокручивающимся снизу вверх катакомбам, уворачиваясь от зомби.
У Atari 2600 было всего 128 байт ОЗУ; тем не менее, кажущийся бесконечным лабиринт при каждом запуске был новым, т.е. генерировался в памяти. Как же программистам это удалось? Вот комментарий Стивена Сидли — программиста, 38 лет назад создавшего эту игру:
Основную часть генератора лабиринтов написал какой-то уволившийся торчок. Я связался с ним, чтобы выяснить, как его алгоритм работал. Он ответил, что придумал этот алгоритм, когда был вусмерть накурен и вдобавок пьян, что написал его сразу на ассемблере прежде чем вырубился, а потом даже близко не мог вспомнить, в чем его алгоритм состоял.
Система генерации ландшафта лабиринта с улучшенным визуальным реализмом [перевод статьи Jinmo Kim]
2019-06-11 в 15:27, admin, рубрики: 3d, AR и VR, алгоритм, Алгоритмы, генерация ландшафта, Дизайн игр, Лабиринт, ландшафт, перевод статьи, Программирование, разработка алгоритмов, разработка игрПривет!
В этой публикации я расскажу о статье автора Jinmo Kim: "Maze Terrain Authoring System in Immersive Virtual Reality for New Visual Realism". Она была опубликована 4.04.2019. Полный текст статьи можно посмотреть здесь.
Краткое описание системы
В статье предложена авторская система создания лабиринтных ландшафтов, с помощью которой пользователь может автоматически генерировать различные сложные узоры в простой и интуитивно понятной системе. С помощью информации о лабиринте, рассчитанной в программе, быстро и эффективно генерируется трехмерный ландшафт лабиринта.
Предложенная система генерации ландшафта лабиринта состоит из трех основных функций:
- функция автоматической генерации сетки лабиринта различных размеров и узоров, реализованная с помощью классического алгоритма генерации лабиринта;
- функция генерации кругового лабиринта;
- функция преобразования лабиринта из ручного эскиза в 3D объект с помощью алгоритма обработки изображений.
С помощью предложенной системы, состоящей из этих трех функций, можно эффективно создавать различные лабиринты, от однородных до нерегулярных. Эта разработка позволит генерировать лабиринтные ландшафты различных концепций напрямую из расчетов, сделанных через эту же систему. Кроме того, в этой работе проведен анализ улучшения эффекта присутствия и погружения в виртуальную реальность, т.е. визуального реализма. Также, в этой работе был проведен анализ пригодности предложенной авторской системы с помощью опроса.
Бегущий в лабиринте: анализ нейронной активности мозга крысы в реальном времени
2018-12-07 в 9:00, admin, рубрики: Биотехнологии, Блог компании ua-hosting.company, крысы, Лабиринт, мозг, Научно-популярное, нейробиология, нейроны, спайки, физика
Какую суперсилу вы бы выбрали: полет, невидимость или телепатию? Живым, в каком-то смысле, воплощением последнего всегда был персонаж комиксов Люди-Икс профессор Чарльз Ксавье, появившийся еще в далеком 1963 году из-под пера Стэна Ли. Но в комиксах и не такие суперсилы можно встретить. А что насчет реальности? Можно ли читать мысли другого существа? Как оказывается, теперь можно, но не так как вы себе представляете. Сегодня мы с вами будем знакомиться с исследованием, главным достижением которого является считывание электронной активности нейронов мозга подопытной крысы, бегущей по лабиринту, в реальном времени. Как ученым удалось забраться в голову крысы, что им удалось этим добиться и какие перспективы их технологии? Доклад исследователей даст нам ответы на эти и другие вопросы. Поехали.Читать полностью »
Алгоритм генерации гирлянды для новогодней головоломки
2017-12-15 в 5:49, admin, рубрики: android, Алгоритмы, Лабиринт, я пиарюсь
Чтобы занять себя как-то бессонными ночами, опять засел за написание игрушек под Android. Так как скоро новый год, то решил, что игрушка должна быть новогодней. Для меня неотъемлемой частью нового года и новогодней ёлки является гирлянда, так что решение идея пришла сама — буду делать головоломку — собери гирлянду. В процессе разработки, для меня было два интересных момента:
1. Генерация гирлянды.
2. Работа с платежами в Google Play.
Вот об этом я и расскажу подробнее ниже…
Читать полностью »
Неприлично простая реализация неприлично простого алгоритма генерации лабиринта
2017-01-14 в 17:54, admin, рубрики: c++, Алгоритмы, генерация, генерация лабиринтов, длиннопост, Лабиринт, лабиринтостроительство, много кодаПродолжение этой статьи об очень простом алгоритме генерации прямоугольных лабиринтов. В этой статье я приведу мою реализацию алгоритма на С++, а также покажу несколько дополнительных функций, которые породил мой скучающий мозг. Если осмелитесь продолжить читать, убедитесь, что ознакомились с моей предыдущей статьей. Глянули? Молодцы, продолжаем.Читать полностью »
Неприлично простой алгоритм генерации лабиринтов
2016-12-27 в 7:03, admin, рубрики: Алгоритмы, генерация лабиринтов, Лабиринт, Лабиринты, метки: ЛабиринтыПростенький алгоритм генерации идеальных лабиринтов в самом обычном двухмерном пространстве. Nuff said, остальное под катом.
Читать полностью »