基于BFS算法的停车场出库问题求解与实现

之前在家跟孩子玩过一个叫《停车场出库，Car Park Puzzle》的益智小游戏，核心玩法借鉴了经典的华容道（滑块拼图）机制。游戏规则简单易懂，游戏关卡分为初级、中级和高级。初级较简单，中级、高级关卡则比较复杂。中高级关卡对于四五岁的小孩挫败感较强，即使对于成年人也很有挑战，游戏没有提供正确解法，人工试错效率低，也容易陷入死胡同。基于以上难点，我在思考能否用算法来解决这个问题。

▲ 移车出库游戏

在上一篇文章迷宫与网格寻路：四种经典算法对比 中介绍了深度优先(DFS)、广度优先(BFS)、Dijkstra和A*等经典的路径搜索算法。本文在此基础上，具体分析了广度优先算法(BFS) 在停车场出库这一款游戏中的解法，包括游戏的计算机表示、BFS核心求解算法、UI界面的设计与实现、鼠标或键盘交互、最小步骤计算、状态去重等细节。

项目实现使用C++和Qt，构建工具使用CMake，开发环境是Windows + Visual Studio，理论上可以跨平台。

下面是最终效果图：

▲ 停车场出库的最优解与自动演示

一、游戏介绍

游戏规则很简单：

• 停车场为固定网格（常见 6×6）
• 场上有多辆汽车，分为横向车与纵向车
• 横向车只能左右移动，纵向车只能上下移动
• 车辆长度分为 2 格和 3 格两种
• 有一辆特殊目标车辆（游戏中为警车）正对出口
• 通过移开阻挡车辆，将目标车辆移动到出口，即为通关

▲ 一个“移车出库”的例子

游戏提供了初级、中级和高级共200多道关卡设置的地图，每个关卡只标识最少移动步数（可能有误）。按照地图布局摆放车辆，然后通过各种移动来实现车辆出库。游戏关卡的特点如下：

• 初级关卡：车辆少、阻挡简单，儿童可尝试
• 中 / 高级关卡：车辆密集、阻挡链长，移动环环相扣
• 对四五岁儿童挫败感较强
• 对成人也存在一定试错成本
• 人工难以一眼看出最短路径

▲ 关卡本

二、游戏的解法分析

回顾一下之前的路径搜索的四种算法：

1. 深度优先：优先指定方向搜索，速度快，它不保证找到的是最短路径。
2. 广度优先：层层扩张搜索，直到达到目标，找到的一定是最小步骤的最优解。
3. Dijkstra：它是带有权重的广度优先。
4. A*：它也是带有权重的广度优先算法，特殊点在于它的权重=当前点离起始点权重+当前点距离终点预估预估，带有方向性。

可以看到，在当前的游戏中，需要寻找不是任意解，而是最小步骤的最优解。另外所有车辆的移动权重都是相同的，第一次到达目标就是最短路径，所以这应该就是广度优先(BFS)的应用场景。

但这里的BFS又与前文迷宫搜索路径中的单点BFS有些不同，在传统的迷宫搜索中：

• 搜索对象：单个点 (x, y)
• 移动方式：上下左右四方向
• BFS 按 “层” 扩展：
  第 0 层：起点
  第 1 层：走 1 步可达的所有格子
  第 2 层：走 2 步可达的所有格子
  ……
• 第一次到达终点，就是最短路径。

而在移车出库问题中，停车场问题不再是“单点移动”，而是全局状态(所有车辆位置)转移：

• 搜索对象：整个停车场的车辆布局（状态）
• 一次移动：某一辆车沿合法方向移动一格
• 每一步都会生成一个全新的布局（状态）
• BFS 依然按层扩展：
  第 0 层：初始关卡布局
  第 1 层：移动任意一辆车一步后的所有布局
  第 2 层：在第 1 层基础上再移动一步的布局
  ……
• 第一次抵达胜利状态，就是最小步数解。

三、建模与数据结构

