分享天天爱消除算法

一、三消游戏的理解

我花了两周时间做了一个视频中的三消游戏，不过这只是个简单的Demo，存在一些bug，且几乎没有特效。在我看来，三消游戏的开发需要投入大量精力去打磨，打磨得越精细，游戏就越容易成为精品。目前市场上的三消游戏数量众多，主流的是地图型且近乎无尽模式的游戏，这类游戏拥有各种消除特效和多样化的过关方式，玩起来体验不错。但玩家在遇到较难的关卡时，可能需要多次尝试，只有运气好的时候才能过关，否则就会卡在关卡中。

三消游戏真正的扩展方向在于过关模式，这需要开发一个特殊的地图编辑器，并与策划人员紧密配合，不断对游戏进行升级。

二、消除涉及到的简单算法

2.1 生成随机地图算法

在三消游戏中，存在各种各样的地图，这里我们以最简单的矩形地图为例。该算法的需求如下：

1. 生成一个随机地图，要求地图中不能出现三个横着相同或者三个竖着相同的元素。
2. 生成的地图要保证用户移动一步就能进行消除（即不能是死地图）。

乍一看，这个需求似乎颇具挑战性。但仔细思考后，我们可以先不考虑第二个需求。若生成的是死地图，重新生成一张地图即可。经过测试，生成死地图的概率非常低。

下面是算法实现的详细描述： 假设地图的坐标原点 (0, 0) 位于左上角。算法从地图的左上角开始，x 坐标从左向右依次生成元素，y 坐标从上到下依次生成元素。在生成每个元素时，需要先判断其左边两个元素和上面两个元素是否同色。若同色，则要排除该颜色。

例如，假设已经生成的地图如下：

2, 3, 3, 4, 1, 3, 2
1, 2, 3, 4, 4, 3, 3
1, 2, 3, 2, 2, X

由于 X 的左边两个元素都是 2，所以 X 不能再是 2；其上面两个元素都是 3，所以 X 也不能是 3。因此，X 的取值只能从 0、1、4 中随机选取一个。

以下是实现该算法的伪代码：

enum MatchItemType {
kRedItem = 0, // 0
kGreenItem,   // 1
kBlueItem,    // 2
kWhiteItem,   // 3
kOrangeItem
};

MatchItemType getOneRandomTypeExceptParameter(const MatchItemType& type) {
MatchItemType allType[5] = {kRedItem, kGreenItem, kBlueItem, kWhiteItem, kOrangeItem};
std::vector<MatchItemType> restType;
for (int i = 0; i < 5; ++i) {
if (allType[i] != type) {
restType.push_back(allType[i]);
}
}
int restSize = restType.size();
int randomIndex = rand() % restSize;
return restType[randomIndex];
}

Array2D getOneRandomMapArray() {
Array2D map = Array2D(7, 7);
bool findThreeSameInX = false;
bool findThreeSameInY = false;
for (int y = 0; y < 7; ++y) {
for (int x = 0; x < 7; ++x) {
MatchItemType randomType = (MatchItemType)(rand() % 5);
if (x >= 2) {
// 左边两个是同色
if (map.Get(x - 1, y) == map.Get(x - 2, y)) {
// need find a new type
findThreeSameInX = true;
} else {
findThreeSameInX = false;
}
} else {
findThreeSameInX = false;
}
if (y >= 2) {
// 上面两个是同色
if (map.Get(x, y - 1) == map.Get(x, y - 2)) {
// need find a new type;
findThreeSameInY = true;
} else {
findThreeSameInY = false;
}
} else {
findThreeSameInY = false;
}
if (findThreeSameInX == false && findThreeSameInY == false) {
// do nothing
} else if (findThreeSameInX == true && findThreeSameInY == false) {
randomType = getOneRandomTypeExceptParameter(map.Get(x - 1, y));
} else if (findThreeSameInX == false && findThreeSameInY == true) {
randomType = getOneRandomTypeExceptParameter(map.Get(x, y - 1));
} else {
// 这里原代码函数调用参数有误，可修改为合适的逻辑
// 例如添加一个重载函数处理两个参数的情况
randomType = getOneRandomTypeExceptParameter(map.Get(x - 1, y));
}
map.Set(x, y, randomType);
}
}
return map;
}

2.2 判断地图是否是死地图

如果整个地图中，用户无论移动哪一步都无法进行消除，那么该地图就是死地图，需要重新生成。

以下是两种简单的情况示例：

// case 1
/////[x]//////[x]////////
//[x][o][x][x][o][x]/////
/////[x]//////[x]////////
/////////////////////////

// case 2
////////[x]//////////////
/////[x][o][x]///////////
////////[x]//////////////
////////[x]//////////////
/////[x][o][x]///////////
////////[x]//////////////

