分享天天爱消除算法

1.三消游戏我的理解

上面视频中的游戏，我做了2个星期时间，只能算个简单Demo，还有bug，特效也几乎没有。感觉三消游戏主要靠磨，越磨越精品。市场上三消游戏已经超级多了。主流的是地图型的，几乎是无尽模式，各种消除特效，各种各样的过关方式，玩起来还是不错的，就是遇到比较难的关卡，要多试几次，运气非常好的时候就过了，不然卡死。

这个游戏真正扩展的地方就是过关模式，还需要整个特殊的地图编辑器，配合策划，不断升级游戏。

2.消除涉及到的简单算法

2.1 生成随机地图算法

      

有各种各样的地图，这里拿最简单的矩形来说。需求：

1.这个算法要生成一个随机的地图，不能有3个横着相同或者3个竖着相同。

2.这个地图用户移动一步能进行消除(不能是个死地图)

初看到这个需求感觉还是蛮难的，后来想了下第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 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.Get(x, y – 1));

}

map.Set(x, y, randomType);

}

}

return map;

}

3.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]//

这里用注释画了简单的两种情况，注意x的位置。case1 是横着有两个同色的情况，移动一步能消除只有6种可能，左边3种，右边3种。下面是竖着有两个同色的情况，移动一步能消除也是6种情况。上面3种，下面3种。知道了这个，代码就容易了。记得找到一个就直接return。

vector getThreeMatchItemCanRemoveByOneStep(const Array2D & map){

vector 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 < GameGlobal::xMapCount){

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;

}