现在已经明确了使用BFS来解决车辆移动出库问题，要让算法能理解游戏，必须建立合适的模型。

车辆 Car.h 的定义如下：

#pragma once
#include <QPoint>
#include <QColor>
#include <QList>
#include <QRect>
//车辆方向
enum Direction { HORIZONTAL, VERTICAL };
 
class Car {

public:
	Car(){}
	Car(int id_, int x_, int y_, int len_, Direction direction_, QColor color_, bool isTarget_ = false) :
		id(id_), pos({ x_,y_ }), length(len_), direction(direction_), color(color_), isTarget(isTarget_) {}
	int id;				//唯一标识
	QPoint pos;			//左上角坐标，行，列
	int length;			//长度2，3
	Direction direction;//方向
	QColor color;		//颜色
	bool isTarget;		//是否目标车辆
	//获取车辆占用的所有格子
	QList<QPoint> getCells() const;
	//移动一步
	void move(int dx, int dy);
};

这里利用QPoint行列来表示车辆在6*6停车场中的位置。x表示所在的行（从上到下），y表示所在的列（从左到右）。

// 加在 GameLevel 枚举下面
enum Difficulty
{
	EASY,
	MEDIUM,
	HARD
};

// 游戏状态（用于BFS搜索）
struct GameState {
	QList<Car> cars;
	QStringList steps;  // 移动步骤记录
};

// 最终关卡配置结构体 
struct LevelConfig {
	int id;
	QString group;
	QString difficulty;
	int min_steps;
	QList<Car> cars;
	QJsonObject toJson() const;
	static LevelConfig fromJson(const QJsonObject& obj);
};

Difficulty是对关卡难易的定义，GameState是游戏状态的表示，它的内部有一个存放当前所有车辆信息的列表和一个记录移动步骤的字段。LevelConfig是对移车出库游戏中某一个关卡图的对象表示，这里是以Json格式持久化保存的，在系统里提供了关卡的录入、编辑和保存。

之后就是停车场 CarParkGame.h 的定义：

#pragma once

#include <iostream>
#include "Car.h"
#include <QList>
#include <QStringList>
#include <QJsonObject>
#include <QJsonArray>
#include <QString>
#include <queue>
#include <set>
 
class CarParkGame
{
public:
	const int ROWS = 6;
	const int COLS = 6;
	const int EXIT_ROW = 2;     // 红车第三行(2)，
	const int EXIT_COL = 5;     // 出口第三行最后一列(5)
	bool loadLevelsFromFile(const QString& filepath);
	void loadLevel(int index);
	void loadLevelConfig(const LevelConfig& cfg);
	bool saveLevelsToFile(const QString& path);
	QList<LevelConfig> allLevels;
	// 获取当前关最少推荐步数
	int getMinStepHint() const { return currentMinStep; }
	//移动车辆(合法性检查)
	bool moveCar(int carId, int dx, int dy);
	// 判断游戏胜利
	bool isWin() const;
	//BFS算法：自动求解最优步骤
	QStringList autoSolve();
	int autoSolve(const LevelConfig& level);
	//获取所有车辆
	const QList<Car>& getCars() const { return cars; }
	void generateRandomDifficulty(Difficulty diff);
	// 重置当前随机关卡（保持布局一样）
	void resetCurrentRandomDifficulty();
	//获取搜索步数
	int getSearchStepCount() const { return m_searchStepCount; }
private:
	QList<Car> cars;
	int currentMinStep=0;
	//检查位置是否被占用
	bool isCellOccupied(int x, int y, const Car* excludeCar = nullptr) const;
	//检查移动是否合法
	bool isMoveValid(const Car& car, int dx, int dy) const;
	//状态编码，用于去重
	QString encodeState(const QList<Car>& cars) const;
	// 保存随机关卡数据，用于重置
	QList<Car> savedRandomCars;
	Difficulty currentDifficulty;
	// 统计变量
	int m_searchStepCount = 0;
};

停车场固定为了6*6的大小，固定了出口位置，位于第三行，最后一列。

