Лучшая логика для создания (истинного) случайного лабиринта

Question

Я пытался сделать небольшую простую игру, чтобы просто проверить мою логику, и это простой лабиринт, он уродлив и до сих пор отстой.

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

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

Если вы не заметили, это ОЧЕНЬ глупый способ создания моего случайного лабиринта по следующим причинам:

1 - Это может получиться очень легко (гигантские острова полаили несколько стен вместе, образующих только один чрезвычайно видимый путь, создающий тупой (хотя и действительный) лабиринт
2 - Это потенциально самый быстрый способ создания идеального случайного лабиринта КОГДА-ЛИБО, нов то же время он потенциально самый медленный и занимает столько времени, сколько ... бесконечно. Эта разница заметна еще больше, когда я устанавливаю сетку на 30x30 или более (когда что-то не переполняется)
3 - Это глупо и оскорблять саму логику.

В своей защите я не планировал делать так с самого начала, как описано, одна вещь привела к другой.

Итак, я начал думать о способах сделать красивый (полный путей, хитрый и выигрышный) лабиринт, затем я подумал о создании крошечных маленьких (скажем) блоков 5x5 с предварительно разработанными входами и монтированиемони вместе таким образом, что это подходит, но это пошло бы вразрез с моим истинным случайным желанием, а также моим нежеланием рисовать его вручную.

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

Вы можете проверить, что я уже сделал по этой ссылке.

Примечание: я не собираюсь наносить вред чьему-либо компьютеру.
Первый, кто откроет его, прокомментируйте здесь, говоря, что это безопасно. - Готово (спасибо, Jonno_FTW)
Если вы все еще не доверяете нам,Виртуальная машина.

ОБС: Я знаю, что это не лучший способ что-либо разработать.Мне нужен хороший игровой движок, бла-бла-бла, для меня это был какой-то вызов.

Answer 1

Вот обширный веб-сайт, посвященный лабиринтам: http://www.astrolog.org/labyrnth/algrithm.htm

Объясняет, какие существуют типы лабиринтов, рассказывает об алгоритмах генерации и алгоритмах решения, имеет много интересных картинок.

Answer 2

Я сделал поколение лабиринтов. Вы не хотите размещать вещи случайно и проверять. Вместо этого вы генерируете его из начальной точки.

Выберите отправную точку, двигайтесь в случайном направлении. Есть случайная вероятность выбора нового направления. Никогда не двигайтесь в занятую клетку, если вы натолкнетесь на нее, текущая тропа заканчивается. Если текущая тропа заканчивается, выберите квадрат, который вы уже посетили, выберите новое направление и совершите случайную прогулку, как вы сделали для первого. Повторяйте, пока лабиринт не станет настолько полным, насколько вы хотите.

Вероятность изменения направления должна быть входным параметром, поскольку он имеет большое значение. Обратите внимание, что если вы делаете 3D-лабиринт, шансы вертикального поворота должны быть намного ниже, чем шансы горизонтального перемещения.

Answer 3

Посмотрите на исходный код в моей игре на Roguelike, Тиран:

Код для Dungeon.java

Существует множество различных методов генерации карт, используемых для создания разных типов уровней. Но самый простой шаблон заключается в следующем:

1. Начните с пустой карты
2. Создать одну случайную комнату / открытое пространство на карте
3. Случайно выберите плитку на краю открытой в данный момент области
4. Попытка "вырастить" коридор или комнату случайным образом из этого пространства (если оно не подходит, ничего не делать)
5. Возвращайтесь к шагу 3 столько раз, сколько вам нужно, чтобы создать приличный лабиринт
6. Наконец, пройдите по всей карте и преобразуйте оставшееся свободное пространство в стены

Вот скриншот того, что вы получаете (посмотрите на мини-карту из структуры лабиринта):

Скриншот Тирана http://www.freeimagehosting.net/uploads/af45502c9c.png

Answer 4

В Википедии есть отличная статья о алгоритмах создания лабиринта

Answer 5

Ваш вопрос заставляет меня задуматься о программе XScreensaver Maze .Посмотрите на скриншоты , чтобы увидеть, является ли это желаемым эффектом.

Похоже, он взял алгоритм генерации лабиринта из Википедии.

Answer 6

На самом деле есть трюк, который Эл Лоу использовал для одной из своих игр «Leisure Suit Larry» (я считаю, что LSL 3).

По сути, он создал лабиринт бамбукового леса, который игрокпришлось ориентироваться.Однако вместо того, чтобы создавать отдельный «квадрат» лабиринта для каждого экрана, он просто «перевернул» уже созданный им экран и зашел в тупик, заблокировав различные входы одним изображением «бамбуковой стены».

Возможно, вы могли бы сделать то же самое: сделать так, чтобы генератор вырезал действительный лабиринт, а затем приказал ему разместить тупиковые блоки вдоль некоторых путей.Это гарантировало бы наличие хотя бы одного действительного открытого пути к «финишной черте», а также не позволяло игрокам просто прогуливаться по супер-простому макету.

Это также сделает лабиринт 30х30 большеработоспособным, поскольку компьютеру не нужно будет проверять каждый квадрат сетки на 900 квадратов на достоверность.

Answer 7

То, как вы создадите случайный лабиринт, будет зависеть от того, как вы хотите, чтобы он выглядел. Если вы создаете что-то, предназначенное для множества тупиков, то вы можете просто «случайным образом» проследить путь от начальной точки до конечной точки, а затем случайным образом заполнить пустые места, по существу вырезая путь из сплошной блок материала. Например. представьте, у вас была каменная табличка. Первым шагом будет прохождение пути «решения». Тогда ты пойдешь и сделаешь все тупики.

Если вы хотите что-то более «игровое», чем «головоломка», то, вероятно, стоит создать кучу фрагментов, которые по-разному сочетаются друг с другом. Это то, как игры Diablo сделали это, насколько я могу судить; ряд заранее разработанных «наборов» и правил о том, как они сочетаются друг с другом. Вы пометите четыре стороны блока такими вещами, как «три открытых пространства, за которыми следуют два закрытых», а затем, если другой фрагмент также имеет соответствующее описание, их можно соединить вместе.

После этого все, что вам нужно сделать, это выяснить, как вы можете последовательно отображать «случайное» поведение.