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

问题：

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

解法：

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

#include <iostream>#include <algorithm>#include <cstdlib>#include <ctime>using namespace std;// 积木块的信息#define BLOCK_SIZE7#define ROTATE_SIZE 4#define SIDE_LEN4const int BLOCK_AREA = SIDE_LEN*SIDE_LEN;// 棋盘的信息#define HORIZ_LEN12#define VERT_LEN15const int CHESS_AREA = HORIZ_LEN*VERT_LEN;// 其它信息#define TOP_STEP25#define inf10000// 计分信息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列落下，会落在第几行，即offsetYint 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列落下，所落在棋盘的位置offsetYoffsetY = 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);}}