在整个BFS搜索中，就是停车场状态的转移。整个停车场的状态，就是当前所有车辆的位置的集合。为了避免重复搜索、死循环，需要对每一次移动一个车辆后的停车场状态生成唯一标识。这是通过encodeState方法来实现的。

QString CarParkGame::encodeState(const QList<Car>& cars) const
{
	QString code;
	for (const Car&c :cars)
	{
		code += QString("%1,%2,%3|").arg(c.pos.x()).arg(c.pos.y()).arg(c.id);
	}
	return code;
}

方法相当简单，就是保存的每个车辆的位置和id，然后用“|”分隔符拼接起来。因为每辆车的id是唯一的，所以最后一位是不同的。使用std::set<QString>来存储已访问的编码，在搜索的前，到std::set<QString>中查找是否已经存在，这样可以确保每个状态只搜索一次。在车辆移动的过程中，会调用isMoveValid方法，该方法内部会调用isCellOccupied检查待移动的位置的单元格是否被其它车辆所占用。

最后isWin函数用来判断当前状态是否胜利，条件是目标车辆的车头或车身到达出口格子。

bool CarParkGame::isWin() const
{
	for (const auto& car:cars)
	{
		if (car.isTarget)
		{
			int targetCol = car.pos.y() + car.length - 1;
			int  rightRow = car.pos.x();
			// 纵向车，尾部坐标 + 长度 -1 == 出口行
			return rightRow == EXIT_ROW && targetCol == EXIT_COL  ;
		}
	}
	return false;
}

四、BFS算法的实现

算法的伪代码实现如下：

初始化队列，存入初始状态
初始化已访问集合，标记初始状态

while 队列不为空:
    取出队首状态
    如果该状态已胜利 → 返回步骤序列
    遍历每一辆车
        遍历四个方向
            若方向与车辆类型匹配（横向车不移上下）
            尝试移动车辆
            生成新状态
            若新状态未被访问
                加入队列
                标记已访问
                记录移动步骤

所有的核心实现在autoSolve方法中：

QStringList CarParkGame::autoSolve()
{
	// 重置搜索步数计数器
	m_searchStepCount = 0;
	// 定义搜索节点
	struct Node {
		QList<Car> cars;
		QStringList steps;
	};

	std::queue<Node> q;
	std::set<QString> visited;
	
	Node start;
	start.cars = cars;
	q.push(start);
	visited.insert(encodeState(cars));

	//移动方向
	QVector<QPoint> dirs = { {-1,0},{1,0},{0,-1},{0,1} };
	while (!q.empty())
	{
		Node  cur = q.front();
		q.pop();
		// 每尝试一个新状态 = 搜索一步
		m_searchStepCount++;
		// 判断是否到达终点
		CarParkGame tempGame;
		tempGame.cars = cur.cars;
		if (tempGame.isWin()) return cur.steps;

		// 遍历所有车辆
		for (int i = 0; i < cur.cars.size(); ++i) {
			// 从当前状态安全获取车辆
			Car car = cur.cars[i];
			// 尝试所有方向
			for (auto d : dirs) {
				// 方向规则
				if (car.direction == HORIZONTAL && d.x() != 0) continue;
				if (car.direction == VERTICAL && d.y() != 0) continue;

				// 复制状态
				CarParkGame g;
				g.cars = cur.cars;
				// 尝试移动
				if (g.moveCar(car.id, d.x(), d.y()))
				{
					QString code = g.encodeState(g.cars);
					if (!visited.count(code))
					{
						visited.insert(code);
						Node nextNode = cur;
						nextNode.cars = g.cars;

						// 生成正确步骤（ID 100% 正确）
						QString op;
						if (d == QPoint(-1, 0)) op = "上移";
						else if (d == QPoint(1, 0)) op = "下移";
						else if (d == QPoint(0, -1)) op = "左移";
						else if (d == QPoint(0, 1)) op = "右移";

						nextNode.steps.append(QString("车辆%1 %2").arg(car.id).arg(op));
						q.push(nextNode);
					}
				}
			}
		}
	}
	return { "当前关卡无解" };
}

