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

User Tag List

Страница 1 из 10 12345 ... ПоследняяПоследняя
Показано с 1 по 10 из 91

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

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

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

    Ищу совета и информации по этому поводу. Единственный генератор лабиринтов с настраиваемыми параметрами мне удалось написать только под IBM. И то подтормаживает.
    Второй неплохой генератор, с которым я знаком -- встроен в MAZIACS. Однако он ненастраиваемый, создаёт битовый лабиринт 64x64 причём правая часть каждой строки соединяется не с левой частью не самой себя, а строки следующей(!) -- явное упрощение для экономии времени создания. Когда-то я выдирал этот генератор и строил на его основе свои проги с лабиринтами. Однако до сих пор не дебаггил и потому не в курсе насчёт алгоритма...

    Выдранный генератор из MAZIACS, а также свою прогу на Delphi 6 (с исходниками) могу выложить по требованию. Но больше всего меня интересует, не знает ли кто быстрого и дост. универсального алгоритма построения 2D лабиринтов в прямоугольнике?
    Помни. Только на компьютере можно семь раз 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
    [свернуть]


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

  3. #2
    Veteran Аватар для Sinus
    Регистрация
    29.01.2005
    Адрес
    Belarus, Grodno
    Сообщений
    1,270
    Благодарностей: 190
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Т.е. тебе нужен 2D лабиринт, причём для любых точек (x1,y1) и (x2,y2) где (x1,y1)!=(x2,y2) и lab[y1][x1]=FLOOR и lab[y2][x2]=FLOOR существует путь между точками (x1,y1) и (x2,y2).
    По этому поводу есть какая-то спековская книжка по бейсику, там есть примерчик. Книжку мне искать лень, если будет время, то накатаю сам.
    Однако, на самом деле сделать так, что бы этот генератор лаиринтов тормоил довольно сложно

    PS. Тебе нужен лабиринт вида (1) или вида (2)? (см. аттач)
    Последний раз редактировалось Sinus; 07.09.2005 в 13:31.
    [target] [zemu] [js8x] [pouet 1, 2]
    KAY-1024, 5''FDD, 3''FDD, HDD

  4. #3
    Guru Аватар для rasmer
    Регистрация
    20.01.2005
    Адрес
    Саранск
    Сообщений
    2,172
    Благодарностей: 140
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от Sinus
    Т.е. тебе нужен 2D лабиринт, причём для любых точек (x1,y1) и (x2,y2) где (x1,y1)!=(x2,y2) и lab[y1][x1]=FLOOR и lab[y2][x2]=FLOOR существует путь между точками (x1,y1) и (x2,y2).
    По этому поводу есть какая-то спековская книжка по бейсику, там есть примерчик. Книжку мне искать лень, если будет время, то накатаю сам.
    Однако, на самом деле сделать так, что бы этот генератор лаиринтов тормоил довольно сложно

    PS. Тебе нужен лабиринт вида (1) или вида (2)? (см. аттач)
    ну уж поищи книжицу, сделай милость, или вспомни название, народ сканнлист выложит...
    Мои интры: [Kukarachess][Super boot rmx][tRUSHE MOSAIc][BLAZE]
    Мои игры: [Overload][Removal]

    Список игр для ZX-Spectrum: [2015] [2014]

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

    По умолчанию

    Вид лабиринта не имеет значения. Но т.к. вариант 2 легко преобразовывается в 1 (я встроил такую фичу в свою прогу), то лучше 2. Но 1 меня тоже бы устроил.
    Помни. Только на компьютере можно семь раз 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
    [свернуть]


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

    По умолчанию

    Цитата Сообщение от Sinus
    Однако, на самом деле сделать так, что бы этот генератор лаиринтов тормоил довольно сложно
    Нет, если лабиринт, скажем, 20x20, ето без проблем. А вот попробуйте хорошо салгоритмизировать (во загнул генератор для 80x80... Такие большие лабиринты, может, и редки в играх. Но ведь подавляющее большинство интересных игр имеют один-единственный, заранее сделанный лабиринт. Обидно, что второй, третий... пятый раз проходишь уже по проторенной дорожке, обходя тупики и опасности. Вот и захотелось мне разработать свой генератор, причём такой, на основе которого игра каждый раз создавала новое игровое поле. Ну пусть даже 2D, зато - представьте: запускаешь Saboteur, и каждый раз перед тобой другое здание Конечно, до этого далеко, но ведь в принципе осуществимо?

    При этом, как известно, ценятся именно скоростные алгоритмы, ведь после старта игры придётся за новый лабиринт платить долгой паузой. Насколько долгой - вот это я и выясняю. Поэтому и создал тему - вдруг народ знает чего-нибудь, тогда не придётся выдумывать самому улучшения для имеющихся у меня подпрограмм.
    Помни. Только на компьютере можно семь раз 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
    [свернуть]


  7. #6
    Activist
    Регистрация
    04.08.2005
    Адрес
    Nizhnevartovsk
    Сообщений
    352
    Благодарностей: 0
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от TomCaT
    Ну пусть даже 2D, зато - представьте: запускаешь Saboteur, и каждый раз перед тобой другое здание
    Тяжелый случай.
    Я так думаю - что саботер (тем более второй) было бы невозможно пройти, если бы карта была изменяемой.

  8. #7
    Veteran Аватар для SMT
    Регистрация
    16.01.2005
    Адрес
    Бобруйск
    Сообщений
    1,267
    Благодарностей: 30
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    ну если с отгрузками, другое дело

  9. #8
    Veteran Аватар для SMT
    Регистрация
    16.01.2005
    Адрес
    Бобруйск
    Сообщений
    1,267
    Благодарностей: 30
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    а навскидку, самый простой алгоритм такой: начиная с поля без стенок, случайно выбираем, куда поставить стенку. если лабиринт не распадается на 2 области, то сюда стенку не ставим, а если остаётся связным - ставим. и так до тех пор, пока можно ставить стенки...

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

    По умолчанию Угадали :)

    Именно так моя программа строит под IBM. Но боюсь на Speccy переводить - генерация долгая.
    Правда, проверка "распада на 2 части" могла бы быть быстрее, я сецас думаю. По моему алгоритму, проходимость алгоритма ПОСЛЕ КАЖДОЙ поднятой стенки (комнатный вариант, 2 по картинкам от Sinus) проверялась по правилу правой руки. Если от одной комнаты рядом со стенкой можно дойти до отгороженной комнаты (с той стороны стенки) и вернуться затем назад (вот это, кажется, лишнее), лабиринт считается всё ещё проходимым. Иначе стенка помечается неподнимаемой. И так со всеми стенками.
    Думаю, можно бы улучшить как-нибудь проверку...

    2Dexus: сомневаюсь, что к-л без карты удалось пройти игру с ПЕРВОГО РАЗА. С картой всё проще...но и интерес теряется А вот если генератор лабиринтов + беск. (или очень большой) лимит времени... Тогда, имхо, было бы просто захватывающе играть.

    Кстати, проверка окончания построения - нет ли какой-то прямой (не примерной, а точной) зависимости площадь/макс. число поднимаемых стенок? Может, есть формула? Я попробую собрать стат. данные по этому поводу своей прогой. Может, есть зависимость
    Последний раз редактировалось TomCaT; 09.09.2005 в 06:22. Причина: Ответ самому себе впишу ниже
    Помни. Только на компьютере можно семь раз 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. #10
    Moderator Аватар для elf/2
    Регистрация
    14.01.2005
    Адрес
    N.Novgorod
    Сообщений
    803
    Благодарностей: 117
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    можно дернуть алгоритм из opensource игр, например angband'а (http://www.thangorodrim.net/). я когда то смотрел, там сначала комнаты случайным образом расставляют, а потом тоннели между ними организуют. исходники качественно прокомментированы и организованы

Страница 1 из 10 12345 ... ПоследняяПоследняя

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

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

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

Ваши права

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