三消算法

起因

大一上学期的C语言大作业我们编写了一个消消乐游戏，示例视频如下

效果不错，但代码惨不忍睹，尤其是消去判断部分(游戏主体逻辑)。
今天我在这里回顾一下编写的经历及一些改进。

编写代码的过程

构造了一个7行8列的数组存放数字0-5，其中，0代表的是被消去的状态，1-5分别对应着5种图案
而消去判断函数的作用就是接受这个数组，并判断此时是否有可以消去的地方
将其置为0，然后使0上方的图案下降，最上面的随机生成新图案
返回是否可以消去(true/false)，并记录下本次消去的数目(作为分数)
重复调用这个函数，直到返回值为0，即不再有可以消去的地方，就完成了一次排查
我最开始写的代码如下 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
bool judgemove(int a[][8], int *score)
{
    judge = 0;
    for (i = 1; i < 6; i++)
        for (j = 0; j < 8; j++)
        {
            if (a[i][j] != 0&&a[i][j] == a[i - 1][j] && a[i][j] == a[i + 1][j])//逐列寻找
            {
                for (m = i - 1; m <= i + 1; m++)
                {
                    a[m][j] = 0;//找到了三个相连，就将其置为0
                    setpicture(m, j, a[m][j]);//打印消去状态(黑色方块)
                }
                judge = 1;//确实消去了
            }
        }
    for (i = 0; i < 7; i++)//同上，但是逐行寻找
        for (j = 1; j < 7; j++)
        {
            if (a[i][j] != 0 && a[i][j] == a[i][j - 1] && a[i][j] == a[i][j + 1])
            {
                for (m = j - 1; m <= j + 1; m++)
                {
                    a[i][m] = 0;
                    setpicture(i, m, a[i][m]);
                }
                judge = 1;
            }
        }
    Sleep(200);//停顿以显示哪些被消去了
    for (j = 0; j < 8; j++)
        for (i = 6; i >= 0; i--)//逐列从下向上遍历，实现移动
            while (a[i][j] == 0)
            {
                for (m = i; m > 0; m--)
                    a[m][j] = a[m - 1][j];
                if (m == 0)//如果到达最上面，最上面的变成随机颜色
                    a[m][j] = random_picture();
            }
    for (i = 0; i < 7; i++)//重新打印
        for (j = 0; j < 8; j++)
            setpicture(i, j, a[i][j]);
    return judge;
}

