Недавно я часто смотрю, как мои одноклассники играют в лабиринт в компьютерной комнате. Это довольно интересно. Я также использую Java для написания алгоритма для реализации случайных генераций лабиринтов. На самом деле, это алгоритм пересечения глубины для графика. Основная идея заключается в том, что в каждом точке лабиринта есть четыре стены, а затем.
1. Начальный доступ из любой точки (мой алгоритм зафиксирован для запуска с точки (0,0)) и посетите случайное одно из четырех направлений (каждый раз, когда вы получаете доступ к доступной точке, удалите стену в этом направлении этого точки), и доступная точка продолжает получать доступ к нему в этом направлении.
2. Каждая точка посещения идентифицируется как доступ. Когда точка получает доступ к определенному направлению, мы сначала определим, доступна ли доступ к точке, доступ к границе. Если все четыре направления точки были доступны или не могут получить доступ, вернитесь к предыдущему пункту. Предыдущий пункт продолжает процесс.
После прохождения таким образом можно подтвердить, что каждая точка была посещена. Более того, поскольку направление каждого доступа является случайным, будет сформировано много разных ситуаций обхода. В то же время путь между каждыми двумя точками уникален, который образует другой лабиринт, и есть только уникальный путь от начальной точки до конечной точки. Это определяется характеристиками алгоритма обхода глубины графика. В реализации алгоритма главное - использовать стек. В первый раз сначала нажмите первую точку в стеке. Каждый раз, когда обращается к точке, точка вставляется в стек, мы затем случайным образом получают доступ к точке в верхней части стека в четырех направлениях, получают доступ к новой точке, а затем нажимаем новую точку. Как только четыре направления этой точки недоступны, дайте точке уйти из стека, а затем получить доступ к четырем направлениям в верхней части стека и т. Д. До тех пор, пока все точки на выходе из стека, наше обход будет успешным. Это рекурсивный процесс. Этот алгоритм может быть естественно реализован рекурсивными методами. Тем не менее, я делаю это здесь, но вручную реализую его с массивом в качестве стека. Ха -ха ~~, сказав так много, я не знаю, выражается ли то, что я хочу выразить. Тем не менее, я чувствую, что мой конкретный дизайн кода не очень хорошо написан, и есть еще много мест, где не хватает улучшения и оптимизации. Это просто для упражнения алгоритма. Ниже приведены основные коды двух ключевых классов. Что касается кода уровня презентации, я не буду публиковать их, потому что они очень тривиальны.
Вот рендеринг:
Класс лабиринта:
// Автор: Zhongzw // Электронная почта: [email protected] Пакет CN.Zhongzw.model; импортировать java.util.arraylist; импортировать java.util.random; открытый класс mazemodel {private int width = 0; частный int height = 0; частное случайное rnd = new Random (); public mazemodel () {this.width = 50; // ширина лабиринта this.height = 50; // высота лабиринта} public int getWidth () {return ширина; } public void setwidth (int width) {this.width = width; } public int getheight () {return Height; } public void setheight (int height) {this.height = height; } public mazemodel (int width, int height) {super (); this.width = ширина; this.height = высота; } public ArrayList <MazePoint> getMaze () {ArrayList <MazePoint> maze = new ArrayList <MazePoint> (); for (int h = 0; h <height; h ++) {for (int w = 0; w <width; w ++) {mazepoint point = new mazepoint (w, h); Maze.Add (точка); }} вернуть CreateMaze (Maze); } private ArrayList <MazePoint> createMaze (ArrayList <MazePoint> Maze) {int top = 0; int x = 0; int y = 0; ArrayList <mazepoint> team = new Arraylist <mazepoint> (); team.add (maze.get (x + y * width)); while (top> = 0) {int [] val = new int [] {-1, -1, -1, -1}; int times = 0; логический флаг = false; Mazepoint pt = (mazepoint) team.get (top); x = pt.getx (); y = pt.gety (); pt. -quisted = true; ro1: while (times <4) {int dir = rnd.nextint (4); if (val [dir] == dir) продолжить; else val [dir] = dir; Switch (dir) {case 0: // Left if ((x - 1)> = 0 && maze.get (x - 1 + y * width). Maze.get (x - 1 + y * width) .setright (); team.add (maze.get (x - 1 + y * width)); top ++; flag = true; сломать RO1; } перерыв; Случай 1: // right if ((x + 1) <width && maze.get (x + 1 + y * width). maze.get (x + 1 + y * width) .setleft (); team.add (maze.get (x + 1 + y * width)); top ++; flag = true; сломать RO1; } перерыв; случай 2: // if ((y - 1)> = 0 && maze.get (x + (y - 1) * width). Maze.Get (x + (y - 1) * ширина) .setDown (); team.add (maze.get (x + (y - 1) * ширина)); top ++; flag = true; сломать RO1; } перерыв; Случай 3: // ниже if ((y + 1) <height && maze.get (x + (y + 1) * width). Maze.Get (x + (y + 1) * ширина) .setUp (); team.add (maze.get (x + (y + 1) * ширина)); top ++; flag = true; сломать RO1; } перерыв; } times += 1; } if (! flag) {team.remove (top); Верх -= 1; }} return Maze; }}
лабиринт
// Автор: Zhongzw // Электронная почта: [email protected] Пакет CN.Zhongzw.model; Импорт java.util.*; импортировать java.lang.*; открытый класс MazePoint {private int Left = 0; private int right = 0; private int up = 0; private int down = 0; частный int x; частный инт; Публичный логический свидетелем; public mazepoint (int x, int y) {this.x = x; this.y = y; } public int getleft () {return Left; } public void setleft () {this.left = 1; } public int get getright () {return right; } public void setright () {this.right = 1; } public int getUp () {return up; } public void setup () {this.up = 1; } public int getDown () {return Down; } public void setdown () {this.down = 1; } public int getx () {return x; } public void setx (int x) {this.x = x; } public int gety () {return y; } public void sety (int y) {this.y = y; }}
Выше всего содержание этой статьи. Я надеюсь, что это будет полезно для каждого обучения, и я надеюсь, что все будут поддерживать Wulin.com больше.