后端战狼奈非天 源文：jrsinclair.com/articles/20…
前言
你有多久没有为自己写过代码了？
我本科是纯机械专业，如果想要去实现一个自己的作品，需要机床，需要物料，需要场地，遗憾的是我的学校水平一般，只有少部分优秀的学生才能够有自己的工作站来进行一些创作。因此，我们专业更专注于CAD、SolidWorks、UG制图，虽然也算一定程度上的创造，但大多数时候是感到乏味与无聊的。
第一次接触到代码是数控编程，网上找了一张图，数控编程的代码大概就是这样子的。通过指令，在一个固定的坐标系中控制刀具的运作。在程序员的眼里，这代码看起来的确不咋地，但是对我来说，这代码实实在在让我感受到了 代码/软件可以控制物理世界 的魅力。
我发现写代码似乎是一件很有趣的事情，用很低的成本就能够实现对现实世界的影响和创造。于是，在大三那年我毅然转码，当时觉得还是对口学历比较重要，于是考了计算机的研究生。
记得那一个暑假真的很开心，一切都是未知的，一切都是充满新奇的。还记得7月份的时候跟着B站上的教程，用python写了个飞机大战的小游戏，真的很有成就感。那时候不会觉得重复造轮子是一件很无趣的事情，只有我会了，我也能开发这样的程序的激动。
时光荏苒，研究生经过了疫情2年，后知后觉地就毕业了。也经历了一些事情，比如刚入职就经历了工作的滑铁卢（有赞毁约），随后只能将就着入职了一家小公司苟着。比起同一起跑线的同学，看起来已经落后了许多（薪资、履历）。也的确如此，几年地工作时间让我成为了一个普通地后端Java程序员，熟练地使用Springboot进行简单业务地开发，除此之外我似乎什么也不会了。网上总是嘲笑Java后端开发是Spring Boy，我觉得我就是。
我厌恶写代码，我觉得公司在压榨我，我觉得我写的代码没有任何意义，我觉得我在制造垃圾。这种感觉无时无刻在折磨我，以至于每当我使用IDEA打开公司的代码项目，我都感觉到生理性厌恶，反胃！我迷失了，我写代码只为糊口，我接受自己平凡地工作者，我接受我的工作没有创造性，我接受写出一行行屎一样的垃圾业务。我安慰自己，没关系，只要工作稳定就好了。我变得浮躁，总想很快学会一门技术，但又苦恼于学习停留于表面，始终无法更深层次地探索，又总觉得过于投入研究底层就是浪费时间，是没有性价比的行为；总想着通过数字货币、股市暴富。我越来越浮躁，我丢失了最初学习写代码的初心--有趣和改变世界。
庆幸地是我还保留着高强度上网冲浪的习惯（摸鱼），偶然间看到了这篇文章：
文章的标题是《The joy of recursion, immutable data, and pure functions: Generating mazes with JavaScript》，猜一下吸引我看这篇文章的关键词是哪一个？没错，是Joy。我多久没有因为有趣而去写一段代码了？
这篇文章的内容是使用Javascript实现一个迷宫生成器，作者一步步手把手带你实现，其中不乏一些代码思想的设计，比如 面向对象的思想，函数式编程，不可变对象等。
但对我来说这些都不重要，我唯一迫切地想要知道的是代码怎么生成迷宫？天哪，我太想知道了，我打小就喜欢画迷宫让同学”逃离“，当时我就好奇，那些画本上复杂的迷宫到底是怎样创作的？于是抱着好奇心，我跟着这篇文章使用java实现一遍。
本篇文章的内容就是使用java实现迷宫生成器，包含了一个Swing实现的GUI界面，如果你更熟悉Javascript，或者觉得我的文笔一般，可以直接阅读本文开始的链接地址就好了。如果你英语水平一般，也对迷宫的实现感兴趣，那就只能花上一些时间阅读下我这篇朽木~，感谢阅读。
正文
构建迷宫
一个典型的迷宫如下图所示，黑线表示墙体不可穿透，空白则是可通过的路径。
那么如何使用算法生成一个迷宫呢？
假设我们有一个4x4矩阵，每一个小格子代表一个房间，我们随机挑选一个房间作为起点，下图中的蓝点就是我们的起始位置。
然后，我们可以随机挑选东南西北中某个方向作为下一个位置，并将房间和房间之间的墙打通，这里的墙指的就是格子间的黑线。
在移动到新的房间后，我们重复上一步的行为。但是有两点需要注意：
- 不能超过矩阵
- 不能访问已经被访问过的房间
按照上面的规则，不断随机移动蓝点，打通房间之间的墙，直到访问过所有的房间，最终形成了迷宫。
最终我们可以打通某两面墙作为出入口，如下图所示。
如果你对算法有所了解，可以感受到我们其实是在构建一个无向无环图。
算法实现
通过上面的案例，可以总结出如下的步来骤构建迷宫：
-
随机挑选一个起始房间。
-
列出与当前位置相邻的房间，随机挑选一个相邻房间并移动，该房间需要满足：
- 没有超出矩阵范围
- 未被访问过
-
在新的房间重复第二步的动作。
-
当当前房间没有可移动的下一个房间时，回退到当前房间的上一个房间，并重复2-4步骤。
数据结构
在开始写代码前我们需要考虑如何定义我们的矩阵，一般来说我们习惯使用数组来模拟矩阵：
int[][] grid = new int[N][M];
在迷宫这个场景下，我们需要描述矩阵中各个节点的联通关系，如果使用数组来表示矩阵，我们需要额外的一个map来记录。可以通过以下数据结构来记录节点和节点之间的联接关系，我们将这一个map称为邻接表。
// i -> 矩阵y轴索引，j -> 矩阵x轴索引
// key = i * N + j;
// value = List.of(i_1 * N + j_1, ....., i_k * N + j_k)
Map<Integer, List<Integer>> map = new HashMap<>();
似乎我们已经完成了初步数据结构的设计。但请等一等，我们真的需要grid这个数组吗？map实际上会包含所有的矩阵节点，已经隐式地描述了矩阵，因此我们可以将grid省略。
对于key和value，我们目前都是计算得到编码来表示所处矩阵中的位置。虽然这种表示很高效并节省内存，但就代码阅读和后续维护而言，并不能带来特别好的体验，我们完全可以抽象出一个对象来表示所处矩阵位置：
@Getter
@AllArgsConstructor
// 注意只有getter没有setter，我们不希望在程序运行过程中改变坐标。
public class Point {
private int x;
private int y;
}
于是Map变为了
Map<Point, List<Point>> gridMap = new HashMap<>();
但是我们会面临一个问题：
Map<Point, String> map = new HashMap<>();
Point p1 = new Point(1, 1);
Point p2 = new Point(1, 1);
map.put(p1, "1");
map.put(p2, "2");
Assert.equal(map.getSize(), 1);
Assert.equal(map.get(p1), "2");
显然在我们预想中p1和p2应该是一样的，代表同一个节点。为了完成这样的效果，我们需要进行一些改造。回顾下HashMap是如何判定一个key是相同的，首先比较hashcode，然后根据equal方法比较对象。在默认情况下对象的hashcode与内存地址相关，equal方法也是比较内存地址是否相同，因此我们需要重写这两个方法，但好在Lombok已经提供了开箱即用的注解。
@Getter
@AllArgsConstructor
@EqualsAndHashCode
@ToString
// 注意只有getter没有setter，我们不希望在程序运行过程中改变某个Point对象的坐标。
public class Point {
private int x;
private int y;
}
算法细节
工具定义
为了方便后续编码，我们可以预先定义一些用到的常量和静态方法
- 移动方向定义
public static final Point NORTH = new Point(0, -1);
public static final Point EAST = new Point(1, 0);
public static final Point SOUTH = new Point(0, 1);
public static final Point WEST = new Point(-1, 0);
- 移动坐标计算
public static Point addPoint(Point a, Point b) {
return new Point(a.getX() + b.getX(), a.getY() + b.getY());
}
- 获取相邻节点
// 获取相邻节点，并且相邻节点未被访问过
public static List<Point> getCandidates(Point room, Map<Point, List<Point>> mazeSoFar) {
return Stream.of(Point.NORTH, Point.SOUTH, Point.EAST, Point.WEST)
.map(direction -> addPoint(room, direction))
.filter(pt -> Objects.nonNull(mazeSoFar.get(pt)) && mazeSoFar.get(pt).isEmpty())
.toList();
}
- 初始化构建矩阵
public static Map<Point, List<Point>> buildGrid(int n) {
Map<Point, List<Point>> map = new HashMap<>();
for (int i = 0; i < n * n; i++) {
map.put(new Point(i % n, i / n), new ArrayList<>());
}
return map;
}
- 随机挑选位置
注意这里seed的使用，这样做的好处是能够保证比较高的随机性，避免生成的位置过于固定。
// 随机生成一个0 - (n-1)的值，并返回下一个随机种子
public static int[] randomInRange(int seed, int n) {
int nextSeed = randomInt(seed);
int randVal = Math.abs(nextSeed) % n;
return new int[]{nextSeed, randVal};
}
public static int randomInt(int seed) {
Random random = new Random(seed);
return random.nextInt();
}
完整的工具代码如下
public class MazesUtil {
public static final Point NORTH = new Point(0, -1);
public static final Point EAST = new Point(1, 0);
public static final Point SOUTH = new Point(0, 1);
public static final Point WEST = new Point(-1, 0);
public static Map<Point, List<Point>> buildGrid(int n) {
Map<Point, List<Point>> map = new HashMap<>();
for (int i = 0; i < n * n; i++) {
map.put(new Point(i % n, i / n), new ArrayList<>());
}
return map;
}
public static int[] randomInRange(int seed, int n) {
int nextSeed = randomInt(seed);
int randVal = Math.abs(nextSeed) % n;
return new int[]{nextSeed, randVal};
}
public static int randomInt(int seed) {
Random random = new Random(seed);
return random.nextInt();
}
public static Point addPoint(Point a, Point b) {
return new Point(a.getX() + b.getX(), a.getY() + b.getY());
}
public static List<Point> getCandidates(Point room, Map<Point, List<Point>> mazeSoFar) {
return Stream.of(Point.NORTH, Point.SOUTH, Point.EAST, Point.WEST)
.map(direction -> addPoint(room, direction))
.filter(pt -> Objects.nonNull(mazeSoFar.get(pt))&& mazeSoFar.get(pt).isEmpty())
.toList();
}
}
实现算法
回顾下我们总结的算法步骤：
-
随机挑选一个起始房间。
-
列出与当前位置相邻的房间，随机挑选一个相邻房间并移动，该房间需要满足：
- 没有超出矩阵范围
- 未被访问过
-
在新的房间重复第二步的动作。
-
当当前房间没有可移动的下一个房间时，回退到当前房间的上一个房间，并重复2-4步骤。
初始状态计算
我们需要完成第一步的编码，随机挑选一个起始房间，这个操作也隐含了迷宫矩阵的初始化
public class Mazes {
private final Map<Point, List<Point>> mazes;
private InitialState buildInitialState(int n, int seed) {
// 构建矩阵
Map<Point, List<Point>> grid = buildGrid(n);
// 随机挑选一个位置
int[] randomPair = randomInRange(seed, n ^ 2);
int newSeed = randomPair[0];
int roomIdx = randomPair[1];
// 随机挑选的起始房间
Point room = new Point(roomIdx % n, roomIdx / n);
// 返回初始状态
return new InitialState(room, grid, newSeed);
}
}
@AllArgsConstructor
@Getter
public class InitialState {
public final Point room;
public final Map<Point, List<Point>> grid;
public final int newSeed;
}
递归生成迷宫
算法的2-4步实际上是一个递归的过程，如果你熟悉DFS算法的话你可以轻易写出实现的代码。
我们在写递归的时，往往关注几个关键点：
- 往哪里递归
- 递归结束的条件是什么？
在我们的场景下，我们递归的方向是相邻的可以访问的节点，递归结束的条件则是当前节点没有响应的节点可以访问了。
private State buildMaze(Point room, Map<Point, List<Point>> mazeSoFar, int seed) {
// 获取未被访问过的相邻节点
List<Point> candidates = getCandidates(room, mazeSoFar);
// 不满足条件，结束递归
if (candidates.isEmpty()) {
return new State(mazeSoFar, seed);
}
// 随机挑选下一个节点
int[] randomPair = randomInRange(seed, candidates.size());
int newSeed = randomPair[0];
int idx = randomPair[1];
Point roomToConnect = candidates.get(idx);
// 记录节点之间的联通关系(边)
mazeSoFar.get(roomToConnect).add(room);
mazeSoFar.get(room).add(roomToConnect);
// 下一个节点的递归
State state = buildMaze(roomToConnect, mazeSoFar, newSeed);
// 递归访问当前节点的其他节点
return buildMaze(room, mazeSoFar, state.getNewSeed());
}
@Getter
@AllArgsConstructor
public class State {
public final Map<Point, List<Point>> grid;
public final int newSeed;
}
完整代码
public class Mazes {
private final Map<Point, List<Point>> mazes;
public Mazes(int n, int seed0) {
InitialState initialState = buildInitialState(n, seed0);
State state = buildMaze(initialState.getRoom(), initialState.getGrid(), initialState.getNewSeed());
mazes = Collections.unmodifiableMap(state.getGrid());
}
public Map<Point, List<Point>> getMazes() {
return mazes;
}
private State buildMaze(Point room, Map<Point, List<Point>> mazeSoFar, int seed) {
List<Point> candidates = getCandidates(room, mazeSoFar);
if (candidates.isEmpty()) {
return new State(mazeSoFar, seed);
}
int[] randomPair = randomInRange(seed, candidates.size());
int newSeed = randomPair[0];
int idx = randomPair[1];
Point roomToConnect = candidates.get(idx);
mazeSoFar.get(roomToConnect).add(room);
mazeSoFar.get(room).add(roomToConnect);
State state = buildMaze(roomToConnect, mazeSoFar, newSeed);
return buildMaze(room, mazeSoFar, state.getNewSeed());
}
private InitialState buildInitialState(int n, int seed) {
Map<Point, List<Point>> grid = buildGrid(n);
int[] randomPair = randomInRange(seed, n ^ 2);
int newSeed = randomPair[0];
int roomIdx = randomPair[1];
Point room = new Point(roomIdx % n, roomIdx / n);
return new InitialState(room, grid, newSeed);
}
}
GUI实现
在上一章我们已经实现了迷宫算法的细节，下面的代码便是生成迷宫，并将其邻接表打印到控制台。
public class Main {
public static void main(String[] args) {
Mazes mazes = new Mazes(5, 1);
System.out.println(mazes.getMazes());
}
}
显然我们无法接受这个结果，我们要的是一个可视化的迷宫，而不是这样冷冰冰的一串字符，我们需要一个GUI界面。
在早几年，我倒是用pyqt开发过桌面端的GUI，但是Java的Swing我并不了解。那怎么办呢？别担心，让我们来问问神奇海螺吧（bushi）。
神奇海螺（cursor）马上就帮我实现了一个可用的gui代码，让我们来看看最终的效果。
算不上精美，但已经完全满足我们的迷宫生成，可以指定迷宫大小，可以指定迷宫初始随机种子。
package awesome.mazes;
import javax.swing.*;
import java.awt.*;
import java.util.List;
import java.util.Map;
public class MazePanel extends JPanel {
private Map<Point, List<Point>> maze;
private int mazeSize;
private static final int CELL_SIZE = 30;
private static final int WALL_THICKNESS = 2;
public MazePanel() {
setBackground(Color.WHITE);
setBorder(BorderFactory.createLineBorder(Color.LIGHT_GRAY));
}
public void setMaze(Map<Point, List<Point>> maze, int mazeSize) {
this.maze = maze;
this.mazeSize = mazeSize;
repaint();
}
@Override
protected void paintComponent(Graphics g) {
super.paintComponent(g);
Graphics2D g2d = (Graphics2D) g;
g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
if (maze == null || mazeSize <= 0) {
return;
}
// 计算迷宫在面板中的位置，使其居中
int panelWidth = getWidth();
int panelHeight = getHeight();
int mazeWidth = mazeSize * CELL_SIZE;
int mazeHeight = mazeSize * CELL_SIZE;
int startX = (panelWidth - mazeWidth) / 2;
int startY = (panelHeight - mazeHeight) / 2;
// 绘制迷宫网格
drawMaze(g2d, startX, startY);
}
private void drawMaze(Graphics2D g2d, int startX, int startY) {
g2d.setColor(Color.BLACK);
g2d.setStroke(new BasicStroke(WALL_THICKNESS));
// 绘制每个单元格的墙壁
for (int y = 0; y < mazeSize; y++) {
for (int x = 0; x < mazeSize; x++) {
Point currentPoint = new Point(x, y);
List<Point> connections = maze.get(currentPoint);
int cellX = startX + x * CELL_SIZE;
int cellY = startY + y * CELL_SIZE;
// 检查四个方向的连接
boolean hasNorth = connections != null && connections.contains(new Point(x, y - 1));
boolean hasSouth = connections != null && connections.contains(new Point(x, y + 1));
boolean hasEast = connections != null && connections.contains(new Point(x + 1, y));
boolean hasWest = connections != null && connections.contains(new Point(x - 1, y));
// 绘制北墙（如果没有连接）
if (!hasNorth) {
g2d.drawLine(cellX, cellY, cellX + CELL_SIZE, cellY);
}
// 绘制南墙（如果没有连接）
if (!hasSouth) {
g2d.drawLine(cellX, cellY + CELL_SIZE, cellX + CELL_SIZE, cellY + CELL_SIZE);
}
// 绘制东墙（如果没有连接）
if (!hasEast) {
g2d.drawLine(cellX + CELL_SIZE, cellY, cellX + CELL_SIZE, cellY + CELL_SIZE);
}
// 绘制西墙（如果没有连接）
if (!hasWest) {
g2d.drawLine(cellX, cellY, cellX, cellY + CELL_SIZE);
}
}
}
// 绘制迷宫边界
g2d.setStroke(new BasicStroke(WALL_THICKNESS + 1));
g2d.drawRect(startX, startY, mazeSize * CELL_SIZE, mazeSize * CELL_SIZE);
}
@Override
public Dimension getPreferredSize() {
if (mazeSize > 0) {
int size = mazeSize * CELL_SIZE + 40; // 添加一些边距
return new Dimension(size, size);
}
return new Dimension(400, 400);
}
}
package awesome.mazes;
import javax.swing.*;
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.Map;
public class MazeGUI extends JFrame {
private JSlider sizeSlider;
private JTextField seedField;
private MazePanel mazePanel;
private Mazes currentMaze;
public MazeGUI() {
setTitle("迷宫生成器");
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
setSize(800, 600);
setLocationRelativeTo(null);
initComponents();
generateMaze();
}
private void initComponents() {
// 创建主面板
JPanel mainPanel = new JPanel(new BorderLayout());
// 创建控制面板
JPanel controlPanel = createControlPanel();
mainPanel.add(controlPanel, BorderLayout.NORTH);
// 创建迷宫显示面板
mazePanel = new MazePanel();
mainPanel.add(mazePanel, BorderLayout.CENTER);
setContentPane(mainPanel);
}
private JPanel createControlPanel() {
JPanel panel = new JPanel();
panel.setBorder(BorderFactory.createEmptyBorder(10, 10, 10, 10));
panel.setBackground(new Color(245, 245, 240)); // 浅米色背景
// 尺寸标签和滑块
JLabel sizeLabel = new JLabel("尺寸:");
sizeSlider = new JSlider(3, 20, 10);
sizeSlider.setMajorTickSpacing(5);
sizeSlider.setMinorTickSpacing(1);
sizeSlider.setPaintTicks(true);
sizeSlider.setPaintLabels(true);
sizeSlider.setBackground(new Color(245, 245, 240));
// 种子标签和输入框
JLabel seedLabel = new JLabel("种子:");
seedField = new JTextField("42", 8);
seedField.setHorizontalAlignment(JTextField.CENTER);
// 生成按钮
JButton generateButton = new JButton("生成迷宫");
generateButton.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
generateMaze();
}
});
// 随机种子按钮
JButton randomButton = new JButton("随机种子");
randomButton.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
int randomSeed = (int) (Math.random() * 10000);
seedField.setText(String.valueOf(randomSeed));
generateMaze();
}
});
// 布局控制面板
panel.add(sizeLabel);
panel.add(sizeSlider);
panel.add(Box.createHorizontalStrut(20));
panel.add(seedLabel);
panel.add(seedField);
panel.add(Box.createHorizontalStrut(20));
panel.add(generateButton);
panel.add(randomButton);
return panel;
}
private void generateMaze() {
try {
int size = sizeSlider.getValue();
int seed = Integer.parseInt(seedField.getText());
currentMaze = new Mazes(size, seed);
mazePanel.setMaze(currentMaze.getMazes(), size);
mazePanel.repaint();
} catch (NumberFormatException ex) {
JOptionPane.showMessageDialog(this, "请输入有效的种子数字", "输入错误", JOptionPane.ERROR_MESSAGE);
}
}
}
总结
说实话这篇文章很水，实现这个迷宫也不能为我带来什么利益，但是有什么关系呢？至少在读《The joy of recursion, immutable data, and pure functions: Generating mazes with JavaScript》时，我是真的带着Joy去读的，在写代码时也是好奇心驱动的，至少在这一刻我不是一个Spring Boy。
我们不见得是向名为生活的风车发起无畏冲锋的唐吉可德，也不是周而复始推石上山的西西弗斯，更不是尼采口中的超人。我还是只能写着枯燥无味springboot，沉浸在自己不喜欢的业务中，赚着一份微不足道的工资，被工作和琐事困扰，然后艰难地向上。
但是，千万不要忘记自己地初心和乐趣所在，慢慢试着让自己的乐趣成为自己的alpha，试着在生活中多寻找一些变量，禁止停步，禁止不探寻，禁止成为spring boy。倒不是劝自己更卷，而是关注于自己的心情，关注兴趣，就算躺平我认为也是一种探索和体验，只要自己是开心满足就够了。这应该就是我写这篇文章的目的，提醒自己，不要继续沉沦，试着多写一些自己真正感兴趣的代码，试着多一些好奇心，多一些求知欲，多一些对生活的激情，从自己本身出发获得成就感，获得持久的乐趣。
![[爱了]](/js/img/d1.gif)
![[尴尬]](/js/img/d16.gif)