可以看到，代码结构还是一个很明显的BFS结构：

• 有一个FIFO队列 std::queue<Node> q，存放每次移动一个车辆后，当前停车场所有车辆的状态。
• 有一个集合 std::set<QString> visited ，来保存每次访问过的状态，防止重复访问和死循环。
• 循环中，每次取出一个状态节点Node，判断当前棋盘状态是否已经胜利，如果是，则退出循环，表示已经找到了最短路径，否则继续。
• 如果所有的状态都遍历过了，q节点为空，仍然没有找到最短路径，则表示当前的关卡无解。

五、UI界面的实现

UI界面主要包括游戏的主界面，布局如下：

▲ 游戏主界面

主界面的左边是游戏区:

• 上面一排是游戏关卡选择区，对照着游戏关卡地图里面的初中高级关卡选择；最右侧按钮是编辑关卡按钮，可以把关卡地图的关卡录入进来，或者自制关卡。
• 中间区域是游戏区，ID为0的红色矩形就是目标车辆，右侧浅红色背景单元格，画有箭头的就是车库出口。点击鼠标选中某个车辆，可以鼠标拖动车辆移动，或者使用键盘的上下左右按键移动车辆。
• 下面的四个按钮分别是：
  • 最优解：系统提供的标准最快解答的步骤
  • 自动演示：系统根据标准最快解答步骤，自动移动车辆展示解答过程
  • 重置本局：重新恢复本局到初始位置
  • 随机新局：是随机生成一个关卡布局，默认生成的关卡布局可能较简单。

主界面有右侧是步骤对照区：

• 上面是最有参考步骤：默认会显示当前关卡通关的最少步数；当点击最优解时，会显示具体的通关移动步骤。
• 下面是手动移动车辆时的步骤：当用鼠标或者键盘移动车辆时，这里会显示当前的操作步骤；当点击自动演示时，这里也会显示自动演示时，对应的当前最新的操作步骤。

紧接着是关卡选择界面：

▲ 关卡选择界面

在关卡选择界面中，可以选择之前已经编辑好的关卡，左侧是所有该难度级别的关卡，右侧是该关卡的预览，点击确定，就会把选择的关卡加载到主界面的关卡地图中。

最后就是关卡编辑器，这是录入和编辑关卡的界面。

▲关卡编辑界面

这个界面是三列式布局：

• 最左侧是目前所有的已录入的关卡列表，每一行显示了该关卡的ID、难度等级和最小步数，当选中之后，可以点击加载选中关卡到中间进行继续编辑。点击新建空白关卡可以新建全新的关卡。
• 中间的是关卡的编辑地图区域，用鼠标选中后某个车辆后，可以进行拖动改变它的摆放位置，可以任意摆放，当改变摆放位置时，右侧表格里面对应的车辆的相关属性也会对应的修改，相应的行业会被选中。
• 最右侧的就是关卡的详细属性修改界面了。上方表格里面列出了所有车辆的ID，行号x、列号y，长度，以及方向。默认ID为0的是目标车辆。目标车辆固定在第一三行的第一列和第二列的位置。下方可以修改车辆的方向、长度、颜色。可以添加车辆，删除选中的车辆。修改完成之后，如果是编辑之前的某一个关卡，点击覆盖保存，如果是新建的空白关卡，则点击另存为新关卡，关卡的ID自增。

在上图中，我们当前正在录入的是游戏配套的关卡地图的高级关卡的最有一道关卡（上图右下角），只需要对照关卡地图设置好相应的代表车辆的矩形的长度和大小以及位置即可。

可以看到，在上述三个界面上，都有地图绘制的相关功能，为了保证一致性，我们将地图的绘制制作成了一个公共模块BoardCanvas，代码如下：

#pragma once
#include <QLabel>
#include <QMouseEvent>
#include "CarParkGame.h"

