编程之好1.17——俄罗斯方块游戏

问题：

让电脑自动下俄罗斯方块游戏。

解法：

对当前的积木块，枚举它旋转后的每一个形状从每一列落下的棋盘，将该棋盘和前一个棋盘进行对比，并打分，最后取得分最高的那个形状和那一列作为电脑的当前操作。（由于程序的输入数据比较多，我将其和代码打包放在资源下载中，需要的读者可以去下载）。

#include <iostream> #include <algorithm> #include <cstdlib> #include <ctime> using namespace std; // 积木块的信息 #define BLOCK_SIZE 7 #define ROTATE_SIZE 4 #define SIDE_LEN 4 const int BLOCK_AREA = SIDE_LEN*SIDE_LEN; // 棋盘的信息 #define HORIZ_LEN 12 #define VERT_LEN 15 const int CHESS_AREA = HORIZ_LEN*VERT_LEN; // 其它信息 #define TOP_STEP 25 #define inf 10000 // 计分信息 const int clearLineScore[] = {0, 1, 3, 7, 13}; struct Block // 积木块 { void init(unsigned char *l) { memcpy(layout, l, BLOCK_AREA); int i, j; for (i=0; i<SIDE_LEN; i++) { for (j=SIDE_LEN-1; j>=0 && layout[j*SIDE_LEN+i]==0; j--); maxRow[i] = j+1; } for(i=0; i<SIDE_LEN && maxRow[i]==0; i++); minCol = i; for (i=SIDE_LEN-1; i>=0 && maxRow[i]==0; i--); maxCol = i; } unsigned char layout[BLOCK_AREA]; // 积木块的布局 unsigned char maxRow[SIDE_LEN]; // 积木块每一列所占区域的最大行，取值从1开始 unsigned char minCol; // 积木块所占区域的最小值列和最大列，取值从0开始 unsigned char maxCol; }; Block blockSet[BLOCK_SIZE][ROTATE_SIZE]; // 7种积木块，每种积木块有4种旋转方向 unsigned char chess[CHESS_AREA]; // 棋盘的布局 unsigned char nextChess[CHESS_AREA]; // 下一步棋盘的布局 int height[HORIZ_LEN]; // 棋盘每一列所占区域的最小行，即高度 void calcHeight(unsigned char *curchess) // 计算当前棋盘的高度信息 { int i, j; for (i=0; i<HORIZ_LEN; i++) { for (j=0; j<VERT_LEN && curchess[j*HORIZ_LEN+i]==0; j++); height[i] = j; } } // 计算若积木块从offsetX列落下，会落在第几行，即offsetY int calcBottomOffsetY(const Block& b, int offsetX) { int offsetY = VERT_LEN; for (int i=0; i<SIDE_LEN; i++) { if (b.maxRow[i]==0) continue; offsetY = min(offsetY, height[offsetX+i]-b.maxRow[i]); } return offsetY; } // 将积木块贴到棋盘上 void pasteTo(unsigned char *curchess, const Block& b, int offsetX, int offsetY) { for (int i=b.minCol; i<=b.maxCol; i++) for (int j=0; j<SIDE_LEN; j++) { unsigned char bij = b.layout[j*SIDE_LEN + i]; unsigned char& cij = curchess[(j+offsetY)*HORIZ_LEN + i+offsetX]; if (bij && cij==0) cij = bij; else if (bij && cij) cout << "ERROR" << endl; } } // 消去[offsetY,offsetY+SIDE_LEN)中remline为1的行 void clearLines(unsigned char *curchess, int offsetY, unsigned char *remline) { int i, j, gap=0; for (j=offsetY+SIDE_LEN-1; j>=0; j--) { if (j-offsetY>=0 && remline[j-offsetY]) gap++; else if (gap) { memcpy(curchess+(j+gap)*HORIZ_LEN, curchess+j*HORIZ_LEN, HORIZ_LEN); } } } // 计算[offsetX,offsetX+SIDE_LEN)列的洞的个数 int calcHoles(unsigned char *curchess, int offsetX, int offsetY) { int i, j; int holeCount = 0; for (i=offsetX; i<offsetX+SIDE_LEN; i++) { if (i<0 || i>=HORIZ_LEN) continue; for (j=offsetY; j<VERT_LEN && curchess[j*HORIZ_LEN+i]==0; j++); for (; j<VERT_LEN; j++) if (curchess[j*HORIZ_LEN+i]==0) holeCount++; } return holeCount; } // 计算当前棋盘的得分 int calcScore(unsigned char *curchess, int offsetX, int offsetY) { int i, j, score = 0; int remlineCount = 0; unsigned char remline[SIDE_LEN] = {0}; // 统计消行数 for (j=offsetY; j<offsetY+SIDE_LEN; j++) { for (i=0; i<HORIZ_LEN && curchess[j*HORIZ_LEN+i]; i++); if (i==HORIZ_LEN) { remlineCount++; remline[j-offsetY] = 1; } } score += clearLineScore[remlineCount]; // 统计洞的个数 if (remlineCount) clearLines(curchess, offsetY, remline); int holeCount = calcHoles(curchess, offsetX, offsetY) - calcHoles(chess, offsetX, offsetY); score -= holeCount*4; // 位置过高则扣分 if (holeCount > 5) score -= 15; if (offsetY-remlineCount < VERT_LEN*3/5) score -= VERT_LEN*3/5-(offsetY-remlineCount); return score; } void output(unsigned char *curchess) { for (int j=0; j<VERT_LEN; j++) { for (int i=0; i<HORIZ_LEN; i++) cout << curchess[j*HORIZ_LEN+i] << " "; cout << endl; } } int main() { srand(time(0)); int i, j, k, n, m; // 初始化积木块 for (i=0; i<BLOCK_SIZE; i++) for (j=0; j<ROTATE_SIZE; j++) { unsigned char l[BLOCK_AREA]; for (k=0; k<BLOCK_AREA; k++) scanf("%d",&l[k]); blockSet[i][j].init(l); } // 初始化棋盘 for (i=0; i<CHESS_AREA; i++) scanf("%d",&chess[i]); // 显示前TOP_STEP步 int offsetX, offsetY; unsigned char tmpchess[CHESS_AREA]; for (n=TOP_STEP; n>=0; n--) { output(chess); calcHeight(chess); // 为每一步计算一次height数组，避免计算offsetY时过多的重复计算 int bind = rand()%BLOCK_SIZE; // 积木块的序号 int maxScore = -inf; for (j=0; j<ROTATE_SIZE; j++) // 要考虑积木块的各种旋转情况 { const Block& b = blockSet[bind][j]; // 得到当前的积木块 for (offsetX=-b.minCol; offsetX<HORIZ_LEN-b.maxCol; offsetX++) { // 计算从offsetX列落下，所落在棋盘的位置offsetY offsetY = calcBottomOffsetY(b, offsetX); if (offsetY<0) continue; memcpy(tmpchess, chess, CHESS_AREA); pasteTo(tmpchess, b, offsetX, offsetY); // 在棋盘中添加积木块 int curScore = calcScore(tmpchess, offsetX, offsetY); // 计算当前情况下的得分 if (curScore > maxScore) { maxScore = curScore; memcpy(nextChess, tmpchess, CHESS_AREA); } } } memcpy(chess, nextChess, CHESS_AREA); } }