Лабиринты использовались в видеоиграх с момента их появления. Первой видеоигрой с процедурно генерируемым лабиринтом была Beneath Apple Manor, выпущенная в 1978 году. Лабиринт в ней генерировался методом деления на комнаты и коридоры, из-за этого лабиринт часто выглядел однообразным и предсказуемым, что портило впечатление от игры. Для того, чтобы лабиринт выглядел естественнее разработчики стали использовать различные алгоритмы на графах. В этой статье мы рассмотрим реализации генерации идеального лабиринта с помощью алгоритма Прима.
Рубрика «алгоритм Прима»
Создание идеального лабиринта с помощью упрощённого алгоритма Прима
2026-02-28 в 10:46, admin, рубрики: алгоритм Прима, Алгоритмы, алгоритмы и структуры данных, Лабиринт, лабиринтостроительство, ЛабиринтыАлгоритм Прима
2024-10-03 в 7:16, admin, рубрики: алгоритм Прима, Алгоритмы, графы, матрица смежности, минимальное остовное деревоВ данной статье я бы хотел объяснить работу алгоритма Прима. Алгоритм используется для нахождения минимального остовного дерева. Сам алгоритм очень прост, в статье хотел бы поделиться своей реализации на языке Go.
Начальные термины
-
Граф — это структура данных в которой хранятся вершины и связи между ними. Удобнее всего представлять графы в виде матрицы смежности.
-
Матрица смежности — эта квадратная матрица, размер матрицы равен количеству вершин в графе. В ней хранится информация о соседях вершин графа.
-
Минимальное остовное деревоЧитать полностью »
SQL HowTo: генерируем лабиринты (алгоритм Прима и геометрические типы)
2021-11-22 в 5:40, admin, рубрики: postgresql, sql, sql tips and tricks, алгоритм Прима, Алгоритмы, Блог компании Тензор, Занимательные задачки, лабиринтостроительство
SQL является мощным инструментом для обработки множеств, а функционал PostgreSQL позволяет делать многие вещи еще проще, поэтому идеально подходит для реализации некоторых алгоритмов на графах.
Использование алгоритма Прима для генерации соединённых друг с другом пещер
2021-01-19 в 6:33, admin, рубрики: алгоритм Прима, Алгоритмы, генерация лабиринтов, клеточные автоматы, пещеры, процедурная генерация карт, разработка игр
Я решил объяснить один из алгоритмов генерации карты, используемых в моей игре In the House of Silence. Главное преимущество этого способа заключается в том, что в отличие от других алгоритмов, он никаким образом не может сгенерировать карту с разделёнными частями.
Генерация идеального лабиринта
Как понятно из названия, я использую хорошо задокументированный рандомизированный алгоритм Прима. Описание этого алгоритма можно найти на Википедии, однако вы можете применить любой другой алгоритм генерации лабиринтов.
Для понятности я привёл псевдокод, описывающий алгоритм Прима. Будет довольно просто приспособить его под любой язык программирования.
Читать полностью »
Джулия в лабиринте
2019-05-17 в 6:07, admin, рубрики: astar, Julia, алгоритм Прима, Лабиринты, ненормальное программирование, олимпиадные задачи, поиск в глубину, Программирование, Спортивное программирование
Разбирая одну олимпиадную задачу мы отправимся по петляющим коридорам генерации лабиринтов и их прохождения, а также увидим, что на языке Julia простота реализаций алгоритмов граничит с их псевдокодом.
Случайный лабиринт на JS в сами знаете сколько строк
2015-02-06 в 12:31, admin, рубрики: 30 строк js, javascript, алгоритм Прима, Алгоритмы, Лабиринт, ненормальное программирование, метки: лабиринтНачитавшись статей про [все что угодно] на JavaScript в 30 строк кода, я подумал: чем я хуже? Не найдя в перечне своих недостатков пункт «написание плохого кода», решил сделать что-нибудь интересное.
Лабиринты всегда веяли в мою сторону некоторой магией и загадками, поэтому поиск «чего-нибудь интересного» закончился достаточно быстро. К сожалению, создание игры затянулось на долгие часы экспериментов над консолью и моими нервами.
Изначально, осознавая размеры праведного гнева адептов непорочного программирования, я не планировал публиковать свои труды, но после того, как игра понравилась коту, паре друзей и моему самолюбию — решил написать статью (благо в нее можно внедрить теоретическую часть).
Для сторонников принципа «меньше знаешь — крепче спишь» предлагается cсылка на JSFiddle (управление стрелочками).
Читать полностью »