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

利用电脑玩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;}

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

查看更多 下一篇