这段代码的不足是明显的，即仅仅判断了连续三个消除的情况，对于连续四个或五个，只会消去前三个
同时，对于T字形，由于纵向遍历在前，只会消除一竖排，而横排不会被消去
这都是很明显的错误
基于此，不断尝试，修修补补，终于把所有情况都写进来了，得到如下代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
bool judgemove(int a[][8],int version ,int *score)//version代表不同位置使用的判断（是否掉落与替换）
{
    static int judge1=1, judge2=0, judge3=0, i, j, m, n,p,q;
    int countx = 0, county = 0;//countx,county用来判断一次消去的个数（有没有五连消）
    if(version==1)
        Sleep(200);//暂停来调试
    judge1 = 0;//judge1用来判断还有没有待消去的棋子
    //如果出现了可以消去的棋子，先赋成零（形象化变为白色）
    for (i = 0; i < 7; i++)//遍历方向是从上到下，一竖列一竖列遍历
        for (j = 0; j < 8; j++)
        {
            judge2 = 0;
            for (m = i + 1; m<=5 && a[i][j] != 0 && a[m][j] == a[i][j] && a[m + 1][j] == a[i][j]; m++)
            //从小到大遍历，m<=5是因为最多纵向遍历到倒数第三行
            //利用了逻辑运算符的短路特性，最后一个相同点要在循环外面赋值
            {
                if (a[m][j - 1] == a[m][j] && a[m][j + 1] == a[m][j]&&j<7&&j>0)//t字形
                {
                    if (a[m][j + 2] == a[m][j])
                        a[m][j + 2] = 0;
                    if (a[m][j - 2] == a[m][j])
                        a[m][j - 2] = 0;
                    if ((!a[m][j + 2]) && (!a[m][j - 2]))//形成炸弹
                        bomb++;
                    a[m][j - 1] = 0;
                    a[m][j + 1] = 0;
                }
                judge3 = 0;
                for (n = j - 1; n > 0 && a[m][j] != 0 && a[m][n] == a[m][j] && a[m][n - 1] == a[m][j]; n--)//反向探索
                //每消去一个棋子前，都要看看它的横向能不能消去
                {
                    a[m][n] = 0;
                    judge3 = 1;
                    countx++;
                }
                if (judge3&&n>=0&&n<8)
                    a[m][n] = 0;
                judge3 = 0;
                for (n = j + 1; j < 6 && a[m][j] != 0 && a[m][n] == a[m][j] && a[m][n + 1] == a[m][j]; n++)//正向探索
                {
                    a[m][n] = 0;
                    judge3 = 1;
                    countx++;
                }
                if (judge3 && n < 8 && n >= 0)
                {
                    a[m][n] = 0;
                    countx++;
                    if (countx >= 5)
                        bomb++;
                    countx = 0;
                }
                a[m][j] = 0;
                county++;
                judge2 = 1;
                judge1 = 1;
            }
            if (judge2 == 1)//judge2=1代表纵向消去，为最后一个相同点单独赋值
            {
                if (a[m][j - 1] == a[m][j] && a[m][j + 1] == a[m][j]&&j<7&&j>0)//t字形
                {
                    if (a[m][j + 2] == a[m][j])
                        a[m][j + 2] = 0;
                    if (a[m][j - 2] == a[m][j])
                        a[m][j - 2] = 0;
                    if ((!a[m][j + 2]) && (!a[m][j - 2]))//形成炸弹
                        bomb++;
                    a[m][j - 1] = 0;
                    a[m][j + 1] = 0;
                }
                judge3 = 0;
                for (n = j - 1; n > 0 && a[m][j] != 0 && a[m][n] == a[m][j] && a[m][n - 1] == a[m][j]; n--)//反向探索
                {
                    a[m][n] = 0;
                    judge3 = 1;
                    countx++;
                }
                if (judge3&&n>=0&&n<8)
                    a[m][n] = 0;
                judge3 = 0;
                for (n = j + 1; j < 6 && a[m][j] != 0 && a[m][n] == a[m][j] && a[m][n + 1] == a[m][j]; n++)//正向探索
                {
                    a[m][n] = 0;
                    judge3 = 1;
                    countx++;
                }
                if (judge3&&n<8&&n>=0)
                {
                    a[m][n] = 0;
                    countx++;
                    if (countx >= 5)
                        bomb++;
                    countx = 0;
                }
                a[m][j] = 0;
                county+=2;
                if (county >= 5)
                    bomb++;
                county = 0;
            }
            for (n = j + 1; n <= 6 && a[i][j] != 0 && a[i][n] == a[i][j] && a[i][n + 1] == a[i][j]; n++)
                //n<=6是因为最多横向遍历到倒数第三列，逻辑运算符利用了短路特性
            {
                judge3 = 0;
                for (m = i - 1; m>1 && a[i][n] != 0 && a[m][n] == a[i][n] && a[m - 1][n] == a[i][n]; m--)//反向探索
                {
                    a[m][n] = 0;
                    judge3 = 1;
                    county++;
                }
                if (judge3&&m>=0&&n<8)
                    a[m][n] = 0;
                judge3 = 0;
                for (m = i + 1; i < 5 && a[i][n] != 0 && a[m][n] == a[i][n] && a[m + 1][n] == a[i][n]; m++)//正向探索
                {
                    a[m][n] = 0;
                    judge3 = 1;
                    county++;
                }
                if (judge3 && m < 7 && n < 8)
                {
                    a[m][n] = 0;
                    county++;
                    if (county >= 5)
                        bomb++;
                    county = 0;
                }
                a[i][n] = 0;
                countx++;
                judge2 = 2;
                judge1 = 1;
            }
            if (judge2 == 2)//judge2=2代表横向消去，为最后一个相同点单独赋值
            {
                judge3 = 0;
                for (m = i - 1; m > 1 && a[i][n] != 0 && a[m][n] == a[i][n] && a[m - 1][n] == a[i][n]; m--)
                {
                    a[m][n] = 0;
                    judge3 = 1;
                    county++;
                }
                if (judge3&&m>=0 && n < 8)
                    a[m][n] = 0;
                judge3 = 0;
                for (m = i + 1; i < 5 && a[i][n] != 0 && a[m][n] == a[i][n] && a[m + 1][n] == a[i][n]; m++)
                {
                    a[m][n] = 0;
                    judge3 = 1;
                    county++;
                }
                if (judge3 && m < 7 && n < 8)
                {
                    a[m][n] = 0;
                    county++;
                    if (county >= 5)
                        bomb++;
                    county = 0;
                }
                a[i][n] = 0;
                countx += 2;
                if (countx >= 5)
                    bomb++;
                countx = 0;
            }
            if (judge2)//只要有消去，就将起始点消去（前面要保留，否则不能判断既横向又纵向的情况）
                a[i][j] = 0;
        }
    if (version != 2&&version!=3)//如果是判断能不能移动或初次进入，不打印	
    {
        for (p = 0; p < 7; p++)//重新打印，显示出黑色矩形
            for (q = 0; q < 8; q++)
            {
                setpicture(p, q, a[p][q]);
                if (a[p][q] == 0)
                    (*score)++;//分数增加
            }
    }
    if (version == 2)
        return judge1;
    if(version==1)
        Sleep(200);
    for (j = 0; j < 8; j++)
        for (i = 6; i >= 0; i--)
            while (a[i][j] == 0)
            {
                for (m = i; m > 0; m--)
                    a[m][j] = a[m - 1][j];
                if (m == 0)//如果到达最上面，最上面的变成随机图像
                    a[m][j] = random_picture();
            }
    if(version==1)
        for (i = 0; i < 7; i++)//重新打印
            for (j = 0; j < 8; j++)
                setpicture(i, j, a[i][j]);
    return judge1;
}

