6

Я бы хотел реализовать генерацию трехмерного лабиринта, что-то вроде этого

картинка

Ничего путного по этой теме найти не удалось. Есть у кого идеи на эту тему?

3
  • Как то нет желания переходить на неизвестные ссылки. Опишите что это за лабиринт и какие наработки у вас уже есть. Исходя из этого появится возможность Вам помочь. К тому же ссылки извне часто "умирают" - вопрос будет просто хламом и никому от этого пользы не будет.
    – V.March
    3 дек 2017 в 20:26
  • это просто картинка. Ну смотрите есть 2-х мерные лабиринты и алгоритмов их генерации полно: en.wikipedia.org/wiki/Maze_generation_algorithm а есть 2-х мерные в виде куба, наработок нет никаких, делал когда-то давно 2-мерный лабиринт методом Recursive backtracker. Поищите в гугле 3d maze puzzle, там есть картинки головоломок с такими вот лабиринтами. 3 дек 2017 в 20:32
  • Ну так алгоритмы разве не те же?
    – vp_arth
    3 дек 2017 в 20:54

2 ответа 2

6

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

Определение. Лабиринтом на плоскости будем называть связный неориентированный граф без петель, у каждой вершины которого не более 4 ребёр.

Довольно легко провести аналогию решётки-лабиринта nxm и лабиринта. Как это сделать? Достаточно рассмотреть клетку и заметить, что у каждой клетки есть 4 соседа (не берём граничные случаи):

Пример решётки и соседей клетки

Теперь можно убрать, например, одного соседа. Обычная ситуация в лабиринте:

Пример решётки и соседей клетки

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

Вообще говоря, для порождения самого лабиринта, строить граф в явном виде не обязательно. Я лишь заострил внимание на этом, дабы дать волю Вашей фантазии. Построение графа может быть полезно при более детальном изучении вопроса. Вам может быть важно, чтобы лабиринт обладал какими-нибудь свойствами. Может быть Вам захочется ввести некую "плотность" или разветвлённость лабиринта. В таком случае на помощь могут прийти именно графы.

Определение. Границей решётки или просто границей назовём такую вершину, координата которой на решётке равна: (x, m), или (n,x), или (1,x), или (n,x), где х -- любое число из промежутков [1,n] или [1,m].

Теперь же, перейдём к генерации лабиринта. Сделаем это так. Зададим матрицу nxm. Выберем одну точку на одной из границ. После этого запустим из этой точки обход в глубину в пределах решётки.

Для каждой точки лабиринта будем по очереди выбирать каждое из 4х направлений и случайным образом, с вероятность p, принимать решение, есть ли проход в этом направлении или его нет. Будем его выполнять до тех пор, пока суммарное количество точек на границе будет не более k. Как только это произойдёт, мы прекращаем наше выполнение действий.

Делая действия таким образом, можно получить очень неравномерный лабиринт. Поэтому можно критерий останова чуть-чуть изменить. Будем его выполнять процесс до тех пор, пока суммарное количество точек на границе будет не более k и на каждой из границ (всего границы, разумеется, 4), будет не менее k_i точек.

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

Таким образом мы построили алгоритм генерации лабиринта с параметрами: k, k_i (4 шт), p, d.

Советую обратить внимание на такую вещь как теория перколяции. В этой теории реализуется процесс, который я описал выше.

У меня валяются три реализации перколяционного процесса на питоне, матлабе и плюсах. Вы можете на них взгялнуть здесь: 1, 2, 3

8
  • не ясно откуда "без петель" условие. Не все 2D алгоритмы на 3D переносятся.
    – jfs
    6 дек 2017 в 9:10
  • @jfs данный алгоритм переносится легко. В чем непонятки с мигрированием в 3D? Без петель связано с тем, что при отображении графа на решётку, возникнет вопрос, во что переходить петле? 6 дек 2017 в 9:16
  • "Трёхмерный во всех его вариациях строится ровно так же" можно воспринять что любой 2D алгоритм в 3D переносится легко (что не так). Под "без петель" я [неверно] воспринял "без циклов" (перевёл как cycle а нужно было как loop). Цикл длины один (петля, self-loop) действительно для простых лабиринтов смысла не имеют и они обычно не упоминаются.
    – jfs
    6 дек 2017 в 9:45
  • @jfs те модификации построения лабиринтов, которые я описал, построить несложно для размерности n. Кроме того, автор хочет построить не 3х мерный лабиринт, а 6 двумерных, которые соединяются по границам друг с другом. Это также легко сделать. Я имел ввиду именно это, написав фразу "Трёхмерный во всех его вариациях строится ровно так же" 6 дек 2017 в 10:19
  • да я на самом деле уже разобрался, просто не было ответа, чтобы закрыть вопрос. я в математике не силен, особенно в теории графов, поэтому не был уверен что из 2д в 3д получится перенести. Сделал реализацию на c# и рисую в юнити, использовал метод recursive backtracker, если кому интересно будет, могу на гит закинуть. 6 дек 2017 в 13:35
0

Самое простое что может придти в голову, это генерировать 3 мерный массив через Random(), если писать на Java.

        int n = 10;

        int[][][] arr = new int[n][n][n];

        for (int i=0; i<n; i++){

            for (int j=0; j<n; j++){

                for (int k=0; k<n; k++){

                    Random random = new Random();
                    Integer r = random.nextInt(2);
                    if (r != 0) {
                        arr[i][j][k] = 1;
                    }else{
                        arr[i][j][k] = 0;
                    }

                }

            }
        }

Если один, то есть проход, иначе нет прохода. На счет отрисовки его в 3d модели зависит от того на чем вы пишите, на Java можно использовать jPCT.

2
  • 3
    Это не лабиринт, а просто кубик с непроходимыми клетками. Путь в лабиринте должен быть связным и, скорее всего, с единственным входом и единственным выходом.
    – Qwertiy
    3 дек 2017 в 20:45
  • 1
    Согласен, тогда в начале можно сгенерировать рандомный путь например от ячейки [0][0][0] до ячейки [n-1][n-1][n-1].Случайно выбирается один путь из 6(вверх, вниз, вправо, влево, вперед, назад), естественно с учетом границ массива и идем до тех пор пока мы не окажемся в последней ячейки, это будет гарантировать, что в лабиринте есть выход, а после через тот же рандом путаем его, как в алгоритме выше, при этом не перекрывая ячейки правильного пути.
    – Kotysh
    3 дек 2017 в 20:56

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.