在 case 1 中，是横着有两个同色元素的情况，此时移动一步能消除的情况有 6 种，左边 3 种，右边 3 种。在 case 2 中，是竖着有两个同色元素的情况，移动一步能消除的情况同样是 6 种，上面 3 种，下面 3 种。明确了这些情况后，编写代码就相对容易了。需要注意的是，一旦找到可以消除的组合，就应直接返回结果。

以下是实现该功能的代码：

std::vector<MatchItem*> getThreeMatchItemCanRemoveByOneStep(const Array2D & map) {
std::vector<MatchItem*> result;
int maxX = 7;
int maxY = 7;
for (int y = 0; y < maxY; ++y) {
for (int x = 0; x < maxX; ++x) {
if (x + 1 < maxX) {
// case 1
if (map.Get(x, y)->getType() == map.Get(x + 1, y)->getType()) {
MatchItemType currentType = map.Get(x, y)->getType();
// check 6 item, one move one step can combine three same item
if (x - 2 >= 0) {
if (map.Get(x - 2, y)->getType() == currentType) {
// find one
result.push_back(map.Get(x, y));
result.push_back(map.Get(x + 1, y));
result.push_back(map.Get(x - 2, y));
return result;
}
}
if (x - 1 >= 0 && y - 1 >= 0) {
if (map.Get(x - 1, y - 1)->getType() == currentType) {
// find one
result.push_back(map.Get(x, y));
result.push_back(map.Get(x + 1, y));
result.push_back(map.Get(x - 1, y - 1));
return result;
}
}
if (x + 2 < maxX && y - 1 >= 0) {
if (map.Get(x + 2, y - 1)->getType() == currentType) {
// find one
result.push_back(map.Get(x, y));
result.push_back(map.Get(x + 1, y));
result.push_back(map.Get(x + 2, y - 1));
return result;
}
}
if (x + 3 < maxX) {
if (map.Get(x + 3, y)->getType() == currentType) {
// find one
result.push_back(map.Get(x, y));
result.push_back(map.Get(x + 1, y));
result.push_back(map.Get(x + 3, y));
return result;
}
}
if (x + 2 < maxX && y + 1 < maxY) {
if (map.Get(x + 2, y + 1)->getType() == currentType) {
// find one
result.push_back(map.Get(x, y));
result.push_back(map.Get(x + 1, y));
result.push_back(map.Get(x + 2, y + 1));
return result;
}
}
if (x - 1 >= 0 && y + 1 < maxY) {
if (map.Get(x - 1, y + 1)->getType() == currentType) {
// find one
result.push_back(map.Get(x, y));
result.push_back(map.Get(x + 1, y));
result.push_back(map.Get(x - 1, y + 1));
return result;
}
}
}
}
if (y + 1 < maxY) {
MatchItemType currentType = map.Get(x, y)->getType();
// case 2
if (map.Get(x, y)->getType() == map.Get(x, y + 1)->getType()) {
if (y - 2 >= 0) {
if (map.Get(x, y - 2)->getType() == currentType) {
// find one
result.push_back(map.Get(x, y));
result.push_back(map.Get(x, y + 1));
result.push_back(map.Get(x, y - 2));
return result;
}
}
if (x + 1 < maxX && y - 1 >= 0) {
if (map.Get(x + 1, y - 1)->getType() == currentType) {
// find one
result.push_back(map.Get(x, y));
result.push_back(map.Get(x, y + 1));
result.push_back(map.Get(x + 1, y - 1));
return result;
}
}
if (x + 1 < maxX && y + 2 < maxY) {
if (map.Get(x + 1, y + 2)->getType() == currentType) {
// find one
result.push_back(map.Get(x, y));
result.push_back(map.Get(x, y + 1));
result.push_back(map.Get(x + 1, y + 2));
return result;
}
}
if (y + 3 < maxY) {
if (map.Get(x, y + 3)->getType() == currentType) {
// find one
result.push_back(map.Get(x, y));
result.push_back(map.Get(x, y + 1));
result.push_back(map.Get(x, y +   3));
return result;
}
}
if (x - 1 >= 0 && y + 2 < maxY) {
if (map.Get(x - 1, y + 2)->getType() == currentType) {
// find one
result.push_back(map.Get(x, y));
result.push_back(map.Get(x, y + 1));
result.push_back(map.Get(x - 1, y + 2));
return result;
}
}
if (x - 1 >= 0 && y - 1 >= 0) {
if (map.Get(x - 1, y - 1)->getType() == currentType) {
// find one
result.push_back(map.Get(x, y));
result.push_back(map.Get(x, y + 1));
result.push_back(map.Get(x - 1, y - 1));
return result;
}
}
}
}
}
}
return result;
}

通过以上算法，我们可以实现三消游戏中随机地图的生成以及死地图的判断，为游戏的开发提供了基础支持。