Важная информация

User Tag List

Показано с 1 по 10 из 10

Тема: Генератор лабиринтов

  1. #1
    Activist Аватар для Soplik
    Регистрация
    02.04.2005
    Адрес
    Минск
    Сообщений
    378
    Благодарностей: 8
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию Генератор лабиринтов

    Дано: лабиринт 64х64. Клеточка ест четыре байта:
    0 -- начало и конец линии раздела (см. ниже)
    1 -- пол и потолок в левом верхнем углу
    2 -- пол и потолок в правом нижнем углу
    3 -- материал стен и теги.
    Линия раздела -- отрезок внутри клеточки, делящий ее на два сегмента. Он начинается в одной из 16 точек по периметру и заканчивается также в любой из 16 этих точек. В каждом из двух сегментов -- своя высота пола и потолка.
    Один лабиринт без монстров, артефактов и порталов ест таким образом 16 килобайт -- треть сороквосьмой памяти и восьмую часть стодвадцатьвосьмой.

    Хотелось бы научиться их генерировать. Нужны идеи.

    NB: сам я возьмусь за эту игру не раньше, чем допишу белазики. Если кто возьмется развивать идею, буду только рад.
    Последний раз редактировалось Soplik; 24.09.2011 в 00:33.
    Сферический ламер в вакууме

  2. #1
    С любовью к вам, Yandex.Direct
    Размещение рекламы на форуме способствует его дальнейшему развитию

  3. #2
    Veteran Аватар для TomCaT
    Регистрация
    25.06.2005
    Адрес
    Одесса
    Сообщений
    1,683
    Благодарностей: 219
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Это посложнее плоских лабиринтов. А если для одного из двух сегментов комнаты высота пола задана одним числом, а где-то рядом комната (в которую можно перейти) с другой высотой пола - то как предполагается организовать переход с одного уровня высоты на другой?
    Помни. Только на компьютере можно семь раз Cut, а один - Format. В реале все иначе. (c)
    Власть людей сильнее, чем люди у власти.
    Чем меньше мы смотрим на мир, тем больше задумываемся о нем. (c)

    Скрытый текст

    Can you help Robin in his quest for the silver arrow? (c) Odin "Robin of the Wood"
    Мы все немного режем по дереву, а потом собираем корабли в бутылках.
    Is it the same old story you are going to tell me
    or is it the old story telling me and you we are the same?
    http://www.sky.od.ua/~ptsk
    [свернуть]


  4. #3
    Activist Аватар для Soplik
    Регистрация
    02.04.2005
    Адрес
    Минск
    Сообщений
    378
    Благодарностей: 8
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Если вторая комната ненамного выше/ниже -- ничего страшного. Можно вставить спотыкание при маленькой энергии.
    Если сильно ниже -- ушибаемся. Чем дальше падаем, тем сильнее бьёмся.
    Если сильно выше -- это то же самое, что стенка. Если не сильно, но заметно выше -- запрыгиваем с разбегом или без оного.
    Сферический ламер в вакууме

  5. #4
    Master
    Регистрация
    08.05.2007
    Адрес
    Dnepropetrovsk
    Сообщений
    880
    Благодарностей: 470
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

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

  6. Этот пользователь поблагодарил Barmaley_m за это полезное сообщение:
    Soplik (23.09.2011)

  7. #5
    Activist Аватар для Soplik
    Регистрация
    02.04.2005
    Адрес
    Минск
    Сообщений
    378
    Благодарностей: 8
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Монстров, думаю, тоже будет конечное число. Это не FPS.

    ---------- Post added at 00:57 ---------- Previous post was at 00:55 ----------

    Если просто псевдослучайно генерировать, будет не лабиринт, а каша из обломков

    ---------- Post added at 01:28 ---------- Previous post was at 00:57 ----------

    Хм, а вот если как-то продолжать стенку от клеточки к клеточке, расставлять колонны и лестницы, копировать комнаты в ряд...

    ---------- Post added at 01:55 ---------- Previous post was at 01:28 ----------

    Я хочу что-то в духе уровней Doom, но без секторов. И без самой трехмерки.
    Последний раз редактировалось Soplik; 24.09.2011 в 01:01.
    Сферический ламер в вакууме

  8. #6
    Veteran
    Регистрация
    29.12.2010
    Адрес
    Москва
    Сообщений
    1,497
    Благодарностей: 668
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от Soplik Посмотреть сообщение
    Линия раздела -- отрезок внутри клеточки, делящий ее на два сегмента
    А почему нельзя линию раздела делать по границам клеток?
    Генератор лабиринтов: http://zx.pk.ru/showthread.php?t=15939
    Формально всё правильно, а по существу - издевательство (В.И.Ленин)

  9. #7
    Activist Аватар для Soplik
    Регистрация
    02.04.2005
    Адрес
    Минск
    Сообщений
    378
    Благодарностей: 8
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Хочется диагональные стенки, тонкие двери, изгибающиеся коридоры.
    Сферический ламер в вакууме

  10. #8
    Veteran Аватар для TomCaT
    Регистрация
    25.06.2005
    Адрес
    Одесса
    Сообщений
    1,683
    Благодарностей: 219
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Диагональные стенки в формате лабиринта прописаны, а вот как поступать тогда с дверями и коридорами? если с клетки на соседнюю можно перейти в любом месте у края, то с диагональной стенкой может получиться коридор, широкий, но разбитый на несколько клеток... А если переход только через двери, как у Ultimate обычно, то двери выходят шириной что-то около ничего, но коридоры вряд ли получаться - будут комнаты, разделенные на теругольники. Кстати, одна из комбинаций начало-конец-раздела, вроде нуля, наверно, будет исключением для комнат, где раздел отсутствует?

    По ссылке Andrew771 можно поискать в теме разные варианты генераторов лабиринтов в матрице, только с прямыми углами и с однообразными составляющими типа комнат с 4-мя стенками или однобитных блок/проход.

    Твой тип лабиринта ближе к комнатному, но сложнее. Если усложнить комнатный генератор лабиринта с поднимающимися стенками, то можно:
    1) начинать с пустого пространства и хорошего генератора чисел
    2) выбрать случайное препятствие и для пробы установить на поле
    3) проверить одним из методов, можно ли от одной стороны препятствия(стенки комнаты, линии раздела) добраться до другого. Если можно - препятствие не разрывает лабиринт на две части. Можно добавлять следующее с шага 2
    4) если перебрать все возможные препятствия, получится лабиринт, в котором от каждой точки до другой можно добраться единственным путем. Это наиболее сложно, но не увлекательно. Часть допустимых препятствий стоит либо не ставить, либо поубирать потом, перове сложнее, второе - медленнее.
    5) В получившемся лабиринте несколькими способами можно расставить материал стен. Совершенно случайно проще, но выделить зоны, чтобы стены сменялись по мере удаления от старта, можно, один раз проверив расстояния клеток (полу-клеток, т.е. треугольников, если одна половина клетки вышла намного ближе, чем другая половина, можно материал для половинок хранить отдельно). С этой точки зрения лучше реализовать "волну" в пункте 3, чтоб здесь использовать ее же.

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

    Могут быть усложнения с линией раздела, в отличие от клеток-квадратов. Допустим, в комнате 4 двери. Если линия может поворачиваться по всем 360 градусам, и при этом либо отделять 2 двери от других 2-х, либо 1 дверь от 3-х остальных, возникает 6 (логических) вариантов раздела, точную точку из 16 потом можно выбрать случайно. Выбранный один вариант, конечно, отменяет остальные 5.

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

    Высота пола при генерации может вызывать односторонние проходы тогда, когда разница на границе клеток велика для подъема, причем любыми средствами, но мала для того, чтобы без вариантов разбиться при падении - последнее уже есть непроходимое препятствие. Хотя если подъем очень сложен, как в Head over Heels типа, с предмета на голове монстра, но в теории осуществим, можно при небольших разницах в расстоянии от старта для двух соседних клеток игнорировать такой подъем при генерации лабиринта - пусть срезанный путь будет наградой за ловкость игрока.

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

    Еще про односторонние - если от старта к финишу пройти можно только через некоторый односторонний проход - это естественная граница зон, тут можно сменить материал стен. Прохождение такого места, если в дальнейшем понадобится предмет, или нужно будет нажатие кнопки где-то ранее до "границы", приводит в ловушку, которую можно оставить как есть (но игроки ругаются), про которую можно намекнуть как-нибудь, до ее пересечения (если генератор карты помечает это отдельным битом). В Кирандии 2 на ИБМ вообще обеспечивают дальнейшее прохождение игры самопоявлением предметов, и не только в рюкзаке, причем как ни странно, к этому привыкаешь, и напрягает мало. Если не задуматься, конечно... В общем, односторонние проходы - сплошная головная боль, то-то в Диабле их 0,0...1 %, и те заранее продуманы.

    Потолок, если это только потолок, на генерацию не влияет, лишь бы под ним можно было проползти или прыгнуть на более высокий пол. Только бы это не был второй этаж
    Последний раз редактировалось TomCaT; 25.09.2011 в 12:37. Причина: есть, конечно, способы
    Помни. Только на компьютере можно семь раз Cut, а один - Format. В реале все иначе. (c)
    Власть людей сильнее, чем люди у власти.
    Чем меньше мы смотрим на мир, тем больше задумываемся о нем. (c)

    Скрытый текст

    Can you help Robin in his quest for the silver arrow? (c) Odin "Robin of the Wood"
    Мы все немного режем по дереву, а потом собираем корабли в бутылках.
    Is it the same old story you are going to tell me
    or is it the old story telling me and you we are the same?
    http://www.sky.od.ua/~ptsk
    [свернуть]


  11. Этот пользователь поблагодарил TomCaT за это полезное сообщение:
    Soplik (25.09.2011)

  12. #9
    Activist Аватар для Soplik
    Регистрация
    02.04.2005
    Адрес
    Минск
    Сообщений
    378
    Благодарностей: 8
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Теперь второй вопрос: как этото лабиринт лучше всего отображать? Сверху, в изометрии Knight Lore или...
    Сферический ламер в вакууме

  13. #10
    Veteran
    Регистрация
    29.12.2010
    Адрес
    Москва
    Сообщений
    1,497
    Благодарностей: 668
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от Soplik Посмотреть сообщение
    Теперь второй вопрос: как этото лабиринт лучше всего отображать? Сверху, в изометрии Knight Lore или...
    как хочешь
    Формально всё правильно, а по существу - издевательство (В.И.Ленин)

Информация о теме

Пользователи, просматривающие эту тему

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Похожие темы

  1. Генератор лабиринтов
    от Andrew771 в разделе Софт
    Ответов: 23
    Последнее: 14.11.2012, 16:44
  2. Генератор плейлистов
    от SGO в разделе Творчество
    Ответов: 8
    Последнее: 24.10.2012, 08:14
  3. Генерация лабиринтов
    от TomCaT в разделе Программирование
    Ответов: 90
    Последнее: 26.06.2012, 08:59
  4. Генератор RND
    от Destr в разделе Программирование
    Ответов: 4
    Последнее: 19.10.2009, 20:16
  5. генератор тора
    от voodoogod в разделе Программирование
    Ответов: 1
    Последнее: 10.03.2005, 20:19

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •