origin:
Last year (first semester of junior high school), I liked to write small games, so I wanted to try writing a maze.
Program effects:
Press space to display the path:
Thinking process:
The maze consists of grids, requiring only one path from the entrance to the exit.
After thinking about various data structures, it seems that trees are more suitable, with only one path from the root node to each child node. Assuming that the entrance is the root node and the exit is a child node in the tree, then the path from the root node to the child node is definitely unique.
So if a tree can be constructed to cover all the grids, a maze can be created.
In addition, it is required that the parent and child nodes of the tree must be adjacent grids on the interface.
When displaying the interface, if the edges shared between the parent node and the child node are not drawn, and other edges are drawn, a maze can be drawn.
Then I thought about how to implement such a tree.
The first two questions:
1. How do trees represent?
2. How to construct this tree?
1. How do trees represent?
Assuming that this tree is implemented like writing a binary tree, each tree node needs to store a coordinate (X, Y) to represent a grid, and four pointers must be stored. Some pointers are empty, some are not empty, and the pointers that are not empty point to the child nodes, and the child nodes save the coordinates of the neighbor grid. The biggest problem with doing this is that it is impossible to determine whether all grids are in the tree. Maybe a two-dimensional array is also used as a flag array.
Suppose you use a two-dimensional array to represent the grid of the maze. Each array element stores a reference to the parent node, which can also form a virtual tree. So a two-dimensional array of N*N represents N*N grids, and each array element (Lattice) has a reference to the parent node. In addition, in order to easily obtain the coordinates of the grid, coordinate information must also be saved.
2. How to construct this tree?
First select a grid as the root node. In order to make the shape of the maze random enough, I chose to randomly generate a coordinate as the root node. In fact, it is also OK to choose a coordinate that is determined.
Then, how to add nodes to this tree?
I took a lot of detours here. At first I thought of an algorithm that seems to be similar to backtracking now (I didn't know the backtracking algorithm at that time. .), but the time complexity is very high. Perhaps when the maze is 64*64, the algorithm will not produce any results.
Then, a method of scanning depth search is also backtracking. Each time I scan, I find a node in the current tree to see if its neighbor grid is in the tree. If it is not in the tree, add the neighbor grid to the tree. If it is already in the tree, look at the next neighbor grid. If all neighbor grids of the node are in the tree, find the next node and continue the same operation. In addition, in order to make the maze randomly generated, the start position of the scan is just random. However, the paths in the maze generated by this method are always not deep enough to have the tortuous and in-depth effect I want. After all, it is a similar method to breadth search. Moreover, doing this always seems to rely on brute force, and the algorithm is not smart and concise enough.
Finally, I finally thought of using in-depth search. . Probably because I have learned data structure for a year and haven’t practiced it too much, I have never thought of this first method I should think of. .
Randomly select a grid as the root node, start from it and search in depth, and open a way until there is no way to go, retreat one step, change another way, and then walk to no way to go, take one step back, change another... This cycle goes on until there is no way to go. . . In fact, it's still backtracking.
In the program, the following process is (see the createMaze() function in the code for details):
Randomly select a grid as the root node and push it into the stack.
Then execute the following loop when the stack is not empty:
Take out a grid, set its INTREE flag to 1, then push all its neighbor grids that are not in the tree into the stack (stories randomly), and let the father of these neighbor grids point to the grid.
After solving these two problems, the rest of the drawing of mazes, displaying paths, and moving balls are relatively simple.
Code
package maze;import java.awt.Color;import java.awt.Graphics;import java.awt.event.KeyAdapter;import java.awt.event.KeyEvent;import java.util.Random;import java.util.Stack;import javax.swing.JFrame;import javax.swing.JOptionPane;import javax.swing.JPanel;class Lattice { static final int INTREE = 1; static final int NOTINTREE = 0; private int x = -1; private int y = -1; private int flag = NOTINTREE; private Lattice father = null; public Lattice(int xx, int yy) { x = xx; y = yy; } public int getX() { return x; } public int getY() { return y; } public int getFlag() { return flag; } public Lattice getFather() { return father; } public void setFather(Lattice f) { father = f; } public void setFlag(int f) { flag = f; } public String toString() { return new String("(" + x + "," + y + ")/n"); }}public class Maze extends JPanel { private static final long serialVersionUID = -8300339045454852626L; private int NUM, width, padding;// width The width and height of each grid private Lattice[][] maze; private int ballX, ballY; private boolean drawPath = false; Maze(int m, int wi, int p) { NUM = m; width = wi; padding = p; maze = new Lattice[NUM][NUM]; for (int i = 0; i <= NUM - 1; i++) for (int j = 0; j <= NUM - 1; j++) maze[i][j] = new Lattice(i, j); createMaze(); setKeyListener(); this.setFocusable(true); } private void init() { for (int i = 0; i <= NUM - 1; i++) for (int j = 0; j <= NUM - 1; j++) { maze[i][j].setFather(null); maze[i][j].setFlag(Lattice.NOTINTREE); } ballX = 0; ballY = 0; drawPath = false; createMaze(); // setKeyListener(); this.setFocusable(true); repaint(); } public int getCenterX(int x) { return padding + x * width + width / 2; } public int getCenterY(int y) { return padding + y * width + width / 2; } public int getCenterX(Lattice p) { return padding + p.getY() * width + width / 2; } public int getCenterY(Lattice p) { return padding + p.getX() * width + width / 2; } private void checkIsWin() { if (ballX == NUM - 1 && ballY == NUM - 1) { JOptionPane.showMessageDialog(null, "YOU WIN !", "You walked out of the maze. ", JOptionPane.PLAIN_MESSAGE); init(); } } synchronized private void move(int c) { int tx = ballX, ty = ballY; // System.out.println(c); switch (c) { case KeyEvent.VK_LEFT : ty--; break; case KeyEvent.VK_RIGHT : ty++; break; case KeyEvent.VK_UP : tx--; break; case KeyEvent.VK_DOWN : tx++; break; case KeyEvent.VK_SPACE : if (drawPath == true) { drawPath = false; } else { drawPath = true; } break; default : } if (!isOutOfBorder(tx, ty) && (maze[tx][ty].getFather() == maze[ballX][ballY] || maze[ballX][ballY].getFather() == maze[tx][ty])) { ballX = tx; ballY = ty; } } private void setKeyListener() { this.addKeyListener(new KeyAdapter() { public void keyPressed(KeyEvent e) { int c = e.getKeyCode(); move(c); repaint(); checkIsWin(); } }); } private boolean isOutOfBorder(Lattice p) { return isOutOfBorder(p.getX(), p.getY()); } private boolean isOutOfBorder(int x, int y) { return (x > NUM - 1 || y > NUM - 1 || x < 0 || y < 0) ? true : false; } private Lattice[] getNeis(Lattice p) { final int[] adds = {-1, 0, 1, 0, -1};// The order is upper, right, left, if (isOutOfBorder(p)) { return null; } Lattice[] ps = new Lattice[4];// The order is upper, right, left, int xt; int yt; for (int i = 0; i <= 3; i++) { xt = p.getX() + adds[i]; yt = p.getY() + adds[i + 1]; if (isOutOfBorder(xt, yt)) continue; ps[i] = maze[xt][yt]; } return ps; } private void createMaze() { Random random = new Random(); int rx = Math.abs(random.nextInt()) % NUM; int ry = Math.abs(random.nextInt()) % NUM; Stack<Lattice> s = new Stack<Lattice>(); Lattice p = maze[rx][ry]; Lattice neis[] = null; s.push(p); while (!s.isEmpty()) { p = s.pop(); p.setFlag(Lattice.INTREE); neis = getNeis(p); int ran = Math.abs(random.nextInt()) % 4; for (int a = 0; a <= 3; a++) { ran++; ran %= 4; if (neis[ran] == null || neis[ran].getFlag() == Lattice.INTREE) continue; s.push(neis[ran]); neis[ran].setFather(p); } } // changeFather(maze[0][0],null); } private void changeFather(Lattice p, Lattice f) { if (p.getFather() == null) { p.setFather(f); return; } else { changeFather(p.getFather(), p); } } private void clearFence(int i, int j, int fx, int fy, Graphics g) { int sx = padding + ((j > fy ? j : fy) * width), sy = padding + ((i > fx ? i : fx) * width), dx = (i == fx ? sx + width), dy = (i == fx ? sy + width : sy); if (sx != dx) { sx++; dx--; } else { sy++; dy--; } g.drawLine(sx, sy, dx, dy); } protected void paintComponent(Graphics g) { super.paintComponent(g); for (int i = 0; i <= NUM; i++) { g.drawLine(padding + i * width, padding, padding + i * width, padding + NUM * width); } for (int j = 0; j <= NUM; j++) { g.drawLine(padding, padding + j * width, padding + NUM * width, padding + j * width); } g.setColor(this.getBackground()); for (int i = NUM - 1; i >= 0; i--) { for (int j = NUM - 1; j >= 0; j--) { Lattice f = maze[i][j].getFather(); if (f != null) { int fx = f.getX(), fy = f.getY(); clearFence(i, j, fx, fy, g); } } } g.drawLine(padding, padding + 1, padding, padding + width - 1); int last = padding + NUM * width; g.drawLine(last, last - 1, last, last - width + 1); g.setColor(Color.RED); g.fillOval(getCenterX(ballY) - width / 3, getCenterY(ballX) - width / 3, width / 2, width / 2); if (drawPath == true) drawPath(g); } private void drawPath(Graphics g) { Color PATH_COLOR = Color.ORANGE, BOTH_PATH_COLOR = Color.PINK; if (drawPath == true) g.setColor(PATH_COLOR); else g.setColor(this.getBackground()); Lattice p = maze[NUM - 1][NUM - 1]; while (p.getFather() != null) { p.setFlag(2); p = p.getFather(); } g.fillOval(getCenterX(p) - width / 3, getCenterY(p) - width / 3, width / 2, width / 2); p = maze[0][0]; while (p.getFather() != null) { if (p.getFlag() == 2) { p.setFlag(3); g.setColor(BOTH_PATH_COLOR); } g.drawLine(getCenterX(p), getCenterY(p), getCenterX(p.getFather()), getCenterY(p.getFather())); p = p.getFather(); } g.setColor(PATH_COLOR); p = maze[NUM - 1][NUM - 1]; while (p.getFather() != null) { if (p.getFlag() == 3) break; g.drawLine(getCenterX(p), getCenterY(p), getCenterX(p.getFather()), getCenterY(p.getFather())); p = p.getFather(); } } public static void main(String[] args) { final int n = 30, width = 600, padding = 20, LX = 200, LY = 100; JPanel p = new Maze(n, (width - padding - padding) / n, padding); JFrame frame = new JFrame("MAZE(show or hide paths by space bar)"); frame.getContentPane().add(p); frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); frame.setSize(width + padding, width + padding + padding); frame.setLocation(LX, LY); frame.setVisible(true); }}