在上一篇俄罗斯方块 AI 算法讲解中我们介绍了 El-Tetris 传统算法的实现思路,本篇文章就是这个算法的具体实现过程。不过在实现之前,你需要先制作出自己的俄罗斯方块游戏,可以参考我前面的文章:Windows 游戏编程之俄罗斯方块(一)Windows 游戏编程之俄罗斯方块(二)

我们在研究 EI-Tetris 算法的时候,已经知道了这个算法的核心就是 6 种特征的计算,而接下来讲解的就是如何使用代码实时的计算这 6 种特征值的过程。

1. 获取大方块属性

在计算之前,我们需要将俄罗斯方块中 7 种大方块的属性重新计算,在原有的代码中,我们使用了打表法的形式记录了 7 种大方块的形状,不过这些数据在实现 AI 算法的过程是不够的,我们需要更多:

// AI 需要的初始化方块结构
typedef struct AIBlock
{
	unsigned short shape;		//原始数字代表形状
	int leftSpare;				//左侧孔隙
	int rightSpare;				//右侧孔隙
	int topSpare;				//上方孔隙
	int bottomSpare;			//下方孔隙
	int width;					//宽
	int height;					//高
} AIBlock;

上面是新的 7 种方块的结构, shape 变量是原有大方块形状所代表的变量:

static unsigned short gBlockList[BT_NUM][BS_NUM] = {
	{0x00C6, 0x04C8, 0x00C6, 0x04C8}, //S
	{0x006C, 0x08C4, 0x006C, 0x08C4}, //Z
	{0x00E8, 0x088C, 0x002E, 0x0C44}, //J
	{0x00E2, 0x044C, 0x008E, 0x0C88}, //L
	{0x000F, 0x8888, 0x000F, 0x8888}, //I
	{0x04C4, 0x00E4, 0x08C8, 0x004E}, //T
	{0x00CC, 0x00CC, 0x00CC, 0x00CC}  //O
};

现在除了需要大方块表示形状的原始变量,还需要知道这些方块真正的长宽,因为在原来俄罗斯方块的实现过程中,每个大方块相当于用 4 * 4 的矩形表示:

4*4 矩形

但这有个问题,我们无法获取大方块的真实横纵坐标。就如上图所示,这个方块真实的宽高是 3 * 2 ,其中第 0 行和第 3 行是空行,而第 3 列同样是空列,这些属性在原有的程序中无法直接获取。当然如果你要可以忍受效率的影响,每一次动态计算是可行的。不过为了提高效率,这里我们用这个新的结构重新表示一下现有的方块形状。

之所以要获取这些信息,是为了定位我们大方块的真正位置,看看下面几个示意图:

相同位置不同样式

在原来的代码中,我们这样定义一个大方块:

// 方块
typedef struct Block
{
	int row;		// 方块水平位置
	int col;		// 方块垂直位置

	BlockType type;		// 方块类型
	BlockState state;	// 方块状态
} Block;

这种表示在原有的游戏中是可行的,但是如果用这个结构表示上方图中的四种大方块,会发现它们的 row 和 col 完全一样,我们无法区分当前大方块是具体的哪一种,为了解决这个问题,所以我们重新定义了大方块的结构描述,说白了就是确定一下大方块周围缝隙的大小。

我们无需重新修改原来的代码,只需要在程序初始化的时候动态的计算一下现有所有大方块这些属性的值就好了,当然你也可以修改原来的结构,不过那样初始化的过程可能稍微麻烦一点。

// 初始化 AI 列表
void initAIBlockList(AIBlock block[][BS_NUM])
{
	if (!block) {
		return;
	}

    for (int i = 0; i < BT_NUM; i++)
    {
        for (int j = 0; j < BS_NUM; j++)
        {
            unsigned short blockFlag = gBlockList[i][j];

			//计算左右两侧空余空间的大小
			int leftSpare = 0;
			for (int i = 0; i < BLOCK_WIDTH; i++) {
				//从左侧开始查
				if (!((0x1111 << i) & blockFlag)) {
					leftSpare++;
				}
				else {
					break;
				}
			}


			int rightSpare = 0;
			for (int i = 0; i < BLOCK_WIDTH; i++) {
				//从右侧开始查
				if (!((0x8888 >> i)& blockFlag)) {
					rightSpare++;
				}
				else {
					break;
				}
			}


			//计算上下两侧空余空间的大小
			int topSpare = 0;
			for (int i = 0; i < BLOCK_HEIGHT; i++) {
				//从上侧开始查
				if (!((0x000F << (4 * i)) & blockFlag)) {
					topSpare++;
				}
				else {
					break;
				}
			}


			int bottomSpare = 0;
			for (int i = 0; i < BLOCK_HEIGHT; i++) {
				//从下侧开始查
				if (!((0xF000 >> (4 * i))& blockFlag)) {
					bottomSpare++;
				}
				else {
					break;
				}
			}


			//初始化
			block[i][j].shape = blockFlag;
			block[i][j].leftSpare = leftSpare;
			block[i][j].rightSpare = rightSpare;
			block[i][j].topSpare = topSpare;
			block[i][j].bottomSpare = bottomSpare;
			block[i][j].width = BLOCK_WIDTH - leftSpare - rightSpare;
			block[i][j].height = BLOCK_HEIGHT - topSpare - bottomSpare;
        }
    }
}

