Recently, I often watch my classmates playing a maze game in the computer room. It's quite interesting. I also use Java to write an algorithm to implement random generation of mazes. In fact, it is a depth-first traversal algorithm for a graph. The basic idea is that every point in the maze has four walls, and then.
1. Start access from any point (my algorithm is fixed to start from point (0,0)), and visit a random one of the four directions (every time you access an accessible point, remove the wall in that direction of that point), and the accessed point continues to access it in this direction.
2. Each visited point is identified as accessed. When a point accesses a certain direction, we will first determine whether the accessed point has been accessed or touches the boundary. If all four directions of the point have been accessed or are unable to access, return to the previous point. The previous point continues the process.
After traversal in this way, it can be confirmed that each point has been visited. Moreover, since the direction of each access is random, many different traversal situations will be formed. At the same time, the path between each two points is unique, which forms a different maze, and there is only a unique path from the beginning point to the end point. This is determined by the characteristics of the depth traversal algorithm of the graph. In the implementation of the algorithm, the main thing is to use the stack. The first time, first press the first point into the stack. Every time a point is accessed, the point is pushed into the stack, we then randomly access the point at the top of the stack in four directions, access the new point, and then press the new point in. Once the four directions of this point are inaccessible, let the point withdraw from the stack, and then access the four directions of the point at the top of the stack, and so on. Until all the points in the stack exit, our traversal will be successful. This is a recursive process. This algorithm can naturally be implemented by recursive methods. However, I do this here, but manually implement it with an array as the stack. Haha~~ After saying so much, I don’t know if what I want to express is expressed. However, I feel that my specific code design is not well written, and there are still many places where there is a lack of improvement and optimization. It is just to be an algorithm exercise. The following are the core codes of the two key classes. As for the code of the presentation layer, I will not post them because those are very trivial.
Here is the rendering:
Maze class:
//Author: zhongZw //Email: [email protected] package cn.zhongZw.model; import java.util.ArrayList; import java.util.Random; public class MazeModel { private int width = 0; private int height = 0; private Random rnd = new Random(); public MazeModel() { this.width = 50; //Maze width this.height = 50; //Maze height} public int getWidth() { return width; } 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 = width; this.height = 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(point); } } return 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; boolean flag = false; MazePoint pt = (MazePoint) team.get(top); x = pt.getX(); y = pt.getY(); pt.visted = true; ro1: while (times < 4) { int dir = rnd.nextInt(4); if (val[dir] == dir) continue; else val[dir] = dir; switch (dir) { case 0: // left if ((x - 1) >= 0 && maze.get(x - 1 + y * width).visted == false) { maze.get(x + y * width).setLeft(); maze.get(x - 1 + y * width).setRight(); team.add(maze.get(x - 1 + y * width)); top++; flag = true; break ro1; } break; case 1: // right if ((x + 1) < width && maze.get(x + 1 + y * width).visted == false) { maze.get(x + y * width).setRight(); maze.get(x + 1 + y * width).setLeft(); team.add(maze.get(x + 1 + y * width)); top++; flag = true; break ro1; } break; case 2: // if ((y - 1) >= 0 && maze.get(x + (y - 1) * width).visted == false) { maze.get(x + y * width).setUp(); maze.get(x + (y - 1) * width).setDown(); team.add(maze.get(x + (y - 1) * width)); top++; flag = true; break ro1; } break; case 3: // below if ((y + 1) < height && maze.get(x + (y + 1) * width).visted == false) { maze.get(x + y * width).setDown(); maze.get(x + (y + 1) * width).setUp(); team.add(maze.get(x + (y + 1) * width)); top++; flag = true; break ro1; } break; } times += 1; } if (!flag) { team.remove(top); top -= 1; } } return maze; } }
maze
//Author: zhongZw //Email: [email protected] package cn.zhongZw.model; import java.util.*; import java.lang.*; public class MazePoint { private int left = 0; private int right = 0; private int up = 0; private int down = 0; private int x; private int y; public boolean witnessed; 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 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; } }
The above is all the content of this article. I hope it will be helpful to everyone's learning and I hope everyone will support Wulin.com more.