Представляем генератор лабиринтов [Java]

Это проект, который я сделал для предметных структур данных в моем университете.

Его название в значительной степени описывает его, он генерирует случайные лабиринты, а его основным логическим ресурсом является алгоритм Олдоса-Бродера .

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

Алгоритм Олдоса-Бродера

Алгоритм Олдоса-Бродера работает исключительно для генерации лабиринта, он использует матрицу для создания путей. Упрощенный, это алгоритм:

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

Вы можете увидеть полное объяснение и демонстрацию в реальном времени здесь .

Проверка ячеек

Мы проверяем каждую ячейку, устанавливая точку с ее координатами, мы соединяем каждую точку, чтобы создать маршрут. Чтобы проследить этот маршрут, у нас должна быть запись о том, где мы были, поэтому мы создаем два 2D-массива ( starts и заканчивается ).

Давайте посмотрим на краткий пример:

Шаг 1 (случайный выбор начальной ячейки)

Сохраните эту позицию в starts

Шаг 2 (случайный выбор соседней ячейки)

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

Шаг 3 (повторяйте шаг 2 до тех пор, пока не будет проверена каждая ячейка)

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

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

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

Это больше похоже на правду.

Это код, который рисует лабиринт, я просто дам вам JPanel:

package interfazgrafica;

import javax.swing.*;
import java.awt.*;

class MazeIterfacePanel extends JComponent{ // JPANEL

    private int dims, thickness, margin;

    public MazeInterfacePanel(int dims, int thickness, int margin){
        this.dims = dims;
        this.thickness = thickness;
        this.margin = margin;
    }

    public void paintComponent(Graphics g){

        super.paintComponent(g);

        Graphics2D g2 = (Graphics2D) g;
        BasicStroke stroke = new BasicStroke(thickness);
        g2.setStroke(stroke);
        int j = 0;

        for (int i = 0; i < dims*dims; i++) { 
            g2.drawLine(Labyrinth.starts[i][j] * (500/dims) + margin, 
                        Labyrinth.starts[i][j+1] * (500/dims) + margin, 
                        Labyrinth.ends[i][j] * (500/dims) + margin, 
                        Labyrinth.ends[i][j+1] * (500/dims) + margin);
        }
    }     
}

Рисунок выполнен с помощью DrawLine функция из java.awt. Graphics класс, он принимает четыре параметра: первые два – начальная точка линии, остальные – конечная точка. Я позиционирую эти точки, используя пиксели в качестве единицы измерения, я использую dims , чтобы уменьшить коэффициент преобразования 500 пикселей: скажем, размеры лабиринта равны 50×50, затем dims . Кроме того, JPanel создается с особым штрихом и отступом в зависимости от размеров. Все это – то, что заставляет наши лабиринты занимать одно и то же пространство, и помните наши старты и заканчивается массивами? Вот где мы их используем.

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

Вот как выглядят некоторые настоящие случайные лабиринты:

10×10

20×20

50х50

100х100

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

Эпилог

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

Это мой первый актуальный пост, и все ваши замечания приветствуются в комментариях.

Изображение на обложке из Страны грез

Оригинал: “https://dev.to/marksasp95/introducing-maze-generator-java-320g”