连连看规则要求 1，相同的卡片可以消除 2，两张卡片间连线的拐弯不能超过两个 3，用户操作和消除要有较为友好的动画 4，游戏最后要有解
这个是3年前在新光供应链任职，子公司技术总监让写的一份程序，当然最后承诺的机械键盘还是没给我们😅
首先这条是相对容易实现的，我们需要用到的仅仅是绘图与点击事件。考虑使用canvas画布绘制出对应的图案即可。
这里我们用大家最喜欢的微软旗下的mspaint软件以6*6的方格绘制大致模型。四周的方块我们做预留，主要用在下一步的连线绘制上。
具体操作上我们需要自定义View，在onDraw方法中绘制即可。核心代码如下
/** * 绘制棋盘的所有图标 当这个坐标内的值大于0时绘制 */ for (int x = 0; x < map.length; x += 1) { for (int y = 0; y < map[x].length; y += 1) { if (map[x][y] > 0) { Point p = indextoScreen(x, y); canvas.drawBitmap(icons[map[x][y]], p.x, p.y, null); } } }实现效果如图
这里是实现思路的核心，我们在考虑连接卡片的时候需要分析下，这里的连通算法要求至多两个拐点表示相连,也就是最多3条直线。这里我们需要用到分类算法与广度优先算法。 1，广度优先：两个节点node1和node2，将能和node1直接相连的节点加入集合S，然后再将能和S集合中节点直接相连的节点加入S（去重复），最后再将能和S集合中节点直接相连的节点加入S（去重复），如果node2在S集合中，则表示两者相连。 2，分类算法：（此程序采用）首先判断两个节点是否可以直接相连，如果否，则两个节点是否可以通过一个拐角相连（两个节点是一个正方形的对角线），如果还是否，则判断两个节点是否可以通过两个拐角相连。
具体分析如下
1，两个节点是否可以直接相连， 2，如果否，则考虑能否通过2条直线相连， 3，如果否，则考虑3条直线相连 4，否则就是不可连接
这种情况我们需要考虑竖直与水平两种情况
比如Point(1,1)到Point(3,1)为水平方向，Point(1,2)到Point(1,4)为竖直方向，核心算法如下
//这是针对一条线的情况 private boolean linkD(Point p1, Point p2) { //case 1:在同一条垂直线上 if (p1.x == p2.x) { int y1 = Math.min(p1.y, p2.y); int y2 = Math.max(p1.y, p2.y); boolean flag = true; for (int y = y1 + 1; y < y2; y++) { if (map[p1.x][y] != 0) { flag = false; break; } } if (flag) { return true; } } //case 2:在同一条水平线上 if (p1.y == p2.y) { int x1 = Math.min(p1.x, p2.x); int x2 = Math.max(p1.x, p2.x); boolean flag = true; for (int x = x1 + 1; x < x2; x++) { if (map[x][p1.y] != 0) { flag = false; break; } } if (flag) { return true; } } return false; }这种情况我们需要考虑"﹂“型、”﹁"型两种情况
比如从Point(1,1)到Point(3,2)的路径上，我们需要定位到中间拐点，即Point(3,1)、Point(1,2)，其中任意一点能通则认为是连通的。核心算法如下
//判断两个点是否可以连接，并将可以连接的中间点全部记录在path中，用于连线动画 private boolean link(Point p1, Point p2) { //如果是同一个点的话就返回false if (p1.equals(p2)) { return false; } //下面都不是同一个点 path.clear(); if (map[p1.x][p1.y] == map[p2.x][p2.y]) { //case 1:一条线可以连接的情况 if (linkD(p1, p2)) { path.add(p1); path.add(p2); return true; } //case 2:两条线可以连接的情况 //2.1"﹂"型 Point p = new Point(p1.x, p2.y); if (map[p.x][p.y] == 0) { if (linkD(p1, p) && linkD(p, p2)) { path.add(p1); path.add(p); path.add(p2); return true; } } //2.2"﹁"型 p = new Point(p2.x, p1.y); if (map[p.x][p.y] == 0) { if (linkD(p1, p) && linkD(p, p2)) { path.add(p1); path.add(p); path.add(p2); return true; } } expandX(p1, p1E);//加载p1水平方向的所有点 expandX(p2, p2E);//加载p2水品方向的所有点 for (Point pt1 : p1E) { for (Point pt2 : p2E) { if (pt1.x == pt2.x) {//如果水平值相等，即在同一垂直线上就有可能连接 if (linkD(pt1, pt2)) { path.add(p1); path.add(pt1); path.add(pt2); path.add(p2); return true; } } } } //换成垂直方向上的同理可得 expandY(p1, p1E); expandY(p2, p2E); for (Point pt1 : p1E) { for (Point pt2 : p2E) { if (pt1.y == pt2.y) { if (linkD(pt1, pt2)) { path.add(p1); path.add(pt1); path.add(pt2); path.add(p2); return true; } } } } return false; } return false; }这种情况我们仍然要考虑水平与竖直方向，这里仅以水平方向阐述思维方式
这里从Point(2,1)到Point(1,3)的路径上，我们获取Point(2,1)在水平方向上的延伸区域，得到点的集合Point(0,1)、Point(1,1)、Point(5,1)共计3个点同理我们获取Point(1,3)在水平方向上的延伸区域，得到点的集合Point(0,3)共计1个点然后使用双层循环判断，Point(2,1)在水平方向上的延伸点与Point(1,3)在水平方向上的延伸点是否可以用直线连接。这里我们找到Point(0,1)与Point(0,3)是直线连通点，即从Point(2,1)到Point(1,3)的路径上可以3条直线相连核心算法如下
//将p点左右的点都加到l中去 private void expandX(Point p, List<Point> l) { l.clear(); for (int x = p.x + 1; x < xCount; x++) { if (map[x][p.y] != 0) { break; } l.add(new Point(x, p.y)); } for (int x = p.x - 1; x >= 0; x--) { if (map[x][p.y] != 0) { break; } l.add(new Point(x, p.y)); } }我们在进行连通判断的时候，保存了有用户连通点的路径path.add(p1)。这里我们仅仅需要用这些连通点在方块中间绘制直线即可
代码实现如下
@Override protected void onDraw(Canvas canvas) { super.onDraw(canvas); /** * 绘制连通路径，然后将路径以及两个图标清除 */ if (path != null && path.length >= 2) { for (int i = 0; i < path.length - 1; i++) { Paint paint = new Paint(); paint.setColor(Color.CYAN); paint.setStyle(Paint.Style.STROKE); paint.setStrokeWidth(3); Point p1 = indextoScreen(path[i].x, path[i].y); Point p2 = indextoScreen(path[i + 1].x, path[i + 1].y); canvas.drawLine(p1.x + iconSize / 2, p1.y + iconSize / 2, p2.x + iconSize / 2, p2.y + iconSize / 2, paint); } /** * 消除连线上的第一个path[0] */ Point p = path[0]; map[p.x][p.y] = 0; /** * 消除连线上的最后一个path[0] */ p = path[path.length - 1]; map[p.x][p.y] = 0; /** * 消除 */ selected.clear(); /** * 1,消除线条:(path == null && path.length < 2) * 2,由后面的this.invalidate()方法刷新 */ path = null; } /** * 绘制棋盘的所有图标 当这个坐标内的值大于0时绘制 */ for (int x = 0; x < map.length; x += 1) { for (int y = 0; y < map[x].length; y += 1) { if (map[x][y] > 0) { Point p = indextoScreen(x, y); canvas.drawBitmap(icons[map[x][y]], p.x, p.y, null); } } } /** * 绘制选中图标，当选中时图标放大显示 */ for (Point position : selected) { Point p = indextoScreen(position.x, position.y); if (map[position.x][position.y] >= 1) { canvas.drawBitmap(icons[map[position.x][position.y]], null, new Rect(p.x - 5, p.y - 5, p.x + iconSize + 5, p.y + iconSize + 5), null); } } }具体效果(这里特意放大便于效果图)
在判断第一个Point不可连接后，我们需要循环判断棋盘上所有的Point是否可以连接，如果都不能连接。则分析问题出在 1，棋盘初始化本就无解 2，本来整个棋盘是可以完全消除所有单元格的，但是由于我们操作的顺序发生了变化，最终导致棋盘无解。
关于连连看有解，我查阅了下文档加上自己思索了下，大概有以下几种处理方法
这种处理方法demo中有加上，好处是棋子的随机性特别强，对于玩家来说难度挑战可以最大化，缺点是打乱图案是一种极不友好的交互方式。参考新浪微博、参考NGA
1）清空地图 2）随机生成一个图块，并执行下一行：随机在另一处生成同样的图块，如果之间有通路，就保留，否则回到上一行重新生成； 3）如果这样下去能生成整张地图，就结束，否则回溯继续试探。 也就是随机试探着一对一对地增加图块。 这是个拉斯维加斯算法+回溯法。又因为连连看破解的时候是从外向内的，类似拓扑排序，所以从简单往复杂方向生成的话，可以保证最后可破解的。
这个意义不大 1，算法时间复杂度开销太大。需要不停的回溯。 2，从概率的角度讲，实现一种生成有效棋盘的算法没有多大意义，因为即使产生的棋盘有效，我们在游戏时，最后也有可能将游戏的棋盘玩死。参考知乎
这个在棋子比较多的时候体验还行，像上图只有4个的情况下也会显得非常尴尬
规律可以是在保证有解的情况下轻微的颠倒棋子顺序，或者初始化棋盘的时候先有规律地初始化棋盘中心等方式，这种处理方法demo中也有加上。体验上可以保证有解，但是对于玩家来说难度挑战就难以最大化。
demo下载地址，免积分下载，如果需要积分可以留言邮箱。 这个确实是做前端程序好啊，想写个什么出来玩，就可以真的弄个出来玩。对于文中处理方式，大家如果有更好的方法，或者觉得哪里有问题的欢迎留言。如果觉得有用，欢迎收藏或者打赏
