Меня заинтересовала эта тема. Есть сцнарий игры про лабиринт как таковой но некогда писать.
Вид для печати
Меня заинтересовала эта тема. Есть сцнарий игры про лабиринт как таковой но некогда писать.
Лабиринт по второму варианту это самое оно для моей игры. Если интересно кому могу выложить всю концепцию.
Выкладывай, но в целях антифлейма лучше рядом отд. тема :) . Имхо.Цитата:
Сообщение от ws_mason
А если тебе надо помочь с генератором, обращайся, у меня 2-3 варианта есть, вот только хотелось бы ЕЩЁ поскоростнее (чем эти мои варианты). Поэтому и создал тему.
если ещё подумать, можно предложить делить карту на несколько частей извилистыми линиями, в каждой замкнутой области строить свой лабиринт (ведь время построения зависит от площади нелинейно и быстрее создать 4 по 16 клеток, чем 1 из 64) и сломать по одной из стен в изначальной линии между подчастями, чтобы соединить лабиринты в один
а вот что получится, если дальше развить эту идею. пусть каждая клетка может быть в одном из множеств А или Б. клетки из А - те, которые внутри лабиринта, Б - внешние для лабиринта. алгоритм простой: ставим все возможные стенки на поле. одну любую клетку включаем в А, остальные - в Б
шаг1. выбираем случайно одну клетку из Б, граничащую с некоторой клеткой из А (можно наоборот). стираем между ними стенку, перемещаем клетку из множества Б а А. повтор шага 1, пока Б не пусто
можно поделить клетки на 3 множества (внешние, строго внутренние и внутренние, но пограничные). тогда нужно выбирать лишь из пограничных клеток, и не надо повторно перебирать клетки, которые уже давно внутри лабиринта (если у клетки нет подходящих соседей, сразу переводим её в "мёртвое" множество). увы, немного усложняется алгоритм
Это неправильный алгоритм. Есть более другой, и хотя лабиринты с ним получаются может чуток менее "крутыми", но зато работает он сильно быстрее.Цитата:
Сообщение от TomCaT
По порядку - если Ваш вариант с мн-вами А и Б служит как бы для "расширения данного лабиринта в произвольном направлении" (как я понял), то как вы собираетесь организовывать незабвенные тупики?Цитата:
Сообщение от SMT
Вариант 3 - алгоритм реально не намного сложнее. Выяснить периметр в матрице комнат лабиринта не очень сложная задача (то же правило правой руки в комнате сложной формы без внутренних препятствий).
Ну, Вы на этот алгоритм хоть намекните, хоть принцип, а там уже люди сравнят и решат. Просто-напросто этот "неправильный алгоритм" -- единственный, который я знаю (и про который знаю, что он РАБОТАЕТ).Цитата:
Сообщение от Sinus
подскажите к-л быстрый способ определения связности. Фактически, в моей проге на писи всё по вашему алгоритму, но связность - по правилу правой руки - самая муторная, сложная и времежрущая часть. Может, можно не обходить после каждой стенки пол-лабиринта?Цитата:
Сообщение от SMT
сделаю маленький пример, лабиринт 3x3, 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|
+-+-+-+
разве не получились тупики?Код:+-+-+-+
|1 2 3|
+-+-+ +
|4 5 6|
+ + + +
|7|8|9|
+-+-+-+
кроме того, при соотв. выборе ГСЧ, получается произвольный заранее заданный лабиринт, как и в Вашем алгоритме. они делают примерно одинаковые лабиринтыКод:+-+-+-+
| |
+-+-+ +
| |
+ + + +
| | | |
+-+-+-+
это ещё не связность, а лишь наличие пути между двумя точками :) его тут достаточно. да и обход по руке будет более оптимален, чем обходы в глубину или ширину. кажется, тут уже ничего алгоритмически не сделаешь, нужно думать, как оптимально накодить обход по правой руке (ну, или алгоримт с А-Б заюзать)Цитата:
связность - по правилу правой руки - самая муторная, сложная и времежрущая часть
Да, я понял. Вы действуете с А и Б в пределах одного прямоугольника. Действительно, м/б быстрее. Я всё же думаю, MAZIACS сей алгоритм не применяли, а там лабиринты О-ГО-ГО какие качественные. Хотя может, я ошибаюсь...Цитата:
Сообщение от SMT
Нет. В моём алгоритме не используется ГСЧ. На самом деле предварительно составляется список всех поднимаемых стенок, а затем список "рассортировывается" по ГСЧ, который сложным образом зависит от дата/времени. Т.о. повторяемость лабиринтов минимальна. Но это на IBM. Для Спекки такое малоприменимо. Разве что подсчитывать время, в течение которого юзер разглядывает меню, а затем использовать как SEED :)Цитата:
кроме того, при соотв. выборе ГСЧ, получается произвольный заранее заданный лабиринт, как и в Вашем алгоритме. они делают примерно одинаковые лабиринты
Тогда объясните, что вы понимаете под проверкой связности. И почему путь между двумя точками (если эти две точки - в комнатах по обе стороны только что поднятой стенки) не указывает однозначно на наличие/отсутствие связности?Цитата:
Это ещё не связность, а лишь наличие пути между двумя точками :) его тут достаточно. да и обход по руке будет более оптимален, чем обходы в глубину или ширину. кажется, тут уже ничего алгоритмически не сделаешь, нужно думать, как оптимально накодить обход по правой руке (ну, или алгоримт с А-Б заюзать)
2All:
как и обещал, высылаю выдранный из MAZIACS генератор. Не удосужился дебаггнуть. Если кто-то хочет его использовать, но не знает как, пишите мне на мыло или сюда, я раскопаю свой Labirint на BASIC'е и припомню вх./вых. параметры процедурки.