c - 模拟 Block Drop 的最佳算法

Question

这是一个演示图像：

有 8x8 块，里面有一些随机的红色块。当用户选择它们时，它们上方的所有块都会掉落。我想找到一种最好的方法来模拟这种情况，而且复杂度很小。

for (int i = 0; i < 8; i++)
  for (int j = 0; j < 8; j++) {
     if (currentBlock == blank) {
        while((currentBlock.pos.x - 8) >= 0) {
           aboveBlock = (currentBlock.pos.x - 8);
           replace(currentBlock,aboveBlock);
        }
     }

但我认为这根本不是一个完美的算法。谁能帮我？请。非常感谢。

Answer 1

如果您可以将所有移除的块的位置结转，您可以避免遍历所有的游戏场地来找到您需要丢弃的位置。

此外，您可以实现一个递归方法，该方法在顶部位置调用自身，直到它到达顶部。

//Called on an empty block
Drop(int x, int y) {
    if (y > 0) {
        aboveBlock = (currentBlock.pos.x - 8)
        replace(currentBlock,aboveBlock);
        Drop(x,y-1);
    }
}

只需调用Drop()玩家移动清除的最底部位置

Answer 2

1）尽可能少移动的低级方法？
保留一个读指针和一个写指针。仅当存在空白元素时，才将数据从读取移动到写入。（如有必要，颠倒索引 [y][x] 与 [x][y] 的顺序）。

Y = 0; // index for reading
y = 0; // index for writing
while (Y < height) {
    if (block[x][Y] == blank) { Y++; continue; }
    if (Y > y) block[x][y] = block[x][Y];
    Y++; y++;
}
// At this point the source ptr/index 'y' can lag behind -- clear the rest 
while (y < height) block[x][y++] = blank; 

1b）这可以通过跟踪已删除块的最小索引“y”和/或跳过未受影响的列来稍微改进。

2) 高级方法：使用 qsort 对每一列进行排序。