用qt实现一个迷宫，玩家通过键盘方向键移动，从左上角走到右下角即为成功。
先来看下最终实现效果：
其实重点在于随机迷宫的生成，而迷宫的生成靠的是并查集算法。
思路参考自bigsai（感谢授权）：
游戏总结如下：
游戏规则为若两个小方块之间没有线，说明是互通的，可以移动，否则两个方块之间被“墙”阻隔不能移动。因此我们先画一个由多个小方块组成的初始地图，然后随机擦除其中的一些线，就可以生成一个迷宫了。就像这样：
而将两个方格之间的线擦除，是不是也就意味着这两个方格是一个集合了（他们是一家子了），所以擦除线的过程实际上就是两个原本不相交的集合合并的过程，而并查集解决的正是合并的问题。知道了使用并查集，那么对于地图而言，该如何实现这个合并过程呢？我们可以将地图中每个方格抽象成一个个点，比如对于5 x 5大小的地图，就有25个小方格，按顺序排个号，这时我们可以发现，其实数值和数值在地图中的坐标是存在关系的，比如：11 / 5 == 2；11 % 5 == 1，而（2， 1）正是11所在地图的位置，利用这种关系就可以把地图当做一个一维数组来看待。
这样一来就好办了，直接套用并查集的模板即可。
游戏的目的是从左上角走到右下角，也就意味着左上角的点和右下角的点一定是可以连通的。为了生成随机迷宫，我们在地图中随机找一些点，判断它和它上下左右四个方向的点是否连通，不连通则将两个集合连通，一直重复，直到左上角和右下角连通了，说明游戏是有解的了，这时就不再合并了。总结一下就是：我们为了让游戏是有解的，就在地图中随机找点合并一些集合，当发现有解时，就不再合并。当把两个点连通时，就将它们之间的线擦除，也就形成了视觉上的随机地图。
迷宫生成了，但是在玩家走的时候，如何判断当前所走方向有没有被阻隔（有没有线）呢？这很好办，通过一个二维数组来记录两个点之间有没有线，比如：在合并的过程中，合并1和2，则让arr[1][2] = 1，这样当1走向2或2走向1时判断arr[1][2]是否为1即可。
这样的话，随机地图产生了，并且左上角到右下角是连通的，判断两格之间是否能走的问题也解决了，迷宫也就没什么难的了。
下面看一下一些关键的代码片段：
初始化地图（画方格）：
int x1 = BEGINX, y1 = 0, x2 = ENDX, y2 = 0; for (int i = 0; i < LINENUM; i++) { y1 += LINEHEIGHT; y2 = y1; //画横线 line.setLine(x1, y1, x2, y2); m_pPainter->drawLine(line); //画竖线 line.setLine(y1, x1, y2, x2); m_pPainter->drawLine(line); }
生成随机地图：
//当左上角的点和右下角的点不连通 while (find(0) != find(SQUARESNUM - 1)) { //在合法范围内随机生成一个点 int randnum = rand() % SQUARESNUM; //随机找一个邻居（上下左右） int neighbor = getNeighbor(randnum); if (find(randnum) != find(neighbor)) { m_qvectorIsUnicom[randnum][neighbor] = m_qvectorIsUnicom[neighbor][randnum] = 1; //将两个点之间的线擦除 myDrawLine(randnum, neighbor); merge(randnum, neighbor); } }
这里的画线只是为了满足视觉上的效果，因此，我只是把画笔的颜色改成了白色，覆盖了之前的黑色，也就形成了擦除的效果。
找邻居：
int Widget::getNeighbor(int n) { //计算得到点n在地图中的坐标 int x = n / ROWNUM; int y = n % ROWNUM; QVector<int> arr; //判断是否出界 if (y > 0) arr.push_back(n - 1);//左邻居 if (y < ROWNUM - 1) arr.push_back(n + 1);//右邻居 if (x > 0) arr.push_back((x - 1) * ROWNUM + y);//上邻居 if (x < ROWNUM - 1) arr.push_back((x + 1) * ROWNUM + y);//下邻居 //取一个随机的邻居 int tmp = rand() % arr.size(); return arr[tmp]; }
擦除线：
void Widget::myDrawLine(int n, int m) { int x1 = n / ROWNUM; int y1 = n % ROWNUM; int x2 = m / ROWNUM; int y2 = m % ROWNUM; //取两点中间线位置 int x3 = (x1 + x2) / 2 + 1; int y3 = (y1 + y2) / 2 + 1; QPen pen; pen.setColor(QColor(Qt::white)); pen.setWidth(3); QLineF line; m_pPainter->begin(m_pPixmap); m_pPainter->setPen(pen); //上下方向的点，画横线 if (x1 - x2 == 1 || x1 - x2 == -1) { line.setLine(y1 * LINEWIDTH + BEGINX, x3 * LINEHEIGHT + BEGINX, (y1 + 1) * LINEWIDTH + BEGINX, (x3 + 1) * LINEHEIGHT); } else { line.setLine(y3 * LINEWIDTH + BEGINX, x1 * LINEHEIGHT + BEGINX, (y3 + 1) * LINEWIDTH, (x1 + 1) * LINEHEIGHT + BEGINX); } m_pPainter->drawLine(line); m_pPainter->end(); }
并查集的合并和查询：
int Widget::find(int n) { if (m_qvectorArray[n] == n) return n; return find(m_qvectorArray[n]); } void Widget::merge(int n, int m) { int fn = find(n), fm = find(m); if (fn == fm) return; if (m_qvectorSize[fn] > m_qvectorSize[fm]) std::swap(fn, fm); m_qvectorArray[fn] = fm; m_qvectorSize[fm] += m_qvectorSize[fn]; return; }
至此就完成了迷宫的核心部分，剩下的就是通过qt完成控制，画线以及对游戏体验的优化了，见源代码。最后放上操作指南：按下方向键开始游戏，方向键控制走向，超过一分钟游戏自动结束，按下重置按钮更换地图，游戏就绪。
效果图：
源代码（包含可执行程序）：
https://gitee.com/gao-yuelong/qtdemo/tree/master/mazes
最后还是感谢bigsai提供的思路，非常感谢。
