写点什么

用回溯法计算消消乐游戏最大得分

用户头像
DoneSpeak
关注
发布于: 3 小时前
用回溯法计算消消乐游戏最大得分

前言

这是一个非常非常简单的消消乐游戏。在一个 M*N 的网格中,一共有种物品。玩家可以列向或者行向得交换两个物品。当列向或者行向存在 3 ~ 5 个连续的相同物品时就可以消除将这些物品。消除 3,4,5 个连续的相同物品的得分分别为 1,3,10。当物品被消除之后,上方的物品会垂直下落对空缺进行填补。如果填补之后依旧存在 3~5 个连续且相同的物品,则继续进行消除。如果交换操作无法消除任何物品,则禁止该操作。题目要求在指定的步数内拿到最高的分数。



如上图所示,交换了图中 2 和 3 之后,会存在连续的 4 个 2 和 3 个 3 的情况,然后会一起消除,得分为 1 + 3 = 4 分。事实上,再消除完成之后,上方的物品掉落下来会出现连续的 3 个 2 和 4 个 4 还可以消除。

写个简单的消消乐

基本算法思路及需要解决的问题

基本的算法思路如下:


  1. 交换两个需要交换的点;

  2. 从交换的点出发,分别统计上下左右与之连续且相同的元素的数量,并按照记分规则进行记分。如果交换之后无法消除任何元素,则禁止点的交换。

  3. 消除需要消除的元素,然后将消除的元素上方的元素进行下移操作以填补空缺,顶部落空的位置则标记为无物品;

  4. 进行全盘的检查,对每个点按照步骤 2 中的方法进行标记记分;

  5. 如果全盘检查发现还存在可以消除的元素,则回到步骤 3 进行执行,否则结束检查调整。


为了实现用回溯法解决计算消消乐游戏最大得分问题,我们需要先实现一个简单的消消乐游戏。消消乐游戏需要解决的两个主要的问题如下(这里称游戏的网格为棋盘):


  • 检查是否存在连续 3~5 个连续且相同物品

  • 计算消除物品之后的得分

  • 消除物品和物品下落之后棋盘调整

问题 1: 检查是否存在连续 3~5 个连续且相同物品

根据游戏规则,每次操作都是在交换了两个相邻的点,那么我们只要从交换的点开始进行对上下左右的四个方向进行检查。为了方便程序的实现,我们实现了如下四个方向的 Enum 类,其中的Point类只有rowcol两个属性。


ArrowE.class


