消灭星星算法

引言

在消灭星星游戏中，StarMatrix 是对一个内置的 Star* 二维数组的包装。当 StarMatrix 获得触摸点后，我们需要解决如何操作这个 Star* 二维数组的问题。下面我们将详细探讨星星的连接和消除逻辑。

星星的连接与消除流程

1. 触摸事件处理

当玩家点击屏幕时，StarMatrix 的 onTouch 方法会被触发，该方法是由 GameLayer 传过来的触摸点的入口。以下是 onTouch 方法的实现：

void StarMatrix::onTouch(const Point& p) {
Star* s = getStarByTouch(p);
if (s) {
genSelectedList(s);
CCLOG("SIZE = %d", selectedList.size());
deleteSelectedList();
}
}

• getStarByTouch 方法：通过触摸点得到矩阵中一个星星的方法，它通过一些像素与矩阵坐标的转换来实现。具体代码如下：

  Star* StarMatrix::getStarByTouch(const Point& p) {
  int k = p.y / Star::STAR_HEIGHT; // 这里要用 k 转一下 int，不然得不到正确结果
  int i = ROW_NUM - 1 - k;
  int j = p.x / Star::STAR_WIDTH;
  if (i >= 0 && i < ROW_NUM &&
  j >= 0 && j < COL_NUM &&
  stars[j] != nullptr) {
  CCLOG("i=%d,j=%d", i, j);
  return stars[j];
  } else {
  return nullptr;
  }
  }
  

• genSelectedList 方法：用于得到一串连接的星星的函数。
• deleteSelectedList 方法：用于删除一串连接的星星的函数。

2. 生成待删除星星列表（广度优先遍历算法）

当点击星星时，需要把与点击星星相连且颜色相同的星星都找出来，并让它们消失。这里使用了广度优先遍历算法，并且用一个队列来辅助实现。具体步骤如下：

1. 把被点击的星星放进遍历队列。
2. 分别对遍历队列里面的元素进行如下操作：
   • 把该元素放进待删除的列表（即我们要的列表）。
   • 检查上方是否有相同颜色的星星，如果有，把上方的星星放进遍历队列。
   • 检查下方是否有相同颜色的星星，如果有，把下方的星星放进遍历队列。
   • 检查左边是否有相同颜色的星星，如果有，把左边的星星放进遍历队列。
   • 检查右边是否有相同颜色的星星，如果有，把右边的星星放进遍历队列。
3. 遍历队列队头出列，得到新的队头。
4. 重复步骤 2，直到遍历队列为空。

以下是 genSelectedList 方法的代码实现：

void StarMatrix::genSelectedList(Star* s) {
selectedList.clear(); // 记得每次点击都要先把待删除列表清空
std::deque<Star*> travelList; // 遍历队列
travelList.push_back(s); // 把点击的星星放进遍历队列
std::deque<Star*>::iterator it;
for (it = travelList.begin(); it != travelList.end();) { // 当遍历队列为空的时候停止
Star* star = *it;
Star* linkStar = nullptr;
int index_i = star->getIndexI();
int index_j = star->getIndexJ();
// 上
if (index_i - 1 >= 0 && (linkStar = stars[index_i - 1][index_j])) { // 判断是否数组越界
if (!linkStar->isSelected() && linkStar->getColor() == star->getColor()) { // 判断是否已经被纳入选择队列并且与遍历队列的星星颜色一样
travelList.push_back(stars[index_i - 1][index_j]); // 如果没有被纳入选择队列，并且颜色一样就加入遍历队列
}
}
// 下
if (index_i + 1 < ROW_NUM && (linkStar = stars[index_i + 1][index_j])) {
if (!linkStar->isSelected() && linkStar->getColor() == star->getColor()) {
travelList.push_back(stars[index_i + 1][index_j]);
}
}
// 左
if (index_j - 1 >= 0 && (linkStar = stars[index_i][index_j - 1])) {
if (!linkStar->isSelected() && linkStar->getColor() == star->getColor()) {
travelList.push_back(stars[index_i][index_j - 1]);
}
}
// 右
if (index_j + 1 < COL_NUM && (linkStar = stars[index_i][index_j + 1])) {
if (!linkStar->isSelected() && linkStar->getColor() == star->getColor()) {
travelList.push_back(stars[index_i][index_j + 1]);
}
}
if (!star->isSelected()) { // 处理当前的星星
star->setSelected(true); // 设置已经被加入到选择队列（待删除队列）
selectedList.push_back(star); // 加入到选择队列（待删除队列）
}
travelList.pop_front(); // 队头出队
it = travelList.begin(); // 得到新的队头
}
}

如果对上述的算法还不是很懂，可以百度一下广度优先遍历。

3. 删除待删除星星列表

通过 genSelectedList 我们可以得到一个待删除的列表，接下来使用 deleteSelectedList 方法删除这个列表。具体做法是先判断一下待删除列表的长度是否大于等于 2，如果是就对列表里面的每一个 Star* 进行 removeFromParentAndCleanUp 操作。

void StarMatrix::deleteSelectedList() {
if (selectedList.size() >= 2) {
for (auto star : selectedList) {
star->removeFromParentAndCleanUp();
}
adjustMatrix();
}
}

4. 调整星星矩阵

删除星星后，我们还需要对新的星星矩阵进行调整，让底下没有星星的星星下落，并且当一整列都没有星星时，让星星向左靠拢。因此，在 deleteSelectedList 里面调用了 adjustMatrix 函数，该函数分为垂直方向调整和水平方向调整两部分。

void StarMatrix::adjustMatrix() {
// 垂直方向调整
for (int i = ROW_NUM - 1; i >= 0; i--) {
for (int j = COL_NUM - 1; j >= 0; j--) {
if (stars[j] == nullptr) {
int up = i;
int dis = 0;
while (stars[up][j] == nullptr) {
dis++;
up--;
if (up < 0) {
break;
}
}
for (int begin_i = i - dis; begin_i >= 0; begin_i--) {
if (stars[begin_i][j] == nullptr)
continue;
Star* s = stars[begin_i + dis][j] = stars[begin_i][j];
s->setIndex_ij(begin_i + dis, j);
s->setDesPosition(getPositionByIndex(begin_i + dis, j));
stars[begin_i][j] = nullptr;
}
} else {
continue;
}
}
}
// 水平方向调整
for (int j = 0; j < COL_NUM; j++) {
if (stars[ROW_NUM - 1][j] == nullptr) {
int des = 0;
int right = j;
while (stars[ROW_NUM - 1][right] == nullptr) {
des++;
right++;
}
for (int begin_i = 0; begin_i < ROW_NUM; begin_i++) {
for (int begin_j = j + des; begin_j < COL_NUM; begin_j++) {
if (stars[begin_i][begin_j] == nullptr)
continue;
Star* s = stars[begin_i][begin_j - des] = stars[begin_i][begin_j];
s->setIndex_ij(begin_i, begin_j - des);
s->setDesPosition(getPositionByIndex(begin_i, begin_j - des));
stars[begin_i][begin_j] = nullptr;
}
}
}
}
}

注意事项

• 调整分为垂直调整和水平调整两方面，垂直方向就是星星会下落，而水平方向指的是当一整列都没有了的时候，向左靠拢。
• 这里的调整其实就是调整内部二维 Star* 数组的内容。
• 星星有两个位置（一个当前位置，一个目标位置），调整的时候只要设置星星新的目标位置，因为 update 函数的关系，星星就会从当前位置移动到目标位置。

至此，整个消灭星星最难的部分都实现了，游戏的雏形也基本出来了。