在原有的方块形状数组之上,我们重新生成了一个数组,并根据原有大方块的表示,计算出这些大方块周围的缝隙,以及大方块真正的宽和高,在接下来的代码中,直接使用新生成的 block 数组即可。

2. 计算 Landing Height

计算 Landing Height 只需要将现有容器的高度加上现有大方块高的一半,代码如下:

//计算 Landing Height
static float getLandingHeight(const Tetris* tetris, BlockType type, BlockState state, int column)
{
	const AIBlock* props = getBlockProps(type, state);
	assert(props);

	//水平越界,给一个无限大的值
	if (column > TETRIS_CONTAINER_WIDTH - 2 - props->width) {
		return -1.0f;
	}

	//模拟下落,最终小块的位置
	Block block = { 0, -props->leftSpare + column + 1, type, state };
	while (!hitTest(&block, tetris)) {
		moveDown(&block);
	}
	block.row -= 1;

	float lh = (TETRIS_CONTAINER_HEIGHT - 1) - block.row - props->topSpare - props->height * 0.5f;

	assert(lh >= 0);

	return lh;
}

函数中 column 表示大方块所在的列,这个列是真正的列,不是原有结构中的 col 属性。我们需要通过 column 的值反向求出当前大方块的位置,即计算出大方块的 row 和 col,接着根据当前大方块的位置模拟真实下落后的状态,最后求出 Landing Height 的特征值。

3. 计算 Rows eliminated

//计算 Rows eliminated 
static int getEliminatedRows(const Tetris* tetris, BlockType type, BlockState state, int column)
{
	//合并
	unsigned long container[TETRIS_CONTAINER_HEIGHT] = { 0 };
	int row = getMergedContainer(tetris, type, state, column, container);
	if (row < 0) {
		return -1;
	}

	//查看销行
	int eraseLine = 0;
	for (int i = 0; i < BLOCK_HEIGHT; i++)
	{
		if (container[row + i] == 0x0FFF) {
			eraseLine++;
		}
	}

	return eraseLine;
}

计算消行的内容和原来类似,枚举容器中的行,当出现 0x0FFF 的行时,消行数加一。

4. 计算 Row Transitions 和 Column Transitions

这两个特征值的计算方法类似,这里只讲解一下 Row Transitions 的计算方块。

//计算 Row Transitions
static getRowTransitions(const Tetris* tetris, BlockType type, BlockState state, int column)
{
	//合并
	unsigned long container[TETRIS_CONTAINER_HEIGHT] = { 0 };
	if (getMergedContainer(tetris, type, state, column, container) < 0) {
		return -1;
	}


	//检测行反转
	int transitions = 0;
	for (int i = BLOCK_HEIGHT; i < TETRIS_CONTAINER_HEIGHT - 1; i++)
	{
		int lastBit = 0x01;

		for (int j = 0; j < TETRIS_CONTAINER_WIDTH; j++)
		{
			unsigned char currBit = (container[i] >> j) & 0x01;

			if (currBit != lastBit) {
				++transitions;
			}

			lastBit = currBit;
		}
	}

	return transitions;
}

代码中首先是将现有的方块和容器合并,求出合并后的容器结果。接着枚举所有行,查看每一行的变换次数。算法很简单,只需要先记录上一次小方块的样式,将其存储到 lastBit 变量,接着查看当前的小方块样式,如果现在的和上一次不同,则转换加 1 ,查看后不要忘记更新 lastBit 。

5. 计算 Number of Holes

计算洞洞的个数,其实和计算 Row Transitions 方法类似,只不过这一次不再是记录变化的次数,而是记录真正空洞的个数。

//计算 Number of Holes
static int getNumberOfHoles(const Tetris* tetris, BlockType type, BlockState state, int column)
{
	//合并
	unsigned long container[TETRIS_CONTAINER_HEIGHT] = { 0 };
	if (getMergedContainer(tetris, type, state, column, container) < 0) {
		return -1;
	}

	//计算洞洞
	int holes = 0;
	unsigned long rowHoles = 0;
	unsigned long prevRow = container[BLOCK_HEIGHT];
	for (int i = BLOCK_HEIGHT+1; i < TETRIS_CONTAINER_HEIGHT - 1; i++)
	{
		//计算当前行洞洞位置
		rowHoles = ~container[i] & (prevRow | rowHoles);

		//统计
		for (int j = 1; j < TETRIS_CONTAINER_WIDTH - 1; j++)
		{
			holes += ((rowHoles >> j) & 0x01);
		}

		prevRow = container[i];
	}

	return holes;
}