public enum ArrowE {    UP(1, "^", "up", new Point(-1, 0)),    RIGHT(2, ">", "right", new Point(0, 1)),    DOWN(3, "v", "down", new Point(1, 0)),    LEFT(4, "<", "left", new Point(0, -1))    ;
private final int value; private final String arrow; private final String name; private final Point vector;
private static final Map<ArrowE, ArrowE> arrowMapReverse; static { arrowMapReverse = new HashMap<ArrowE, ArrowE>(); addReverse(ArrowE.UP, ArrowE.DOWN); addReverse(ArrowE.LEFT, ArrowE.RIGHT); } // getters and setters ...
// 获取相反方向的方法 public ArrowE getReverse() { return arrowMapReverse.get(this); }}
复制代码


基本的思路很简单,从一个点出发,分别计算向上和下与之相同的物品的总数numUpnumDown,以及分别向左和向右与相同的物品的总数numLeftnumRight。然后按照计算规则计算 numUp + 1 + numDownnumLeft + 1 + numRight 的得分即可,如果得分大于 0,则执行物品消除的操作,否则不计算进行后续操作。


按照上面的逻辑,似乎很简单,而且马上就可以进行消除了,似乎只要消除交换点和numUp numDown numLeft numRight规定的范围就可以了。然而在实际的操作中,会出现更加复杂的场景。如下图:



在正常的交换之后,可以通过上面描述的方式对交换点的行列进行检查,并标记可消除的位置。但是交换之后,由于物品的掉落,会出现非常复杂的场景,如上图中的图三。甚至还可以出现更加复杂的情况,就是出现多个可以消除的不相连的区域。对于这种情况,只能对整个棋盘进行检查判断,找到所有可以消除的区域。


上图中的图三的可消除区域存在 2 个行和 4 个列,其中的一些位置会同时作用于一个行和列当中,如[3, 0], [3, 1]等。通过设计一个标记值,标记一个元素参与了行或者是列的消除。标记值为 1 时,表示该元素会在行中消除,2 是为列中消除,3 表示同时在行和列中消除(这里的 1 + 2 = 3 非常的巧妙)。如果一个点参与了行的消除,那么这个点就不能再参与其他行的消除,但可以继续参与其他列的消除。同理,如果这个点参与了列的消除,则这个点就不能再参与其他列的消除,但可以参与其他列的消除。当标记位置的值为 3 时,则该点无法继续参与其他行或者列的消除。


由于需要消除的元素构成的区域,无法简单的从一个点向上下左右进行拓展,因此需要设计一个二维数组进行标记。上图图 3 可以得到如下的标记位图。



在进行标记的过程中,可以按照简单版的方式进行记分,也可以直接对标记的二维数组进行行列统计记分。

问题 2: 计算消除物品之后的得分

上面已经简单的说明了,这里就不再重复说明。

问题 3: 消除物品和物品下落之后棋盘调整

消除操作对于整个过程来说也比较重要,但说简单也不简单,说复杂也不复杂。根据二维标记数组,找到存在需要消除的元素的列,进行列上的下落操作。核心的代码也就只有如下的一行:


chessboard[row][col] = chessboard[row - offset][col];
复制代码


列消除下落的完整代码如下:


/**    * 将第 col 列的,位于(row, col)上方offset距离的点下落位置到从(row, col)开始向上的位置    * 这将会从(row, col)开始覆盖    * <pre>    * 0 0 0  0  0    * 0 0 0  1  0    * 0 0 0  x  0    * 0 0 0  x  0    * 0 0 0  *  0    * 0 0 0 (*) 0    *    v    * row = row(*),col=col(*),offset=num(*)    *    v    * 0 0 0  0  0    * 0 0 0  0  0    * 0 0 0  0  0    * 0 0 0  1  0    * 0 0 0  x  0    * 0 0 0  x  0    * </pre>    * @param row 目的位置的行号    * @param col 目的位置的列号    * @param offset 下降距离    */private void dropColDownTo(int row, int col, int offset) {    if(offset == 0) {        return;    }    while(row - offset >= 0) {        // 如果 chessboard[row][col] == 0,则表示 chessboard[row][col] 上方的所有点都是 0        chessboard[row][col] = chessboard[row - offset][col];        row --;    }    while(row >= 0 && chessboard[row][col] != 0) {        chessboard[row][col] = 0;        row --;    }}
复制代码


完整的对整个棋盘进行调整的实现为如下的一个双重 for 循环。这里有一个细节需要特别注意,也就是必须对每一列从上到下进行调整。因为如果从下到上进行调整,会改变上方的元素原本的位置。从而导致调整之后调整上方元素的时候没有调整到正确的元素。


/*** 在指定的范围内,消除标记了的元素。消除方法为:从左到右对每一列进行检测,然后对每一列从上到下进行消除和下落。* <pre>*  0  0  0  0* (1)(1)(1) 0*  3  3  2  0*  4 (2)(2)(2)*  *  0  0  0  0* (0)(1)(1) 0*  3  3  2  0*  4 (2)(2)(2)*  *  0  0  0  0* (0)(0)(1) 0*  3  3  2  0*  4 (2)(2)(2)*  *  0  0  0  0* (0)(0)(1) 0*  3  3  2  0*  4 (0)(2)(2)* </pre>* @param range 需要调整的范围* @param marks 标记需要消除的元素*/private void eliminateAndDropDownAdjust(DetectionRange range, int[][] marks) {    for(int c = range.getColLeft(); c <= range.getColRight(); c ++) {        // 对每一列进行调整,从上到下        for(int r = range.getRowTop(); r <= range.getRowBottom(); r ++) {            // 计算被消除的列长度            int originalR = r;            while(r <= range.getRowBottom() && marks[r][c] != 0) {                // 取消标记                marks[r ++][c] = 0;            }            dropColDownTo(r - 1, c, r - originalR);        }    }}
复制代码


这里其实基本上已经完成了物品的消除和棋盘的调整。但可以注意到,上面的代码中有一个特别的类 DetectionRange。该类如同它的名字一样,为“检测范围”,在统计为需要元素和计算得分之后,并不需要对整个棋盘进行调整,仅需要对受影响的范围进行调整即可。通过对范围的限制,可以减少部分计算。


还有一点小小的优化在上方提及的,就是进行检测的时候全盘检测的时候是从左下角开始,分别向右和上进行检查。这是因为在进行消除之后,顶部的都是没有物品的位置,对其再进行重复的检测没有意义。此外,仅仅检测“右”和“上”两个方向即可覆盖全部检测,无需再进行”左“和”下“的检测,因为“右”和“左”,“上”和“下”是可以等价的。

用回溯法计算消消乐游戏最大得分

整体实现而言,都是很传统的回溯法实现方式。基本的思路如下:


MasScore(xiaoXiaoLeGame, leftStep) = MaxScore(everyPointInChess, xiaoXiaoLeGame, leftStep);MaxScore(pointInChess, xiaoXiaoLeGame, leftStep) =     max(向右交换得分 + MaxScore(xiaoXiaoLeGame.exchange(pointInChess, Right), leftStep - 1),        向上交换得分 + MaxScore(xiaoXiaoLeGame.exchange(pointInChess, Up), leftStep - 1));
复制代码


因为消消乐游戏的代码实现得比较完善,因而实现的代码也没有太多,这里就全部粘贴出来了。


package cn.donespeak.xiaoxiaole;
import java.util.ArrayList;import java.util.LinkedList;import java.util.List;
import cn.donespeak.xiaoxiaole.XiaoXiaoLe.OperationForbiddenException;
public class AutoPlayer { private XiaoXiaoLe xiaoXiaoLe; private int stepsLeft; private List<TipsPoint> tips; private int maxScore; public AutoPlayer(XiaoXiaoLe xiaoXiaoLe, int stepsLeft) { this.xiaoXiaoLe = xiaoXiaoLe; this.stepsLeft = stepsLeft; this.tips = new LinkedList<TipsPoint>(); this.maxScore = 0; } public void start() { maxScore = getMaxScore(xiaoXiaoLe, stepsLeft, tips); } public int getMaxScore() { return maxScore; } public List<TipsPoint> getTips() { return tips; } private int getMaxScore(XiaoXiaoLe xiaoXiaoLe, int stepsLeft, List<TipsPoint> tips) { if(stepsLeft == 0) { return 0; } int maxScore = 0; List<TipsPoint> tipsPicked = new ArrayList<>(); for(int r = xiaoXiaoLe.getRowNum() - 1; r >= 0; r --) { for(int c = 0; c < xiaoXiaoLe.getColNum(); c ++) {
if(xiaoXiaoLe.getChessboardCell(r, c) == 0) { continue; } List<TipsPoint> tipsRight = new ArrayList<>(); List<TipsPoint> tipsUp = new ArrayList<>(); XiaoXiaoLe xiaoXiaoLeRight = xiaoXiaoLe.getSnapshot(); XiaoXiaoLe xiaoXiaoLeUp = xiaoXiaoLe.getSnapshot(); int scoreRight = exchangeRight(xiaoXiaoLeRight, r, c, stepsLeft, tipsRight); int scoreUp = exchangeUp(xiaoXiaoLeUp, r, c, stepsLeft, tipsUp); int maxIncreasement = Math.max(scoreRight, scoreUp); maxScore = Math.max(maxIncreasement, maxScore);
if(maxIncreasement == maxScore) { if(maxIncreasement == scoreRight) { if(scoreRight == scoreUp) { // 两个方法得分相同时候,取路径最短的 tipsPicked = tipsRight.size() < tipsUp.size()? tipsRight: tipsUp; } else { tipsPicked = tipsRight; } } else if(maxIncreasement == scoreUp) { tipsPicked = tipsUp; } } } } tips.addAll(tipsPicked); return maxScore; }
private int exchangeUp(XiaoXiaoLe xiaoXiaoLe, int r, int c, int stepsLeft, List<TipsPoint> tips) { return exchange(xiaoXiaoLe, r, c, stepsLeft, ArrowE.UP, tips); }
private int exchangeRight(XiaoXiaoLe xiaoXiaoLe, int r, int c, int stepsLeft, List<TipsPoint> tips) { return exchange(xiaoXiaoLe, r, c, stepsLeft, ArrowE.RIGHT, tips); } private int exchange(XiaoXiaoLe xiaoXiaoLe, int r, int c, int stepsLeft, ArrowE arrow, List<TipsPoint> tips) { int increasement = 0; try { tips.add(new TipsPoint(r, c, arrow)); increasement += xiaoXiaoLe.exchangeWith(r, c, arrow); increasement += getMaxScore(xiaoXiaoLe, stepsLeft - 1, tips); // 如果操作允许,也就是没有抛出异常,其该操作得到分数,则添加该操作 } catch (OperationForbiddenException e) { // do nothing } finally { if(increasement == 0) { tips.remove(tips.size() - 1); } } return increasement; }}
复制代码


上面代码的TipPoint的基本结构如下:


public class TipsPoint extends Point {  // 可以考虑加入方向 ArrowE  private ArrowE arrow;}
复制代码


整体而言,实现的难度在于消消乐游戏的实现,而不在于回溯法的是实现。


完整的代码实现见:relaxinginjava/xiaoxiaole @Github

发布于: 3 小时前阅读数: 2
用户头像

DoneSpeak

关注

Let the Work That I've Done Speak for Me 2018.05.10 加入

Java后端开发

评论

发布
暂无评论
用回溯法计算消消乐游戏最大得分