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

Question

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

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

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

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

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

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

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

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

You can check what I've done so far in this link.

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

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

Answer 1

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

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

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

Answer 2

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

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

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

Answer 3

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

Похоже, что это взяло его maze generation algorithm из Википедии.

Answer 4

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

Code for Dungeon.java

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

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

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

Tyrant screenshot http://www.freeimagehosting.net/uploads/af45502c9c.png

Answer 5

Википедии есть большая статья на Maze generation algorithms

Answer 6

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

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

Answer 7

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

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

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

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