Создание 3D лабиринта на Java

Question

Цель

---

Я создаю программу, которая генерирует 3D-лабиринт, и у меня возникли некоторые проблемы с алгоритмом создания.Для простоты взаимодействия это будет прямоугольная призма с одним входом и одним выходом.

Алгоритм

---

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

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

Вопрос

---

Пока я думаю, у меня есть основная идея алгоритма, но я не знаю, как его кодировать. Может кто-нибудь придуматьАлгоритм Java для этого, который выполняет задачу относительно быстро?

Решение не должно использовать внешние библиотеки.

Answer 1

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

В качестве примерадавайте предположим, что у нас есть двумерная сетка ячеек (которую я могу визуализировать с использованием ASCII-графики!), которая выглядит следующим образом:

*---*---*---*
|   |   |   |
*---*---*---*
|   |   |   |
*---*---*---*
|   |   |   |
*---*---*---*

Мы можем представить это как график, в котором каждая ячейка является вершинойи каждое из соединений между ячейками является ребром.Наша цель - найти какое-то дерево, которое соединяет все узлы.Если мы сделаем это, то все ячейки будут доступны друг от друга (потому что дерево связно), но циклов нет (потому что дерево является минимально связным графом).Есть много разных деревьев, которые мы могли бы использовать;например, вот одно дерево:

*---*---*---*
|   |   |   |
*   *   *   *
|   |   |   |
*   *   *   *
|   |   |   |
*   *   *   *

А вот другое:

*   *---*   *
|   |   |   |
*---*   *   *
        |   |
*---*---*---*
    |       |
*---*   *---*

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

Еще один подход, который обычно используется для создания лабиринтов, состоит в том, чтобы уменьшить его допроблема нахождения минимального остовного дерева графа.В частности, предположим, что вы создаете граф, где каждая ячейка является узлом со ссылками на каждого из своих соседей.Выберите случайные веса для каждого из ребер, а затем создайте минимальное остовное дерево для графа.Это дерево не имеет циклов, и существует уникальный путь от каждого узла к каждому другому узлу, что означает, что лабиринт имеет уникальное решение.Более того, алгоритм очень эффективен - в трехмерном кубе размером nxnxn у вас есть O (n ³ ) узлов, O (n ³ ) ребер, и вы можете найтиMST за O (n ³ lg n) с использованием алгоритма Прима или алгоритма Крускала .Они также производят высококачественные лабиринты, хотя их свойства сильно отличаются от лабиринтов, созданных с помощью рандомизированного поиска в глубину.

Надеюсь, это поможет!