实在太长了，我自己都懒得看，而且有太多重复的部分
值得一提的是，该函数又引入了一个参数version
version代表该函数被调用的位置
version1:游戏过程中，正常地判断，返回，消去，打印
version2:反馈给鼠标控制函数移动是否合法，只需要是否能消去这个结果(true/false)
version3:刚进入游戏，此时不会把中间过程打印在屏幕上
并且会记录每次消去的个数，到达五个会给予奖励
这个函数成功地实现了所需的功能，并作为了提交版本
而今天再看时，发现如此复杂的原因是每次都是找到时就将它们置零
这就代表当时就要考虑所有情况，十分麻烦
今天我做了修改，仅仅将要消去的元素记录下来，到最后再一并消去
代码如下 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
bool judgemove(int a[][8], int version, int* score)//version代表不同位置使用的判断（是否掉落与替换）
{
    static int judge1 = 1, judge2 = 0, i, j, m, n, p, q;
    int countx = 0, county = 0;//countx,county用来判断一次消去的个数（有没有五连消）
    int count, change[2][100], t=0;//change数组记录下要消去的坐标，第一行记录行数，第二行记录列数
    if (version == 1)
        Sleep(200);//暂停来调试
    judge1 = 0;//judge1用来判断还有没有待消去的棋子
    //如果出现了可以消去的棋子，先赋成零（形象化变为白色）
    for (i = 0; i < 7; i++)//遍历方向是从上到下，一竖列一竖列遍历
        for (j = 0; j < 8; j++)
        {
            judge2 = 0;
            for (m = i + 1; m <= 5 && a[i][j] != 0 && a[m][j] == a[i][j] && a[m + 1][j] == a[i][j]; m++)
            //从小到大遍历，m<=5是因为最多纵向遍历到倒数第三行
            //利用了逻辑运算符的短路特性，最后一个相同点要在循环外面赋值
            {
                change[0][t] = m;
                change[1][t] = j;
                ++t;
                ++county;
                judge2 = 1;
                judge1 = 1;
            }
            if (judge2 == 1)//judge2=1代表纵向消去，为最后一个相同点单独赋值
            {
                change[0][t] = m;
                change[1][t] = j;
                ++t;
                county += 2;
                if (county >= 5)
                    bomb++;
                county = 0;
            }
            for (n = j + 1; n <= 6 && a[i][j] != 0 && a[i][n] == a[i][j] && a[i][n + 1] == a[i][j]; n++)
                //n<=6是因为最多横向遍历到倒数第三列，逻辑运算符利用了短路特性
            {
                change[0][t] = i;
                change[1][t] = n;
                ++t;
                ++countx;
                judge2 = 2;
                judge1 = 1;
            }
            if (judge2 == 2)//judge2=2代表横向消去，为最后一个相同点单独赋值
            {
                
                change[0][t] = i;
                change[1][t] = n;
                ++t;
                countx += 2;
                if (countx >= 5)
                    bomb++;
                countx = 0;
            }
            if (judge2)//只要有消去，就将起始点消去
                a[i][j] = 0;
        }
    for (i = 0; i < t; ++i)
        a[change[0][i]][change[1][i]] = 0;
    if (version != 2 && version != 3)//如果是判断能不能移动或初次进入，不打印	
    {
        for (p = 0; p < 7; p++)//重新打印，显示出黑色矩形
            for (q = 0; q < 8; q++)
            {
                setpicture(p, q, a[p][q]);
                if (a[p][q] == 0)
                    (*score)++;//分数增加
            }
    }
    if (version == 2)
        return judge1;
    if (version == 1)
        Sleep(200);
    for (j = 0; j < 8; j++)
        for (i = 6; i >= 0; i--)
            while (a[i][j] == 0)
            {
                for (m = i; m > 0; m--)
                    a[m][j] = a[m - 1][j];
                if (m == 0)//如果到达最上面，最上面的变成随机图像
                    a[m][j] = random_picture();
            }
    if (version == 1)
        for (i = 0; i < 7; i++)//重新打印
            for (j = 0; j < 8; j++)
                setpicture(i, j, a[i][j]);
    return judge1;
}

至此，该函数已足够简单了(还是有一些重复的部分)
或许以后还会修改呢😂