利用电脑玩Android版“天天连萌”刷高分（三）——连连看消除搜索

差点忘了写接下来的这两篇博客了，这篇如果接不上上一篇，请勿见怪啊，因为我自己都忘了。

上两篇分别提到了截图和图像识别，接下来这一篇是说一下连连看的消除算法。
这个算法看似很厉害，其实我在这里采用的是很笨拙的方法，就是枚举。
在上一篇已经连游戏里的方块转换成一个二维数组，所以就通过一个两层循环，遍历每一个元素，看能不能跟其他元素消除，代码如下：

for (int i = 1; i < CODE_ROW - 1; i++) {
				for (int j = 1; j < CODE_COL - 1; j++) {
					if (imageCodes[i][j] != 0) {
						Point point = search(i, j);
						if (point == null) {
							continue;
						}
						touch(new Point(i, j));
						touch(point);
						imageCodes[i][j] = 0;
						imageCodes[point.x][point.y] = 0;
						anyClear = true;
						System.out
								.println(String.format("消除 %d:%d  %d:%d", i, j, point.x, point.y));
					}
				}

其中search方法是搜索可以与该广场消除的方块，返回的point表示另一个方块的坐标。如果搜索不到就返回null，传的对象分别是纵坐标与横坐标。touch是向模拟器发送点击事件，当然每次消除我们要点击两个。消除之后，将对应元素设为。

关于search()方法的实现，就是枚举。我们知道连连看消除有三类路线，一类是直线的，有4种情况，第二类是拐一个弯的，有8种情况，第三类是拐两个弯的，有16种情况。我采用的是比较直接也是比较笨拙的方法，直接对它们进行枚举，代码如下：

/**
	 * 搜索，返回最优点。
	 * 
	 * @return
	 */
	public Point search(int x, int y) {
		return LianlianKan.twoCornerSearch(imageCodes, x, y);
	}
	/**
	 * 连连看搜索算法。
	 * 
	 * @author Geek_Soledad
	 */
	public static class LianlianKan {
		/**
		 * 水平搜索
		 * 
		 * @param datas
		 *            数组
		 * @param row
		 *            对比数值所在的行
		 * @param col
		 *            对比数值所在的列
		 * @param atRow
		 *            进行水平搜索时所在的行
		 * @return
		 */
		private static Point moveHorizon(int[][] datas, int row, int col, int atRow, int atCol) {
			// 再拐左
			for (int k = atCol - 1; k >= 1; k--) {
				if (datas[atRow][k] == datas[row][col]) {
					return new Point(atRow, k);
				} else if (datas[atRow][k] != 0) {
					break;
				}
			}
			// 再拐右
			for (int k = atCol + 1; k < CODE_COL - 1; k++) {
				if (datas[atRow][k] == datas[row][col]) {
					return new Point(atRow, k);
				} else if (datas[atRow][k] != 0) {
					break;
				}
			}
			return null;
		}

		/**
		 * 竖直搜索
		 * 
		 * @param datas
		 *            数组
		 * @param row
		 *            对比数值所在的行
		 * @param col
		 *            对比数值所在的列
		 * @param atCol
		 *            进行水平搜索时所在的列
		 * @return
		 */
		private static Point movePortrait(int[][] datas, int row, int col, int atRow, int atCol) {
			// 再拐上
			for (int k = atCol - 1; k >= 1; k--) {
				if (datas[k][atCol] == datas[row][col]) {
					return new Point(k, atCol);
				} else if (datas[k][atCol] != 0) {
					break;
				}
			}
			// 再拐下
			for (int k = atCol + 1; k < CODE_ROW - 1; k++) {
				if (datas[k][atCol] == datas[row][col]) {
					return new Point(k, atCol);
				} else if (datas[k][atCol] != 0) {
					break;
				}
			}
			return null;
		}

		/**
		 * 两个角搜索
		 * 
		 * @param datas
		 *            数组
		 * @param x
		 *            纵坐标
		 * @param y
		 *            横坐标
		 * @return
		 */
		public static Point twoCornerSearch(int[][] datas, int x, int y) {
			// 向左进行搜索
			for (int i = y - 1; i >= 0; i--) {
				// 向左进行直线搜索
				if (datas[x][i] == datas[x][y]) {
					return new Point(x, i);
				} else if (datas[x][i] != 0) {
					break;
				}
				// 向左，然后拐上进行直角搜索
				for (int j = x - 1; j >= 0; j--) {
					if (datas[j][i] == datas[x][y]) {
						return new Point(j, i);
					} else if (datas[j][i] != 0) {
						break;
					}
					// 向左，拐上，再水平搜索
					Point point = moveHorizon(datas, x, y, j, i);
					if (point != null) {
						return point;
					}
				}
				// 向左，然后拐下进行直角搜索
				for (int j = x + 1; j < CODE_ROW; j++) {
					if (datas[j][i] == datas[x][y]) {
						return new Point(j, i);
					} else if (datas[j][i] != 0) {
						break;
					}
					// 向左，拐下，再水平搜索
					Point point = moveHorizon(datas, x, y, j, i);
					if (point != null) {
						return point;
					}
				}
			}
			// 横向往右搜索
			for (int i = y + 1, length = CODE_COL; i < length; i++) {
				// 向右直线搜索
				if (datas[x][i] == datas[x][y]) {
					return new Point(x, i);
				} else if (datas[x][i] != 0) {
					break;
				}
				// 向右，然后拐上进行直角搜索。
				for (int j = x - 1; j >= 0; j--) {
					if (datas[j][i] == datas[x][y]) {
						return new Point(j, i);
					} else if (datas[j][i] != 0) {
						break;
					}
					// 向右，拐上，再水平搜索
					Point point = moveHorizon(datas, x, y, j, i);
					if (point != null) {
						return point;
					}
				}
				// 向右，然后拐下进行直角搜索
				for (int j = x + 1; j < CODE_ROW; j++) {
					if (datas[j][i] == datas[x][y]) {
						return new Point(j, i);
					} else if (datas[j][i] != 0) {
						break;
					}
					// 向右，拐下，再水平搜索。
					Point point = moveHorizon(datas, x, y, j, i);
					if (point != null) {
						return point;
					}
				}
			}
			// 纵向往上搜索
			for (int i = x - 1; i >= 0; i--) {
				if (datas[i][y] == datas[x][y]) {
					return new Point(i, y);
				} else if (datas[i][y] != 0) {
					break;
				}
				// 向上，然后拐左进行直角搜索。
				for (int j = y - 1; j >= 0; j--) {
					if (datas[i][j] == datas[x][y]) {
						return new Point(i, j);
					} else if (datas[i][j] != 0) {
						break;
					}
					// 向上，拐左，再竖直搜索
					Point point = movePortrait(datas, x, y, i, j);
					if (point != null) {
						return point;
					}
				}
				// 向上，然后拐右进行直角搜索
				for (int j = y + 1; j < CODE_COL; j++) {
					if (datas[i][j] == datas[x][y]) {
						return new Point(i, j);
					} else if (datas[i][j] != 0) {
						break;
					}
					// 向上，拐右，再竖直搜索
					Point point = movePortrait(datas, x, y, i, j);
					if (point != null) {
						return point;
					}

				}
			}
			// 纵向往下搜索
			for (int i = x + 1, length = CODE_ROW; i < length; i++) {
				if (datas[i][y] == datas[x][y]) {
					return new Point(i, y);
				} else if (datas[i][y] != 0) {
					break;
				}
				// 向下，然后拐左进行直角搜索。
				for (int j = y - 1; j >= 0; j--) {
					if (datas[i][j] == datas[x][y]) {
						return new Point(i, j);
					} else if (datas[i][j] != 0) {
						break;
					}
					// 向下，拐右，再竖直搜索
					Point point = movePortrait(datas, x, y, i, j);
					if (point != null) {
						return point;
					}
				}
				// 向下，然后拐右进行直角搜索
				for (int j = y + 1; j < CODE_COL; j++) {
					if (datas[i][j] == datas[x][y]) {
						return new Point(i, j);
					} else if (datas[i][j] != 0) {
						break;
					}
					// 向下，拐右，再竖直搜索
					Point point = movePortrait(datas, x, y, i, j);
					if (point != null) {
						return point;
					}
				}
			}
			return null;
		}
	}

举其中的一个例子，比如我们往右搜索，如果发现右边的不为0但也不和它相等，说明是其他方块，那这条路径就不能执行了。如果与它相等，说明是两个相同的方块，那么返回这个位置的坐标。如果为0，那么我们就可以进行下一步的搜索，比如继续往右（直线情况），或者往上往下（有拐弯的路径）。我把这三种情况都写在一起了，因为我在写的时候发现，直线路径是直角路径的一种特殊情况，而直角路径其实也是两个拐弯的路径的特殊情况。

当每个元素都遍历完之后，我们要判断是否全部消除完毕，如果消除完了，方法执行结束，进行下一次截图。如果没有，那么我们要再遍历搜索一次，因为可能存在的情况是一开始的方块不能被消除，但随着其他方块被消除之后，他们可以被消除了。
另外，我在这里还增加了一个anyClear的布尔变量，这是为了避免死循环，比如出现以下情况：
xo
ox
这种情况下是无法被消除的，游戏里面将会重新组合这些广场。所以当遍历完发现没有方块被消除时，需要重新截图。当然除了出现上面情况，实际操作时发现，其他情况也可能出现无法被消除问题，比如消除了一些方块后，会出现perfect等图案，这些图会影响一些方块的识别。这时也需要重新截图。所以实际上startSearch方法应该如下：

public boolean startSearch(BufferedImage image) throws InterruptedException {
		boolean anyClear = false;
		do {
			anyClear = false;
			for (int i = 1; i < CODE_ROW - 1; i++) {
				for (int j = 1; j < CODE_COL - 1; j++) {
					if (imageCodes[i][j] != 0) {
						Point point = search(i, j);
						if (point == null) {
							continue;
						}
						touch(new Point(i, j));
						touch(point);
						imageCodes[i][j] = 0;
						imageCodes[point.x][point.y] = 0;
						anyClear = true;
						System.out
								.println(String.format("消除 %d:%d  %d:%d", i, j, point.x, point.y));
					}
				}
			}
		} while (anyClear && !isEmpty());
		return anyClear;
	}

这篇就写到这里。下一篇说一下模拟按键，以及针对游戏、手机的实际情况，对程序的优化。