class BoardCanvas : public QLabel
{
Q_OBJECT
public:
    explicit BoardCanvas(QWidget* parent = nullptr,int rows=6,int cols=6,int cellSize=55);
    void setLevel(const LevelConfig& cfg);
    void setSelectedCarId(int id); // 选中高亮
    void setBoardSize(int w, int h);
signals:
    void carMoved(int carId, int newX, int newY);
    void carSelected(int carId);   // 点击车辆时通知编辑器
protected:
    void paintEvent(QPaintEvent*) override;
    void mousePressEvent(QMouseEvent*) override;
    void mouseMoveEvent(QMouseEvent*) override;
    void mouseReleaseEvent(QMouseEvent*) override;
   
private:
    QPoint getGridFromMouse(QPoint pos);
    int getCarIdAtGrid(int x, int y);

    LevelConfig m_level;
    int m_cellSize = 55;
    int m_offset = 20;

    //  固定地图尺寸
    int m_rows;
    int m_cols;

    bool m_isDragging = false;
    int m_dragCarId = -1;
    int m_selectedCarId = -1; // 高亮车辆ID
};

#include "BoardCanvas.h"
#include <QPainter>

BoardCanvas::BoardCanvas(QWidget* parent, int rows, int cols,int cellSize) : QLabel(parent), m_rows(rows), m_cols(cols),m_cellSize(cellSize)
{
	setStyleSheet("background-color: white;");
}

void BoardCanvas::setBoardSize(int w, int h)
{
	setFixedSize(w, h);
}

void BoardCanvas::setLevel(const LevelConfig& cfg)
{
	m_level = cfg;
	update();
}

void BoardCanvas::setSelectedCarId(int id)
{
	m_selectedCarId = id;
	update();
}

QPoint BoardCanvas::getGridFromMouse(QPoint pos)
{
	int col = (pos.x() - m_offset) / m_cellSize;
	int row = (pos.y() - m_offset) / m_cellSize;
	return QPoint(row, col);
}

int BoardCanvas::getCarIdAtGrid(int x, int y)
{
	for (const Car& car : m_level.cars) {
		for (const QPoint& pt : car.getCells()) {
			if (pt.x() == x && pt.y() == y)
				return car.id;
		}
	}
	return -1;
}

void BoardCanvas::paintEvent(QPaintEvent*)
{
	QPainter p(this);
	p.fillRect(rect(), Qt::white);
	p.setRenderHint(QPainter::Antialiasing);

	// 画网格
	p.setPen(QColor(220, 220, 220));
	for (int i = 0; i <= m_rows; ++i) {
		p.drawLine(m_offset, m_offset + i * m_cellSize, m_offset + 6 * m_cellSize, m_offset + i * m_cellSize);
	}

	for (int i = 0; i <= m_cols; ++i) {
		p.drawLine(m_offset + i * m_cellSize, m_offset, m_offset + i * m_cellSize, m_offset + 6 * m_cellSize);
	}

	// 绘制出口：第二行最后一列 (X=1, Y=5) → 绿色高亮
	int exitX = 2;
	int exitY = m_cols-1;
	int exitDrawX = m_offset + exitY * m_cellSize;
	int exitDrawY = m_offset + exitX * m_cellSize;
	p.fillRect(exitDrawX + 1, exitDrawY + 1, m_cellSize - 2, m_cellSize - 2, QColor(255, 220, 220));

    // 出口红色箭头（醒目）
	p.setPen(QPen(Qt::red, 3));
	int cx = exitDrawX + m_cellSize / 2;
	int cy = exitDrawY + m_cellSize / 2;
	int len = m_cellSize * 0.4;

	p.drawLine(cx - len, cy, cx + len, cy);
	QPolygon tri;
	tri << QPoint(cx + len, cy)
		<< QPoint(cx + len * 0.6, cy - len * 0.4)
		<< QPoint(cx + len * 0.6, cy + len * 0.4);
	p.drawPolygon(tri);


	// 画所有车辆（整体矩形，无分割，横竖正确）
	for (const Car& car : m_level.cars) {
		bool sel = (car.id == m_selectedCarId);
		bool target = car.isTarget;

		// 颜色
		QColor fill = target ? QColor(255, 60, 60) : car.color;
		p.setBrush(fill);

		// 选中：粗红框
		if (sel) p.setPen(QPen(Qt::darkRed, 3));
		else     p.setPen(Qt::black);

		// 坐标：pos.x = 行（上下），pos.y = 列（左右）
		int x = car.pos.x();
		int y = car.pos.y();

		// 屏幕绘制坐标
		int px = m_offset + y * m_cellSize;
		int py = m_offset + x * m_cellSize;
		int w, h;

		// 方向：横向左右，竖向上下 —— 100% 正确
		if (car.direction == HORIZONTAL) {
			w = car.length * m_cellSize;
			h = m_cellSize;
		}
		else {
			w = m_cellSize;
			h = car.length * m_cellSize;
		}

		// 整体画一个矩形，不分裂
		p.drawRect(px + 2, py + 2, w - 4, h - 4);
		// 车辆ID 居中绘制
		QRect textRect(px + 2, py + 2, w - 4, h - 4);
		p.setPen(Qt::black);
		p.drawText(textRect, Qt::AlignCenter, QString::number(car.id));
	}
}

