Просмотр полной версии : Генерация лабиринтов
Ищу совета и информации по этому поводу. Единственный генератор лабиринтов с настраиваемыми параметрами мне удалось написать только под IBM. И то подтормаживает.
Второй неплохой генератор, с которым я знаком -- встроен в MAZIACS. Однако он ненастраиваемый, создаёт битовый лабиринт 64x64 причём правая часть каждой строки соединяется не с левой частью не самой себя, а строки следующей(!) -- явное упрощение для экономии времени создания. Когда-то я выдирал этот генератор и строил на его основе свои проги с лабиринтами. Однако до сих пор не дебаггил и потому не в курсе насчёт алгоритма...
Выдранный генератор из MAZIACS, а также свою прогу на Delphi 6 (с исходниками) могу выложить по требованию. Но больше всего меня интересует, не знает ли кто быстрого и дост. универсального алгоритма построения 2D лабиринтов в прямоугольнике?
Т.е. тебе нужен 2D лабиринт, причём для любых точек (x1,y1) и (x2,y2) где (x1,y1)!=(x2,y2) и lab[y1][x1]=FLOOR и lab[y2][x2]=FLOOR существует путь между точками (x1,y1) и (x2,y2).
По этому поводу есть какая-то спековская книжка по бейсику, там есть примерчик. Книжку мне искать лень, если будет время, то накатаю сам.
Однако, на самом деле сделать так, что бы этот генератор лаиринтов тормоил довольно сложно ;)
PS. Тебе нужен лабиринт вида (1) или вида (2)? (см. аттач)
Т.е. тебе нужен 2D лабиринт, причём для любых точек (x1,y1) и (x2,y2) где (x1,y1)!=(x2,y2) и lab[y1][x1]=FLOOR и lab[y2][x2]=FLOOR существует путь между точками (x1,y1) и (x2,y2).
По этому поводу есть какая-то спековская книжка по бейсику, там есть примерчик. Книжку мне искать лень, если будет время, то накатаю сам.
Однако, на самом деле сделать так, что бы этот генератор лаиринтов тормоил довольно сложно ;)
PS. Тебе нужен лабиринт вида (1) или вида (2)? (см. аттач)ну уж поищи книжицу, сделай милость, или вспомни название, народ сканнлист выложит...
Вид лабиринта не имеет значения. Но т.к. вариант 2 легко преобразовывается в 1 (я встроил такую фичу в свою прогу), то лучше 2. Но 1 меня тоже бы устроил.
Однако, на самом деле сделать так, что бы этот генератор лаиринтов тормоил довольно сложно
Нет, если лабиринт, скажем, 20x20, ето без проблем. А вот попробуйте хорошо салгоритмизировать (во загнул :) генератор для 80x80... Такие большие лабиринты, может, и редки в играх. Но ведь подавляющее большинство интересных игр имеют один-единственный, заранее сделанный лабиринт. Обидно, что второй, третий... пятый раз проходишь уже по проторенной дорожке, обходя тупики и опасности. Вот и захотелось мне разработать свой генератор, причём такой, на основе которого игра каждый раз создавала новое игровое поле. Ну пусть даже 2D, зато - представьте: запускаешь Saboteur, и каждый раз перед тобой другое здание :) Конечно, до этого далеко, но ведь в принципе осуществимо?
При этом, как известно, ценятся именно скоростные алгоритмы, ведь после старта игры придётся за новый лабиринт платить долгой паузой. Насколько долгой - вот это я и выясняю. Поэтому и создал тему - вдруг народ знает чего-нибудь, тогда не придётся выдумывать самому улучшения для имеющихся у меня подпрограмм.
Ну пусть даже 2D, зато - представьте: запускаешь Saboteur, и каждый раз перед тобой другое здание
Тяжелый случай.
Я так думаю - что саботер (тем более второй) было бы невозможно пройти, если бы карта была изменяемой.
ну если с отгрузками, другое дело :)
а навскидку, самый простой алгоритм такой: начиная с поля без стенок, случайно выбираем, куда поставить стенку. если лабиринт не распадается на 2 области, то сюда стенку не ставим, а если остаётся связным - ставим. и так до тех пор, пока можно ставить стенки...
Именно так моя программа строит под IBM. Но боюсь на Speccy переводить - генерация долгая.
Правда, проверка "распада на 2 части" могла бы быть быстрее, я сецас думаю. По моему алгоритму, проходимость алгоритма ПОСЛЕ КАЖДОЙ поднятой стенки (комнатный вариант, 2 по картинкам от Sinus) проверялась по правилу правой руки. Если от одной комнаты рядом со стенкой можно дойти до отгороженной комнаты (с той стороны стенки) и вернуться затем назад (вот это, кажется, лишнее), лабиринт считается всё ещё проходимым. Иначе стенка помечается неподнимаемой. И так со всеми стенками.
Думаю, можно бы улучшить как-нибудь проверку...
2Dexus: сомневаюсь, что к-л без карты удалось пройти игру с ПЕРВОГО РАЗА. С картой всё проще...но и интерес теряется :) А вот если генератор лабиринтов + беск. (или очень большой) лимит времени... Тогда, имхо, было бы просто захватывающе играть.
Кстати, проверка окончания построения - нет ли какой-то прямой (не примерной, а точной) зависимости площадь/макс. число поднимаемых стенок? Может, есть формула? Я попробую собрать стат. данные по этому поводу своей прогой. Может, есть зависимость
можно дернуть алгоритм из opensource игр, например angband'а (http://www.thangorodrim.net/). я когда то смотрел, там сначала комнаты случайным образом расставляют, а потом тоннели между ними организуют. исходники качественно прокомментированы и организованы
ws_mason
09.09.2005, 14:25
Меня заинтересовала эта тема. Есть сцнарий игры про лабиринт как таковой но некогда писать.
ws_mason
09.09.2005, 14:26
Лабиринт по второму варианту это самое оно для моей игры. Если интересно кому могу выложить всю концепцию.
Лабиринт по второму варианту это самое оно для моей игры. Если интересно кому могу выложить всю концепцию.
Выкладывай, но в целях антифлейма лучше рядом отд. тема :) . Имхо.
А если тебе надо помочь с генератором, обращайся, у меня 2-3 варианта есть, вот только хотелось бы ЕЩЁ поскоростнее (чем эти мои варианты). Поэтому и создал тему.
если ещё подумать, можно предложить делить карту на несколько частей извилистыми линиями, в каждой замкнутой области строить свой лабиринт (ведь время построения зависит от площади нелинейно и быстрее создать 4 по 16 клеток, чем 1 из 64) и сломать по одной из стен в изначальной линии между подчастями, чтобы соединить лабиринты в один
а вот что получится, если дальше развить эту идею. пусть каждая клетка может быть в одном из множеств А или Б. клетки из А - те, которые внутри лабиринта, Б - внешние для лабиринта. алгоритм простой: ставим все возможные стенки на поле. одну любую клетку включаем в А, остальные - в Б
шаг1. выбираем случайно одну клетку из Б, граничащую с некоторой клеткой из А (можно наоборот). стираем между ними стенку, перемещаем клетку из множества Б а А. повтор шага 1, пока Б не пусто
можно поделить клетки на 3 множества (внешние, строго внутренние и внутренние, но пограничные). тогда нужно выбирать лишь из пограничных клеток, и не надо повторно перебирать клетки, которые уже давно внутри лабиринта (если у клетки нет подходящих соседей, сразу переводим её в "мёртвое" множество). увы, немного усложняется алгоритм
Именно так моя программа строит под IBM. Но боюсь на Speccy переводить - генерация долгая.
Правда, проверка "распада на 2 части" могла бы быть быстрее, я сецас думаю. По моему алгоритму, проходимость алгоритма ПОСЛЕ КАЖДОЙ поднятой стенки (комнатный вариант, 2 по картинкам от Sinus) проверялась по правилу правой руки. Если от одной комнаты рядом со стенкой можно дойти до отгороженной комнаты (с той стороны стенки) и вернуться затем назад (вот это, кажется, лишнее), лабиринт считается всё ещё проходимым. Иначе стенка помечается неподнимаемой. И так со всеми стенками.
Думаю, можно бы улучшить как-нибудь проверку...
2Dexus: сомневаюсь, что к-л без карты удалось пройти игру с ПЕРВОГО РАЗА. С картой всё проще...но и интерес теряется :) А вот если генератор лабиринтов + беск. (или очень большой) лимит времени... Тогда, имхо, было бы просто захватывающе играть.
Кстати, проверка окончания построения - нет ли какой-то прямой (не примерной, а точной) зависимости площадь/макс. число поднимаемых стенок? Может, есть формула? Я попробую собрать стат. данные по этому поводу своей прогой. Может, есть зависимость
Это неправильный алгоритм. Есть более другой, и хотя лабиринты с ним получаются может чуток менее "крутыми", но зато работает он сильно быстрее.
а вот что получится, если дальше развить эту идею. пусть каждая клетка может быть в одном из множеств А или Б. клетки из А - те, которые внутри лабиринта, Б - внешние для лабиринта. алгоритм простой: ставим все возможные стенки на поле. одну любую клетку включаем в А, остальные - в Б
шаг1. выбираем случайно одну клетку из Б, граничащую с некоторой клеткой из А (можно наоборот). стираем между ними стенку, перемещаем клетку из множества Б а А. повтор шага 1, пока Б не пусто
можно поделить клетки на 3 множества (внешние, строго внутренние и внутренние, но пограничные). тогда нужно выбирать лишь из пограничных клеток, и не надо повторно перебирать клетки, которые уже давно внутри лабиринта (если у клетки нет подходящих соседей, сразу переводим её в "мёртвое" множество). увы, немного усложняется алгоритм
По порядку - если Ваш вариант с мн-вами А и Б служит как бы для "расширения данного лабиринта в произвольном направлении" (как я понял), то как вы собираетесь организовывать незабвенные тупики?
Вариант 3 - алгоритм реально не намного сложнее. Выяснить периметр в матрице комнат лабиринта не очень сложная задача (то же правило правой руки в комнате сложной формы без внутренних препятствий).
Есть более другой, и хотя лабиринты с ним получаются может чуток менее "крутыми", но зато работает он сильно быстрее.
Ну, Вы на этот алгоритм хоть намекните, хоть принцип, а там уже люди сравнят и решат. Просто-напросто этот "неправильный алгоритм" -- единственный, который я знаю (и про который знаю, что он РАБОТАЕТ).
а навскидку, самый простой алгоритм такой: начиная с поля без стенок, случайно выбираем, куда поставить стенку. если лабиринт не распадается на 2 области, то сюда стенку не ставим, а если остаётся связным - ставим. и так до тех пор, пока можно ставить стенки...
подскажите к-л быстрый способ определения связности. Фактически, в моей проге на писи всё по вашему алгоритму, но связность - по правилу правой руки - самая муторная, сложная и времежрущая часть. Может, можно не обходить после каждой стенки пол-лабиринта?
Ваш вариант с мн-вами А и Б служит как бы для "расширения данного лабиринта в произвольном направлении" (как я понял), то как вы собираетесь организовывать незабвенные тупикисделаю маленький пример, лабиринт 3x3, 9 клеток:
+-+-+-+
|1|2|3|
+-+-+-+
|4|5|6|
+-+-+-+
|7|8|9|
+-+-+-+
клетку 1 - в А, остальные - в Б. по очереди будем выбирать такие пары А-Б: 1-2, 2-3, 3-6, 6-9:
+-+-+-+
|1 2 3|
+-+-+ +
|4|5|6|
+-+-+ +
|7|8|9|
+-+-+-+
потом 6-5, 5-4, 4-7, 5-8
+-+-+-+
|1 2 3|
+-+-+ +
|4 5 6|
+ + + +
|7|8|9|
+-+-+-+
разве не получились тупики?
+-+-+-+
| |
+-+-+ +
| |
+ + + +
| | | |
+-+-+-+
кроме того, при соотв. выборе ГСЧ, получается произвольный заранее заданный лабиринт, как и в Вашем алгоритме. они делают примерно одинаковые лабиринты
связность - по правилу правой руки - самая муторная, сложная и времежрущая частьэто ещё не связность, а лишь наличие пути между двумя точками :) его тут достаточно. да и обход по руке будет более оптимален, чем обходы в глубину или ширину. кажется, тут уже ничего алгоритмически не сделаешь, нужно думать, как оптимально накодить обход по правой руке (ну, или алгоримт с А-Б заюзать)
сделаю маленький пример, лабиринт 3x3, 9 клеток:
+-+-+-+
|1|2|3|
+-+-+-+
|4|5|6|
+-+-+-+
|7|8|9|
+-+-+-+
клетку 1 - в А, остальные - в Б. по очереди будем выбирать такие пары А-Б: 1-2, 2-3, 3-6, 6-9:
+-+-+-+
|1 2 3|
+-+-+ +
|4|5|6|
+-+-+ +
|7|8|9|
+-+-+-+
потом 6-5, 5-4, 4-7, 5-8
+-+-+-+
|1 2 3|
+-+-+ +
|4 5 6|
+ + + +
|7|8|9|
+-+-+-+
разве не получились тупики?
+-+-+-+
| |
+-+-+ +
| |
+ + + +
| | | |
+-+-+-+
Да, я понял. Вы действуете с А и Б в пределах одного прямоугольника. Действительно, м/б быстрее. Я всё же думаю, MAZIACS сей алгоритм не применяли, а там лабиринты О-ГО-ГО какие качественные. Хотя может, я ошибаюсь...
кроме того, при соотв. выборе ГСЧ, получается произвольный заранее заданный лабиринт, как и в Вашем алгоритме. они делают примерно одинаковые лабиринты
Нет. В моём алгоритме не используется ГСЧ. На самом деле предварительно составляется список всех поднимаемых стенок, а затем список "рассортировывается" по ГСЧ, который сложным образом зависит от дата/времени. Т.о. повторяемость лабиринтов минимальна. Но это на IBM. Для Спекки такое малоприменимо. Разве что подсчитывать время, в течение которого юзер разглядывает меню, а затем использовать как SEED :)
Это ещё не связность, а лишь наличие пути между двумя точками :) его тут достаточно. да и обход по руке будет более оптимален, чем обходы в глубину или ширину. кажется, тут уже ничего алгоритмически не сделаешь, нужно думать, как оптимально накодить обход по правой руке (ну, или алгоримт с А-Б заюзать)
Тогда объясните, что вы понимаете под проверкой связности. И почему путь между двумя точками (если эти две точки - в комнатах по обе стороны только что поднятой стенки) не указывает однозначно на наличие/отсутствие связности?
2All:
как и обещал, высылаю выдранный из MAZIACS генератор. Не удосужился дебаггнуть. Если кто-то хочет его использовать, но не знает как, пишите мне на мыло или сюда, я раскопаю свой Labirint на BASIC'е и припомню вх./вых. параметры процедурки.
В моём алгоритме не используется ГСЧ. На самом деле предварительно составляется список всех поднимаемых стенок, а затем список "рассортировывается" по ГСЧ :)
Тогда объясните, что вы понимаете под проверкой связностивопрос чисто в терминах, поэтому лучше сильно не отходить от темы.
почему путь между двумя точками (если эти две точки - в комнатах по обе стороны только что поднятой стенки) не указывает однозначно на наличие/отсутствие связностипо определению, связность - наличие пути между любыми двумя точками. но в нашем случае, в котором лабиринт до возведения стенки был связным, то он останется таким тогда и только тогда, если найдётся путь между клетками, разделёнными новой стенкой
как и обещал, высылаю выдранный из MAZIACS генератора алгоритм выяснил? если нет, подожду хотя бы вх./вых. параметры...
TCT>> как и обещал, высылаю выдранный из MAZIACS генератор
SMT>а алгоритм выяснил? если нет, подожду хотя бы вх./вых. параметры...
Послушайте, я понимаю, что пишу не туда, и это чистый флейм. Но не в силах ли кто-нибудь подсказать, как файл Hobeta быстро перекинуть на fdi-дискетку для дебага (мой SN недавно сдох, т.к. заапгрейдился до AMD Sempron 1800, - Runtime Error 200, до сих пор даже патчи не помогли). Иначе вх./вых. параметры будут не скоро...
(Хотя если память не врёт, процедура просто вызывается по адресу Start самого файла-аттача. Генерит циклический лабиринт 64x64 из байтов 0 и 1, выходя вниз, приходишь сверху, выходя влево приходишь справа, НО НА 1 СТРОКУ ВЫШЕ. вход помечен квадратом нулей 3x3. Выхода процедура не выставляет. А вот адрес, куда кладётся лабиринт, я уже и не вспомню. Если смогу поднять Spectrum Navigator, расскажу)
Послушайте, я понимаю, что пишу не туда, и это чистый флейм.
Это называется Offtopic а не Flame.
А что касается генерации лабиринтов - действовать от противного.
Сгенерировать непроходимый лабиринт, а потом прорубить случайные проходы. Вообще, я думаю по запросу maze generation гугль вывалит столько...
TomCat: генератор запускается точно не сначала. в начале - мусор
На спеке была поляческая игра так и называлась 3д лабиринт
генерила лабиринт вида 2 с тупиками и тп
и еще игруха Fred
Ура, запустил SN и наконец-то скинул в Shalaev'скую дискетку MAZIACS и свою прогу Labirint на основе выдранного из первой игры куска! Отдебагил всё вкупе, и не зря. В результате:
1)выдранные 1-1,5 килобайт местами содержат мусор, но я просто перестраховывался и сохранил с лишним (помню, сохранил один раз именно этот кусок без пары байт в конце, долго вис и сбрасывался :) )
2) адрес запуска 42720
3) лабиринт после генерации кладётся куда-то с 49000 и дальше, занимает 4кб. Точного адреса размещения пока не выяснил, но это легче, чем точка входа :)
4) для тех, кто не понял, о чём речь, см. мои посты на прошлой странице, гдя я выкладывал процедурку.
5) после недолгого просмотра кода с 42720 (A6E0) выяснил, что скоро идёт вызов процедуры по адресу 42078, которая использует слова по адресам 42074, 42076 как переменные. Так что фактически мусор если и есть, то перемешан с нужными процедурами, что при безусловных переходах делает бесполезным его изъятие :)
6) лабиринт располагается с адреса 49152 (C000) - можно было бы и догадаться, а я вот долго думал, что с 49155 и ещё удивлялся, почему такой странный адрес. В лабиринте 0 - пустоты и проходы, 255 - стенки.
7) проверил, верно то, что выходы из квадрата лабиринта вправо не совпадают с выходами влево - надо следить за переводом строки.
2jerri: это всё тоже интересно, но вот как оттуда генераторы вынуть и рассмотреть? ведь MAZIACS на полу-Бэйсике, а те в маш. кодах (Fred, во всяком разе). Хотя польский 3д лабиринт тоже бы надо посмотреть, может, он и на Бэйсике. Может, ссылку кинешь?
алгоритм раздизасмил. идея довольно простая, но написан жутко неоптимально по скорости. конец генерации лабиринта привязан к таймеру :) (или может, сравнение #5C78 c #96 - это нажатие кнопки - не силён я в basic-переменных)
алгоритм раздизасмил. идея довольно простая, но написан жутко неоптимально по скорости.
Так разжуй же нам, убогим. Даже неоптимальную :D
конец генерации лабиринта привязан к таймеру (или может, сравнение #5C78 c #96 - это нажатие кнопки - не силён я в basic-переменных)
А, понятно... нет, это действительно привязка к таймеру. Хотя внутри, кажется, местами прерывания вырубаются. Просто для "успокоения игрока" время генерации не ниже 3c (#96). Это позволяет не мигать экраном "Подождите, идёт постройка..." и тут же входить в игру, а дать отдохнуть игроку и показать, что в КАЖДОЙ игре лабиринт создаётся небыстро. И лучше мирно подождать, чем злится, что в этот раз "долго строит".
Отсюда, кстати, и неоптимальность по времени. Дону Пристли не нужны были быстрые построения, он сам тормозил их.
2jerri: это всё тоже интересно, но вот как оттуда генераторы вынуть и рассмотреть? ведь MAZIACS на полу-Бэйсике, а те в маш. кодах (Fred, во всяком разе). Хотя польский 3д лабиринт тоже бы надо посмотреть, может, он и на Бэйсике. Может, ссылку кинешь?
он в кодах и там задается лабиринт почти любого размера
http://trd.speccy.cz/gamez/123/3DLABYR_.ZIP
а можно сюда зааттачить Maziaks а то прокся ftp режет
он в кодах и там задается лабиринт почти любого размера
http://trd.speccy.cz/gamez/123/3DLABYR_.ZIP
В том-то и беда, что в кодах. Кто и когда вознамерится найти точку входа (а может, и параметры)? В MAZIACS проще, BASIC-часть потрепал и готово... Но я попробую всё одно.
а можно сюда зааттачить Maziaks а то прокся ftp режет
Вот Maziacs для тех, кто не обзавёлся:
(вложению MAZIACS.ZIP низачот, и с горя оно убило себя об хард, 12.3 Кбайт, 12 просмотров на 19 IX 2006. Поминки на VIRT'е)
еще 3 алгоритма генерации лабиринтов (http://algolist.manual.ru/games/maze.php)
вот этот мне кажется достаточно абсурдным и перспективным :)
Автор:
[email protected]
Время: 11-05-05 06:55
По-моему можно проще:
1) берем чистую матрицу
2) ставим блоки по
периметру
3) обозначаем случайно вход и выход
4) кидаем случайно блок в
пустое место
6) если от входа до выхода можно дайти блок не убираем
5)
если кинули блоков больше, чем нам нужно (процент заполненности - например
40) выход
7) goto 4
//1
int mas[N][M];
memset(mas,0,M*N*sizeof(int));
//2
for(int i = 0;
i < N; i++)mas[i][0]=1;
for(int i = 0; i < N; i++)mas[i][M-1]=1;
for(int i = 0; i < M; i++)mas[0][i]=1;
for(int i = 0; i < M;
i++)mas[N-1][i]=1;
//3
int exit = random(M);
int enter = random(M);
mas[0][exit] = 0;
mas[N-1][enter] = 0;
//4
double percent = 0.4;
int zapolneno = N*2+(M-2)*2;
while(1)
{
x
= random(N-2);
y = random(M-2);
mas[x][y] = 1;
mas[x][y] =
СanPass(mas,0,exit,N-1,enter,N,M);
zapolneno +=max[x][y];
//5
if(zaploneno/(N*M) > percent)break;
}
bool CanPass(int mas[][],x1,y1,x2,y2,N,M)
{
//Волновой допустим
алгоритм проверки возможности пройти от (x1,y1) до (x2,y2)
}
Ну и чем же он отличается от алгоритма SMT для "комнатного" (вариант 2) лабиринта? Разве что волновой помск связности. Может, это и самый быстрый вариант, но как в памяти волну хранить? Помечать в самом лабиринте байты? Может пределов не хватить 0-255, а иначе будет память жрать.
Ну и чем же он отличается от алгоритма SMT для "комнатного" (вариант 2) лабиринта? Разве что волновой помск связности. Может, это и самый быстрый вариант, но как в памяти волну хранить? Помечать в самом лабиринте байты? Может пределов не хватить 0-255, а иначе будет память жрать.
не знаю :)
остальные смотрел?
тебе не надо путь тебе нужна волна
0 - пустое место
255 - стена
128 - волна
если новых 128 нет и выход недостижим - продолжаем генерить
просто имхо
проверять не каждый раз а раз в 16 точек или более
хорошо, попробую на русском (что не смогу перевести, оставлю на МЯ).
итак, лабиринт - массив A[64,64], причём он закольцован по краям, то есть двигаясь влево, выйдем с правой стороны, а двигаясь вниз - сверху. для упрощения, когда я буду писать A[x,y], будет подразумеваться A[x mod 64, y mod 64], (код, который отслеживает переполнения координат, там присутствует и довольно громоздкий)
итак,
fill(A, 255, 64*64); // все стенки
for x=0 to 2 do
for y=0 to 2 do
A[x,y] = #80; // не знаю, зачем
x=y=1
switch (random(4))
{
case 0: x=x+2; break;
case 1: x=x-2; break;
case 2: y=y+2; break;
case 3: y=y-2; break;
// изменения начальной позиции
// так как координаты закольцованы, начать можем даже снизу или справа
}
for (;;) // вечный цикл
{
ХодилиВлево=ХодилиВправо=Х одилиВверх=ХодилиВниз = нет;
пока не (ХодилиВлево и ХодилиВправо и ХодилиВверх и ХодилиВниз)
{
дистанция = 2+random(4);
выбрать_напр:
напр = random(4);
switch (напр) {
case 0:
если (ХодилиВлево) goto выбрать_напр;
for i=1 to дистанция
{
если (A[x-2,y]!=#FF или A[x-1,y]!=#FF или
A[x-2,y-1]!=#FF или A[x-1,y-1]!=#FF или
A[x-2,y+1]!=#FF или A[x-1,y+1]!=#FF)
{
ХодилиВлево = да;
goto выбрать_напр;
}
иначе
{
x=x-1; A[x,y] = 0;
}
}
break;
case 1:
если (ХодилиВправо) goto выбрать_напр;
for i=1 to дистанция
{
если (A[x+2,y]!=#FF или A[x+1,y]!=#FF или
A[x+2,y-1]!=#FF или A[x+1,y-1]!=#FF или
A[x+2,y+1]!=#FF или A[x+1,y+1]!=#FF)
{
ХодилиВправо = да;
goto выбрать_напр;
}
иначе
{
x=x+1; A[x,y] = 0;
}
}
break;
case 2:
если (ХодилиВверх) goto выбрать_напр;
for i=1 to дистанция
{
если (A[x,y-2]!=#FF или A[x,y-1]!=#FF или
A[x-1,y-2]!=#FF или A[x-1,y-1]!=#FF или
A[x+1,y-2]!=#FF или A[x+1,y-1]!=#FF)
{
ХодилиВверх = да;
goto выбрать_напр;
}
иначе
{
y=y-1; A[x,y] = 0;
}
}
break;
case 3:
если (ХодилиВниз) goto выбрать_напр;
for i=1 to дистанция
{
если (A[x,y+2]!=#FF или A[x,y+1]!=#FF или
A[x-1,y+2]!=#FF или A[x-1,y+1]!=#FF или
A[x+1,y+2]!=#FF или A[x+1,y-+]!=#FF)
{
ХодилиВниз = да;
goto выбрать_напр;
}
иначе
{
y=y+1; A[x,y] = 0;
}
}
break;
}
}
// ходили во все 4 стороны
do {
если ( (#5C78) >= #96 ) полный_стоп!
x = random(64);
y = random(64);
} while (A[x,y] != 0);
}
ну что, смогёт кто-нить накодить это для windows-графики, чтобы проверить? :)
а почему реализация мне не понравилась? так потому что как будто компилер делал (мало используются регистры, смешные конструкции типа push hl / pop de). но так как алгоритм сверхбыстрый, огрехи в кодинге им компенсируются
хорошо, попробую на русском (что не смогу перевести, оставлю на МЯ).
итак, лабиринт - массив A[64,64], причём он закольцован по краям, то есть двигаясь влево, выйдем с правой стороны, а двигаясь вниз - сверху. для упрощения, когда я буду писать A[x,y], будет подразумеваться A[x mod 64, y mod 64], (код, который отслеживает переполнения координат, там присутствует и довольно громоздкий)
итак,
fill(A, 255, 64*64); // все стенки
for x=0 to 2 do
for y=0 to 2 do
A[x,y] = #80; // не знаю, зачем
--- Cut ---
...
алгоритм
...
--- Cut ---
ну что, смогёт кто-нить накодить это для windows-графики, чтобы проверить?
Ух, захватывает :) Будет время, закодирую обязательно. Может, на этих выходных. Или раньше.
2jerri: Посмотрел. Первый я пытался ещё Васиком на ZX, так и не перевёл идею рекурс. ходов с ответвлениями из задумки в прогу. А остальные -- вроде уже упоминались, кроме варианта "Жизнь" -- вот это тоже стоит проверить.
Да, а те два цикла от 0 до 2 в начале -- для квадрата старта 3x3. Он не подпадает под правила построения в алгоритме и "вырубается в монолите стенок" с самого начала.
Так, сажусь за Delphi...
немножко наврал в уменьшении переменной "дистанция". на самом деле, это счётчик, который уменьшается после каждого изменения x/y. то есть код внутреннего цикла выглядит как
дистанция = 2+random(4);
выбрать_напр:
напр = random(4);
switch (напр) {
case 0:
если (ХодилиВлево) goto выбрать_напр;
for (;;)
{
если (A[x-2,y]!=#FF или A[x-1,y]!=#FF или
A[x-2,y-1]!=#FF или A[x-1,y-1]!=#FF или
A[x-2,y+1]!=#FF или A[x-1,y+1]!=#FF)
{
ХодилиВлево = да;
goto выбрать_напр;
}
иначе
{
x=x-1; A[x,y] = 0;
дистанция=дистанция-1;
если (дистанция == 0) break; // внутренний for (;;)
}
}
break; // case
// аналогично по остальным направлениям
в принципе, лабиринты тоже будут получаться хорошие, только менее извилистые, т.е. меньше точек, в которых ответвляется корридор. можно попробовать оба варианта :)
ещё забыл вставить перед первым for (;;) команды A[x,y]=0, без которой начальный квадрат оказывается отрезан от остального лабиринта
ещё не забудь, что куча обращений типа A[x+1,y-2] на самом деле кишит остатками от деления на размер лабиринта (mod 64)
а насчёт начального квадрата, почему он кодируется кодом #80, а не #00?
еще алгоритм берем непроходимый лабиринт произвольную клетку делаем проходимой далее повторяем следующий шаг: выбираем произвольную непроходимую клетку, имеющую ровно 1 проходимого соседа, и делаем ее проходимой так до тех пор, пока такие клетки есть в результате получится лабиринт-"дерево" (между любыми двумя проходимыми клетками есть ровно один путь)
а если вот такой алгоритм? тоже должен быть эффективным
В том-то и беда, что в кодах. Кто и когда вознамерится найти точку входа (а может, и параметры)? В MAZIACS проще, BASIC-часть потрепал и готово... Но я попробую всё одно.
Вот Maziacs для тех, кто не обзавёлся:
так в кодах имхо интереснее
чего то у мя игра виснет не запускается
а если вот такой алгоритм? тоже должен быть эффективнымэто пересказ моего АБ-алгоритма для лабиринтов типа 1. если правильно сделать выбор клеток, будет быстро. но, в отличии от maziacs, прямые корридоры будут короткие (сплошной random, нет походов по прямым)
В 3д лабиринте генератор смотрел?
порыскал в инете в принципе генераторов лабиринта не так уж и много
и в основном ссылаются на алгоритм Крускала
а если строить лабиринт из готовых кусков 3*3 это будет быстрее?
ws_mason
15.09.2005, 09:50
А еще можно наготовить стандартных лабиринтиков 3х3, 4х4, 5х5, ловшук, спиралей и все это в случайном порядке друг на друга и на общее поле.
А еще можно наготовить стандартных лабиринтиков 3х3, 4х4, 5х5, ловшук, спиралей и все это в случайном порядке друг на друга и на общее поле.
так собсно и предлягаю но после того как закончится такая прегенерация необходимо обработку провести уже по крускалу чтобы лабиринт связанный был
а волну можно с помощью конвейера гнать - быстрее получится
(подробнее том элементарная графика инфоркома)
тож про лабиринты (http://mysteriousguild.com/forums/index.php?showtopic=19)
ещё не забудь, что куча обращений типа A[x+1,y-2] на самом деле кишит остатками от деления на размер лабиринта (mod 64)
а насчёт начального квадрата, почему он кодируется кодом #80, а не #00?
Ничего не забуду. Общее оформление вот счас сделал, теперь алгоритм странслирую на Pascal, а там и экзешник сюда выложу.
чего то у мя игра виснет не запускается
игра ок. 20 кб, бейсик-коды в виде блока кодов, с дискеты как обычно грузятся в память повыше, а потом перемещаются на адрес 23296 (16384, не помню в оющем). В процессе перемещения могут быть убиты сиспеременные памяти 128-ых и старше. Поэтому запускайся в режиме 48.
А если и там не будет пахать, то где-то у меня z80-образ завалялся. Подойдёт?
пока не (ХодилиВлево и ХодилиВправо и ХодилиВверх и ХодилиВниз)
{
дистанция = 2+random(4);
выбрать_напр:
напр = random(4);
switch (напр) {
case 0:
если (ХодилиВлево) goto выбрать_напр;
for i=1 to дистанция
{
если (A[x-2,y]!=#FF или A[x-1,y]!=#FF или
A[x-2,y-1]!=#FF или A[x-1,y-1]!=#FF или
A[x-2,y+1]!=#FF или A[x-1,y+1]!=#FF)
{
ХодилиВлево = да;
goto выбрать_напр;
}
иначе
{
x=x-1; A[x,y] = 0;
дистанция=дистанция-1;
если (дистанция == 0) break; // внутренний for (;;)
}
}
break;
Странная запись. SMT, перепроверь, плз, куда ведут все Break внутри большого Switch. М/б, некоторые из них Continue. А то выходит, что цикл
пока не (ХодилиВлево и ХодилиВправо и ХодилиВверх и ХодилиВниз)
всегда выполняется только 1 раз. Тогда смысл этого цикла?
Странная запись. SMT, перепроверь, плз, куда ведут все Break внутри большого Switchсишный синтаксис. брейки относятся к switch. а так как после него сразу конец цикла, то от замены их на continue ничего не изменится
вот такая жуткая смесь си, паскаля и великого могучего...
ну что, смогёт кто-нить накодить это для windows-графики, чтобы проверить?
Готово. :) Вот архивчик с исходниками и EXE-файлом на случ., если Delphi 6 нету. Оч. интересно на слабых процах при малом лимите времени и если повезёт -- огромные куски массива не вырезаны и остаются монолитной стеной -- самые красивые, но не самые сложные лабиринты. Да, эта проверка переменной Frames в конце алгоритма -- не просто ожидание в 3с. Так как цикл построения вечный, такая проверка позволяет отрегулировать время построения. Ну, нынешним процам на всё-про всё обычно 5мс хватает, а для Z80 это важно! Но алгоритм самый быстрый из того, что я пробовал до сих пор. Обязательно применю и сделаю Лабираторию 2 (Лабиратория 1 -- вариант 2 с подъёмом стенок и проверкой связности. Если кому надо, могу исходник кинуть тут. Или там :) ). Спасибо, SMT.
Допустим, есть лабиринт-дерево. В каких местах надо убрать несколько стенок, чтобы правило правой руки не срабатывало всегда при старте в случ. позиции.
Иными словами, убирается стенка так, чтобы некоторую группу стенок оторвать от общей группы (в лаб.-дереве все стенки соединены). При этом желательно иметь настройки по сложности "отрезанной группы" (чтоб не было отрезанных столбов, к-е за четыре шага обойти можно).
Можно такой способ - право-левой рукой или волной уходим от некоторой клетки рядом со случайной стенкой, ожидая, пока не окажемся в клетке по ту сторону от стенки, которую хотим убрать. Замеряем путь и убираем стенку, если он не меньше минимально допустимого.
Но это м/б медленно. Хотелось бы уметь это делать в время или до построения лабиринта.
а насчёт начального квадрата, почему он кодируется кодом #80, а не #00?
Кстати, понял - чтобы и не стенка, и не проход. Не проход - чтоб из старта не отводить новые пути при случ. поиске начала нового ответвления. Не стенка - чтоб не закрасить его очередным ответвлением.
уже сам понял. если края окантовать кодов #80 и стартовый квадрат переместить в середину, можно генерить лабиринты без циклического зацикливания по краям
без циклического зацикливания по краям
Шутка дня :) :D :v2_yahoo:
Есть идеи насчёт убыстрения алгоритма анти-право/лево-рукоправильных лабиринтов-недеревьев?
не хотел, так получилось :)
Есть идеи насчёт убыстрения алгоритма
не случайно брать искать начало следующей ветки, а брать из списка. только много памяти надо на быстрое вычёркивание и поиск
не случайно брать искать начало следующей ветки, а брать из списка. только много памяти надо на быстрое вычёркивание и поиск
С этим можно побороться за счёт загрузки блока генератора первым, создания 1 лабиринта и затем загрузки в освоб. рабочее место самой игры. В случ. Saboteur, например, или Robin of the Wood - это было бы неплохо. Разные игроки после загрузки могут играть в 1 лабиринт до сброса, а затем он будет совсем другим.
А как список строить? Случайно - это потому, что неизвестно, как специально ( :) )
А как список строить? Случайно - это потому, что неизвестно, как специальноесть несколько идей, не до конца оформившихся и пока не очень простых. возьму ещё немного времени, обычно идеи сами по себе отшлифовываются до нужного состояния
обычно идеи сами по себе отшлифовываются до нужного состояния
Да :)
Есть мысль: после поднятия стенки, при проверке связности подсчитывать путь волны с этой стороны стенки до той (и если подходит по расстоянию - занести в список). После полного построения лабиринта-дерева дополнительно опустить все стенки из списка.
Но для алгоритма из MAZIACS это вроде не подойдёт. :(
Люди!!! Так сделали генератор лабиринтов ? У меня есть. Я еще в 99м писал. Все быстро, компактно. размер от 4х4 до 254х254, 1 вход 1 выход. Только 1 правильный путь, все остальные тупики.
Дак куда давать ? Jerri на мыло ?
Дак куда давать ? Jerri на мыло ?
Атачем на форум, ёмаё! ;)
Так. Генератор нашел. Работет еще :) Но вид постЯдерный. Генерит такие вещи:
Работает ненормально быстро :) 127х127 лабиринт (есть на скриншоте) генерит 7 секунд. Или это медленно ?
Работает ненормально быстро :) 127х127 лабиринт (есть на скриншоте) генерит 7 секунд. Или это медленно ?
Это, сорец хде? =)
Ну вот нахер те сорец, LVD ? Сорец я выложил, говори - нахер?
Ну мой алгоритм, SMT... Или по полочкам ?
Попробуем вспомнить:
Генерится сперва матрица типа
111111111
101010101...
111111111...
101010101
111111111
(вместо 1 - 255)
Потом берется
рнд вход
если справа от входа нет 0 то опять рнд вход
То же для выхода, но в конце, после генерации.
находимся в 0 справа от входа.
рнд верх вниз лево право
Короче... Там есть 3 маркера
0
255 абсолют не проходимо
254
Нужно вспомнить ?
Ну вот нахер те сорец, LVD ? Сорец я выложил, говори - нахер?
Повтыкать, гыгы. Афтар жжош, пешы есчё! =))
LVD! пофтыкал?
SMT! посмотрел ? Алгоритм объяснять ? Я в тетрадке (вчера нашел) размышлял Там все есть.
посмотрел. объяснять не надо. близко к мазиакам
находимся в 0 справа от входа.
рнд верх вниз лево право
Короче... Там есть 3 маркера
0
255 абсолют не проходимо
254
Нужно вспомнить ?
давай все целиком - у тебя лабиринты на картинках непроходимые
Jerri, проходимые лабиринты. Просто там сразу точечка ездит, которой эти лабиринты проходить. Ну и ессно я поездил. Она видна : нехарактерна для узора лабиринта
Jerri, проходимые лабиринты. Просто там сразу точечка ездит, которой эти лабиринты проходить. Ну и ессно я поездил. Она видна : нехарактерна для узора лабиринта
а исходник где? я смотрю редактировал - исходник убивал?
Убивал :) Возвращаю.
ws_mason, jerri, tomCat - подходит по скорости ? Может я ВАШИ игры на базе сего генератора увижу... Ибо свою так и не сделал :(
Ахтунг! (для Jerri)
При запуске проги генерится лабиринтик и ездит от кемпстона точечка, которой можно проходить... И проверить.
Вообще на atari 2600 была такая игра еще года 81го - лабиринтики проходить. Мож кто помнит ? Вот там был ГЕНЕРАТОР! У моего генератора в сравнении с тем есть один минус :( Догадайтесь какой :)
ws_mason, jerri, tomCat - подходит по скорости ? Может я ВАШИ игры на базе сего генератора увижу... Ибо свою так и не сделал
Может быть, хотя не скоро.
Мой генератор я сумел проделать только на PC. Буду править, заменять проверку проходимости "по правилу 1 руки" на проверку волной. Может, что получится. Подробности см. в нач темы. Сорц своего я пока так и не выложил, приаттачу по первому требованию, или просто переведу наконец для Z80 и выложу тогда, когда время будет. Сегодня вот зато СВЕЖИЙ exe наваял -- лабиринты на PC до 513x513 с настраиваемыми вх-вых (вплоть до "где то в середине за X шагов от выхода) и с просмотром процесса построения и оценки расстояний. Впервые волну в лабиринте увидел -- КРАСИИВО. :rolleyes
А насчёт MAZIACS -- где-то в середине темы SMT выписал примерный алгоритм тамошнего генератора, и я приаттачил прогу по нему на DELPHI. Быстрый алгоритм... но какой-то неоптимальный.
Вообще на atari 2600 была такая игра еще года 81го - лабиринтики проходить. Мож кто помнит ? Вот там был ГЕНЕРАТОР!
Плохо знаком с атари, просветите, плз...
У моего генератора в сравнении с тем есть один минус Догадайтесь какой
Ваш пока быстрейший из замеченных, но прямых там вроде многовато. Или однообразных участков...
Однообразных участков много из-за генератора RND.
(просто едет по всей памяти ld hl,0; ld a,(hl); inc hl тупо-тупо и xor с чем-то там). Рассчитано было на то что память выше 25000 не будет чистой, а с игрой :) Так что можно хотя бы по пзу туда-сюда ездить - эффект будет другой. ибо если все время через рнд выбирать направление в чистой памяти...
Думаю, стоит подобрать неплохой участок ПЗУ -- дост. разнообразный. Пусть и небольшой. Б. часть РНДов может считываться оттуда, а время от времени -- вызываться какой-то алгоритм потормознее, к-й выберет новый адрес и направление внутри этого участка. Может, так лучше.
Мой генератор. Соберусь, на Z80 асм переведу.
ws_mason
01.12.2005, 06:35
ws_mason, jerri, tomCat - подходит по скорости ? Может я ВАШИ игры на базе сего генератора увижу... Ибо свою так и не сделал :(
Забил я писать на Спекки игру, я ее он-лайновую делаю, для своей городской сети. С прицелом на коммерцию.
я ее он-лайновую делаю, для своей городской сети. С прицелом на коммерцию.
Сильный стимул. Но я всё ж за freeware трымаюсь.
спорол чепуху. Ранее выложенные Maziacs и в самом деле вроде не работают. А т.к. в этой теме были люди, не слышавшие об этом шедевре-малютке, сюда кладу правильный аттач. (Тот SN плохо с дискеты писал лучше б сразу сказал Disc error).
(вложение MAZIACS.ZIP перемещено на VIRT, 12.6 Кбайт, 13 просмотров на 19 IX 2006)
О! правильно - есть такие люди :) и они благодарствуют :v2_rolley !
Andrew771
31.03.2011, 16:20
у мой алгоритм, SMT... Или по полочкам ?
Попробуем вспомнить:
Генерится сперва матрица типа
111111111
101010101...
111111111...
101010101
111111111
(вместо 1 - 255)
Потом берется
рнд вход
если справа от входа нет 0 то опять рнд вход
То же для выхода, но в конце, после генерации.
находимся в 0 справа от входа.
рнд верх вниз лево право
Короче... Там есть 3 маркера
0
255 абсолют не проходимо
254
Кажется, вот его человеческое описание с примером на ActionScript: http://coderlife.ru/progr/generaciya-labirinta.html
А чтобы сделать лабиринт с комнатами, за элемент лабиринта надо брать не одну клетку, а квадрат из клеток. Вот здесь уже думал: http://zx.pk.ru/showpost.php?p=361787&postcount=87
Там указан алгоритм Прима или Краскала, но это не обязательно, можно любой другой.
---------- Post added at 15:02 ---------- Previous post was at 14:57 ----------
Описания алгоритмов Прима и Краскала с исходниками на Delphi: http://www.piter-press.ru/attachment.php?barcode=978594723853&at=exc&n=0
---------- Post added at 16:20 ---------- Previous post was at 15:02 ----------
А вот еще такую статью нашел в ZX Review: http://zxpress.ru/article.php?id=1782
Там приведены несколько алгоритмов на Бейсике и один на ассемблере!
тебе нужен этот генератор в виде сорцов?
Andrew771
31.03.2011, 17:11
тебе нужен этот генератор в виде сорцов?
да. Мне этот алгоритм больше всего нравится по простоте и быстродействию.
ну как домой доберусь теперь - на работе нету
Добавил
будут вопросы - задавай
Прога сия написана Знахарем
моё в ней только кой какие косметические изменения
Andrew771
31.03.2011, 17:22
ОК, спасибо тебе заранее! :)
Andrew771
27.04.2011, 17:04
Прога сия написана Знахарем
моё в ней только кой какие косметические изменения
Попробовал компильнуть - не хватает двух процедур. :(
Написал свой генератор на этом же принципе для PC, в котором можно побаловаться параметрами генерации, см.файл. Найду оптимальные и сконвертану в ассемблер.
Каждый уважающий себя геймдевелопер должен написать свой генератор лабиринтов (;
С большой ностальгией просматривал топик. :v2_dizzy_heart:
От себя хочу сказать. Генерация лабиринтов - достаточно простая задача, если усвоить основные принципы. Но после этого не нужно останавливаться. Лабиринты вида Прима-Краскала - это только начало.
Любая генерация происходит для конкретной задачи. Например посмотрим на лабиринты, прошедшие в Google AI Challenge (http://ants.aichallenge.org/specification.php#map_generators). Их условия:
Maps are limited to 2 to 10 players
Maps must be symmetric
Hills must be between 20 and 150 steps away from other enemy hills (friendly hills can be closer)
Hills may not be within close range, euclidean distance no less than 6
Must be a path through all hills traversable by a 3x3 block
Maps must not contain islands
Maps are limited to at most 200 in each direction
Maps are limited in area to 900 to 5000 area per player, with a total area limit of 25,000.
Один из них: http://ants.aichallenge.org/map.php?map=maze/maze_p04_47.map
Он очень непохож на Прима-Краскала. В основном из-за 3х3 блоков, но не только.
Это пример того, что лабиринты бывают очень разные, и делаются они под конкретный геймплей.
И, чтобы не останавливаться, могу предложить следующие лабиринты (для воображения, а не для реализации):
1. Бесконечный лабиринт. Т.е. такой, прохождение которого для игрока требует времени, намного превышающего время его жизни. (геймплей же не обязательно требует бесконечного времени)
2. Динамический лабиринт. Лабиринт меняется в процессе игры, и делает это так, что его свойства сохраняются (например один и только один путь
из любой точки А в точку B).
3. Карта звезд ELITE. Это лабиринт. Лабиринт, в котором из одной звезды (узел графа) в другой можно попасть только тогда, когда расстояние <= 7.0 ly
goblinish
25.06.2012, 07:14
Каждый уважающий себя геймдевелопер должен написать свой генератор лабиринтов (;
не геймдевелопер, но...
нашел в архивах интро на 256 байт для ЦЦ, алгоритм из SWAG'a
Andrew771
26.06.2012, 10:59
Мой генератор для ZX Spectrum, позволяющий автоматически кодировать лабиринт в ассемблер: http://zx.pk.ru/showthread.php?t=15939
Powered by vBulletin® Version 4.2.5 Copyright © 2024 vBulletin Solutions, Inc. All rights reserved. Перевод: zCarot