This post is a sequel to an article I put together earlier, Portal. Mainly want to achieve random maze algorithm and on the basis of this progress to walk the maze of the small game. This program is suitable for Java programmers to consolidate class and object, file reading, event response, AWT package tools related concepts and the exercise of logical ability. Welcome to contact me at VX: WJW0310.
The final effect is as follows:
The data layer
The mazeData.java class is designed to store maze-related data, including the size of the maze (row, column), a character matrix that stores the maze, the path to the solution, the exits and entrances, and the player’s location, and provide external callable query methods.
In addition, a method to judge whether a certain coordinate is in the maze and to obtain the information of a certain coordinate is also designed.
public class MazeData {
public static final char ROAD = ' ';
public static final char WALL = The '#';
private int N, M;
public char[][] maze;
public boolean[][] visited;
public boolean[][] path;
public Position player;
public boolean showPath;
private int entranceX, entranceY;
private int exitX, exitY;
public MazeData(int N, int M){
if( N%2= =0 || M%2= =0)
throw new IllegalArgumentException("Our Maze Generalization Algorihtm requires the width and height of the maze are odd numbers");
this.N = N;
this.M = M;
maze = new char[N][M];
visited = new boolean[N][M];
path = new boolean[N][M];
for(int i = 0 ; i < N ; i ++)
for(int j = 0 ; j < M ; j ++){
if(i%2= =1 && j%2= =1)
maze[i][j] = ROAD;
else
maze[i][j] = WALL;
visited[i][j] = false;
path[i][j] = false;
}
showPath = false;
entranceX = 1;
entranceY = 0;
exitX = N - 2;
exitY = M - 1;
maze[entranceX][entranceY] = ROAD;
maze[exitX][exitY] = ROAD;
}
public int N(a){ return N; }
public int M(a){ return M; }
public int getEntranceX(a){ return entranceX; }
public int getEntranceY(a){ return entranceY; }
public int getExitX(a){ return exitX; }
public int getExitY(a){ return exitY; }
public boolean inArea(int x, int y){
return x >= 0 && x < N && y >= 0 && y < M;
}
public char getMaze(int i, int j){
if(! inArea(i, j))throw new IllegalArgumentException("i or j is out of index in getMaze!");
returnmaze[i][j]; }}Copy the codeAlso, each Position of the maze is encapsulated into a class position.java, which is easy to operate and will not be described here. details
The view layer
Algoframe. Java is the core code of drawing interface, using Java JFrame control, add JPanel on it, define render method in JFrame to call paintComponent method of drawing board to achieve drawing. Java, which encapsulates methods to draw rectangles, set brush colors, pause, etc., and also defines some colors. You can also use various methods in awT package directly in Algoframe.java without defining this helper class. Download the code if necessary.
import java.awt.*;
import javax.swing.*;
public class AlgoFrame extends JFrame{
private int canvasWidth;
private int canvasHeight;
public AlgoFrame(String title, int canvasWidth, int canvasHeight){
super(title);
this.canvasWidth = canvasWidth;
this.canvasHeight = canvasHeight;
AlgoCanvas canvas = new AlgoCanvas();
setContentPane(canvas);
pack();
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
setResizable(false);
setVisible(true);
}
public AlgoFrame(String title){
this(title, 1024.768);
}
public int getCanvasWidth(a){returncanvasWidth; }public int getCanvasHeight(a){returncanvasHeight; }// data
private MazeData data;
public void render(MazeData data){
this.data = data;
repaint();
}
private class AlgoCanvas extends JPanel{
public AlgoCanvas(a){
/ / double cache
super(true);
}
@Override
public void paintComponent(Graphics g) {
super.paintComponent(g);
Graphics2D g2d = (Graphics2D)g;
/ / anti-aliasing
RenderingHints hints = new RenderingHints(
RenderingHints.KEY_ANTIALIASING,
RenderingHints.VALUE_ANTIALIAS_ON);
hints.put(RenderingHints.KEY_RENDERING, RenderingHints.VALUE_RENDER_QUALITY);
g2d.addRenderingHints(hints);
// Make a concrete drawing
int w = canvasWidth/data.M();
int h = canvasHeight/data.N();
for(int i = 0 ; i < data.N() ; i ++ )
for(int j = 0 ; j < data.M() ; j ++){
if(data.maze[i][j] == MazeData.WALL)
AlgoVisHelper.setColor(g2d, AlgoVisHelper.LightBlue);
else
AlgoVisHelper.setColor(g2d, AlgoVisHelper.White);
if(data.path[i][j] && data.showPath == true)
AlgoVisHelper.setColor(g2d, AlgoVisHelper.Yellow);
if(data.player.getX() == i && data.player.getY() == j) AlgoVisHelper.setColor(g2d, AlgoVisHelper.Red); AlgoVisHelper.fillRectangle(g2d, j * w, i * h, w, h); }}@Override
public Dimension getPreferredSize(a){
return newDimension(canvasWidth, canvasHeight); }}}Copy the codeControl layer
The main function AlgoVisualizer. Java, the initialization process is wrapped in the initial function, mainly to complete the generation of random maze and solve the maze through the recursive DFS algorithm in advance. The user can press the space to realize the prompt function, red represents the player, the keyboard up, down, left and right control four directions of movement. The run() method implements all of the animation logic.
import java.awt.*;
import java.awt.event.*;
public class AlgoVisualizer {
private static int DELAY = 5;
private static int blockSide = 8;
private MazeData data;
private AlgoFrame frame;
private static final int d[][] = {{-1.0}, {0.1}, {1.0}, {0, -1}};
public AlgoVisualizer(int N, int M){
// Initialize the data
data = new MazeData(N, M);
int sceneHeight = data.N() * blockSide;
int sceneWidth = data.M() * blockSide;
// Initialize the view
EventQueue.invokeLater(() -> {
frame = new AlgoFrame("Random Maze Generation Visualization", sceneWidth, sceneHeight);
frame.addKeyListener(new AlgoKeyListener());
new Thread(() -> {
run();
}).start();
});
}
private void run(a){
setRoadData(-1, -1);
if (initial())
System.out.println("Initialization completed");
while (true){ frame.render(data); AlgoVisHelper.pause(DELAY); }}private boolean initial(a){
data.player = new Position(data.getEntranceX(), data.getEntranceY());
RandomQueue<Position> queue = new RandomQueue<Position>();
Position first = new Position(data.getEntranceX(), data.getEntranceY()+1);
queue.add(first);
data.visited[first.getX()][first.getY()] = true;
while(queue.size() ! =0){
Position curPos = queue.remove();
for(int i = 0 ; i < 4 ; i ++){
int newX = curPos.getX() + d[i][0] *2;
int newY = curPos.getY() + d[i][1] *2;
if(data.inArea(newX, newY) && ! data.visited[newX][newY]){ queue.add(new Position(newX, newY));
data.visited[newX][newY] = true;
setRoadData(curPos.getX() + d[i][0], curPos.getY() + d[i][1]); }}}for(int i = 0 ; i < data.N() ; i ++)
for(int j = 0 ; j < data.M() ; j ++)
data.visited[i][j] = false;
new Thread(() -> {
go(data.getEntranceX(), data.getEntranceY());
}).start();
return true;
}
private boolean go(int x, int y){
if(! data.inArea(x,y))throw new IllegalArgumentException("x,y are out of index in go function!");
data.visited[x][y] = true;
setPathData(x, y, true);
if(x == data.getExitX() && y == data.getExitY())
return true;
for(int i = 0 ; i < 4 ; i ++){
int newX = x + d[i][0];
int newY = y + d[i][1];
if(data.inArea(newX, newY) && data.maze[newX][newY] == MazeData.ROAD && ! data.visited[newX][newY])if(go(newX, newY))
return true;
}
/ / back
setPathData(x, y, false);
return false;
}
private void setRoadData(int x, int y){
if(data.inArea(x, y))
data.maze[x][y] = MazeData.ROAD;
}
private void setPathData(int x, int y, boolean isPath){
if(data.inArea(x, y))
data.path[x][y] = isPath;
}
private class AlgoKeyListener extends KeyAdapter{
@Override
public void keyPressed(KeyEvent event){
if (event.getKeyCode() == KeyEvent.VK_LEFT){
System.out.println("go left");
oneStep(data.player.getX(), data.player.getY(), 3);
}
else if (event.getKeyCode() == KeyEvent.VK_DOWN){
System.out.println("go down");
oneStep(data.player.getX(), data.player.getY(), 2);
}
else if (event.getKeyCode() == KeyEvent.VK_RIGHT){
System.out.println("go right");
oneStep(data.player.getX(), data.player.getY(), 1);
}
else if (event.getKeyCode() == KeyEvent.VK_UP){
System.out.println("go up");
oneStep(data.player.getX(), data.player.getY(), 0);
}
else if (event.getKeyChar() == ' '){
System.out.println("Display prompt"); data.showPath = ! data.showPath; }}}private void oneStep(int x, int y, int direction){
int newX = x + d[direction][0];
int newY = y + d[direction][1];
if(data.inArea(newX, newY) && data.getMaze(newX, newY) == MazeData.ROAD){ data.player.setX(newX); data.player.setY(newY); }}public static void main(String[] args) {
int N = 101;
int M = 101;
AlgoVisualizer vis = newAlgoVisualizer(N, M); }}Copy the codeAmong them, the random maze generation algorithm is realized by using the data structure of the random queue, which is realized by the Java LinkedList class at the bottom of the random queue. The operation of data joining the queue is to randomly add data at the head or tail, and the operation of data removing the queue is to randomly take out data at the head or tail. At the beginning, the entrance position of the maze is joined in the queue, then one position is taken out from the random queue each time, and the four directions adjacent to this position are joined in the queue until the queue is empty.
Random queue:
import java.util.LinkedList;
public class RandomQueue<E>{
private LinkedList<E> queue;
public RandomQueue(a){
queue = new LinkedList<E>();
}
public void add(E e){
if(Math.random() < 0.5)
queue.addFirst(e);
else
queue.addLast(e);
}
public E remove(a){
if(queue.size() == 0)
throw new IllegalArgumentException("There's no element to remove in Random Qeuue");
if(Math.random() < 0.5)
return queue.removeFirst();
else
return queue.removeLast();
}
public int size(a){
return queue.size();
}
public boolean empty(a){
return size() == 0; }}Copy the code\