void BoardCanvas::mousePressEvent(QMouseEvent* e)
{
	QPoint g = getGridFromMouse(e->pos());
	int id = getCarIdAtGrid(g.x(), g.y());
	if (id < 0) {
		m_selectedCarId = -1;
		update();
		emit carSelected(-1);
		return;
	}
	m_isDragging = true;
	m_dragCarId = id;
	m_selectedCarId = id;
	update();
	emit carSelected(id); // 通知编辑器选中车辆
}

void BoardCanvas::mouseMoveEvent(QMouseEvent* e)
{
	if (!m_isDragging || m_dragCarId < 0) return;
	QPoint g = getGridFromMouse(e->pos());
	emit carMoved(m_dragCarId, g.x(), g.y());
}

void BoardCanvas::mouseReleaseEvent(QMouseEvent*)
{
	m_isDragging = false;
	m_dragCarId = -1;
}

六、运行

这里以难度等级为高的第一个关卡来演示自动求解的功能：

▲ 高阶关卡的最优解与自动演示

上面就是核心功能的演示。这里演示的是高阶关卡的第一个，在关卡图册上写的是最少28步，它说少了，实际上最少需要移动53步！

▲ 关卡本上高阶难度第一个关卡

七、总结

《停车场出库（Car Park Puzzle）》这个游戏的初级关卡比较简单，中级、高级关卡则比较复杂，它的中高级关卡对于四五岁的小孩挫败感较强，即使对于成年人也很有挑战，游戏没有提供正确解法，人工试错效率低，也容易陷入死胡同。针对以上难点，本文使用广度优先搜索（BFS）算法实现了最短路径求解。 文章在上一篇迷宫寻路算法的基础上，对比分析了传统迷宫 BFS 与停车场状态空间 BFS 的差异，详细阐述了从单点坐标搜索到全局面状状态搜索的算法升级思路。使用 C++ 结合 Qt 实现了完整游戏系统包括主界面、关卡选择和关卡编辑，项目采用 CMake 构建，运行于 Windows+Visual Studio 环境，能够跨平台。具体内容涵盖停车场网格与车辆的数据结构建模、游戏状态编码与去重策略、BFS 最优解搜索核心流程、最小步数证明、Qt 界面绘制、鼠标拖拽与键盘交互逻辑设计，并增加了搜索状态计数功能以评估算法效率。实验表明，BFS 因其层序遍历特性，可保证首次抵达目标状态时即为最优解。本文完整实现了从游戏交互到自动求解的全流程，另外，还发现了市面上该类型游戏关卡设计图上最小步骤远远少于实际中能完成闯关的最小步骤，并解决了这些游戏没有提供答案的痛点。

参考：

• https://www.mathplayground.com/pg_car_park_puzzle.html