代码核心实际上就是双层 for 循环,枚举每一个位置,不过有一个 rowHoles 变量需要注意一下。这个变量表示上一行洞洞的情况,这个变量主要的作用是为了区分当前的遇见的空洞是否为真的空洞,如下图:

空洞示例

假设上面是容器最下方的截图,其中橙色是容器中已经有小方块的位置,其中灰色和蓝色是没有小方块的位置,而图中只有蓝色是真正的 “洞”。也就是说,同一个列,上一行有小方块的位置一下行才是洞。

6. 计算 Well Sums

计算“井”的方法很简答,就是要看当前列两边是否都有方块,且当前列是空的地方才算“井”。

//计算 Well Sums
static int getWellSums(const Tetris* tetris, BlockType type, BlockState state, int column)
{
	//合并
	unsigned long container[TETRIS_CONTAINER_HEIGHT] = { 0 };
	if (getMergedContainer(tetris, type, state, column, container) < 0) {
		return -1;
	}


	//计算井
	int wellSums = 0;

	for (int i = 1; i < TETRIS_CONTAINER_WIDTH - 1; i++)
	{
		for (int j = BLOCK_HEIGHT; j < TETRIS_CONTAINER_HEIGHT; j++)
		{
			if (((container[j] >> i) & 0x01) == 0
				&& (container[j] >> (i + 1) & 0x01) == 1
				&& (container[j] >> (i - 1) & 0x01) == 1
				)
			{
				wellSums++;

				for (int k = j + 1; k < TETRIS_CONTAINER_HEIGHT; k++)
				{
					if (((container[k] >> i) & 0x01) == 0) {
						wellSums++;
					} else {
						break;
					}
				}
			}
		}
	}

	return wellSums;
}

这里需要记住,最后计算的不是“井”的深度,而是深度的累加和。

7. 计算最终得分

实现了上述 6 种特征的计算方法,接下来就是将这些特征值乘以一个比例系数,最终求和得到的就是最后的总分。

//计算 score
double evaluateScore(const Tetris* tetris, BlockType type, BlockState state, int column)
{
	//计算第一个参数
	double score = getLandingHeight(tetris, type, state, column);
	if (score < 0) {
		return INT_MIN;
	}

	score = score * -4.500158825082766;

	//定义函数指针
	int (*func[5])(const Tetris * tetris, BlockType type, BlockState state, int column) = 	  {
		getEliminatedRows,
		getRowTransitions,
		getColumnTransitions,
		getNumberOfHoles,
		getWellSums
	};


	//设定函数系数
	double coeffs[5] = {
		 3.4181268101392694,
		 -3.2178882868487753,
		 -9.348695305445199,
		 -7.899265427351652,
		 -3.3855972247263626
	};


	for (int i = 0; i < 5; i++)
	{
		int ret = func[i](tetris, type, state, column);
		if (ret < 0) {
			return INT_MIN;
		}

		score += (ret * coeffs[i]);
	}

	return score;
}

8. 实现智能 AI

最后要想实现真正的智能,需要在每一次出现新方块的时候,计算出大方块最适合的下落位置。说白了就是枚举大方块所有的下落可能,然后求出分数最高的位置。

//获取推荐方块
void getRecommenderBlock(const Tetris* tetris, const Block* src, Block* dst)
{
	assert(src && dst);

	double scores[BS_NUM][TETRIS_CONTAINER_HEIGHT] = { 0 };
	double maxScore = INT_MIN;
	int col = 0;

	dst->col = 0;
	dst->row = 0;
	dst->state = src->state;
	dst->type = src->type;

	//枚举原类型的所有形式
	for (int i = 0; i < BS_NUM; i++)
	{
		//枚举所有位置
		for (int j = 0; j < TETRIS_CONTAINER_HEIGHT; j++)
		{
			scores[i][j] = evaluateScore(tetris, dst->type, i, j);

			if (scores[i][j] >= maxScore) {
				maxScore = scores[i][j];
				dst->state = i;
				col = j;
			}
		}
	}


	//获取推荐方块属性
	const AIBlock* props = getBlockProps(dst->type, dst->state);
	assert(props);


	//获取位置
	dst->col = -props->leftSpare + col + 1;
	while (!hitTest(dst, tetris)) {
		moveDown(dst);
	}
	dst->row -= 1;
}

参数 src 代表当前大方块的位置,而最终计算的结果被保存在 dst 参数中。

到此为止,俄罗斯方块的智能 AI 系统算是实现完毕,下面可以看看运行效果,具体程序演示已经放到了下载页面

tetris